# Mutual Exclusion

Multiple threads (= multiple processes in this course)

• Single shared memory
• Unpredicatble asynchronous delays:
• Cache misses (short)
• Page faults (long)
• Scheduling quantum used up (really long)

## Definitions

• Events: an instantaneous event $$a_0$$ of thread $$A$$
• Assign to shared variable
• Assign to local variable
• Invoke method
• Return from method
• ......
• Threads: a thread $$A$$ is a sequence $$a_0, a_1, \dots$$ of events
• States:
• Thread state: program counter, local variables
• System state: shared variables, union of thread states
• Interval: an interval $$A_0 = (a_0, a_1)$$ is time between events $$a_0$$ and $$a_1$$
• Precendence: $$A_0 \rightarrow B_0$$
• End event of $$A_0$$ before start event of $$B_0$$
• Also called "happens before" or "precedes"
• Partial orders:
• Irreflexive: never true that $$A \rightarrow A$$
• Antisymmetric: if $$A \rightarrow B$$ then not true that $$B \rightarrow A$$
• Transitive: if $$A \rightarrow B$$ and $$B \rightarrow C$$ then $$A \rightarrow C$$
• Total orders:
• Irreflexive, Antisymmetric, Transitive
• Except that for every distinct $$A, B$$, either $$A \rightarrow B$$ or $$B \rightarrow A$$
• Repeated events:
• $$a_0^k$$: $$k$$-th occurrence of event $$a_0$$
• $$A_0^k$$: $$k$$-th occurrence of interval $$A_0$$

## Shared Counter

• Each thread takes a number
• The number increments after taking

Basic implementation:

public class Counter {
private long value;

public long getAndIncrement() {
return value++;
}
}


value++ means:

temp = value;
value = temp + 1;
return temp;


value++ performs two operations: read and write. We need to make these steps atomic (indivisible).

• Method 1: use ReadModifyWrite instruction on multiprocessors
• Method 2: use mutex like synchornized
public class Counter {
private long value;

public long getAndIncrement() {
synchronized {
int temp = value;
value = temp + 1;
}
return temp;
}
}


or, define a mutual exclusive lock:

public interface Lock {
public void lock();
public void unlock();
}

public class Counter {
private long value;
private Lock lock;

public long getAndIncrement() {
lock.lock();
try {
int temp = value;
value = value + 1;
} finally {
lock.unlock();
}
return temp;
}
}


## Mutual Exclusion

Let $$CS_i^k$$ be thread $$i$$'s $$k$$-th critical section execution, and $$CS_j^m$$ be thread $$j$$'s $$m$$-th critical section execution, then either $$CS_i^k \rightarrow CS_j^m$$ or $$CS_j^m \rightarrow CS_i^k$$.

Deadlock Freedom: if some thread calls lock() and never returns

• Then other threads must complete lock() and unlock() calls infinitely often
• System as a whole makes progress even if individuals starve

Starvation Freedom: if some thread calls lock() it will eventually return

### LockOne

public class LockOne implements Lock {
private static boolean[] flag = new boolean;
private int i, j;

public LockOne() {
i = ThreadID.get(); // 0 or 1
j = 1 - i;
}

public void lock() {
flag[i] = true;
while (flag[j]) {}
}

public void unlock() {
flag[i] = false;
}
}

• Deadlock in concurrent execution: both threads set flag to true
• No deadlock in sequential execution

### LockTwo

public class LockTwo implements Lock {
private static int victim;

public void lock() {
victim = i;
while (victim == i) {}
}

public void unlock() {}
}

• Deadlock in sequential execution: vimtim will never change
• No deadlock in concurrent execution

### Peterson's Algorithm

public void lock() {
flag[i] = true;
victim = i;
while (flag[j] && victim == i) {}
}

public void unlock() {
flag[i] = false;
}

• Thread blocked only if it is the victim
• One or the other must not be the victim
• Starvation free:
• Thread $$i$$ blocked only if $$j$$ repeatedly re-enters
• However when $$j$$ re-enters, it sets victim to himself

### The Filter Algorithm

There are $$n-1$$ waiting rooms called levels:

• At each level
• at least one enters level
• at least one blocked if many try
• Only one thread makes it through
public class Filter implements Lock {
private static int[] level;  // level[i] for thread i
private static int[] victim; // victim[l] for level l

public Filter(int n) {
level = new int[n];
victim = new int[n];
for (int i = 0; i < n; ++i) {
level[i] = 0;
}
}

public void lock() {
for (int L = 1; L < n; ++L) {
level[i] = L;
victim[L] = i;
while (exists k != i, level[k] >= L && victim[L] == i) {}
// wait when someone intends to enter same or higher level and I am victim
}
}

public void unlock() {
level[i] = 0;
}
}

• Proof by induction: no more than $$n - L + 1$$ threads at level $$L - 1$$
• Starvation free:
• Same as Peterson Lock
• Fairness:
• Not $$r$$-bounded for any $$r$$

### Bounded Waiting

Divide lock() method into 2 parts:

• Doorway interval $$D_A$$: always finishes in finite steps (before while loop)
• Waiting interval $$W_A$$: may take unbounded steps (after while loop)

$$r$$-bounded waiting: for threads $$A$$ and $$B$$:

• If $$D_A^k \rightarrow D_B^j$$:
• $$A$$'s $$k$$-th doorway precedes $$B$$'s $$j$$-th doorway
• Then $$CS_A^k \rightarrow CS_B^{j+r}$$

Filter lock statisfies deadlock free and starvation free, but not fairness: it is not $$r$$-bounded by any $$r$$. （E.g. 3 threads, where 2 repeatedly enters critical section.)

### Bakery Algorithm

First-come-first-served: $$0$$-bounded, fair lock

public class Bakery implements Lock {
private static boolean[] flag;
private static Label[] label;

public Bakery(int n) {
//...
}

public void lock() {
flag[i] = true;
label[i] = max(label...) + 1; // any read order is OK
while (exists k, flag[k] && (label[i], i) > (label[k], k)) {}
}

public void unlock() {
flag[i] = false;
}
}


Local variable label is really a timestamp. Timestamp requires ability to:

• Compare them
• Generate a later timestamp
• Avoid overflow

## Sequential Timestamping System: Precedence Graphs

• Timestamps from directed graph
• Edge $$x \rightarrow y$$ ($$x$$ dominates $$y$$) means $$x$$ is a later timestamp

Two-Thread Bounded Precedence Graph $$T_2$$: Three-Thread Bounded Precedence Graph $$T_3 = T_2 \times T_2$$: In general, $$T^k = T^2 \times T^{k-1}$$, $$k$$ threads need $$3^{k-1}$$ nodes.

That is, label size = $$log_2 3^{k-1} < 2k$$.

## Shared Memory

• Shared read/write memory locations called registers.
• Different types:
• Multi-Reader-Single-Writer (MRSW): e.g. flag[]
• Multi-Reader-Multi-Writer (MRMW): e.g. victim[]
• Not interesting: SRMW and SRSW

Theorem: at least $$n$$ MRSW registers are needed to solve deadlock-free mutual exclusion for $$n$$ threads. （可以用反证法证明）

Another theorem: at least $$n$$ MRMW registers are needed to solve deadlock-free mutual exclusion for $$n$$ threads.

Upperbound for Bakery algorithm: $$2n$$ MRSW registers.