Lamport’s fast mutual exclusion algorithm intuition

Question

Here's Lamport’s fast mutual exclusion algorithm:

want[i]:=true
fast-lock:=i
if slow-lock<>0 then
     want[i]:=false
     while (slow-lock<>0) {//busy wait}
     goto 1
slow-lock:=i
if fast-lock <> i then
     want[i]:=false
     for j:=1 to n do:
       while (want[j] = true) {//busy wait}
     if slow-lock <> i then
         while (slow-lock <> 0) {//busy wait}
         goto 1
CS
slow-lock:=0
want[i]:=false

I understand why eventually all 4 criteria for mutual exclusion hold, but i dont understand the intuition behind this algorithm:

• In what sense are this locks fast/slow?
• What's the point, for example, after freeing the slow lock, go back to the beginning of the algorithm?

I tried to read this article, but it was to complex for me to understand.

Answer 1

In what sense are this locks fast/slow?

Lamport optimizes for a very specific scenario, as pointed out in the paper:

The current belief among operating system designers is that contention for a critical section is rare in a well-designed system; most of the time, a process will be able to enter without having to wait.

The reasoning goes like this: Most of the time, only a single thread will attempt to get into the critical section. So the codepath that we should try to optimize is the one where the lock is readily available.

The case where there is actual contention on the critical section is considered exceptional. It is fine if the algorithm behaves less than ideal in that case - less than ideal here means, you will never let more than one process into the critical section, but if there's lots of contention, you might have to wait a long time (possibly forever) for your turn to enter the critical section.

To illustrate this point, let's take a look at a classic algorithm for mutual exclusion (coincidentally also by Lamport), the Bakery algorithm. Here, in a nutshell, a thread that wants to enter the critical section picks a number that represents its place in the waiting queue. The thread with the smallest number is at the front of the queue and can enter the critical section, all others have to wait. How do we determine whether we have the smallest number (and hence can enter the critical section)? We have to compare our number against the numbers of all the other threads. This means even if none of the other threads are in the queue at that time (no contention), we have to check the numbers of all the other threads. This is obviously not nice, as locking becomes more expensive as the number of threads increases.

The fast mutual exclusion avoids this: If there is no contention we check slow-lock, which is available. Then we check the fast-lock, which is also available and we enter the critical section. We only need two write operations and two read operations to get into the critical section, regardless of the number of threads.

What's the point, for example, after freeing the slow lock, go back to the beginning of the algorithm?

It's the only safe thing to do. Remember, it is crucial that no more than one algorithm is allowed to enter the critical section. If we fail the slow-lock check, it means that some other thread might already be in the fast-lock check or even in the critical section. Thus we have to back off and restart from the beginning. We will keep doing this until the other thread has left the critical section, which will allow us to pass the check.