Mutual Exclusion

Prev: Introduction Next: Concurrent Objects

Time and events

Reasoning about concurrent computation is mostly reasoning about time. Sometimes we want things to happen simultaneously, and sometimes at different times.

Threads share a common time, and are state machines that transition through events.

We say that if a precedes b, this is written as a -> b, and applies a total order on events.

Critical sections

Mutual exclusion is used to guard critical sections, a block of code that can only be executed by one thread at a time.

public class Counter {
  private long value;
  private Lock lock; // for the critical section
 
  public long getAndIncrement() {
    lock.lock();
    try {
      long temp = value;
      value = temp + 1;
      return temp;
    } finally {
      lock.unlock();
    }
  }
}

Every lock should satisfy mutual exclusion, deadlock freedom, and freedom from starvation.

Two-thread solutions

The LockOne class

To solve the LockOne algorithm, a thread sets its flag to true and waits until the other thread’s flag is false. When that’s done, it finally returns.

class LockOne implements Lock {
private boolean[] flag = new boolean[2];
  // thread-local index, 0 or 1
  public void lock() {
    int i = ThreadID.get();
    int j = 1 - i;
    flag[i] = true;
    while (flag[j]) {} // wait until flag[j] == false
  }
  public void unlock() {
    int i = ThreadID.get();
    flag[i] = false;
   }
 }

Unfortunately, this algorithm can deadlock if thread executions are interleaved.

The LockTwo class

This algorithm supports mutual exclusion, but it gets stuck unless the threads run concurrently, the opposite of LockOne.

class LockTwo implements Lock {
 private int victim;
 public void lock() {
  int i = ThreadID.get();
  victim = i; // let the other go first
  while (victim == i) {} // wait
 }
 public void unlock() {}
}

The Peterson Lock

The Peterson Lock supports a starvation-free lock for two-thread mutual exclusion.

class Peterson implements Lock {
// thread-local index, 0 or 1
private boolean[] flag = new boolean[2];
private int victim;
  public void lock() {
    int i = ThreadID.get();
    int j = 1 - i;
    flag[i] = true; // I'm interested
    victim = i; // you go first
    while (flag[j] && victim == i) {} // wait
  }
  public void unlock() {
  int i = ThreadID.get();
  flag[i] = false; // I'm not interested
  }
}

Notes on deadlock

Even though the Peterson Lock is deadlock-free, if multiple peterson locks are used, livelock can ensue, in which two threads prevent each other from making progress.

The filter lock

The filter lock generalizes the Peterson lock to work for n > 2. It creates n - 1 waiting rooms, called levels.

class Filter implements Lock {
int[] level;
int[] victim;
  public Filter(int n) {
  level = new int[n];
  victim = new int[n]; // use 1..n-1
    for (int i = 0; i < n; i++) {
    level[i] = 0;
    }
  }
  public void lock() {
    int me = ThreadID.get();
    for (int i = 1; i < n; i++) { // attempt to enter level i
    level[me] = i;
    victim[i] = me;
    // spin while conflicts exist
    while ((∃k != me) (level[k] >= i && victim[i] == me)) {};
    }
  }
  public void unlock() {
    int me = ThreadID.get();
    level[me] = 0;
  }
}

Fairness

Although the filter lock is starvation-free, a thread might be overtaken arbitrarily many times by another thread, because accesses to the critical section are not first-come-first-served.

To make this happen, we can split the lock() method into a doorway and a waiting section, where the doorway completes in a bounded number of steps, before entering the waiting area.

class Bakery implements Lock {
  boolean[] flag;
  Label[] label;
  public Bakery (int n) {
    flag = new boolean[n];
    label = new Label[n];
    for (int i = 0; i < n; i++) {
      flag[i] = false; label[i] = 0;
    }
  }
  public void lock() {
    int i = ThreadID.get();
    flag[i] = true;
    label[i] = max(label[0], ...,label[n-1]) + 1;
    while ((∃k != i)(flag[k] && (label[k],k) << (label[i],i))) {};
  }
  public void unlock() {
    flag[ThreadID.get()] = false;
  }
}

Lamport’s Bakery algorithm

Lamport’s bakery algorithm guarantees the first-come-first-served property, while fulfilling mutual exclusion, being deadlock-free, and starvation free.

AtomicIntegerArray ticket = new AtomicIntegerArray(threads); // ticket for threads in line, n - number of threads
// Java initializes each element of 'ticket' to 0
 
AtomicIntegerArray entering = new AtomicIntegerArray(threads); // 1 when thread entering in line
// Java initializes each element of 'entering' to 0
 
