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