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

  • Individual thread makes progress

Two-Thread Solutions

LockOne

public class LockOne implements Lock {
  private static boolean[] flag = new boolean[2];
  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() {
    int i = ThreadId.get();
    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;
}
  • Deadlock free:
    • 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

Multiple-Thread Solutions

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;
  }
}
  • Deadlock free:
    • 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:

  • Read others' timestamps
  • 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.