public void lock(int pid) {
    // thread ID
    entering.set(pid, 1);
    int max = 0;
    for (int i = 0; i < threads; i++) {
        int current = ticket.get(i);
        if (current > max) {
            max = current;
        }
    }
    ticket.set(pid, 1 + max);
    entering.set(pid, 0);
    for (int i = 0; i < ticket.length(); ++i) {
        if (i != pid) {
            while (entering.get(i) == 1) { Thread.yield(); } // wait while other thread picks a ticket
            while (ticket.get(i) != 0 && ( ticket.get(i) < ticket.get(pid) ||
                    (ticket.get(i) == ticket.get(pid) && i < pid))) {
                      Thread.yield();
                    }
        }
    }
    // The critical section goes here...
}
 
public void unlock(int pid) {
  ticket.set(pid, 0);
}

Bounded timestamps

Unfortunately, the bakery algorithm requires that timestamps never overflow, and are totally ordered. Of course, that’s not feasible, since a counter might overflow a 64-bit int, for example.

Exercises

Exercise 2.1. A mutual exclusion algorithm provides $r$ -bounded waiting if there is a way to define a doorway such that if $D_{A}^{j} \to D_{B}^{k}$ , then $C S_{A}^{j} \to C S_{B}^{k + r}$ . Does the Peterson algorithm provide $r$ -bounded waiting for some value of $r$ ?

Exercise 2.2. Why must we define a doorway section, rather than defining first-come-first-served in a mutual exclusion algorithm based on the order in which the first instruction in the lock() method was executed? Argue your answer in a case-by-case manner based on the nature of the first instruction executed by the lock(): a read or a write, to separate locations or the same location.

Exercise 2.3. Programmers at the Flaky Computer Corporation designed the following protocol to achieve $n$ -thread mutual exclusion. For each question, either sketch a proof, or display an execution where it fails.

class Flaky implements Lock {
  private int turn;
  private boolean busy = false;
 
  public void lock() {
    int me = ThreadID.get();
    do {
      do {
        turn = me;
      } while (busy);
      busy = true;
    } while (turn != me);
  }
 
  public void unlock() {
    busy = false;
  }
}

Does this protocol satisfy mutual exclusion?
Is this protocol starvation-free?
Is this protocol deadlock-free?
Is this protocol livelock-free?

Exercise 2.4. Show that the Filter lock allows some threads to overtake others an arbitrary number of times.

Exercise 2.5. Consider a variant of Peterson’s algorithm, where we change the unlock() method to be as shown below. Does the modified algorithm satisfy deadlock-freedom? What about starvation-freedom? Sketch a proof showing why it satisfies both properties, or display an execution where it fails.

public void unlock() {
  int i = ThreadID.get();
  flag[i] = false;
  int j = 1 - i;
  while (flag[j] == true) {}
}

Exercise 2.6. Another way to generalize the two-thread Peterson lock is to arrange a number of two-thread Peterson locks in a binary tree. Suppose $n$ is a power of two. Each thread is assigned a leaf lock which it shares with one other thread. Each lock treats one thread as thread 0 and the other as thread 1.

In the tree-lock’s acquire method, the thread acquires every two-thread Peterson lock from that thread’s leaf to the root. The tree-lock’s release method unlocks each of the two-thread Peterson locks that thread has acquired, from the root back to its leaf. At any time, a thread can be delayed for a finite duration. In other words, threads can take naps, or even vacations, but they do not drop dead.

For each of the following properties, either sketch a proof that it holds, or describe a possibly infinite execution where it is violated:

mutual exclusion,
freedom from deadlock,
freedom from starvation.

Is there an upper bound on the number of times the tree-lock can be acquired and released between the time a thread starts acquiring the tree-lock and when it succeeds?

Exercise 2.7. The $ℓ$ -exclusion problem is a variant of the starvation-free mutual exclusion problem with two changes: up to $ℓ$ threads may be in the critical section at the same time, and fewer than $ℓ$ threads might fail by halting in the critical section.

An implementation must satisfy the following conditions:

$ℓ$ -exclusion: At any time, at most $ℓ$ threads are in the critical section.
$ℓ$ -starvation-freedom: As long as fewer than $ℓ$ threads are in the critical section, some thread that wants to enter the critical section will eventually succeed, even if some threads in the critical section have halted.

Modify the $n$ -thread Filter mutual exclusion algorithm to solve $ℓ$ -exclusion.

Exercise 2.8. In practice, almost all lock acquisitions are uncontended, so the most practical measure of a lock’s performance is the number of steps needed for a thread to acquire a lock when no other thread is concurrently trying to acquire the lock.

Scientists at Cantaloupe-Melon University have devised the following “wrapper” for an arbitrary lock. They claim that if the base Lock class provides mutual exclusion and is starvation-free, so does the FastPath lock, but it can be acquired in a constant number of steps in the absence of contention. Sketch an argument why they are right, or give a counterexample.

class FastPath implements Lock {
  private Lock lock;
  private int x, y = -1;
 
