Lamport's Bakery algorithm

I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 to that and give that number to itself. The thread with the lowest number can enter the critical zone and if two or more threads have the lowest number then the thread with the lowest process id will be allowed to enter the critical area. When a thread exits the critical area then it put it's number to 0, meaning it's not interested in going inside the critical area. First when it picks a number higher than 0 it is interested going inside the critical area.

Now here is what I don't understand:

-
If a thread wants to get into the critical area it picks a number, but what if it changes its mind while it's waiting in line? does it then change its number to 0 or does it go through the critical area anyway when it is its turn?

-
In Lamport's bakery algorithm there is a Boolean value of "true" or "false". If a thread wants to enter it sets the Boolean value to true, but what is that Boolean value used for in the code? Because when a thread has been inside the critical area it changes its number to 0, so other threads in that way can see it's not interested in going inside the critical area, and if it decides it wants inside the critical area again, then it has to ask all the other threads what their number is and then add 1 to the maximum value which will be its number. So the true and false Boolean seems useless to me. Anybody understand why they are there?

Let me try to help you with.

1) The problem here is that you are missing the big picture. Lamport's Bakery Algorithm (LBA) is just a deadlock-free algorithm that is used for mutual exclusion, so inside a bigger software. One typical way to use it is this (Java-like example):

mutex.lock();
try {
    CS(); // critical section
} finally {
    mutex.unlock(); // mutex has to be released also in case of error
}

For the way LBA is designed it does not allow a thread to "change idea" while waiting (there is no timeout notion in the algorithm): once a thread has called lock() it has to wait until lock() returns (possibly waiting all the other threads' unlock()). This does not mean that a thread is forced to enter in the CS once the lock is acquired. One thread could call lock(), wait until it returns and check if it is still required to run the CS. See below:

mutex.lock();
try {
    if(!tooMuchTimeHasPassed()) {  // is it still meaningful to enter CS?
        CS(); // critical section
    }
} finally {
    mutex.unlock(); // mutex has to be released also in any case
}

The example allow this scenario: one thread acquires the lock, notices that running CS is useless and stops by releasing the lock.

2) The boolean value, as you can see here, is not used to notify other threads about the fact that you have a certain priority or that you are inside the CS: it is only used to say to the other threads that you are still choosing a number. How can some threads decide which of them has the highest priority if some threads have not picked a number yet? In order to acquire the lock one thread A must ensure he has a priority higher then all the others (the outer for loop). If A discovers that another thread B is still searching for a number (the max() operation is not atomic and may require a lot of time) then it waits for B to pick a number and later checks who can go first.

Hope it helped!

StackExchange Computer Science Q#57753, answer score: 2