Mutual Exclusion

Reasoning about concurrent computation is mostly about time. Reason about complicated conditions involving how multiple time intervals can overlap, or, sometimes, how they cannot.

A thread is a state machine, and its state transitions are called events.

Events are instantaneous

j-th occurence of an event a_i: a_i^j

a precedes b: a\to b

The precedence relation “\to” is a total order on events.

Interval I_A =(a_0, a_1), I_B = (b_0, b_1), I_A\to I_B if a_1\to b_0.

Mutual Exclusion Critical sections of different threads do not overlap. For threads A and B, and integers j and k, either CS_A^k \to CS_B^j or CS_B^j \to CS_A^k.

Freedom from Deadlock If some thread attempts to acquire the lock, then some thread will succeed in acquiring the lock. If thread A calls lock() but never acquires the lock, then other threads must be completing an infinite number of critical sections.

Freedom from Starvations Every thread that attempts to acquire the lock eventually succeeds. Every call to lock() eventually returns. This property is sometimes called lockout freedom.

NOTE that starvation freedom implies deadlock freedom.

2.3 2-Thread Solutions

LockOne
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
    }
    public void unlock() {
        int i = ThreadID.get();
        flag[i] = false;
    }
}

Mutual excluded but deadlock.

LockTwo
1
2
3
4
5
6
7
8
9
class LockTwo implements Lock {
    private volatile int victim;
    public void lock() {
        int i = ThreadID.get();
        victim = i;
        while (victim == i) ()
    }
    public void unlock() {}
}
The Peterson Lock
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Peterson implements Lock {
    // thread-local index, 0 or 1
    private volatile boolean[] flag = new boolean[2];
    private volatile 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
    }
}

Mutual excluded and starvation free

Work for n threads:

The Filter Lock

a direct generalization of Peterson lock to multipe threads

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 level 1
            level[me] = i;
            victim[i] = me;
            // spin while comflicts exist
            while ((\exist k != me)(level[k] >= i && victim[i] == me)) {};
        }
    }
    public void unlock() {
        int me = ThreadID.get();
        level[me] = 0;
    }
}

Threads run through levels, until 1 level (CS)

Lamport’s Bakery Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Bakery implements Lock {
    boolean[] flag;
    Label[] label;
    public Bakery(int n) {
        flag = new boolean[n];
        lavel = 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[i], ..., label[n - 1]) + 1;
        while ((\exist k != i)(flag[k] && (label[k], k) << (label[i], i))) {};
    }
    public void unlock() {
        flag[ThreadID.get()] = false;
    }
}

lexicographical ordering << （字典序）, to break symmetry caused by same label.

In the waiting part, a thread repeatedly rereads the labels one after the other in some arbitrary order until it determines that no thread with a raised flag has a lexicographically smaller label/id pair.

Each thread’s labels are strictly increasing.

本质上就是排队，先到先执行。

Any algorithm that is both deadlock-free and first-come-first-served is also starvation-free.