  public void lock() {
    int i = ThreadID.get();
    x = i;
    while (y != -1) {}
    y = i;
    if (x != i)
      lock.lock();
  }
 
  public void unlock() {
    y = -1;
    lock.unlock();
  }
}

Exercise 2.9. Suppose $n$ threads call the visit() method of the Bouncer class shown below. Prove the following:

class Bouncer {
  public static final int DOWN = 0;
  public static final int RIGHT = 1;
  public static final int STOP = 2;
  private boolean goRight = false;
  private int last = -1;
 
  int visit() {
    int i = ThreadID.get();
    last = i;
    if (goRight)
      return RIGHT;
    goRight = true;
    if (last == i)
      return STOP;
    else
      return DOWN;
  }
}

At most one thread gets the value STOP.
At most $n - 1$ threads get the value DOWN.
At most $n - 1$ threads get the value RIGHT.

Exercise 2.10. So far, we have assumed that all $n$ threads have small unique IDs. Here is one way to assign small unique IDs to threads. Arrange Bouncer objects in a triangular matrix, where each Bouncer is given an ID as in Fig. 2.20 of the book.

Each thread starts by visiting Bouncer 0. If it gets STOP, it stops. If it gets RIGHT, it visits 1, and if it gets DOWN, it visits 2. In general, if a thread gets STOP, it stops. If it gets RIGHT, it visits the next Bouncer on that row, and if it gets DOWN, it visits the next Bouncer in that column. Each thread takes the ID of the Bouncer object where it stops.

Prove that each thread eventually stops at some Bouncer object.
How many Bouncer objects do you need in the array if you know in advance the total number $n$ of threads?

Exercise 2.11. Prove, by way of a counterexample, that the sequential timestamp system $T^{3}$ , starting in a valid state with no cycles among the labels, does not work for three threads in the concurrent case. Note that it is not a problem to have two identical labels since one can break such ties using thread IDs. The counterexample should display a state of the execution where three labels are not totally ordered.

Exercise 2.12. The sequential timestamp system $T^{n}$ had a range of $O (3^{n})$ different possible label values. Design a sequential timestamp system that requires only $O (n 2^{n})$ labels. Note that in a timestamp system, one may look at all the labels to choose a new label, yet once a label is chosen, it should be comparable to any other label without knowing what the other labels in the system are. Hint: think of the labels in terms of their bit representation.

Exercise 2.13. Give Java code to implement the Timestamp interface of Fig. 2.11 using unbounded labels. Then show how to replace the pseudocode of the Bakery lock of Fig. 2.10 using your Timestamp Java code.

Exercise 2.14. We saw earlier the following theorem on the bounds of shared memory for mutual exclusion: any deadlock-free mutual exclusion algorithm for $n$ threads must use at least $n$ shared registers. For this exercise, we examine a new algorithm that shows that the space lower bound of the above theorem is tight. Specifically, we will show the following:

There is a deadlock-free mutual exclusion algorithm for $n$ threads that uses exactly $n$ shared bits.

To prove this new theorem, we study the OneBit algorithm shown below. This algorithm, developed independently by J. E. Burns and L. Lamport, uses exactly $n$ bits to achieve mutual exclusion; that is, it uses the minimum possible shared space.

class OneBit implements Lock {
  private boolean[] flag;
 
  public OneBit(int n) {
    flag = new boolean[n];
  }
 
  public void lock() {
    int i = ThreadID.get();
    do {
      flag[i] = true;
      for (int j = 0; j < i; j++) {
        if (flag[j] == true) {
          flag[i] = false;
          while (flag[j] == true) {}
          break;
        }
      }
    } while (flag[i] == false);
    for (int j = i + 1; j < n; j++) {
      while (flag[j] == true) {}
    }
  }
 
  public void unlock() {
    flag[ThreadID.get()] = false;
  }
}

The OneBit algorithm works as follows: first, a thread indicates that it wants to acquire the lock by setting its bit to true. Then, it loops and reads the bits of all threads with smaller IDs than its own. If all of these bits are false while its own bit is true, then the thread exits the loop. Otherwise, the thread sets its bit to false, waits until the bit it found to be true becomes false, and starts all over again. Afterwards, the thread reads the bits of all threads that have IDs greater than its own, and waits until they are all false. Once this check passes, the thread can safely enter the critical section.

Prove that the OneBit algorithm satisfies mutual exclusion.
Prove that the OneBit algorithm is deadlock-free.

Prev: Introduction Next: Concurrent Objects

Takashi's Notes

Explorer

Mutual Exclusion

Mutual Exclusion

Time and events

Critical sections

Two-thread solutions

The LockOne class

The LockTwo class

The Peterson Lock

Notes on deadlock

The filter lock

Fairness

Lamport’s Bakery algorithm

Bounded timestamps

Exercises

Graph View

Table of Contents

Backlinks