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.
Prev: introduction Next: concurrent-objects