Lamport's Bakery algorithm

Question

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:

1. 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?

2. 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?

Answer 1

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!

Answer 2

To answer your first point (1.)

Yes. By clearing your ticket back to zero, you are forfeiting the lock. That means, obviously, that you cannot enter the critical section and do anything there. You have to return with some error code such as "interrupted" or "timed out".

If your algorithm may timeout, or fail in some way, while calculating the Number[j] = 1 + max(Number) value, make sure to also set the Boolean value back to false: Entering[j] = false. Not doing so will block the lock mechanism otherwise. (Why would that happen? I implemented snaplock which allows me to obtain locks between any number of computers, at times the calculation of the ticket number fails and I have to make sure the Entering[j] value is set back to false.)

To answer your second point (2.)

The Boolean value is used to properly handle the calculation of max(id1, id2, id3, ...), because while you are calculating a ticket, the while() loop cannot be sure that your state is going to be properly defined so it has to skip over you or wait for you (the Wikipedia implementation waits).

The algorithm from Wikipedia shows that the for() loop sits there if someone is currently entering. This is because testing Number[j], while it is being calculated, is not going to be viewed correctly.

Why is that you might ask?

If thread A enters, it will run the first 3 lines of code to determine the largest Number. While A does that, B enters and starts determining its own largest Number. Once A has its Number, it enters the for() loop, at that moment, B is in an unstable state until Entering[B] = false. You cannot be sure whether Number[B] is going to be:

1. zero,
2. a larger Number than Number[A], or
3. a smaller Number than Number[A]

And that choice is crucial to the algorithm.

  Entering[i] = true;
  Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
  Entering[i] = false;

  for (integer j = 1; j <= NUM_THREADS; j++) {
      // Wait until thread j receives its number:
      while (Entering[j]) { /* nothing */ }

      // Wait until all threads with smaller numbers or with the same
      // number, but with higher priority, finish their work:
      while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
  }

Reading the Wikipedia page (link above) may enlighten you further on the question as they describe the algorithm with different words than mine.