Mutual Exclusion

Ensuring that only one thread (per a shared resource) at a time can run its critical section.

• The threads must not deadlock
• The threads must not starve
• In the absence of contention, a thread should be able to enter its critical section without delay
• The solution must have low overhead
• A halted process in non-critical section must not block others

Possible Solutions

Strict Alternation

Uses a shared turn variable, which indicates which thread is allowed to enter critical section. Only works for fixed number of threads, which is known beforehand. Forces a fixed turn order for threads to enter critical section, which causes unnecessary waiting.

Suppose there are $N$ threads. For thread $T_i$:

while (true) {
    while (turn != i);      // entry section
    // critical section
    turn = (turn + 1) % N;  // exit section
    // remainder section
}

• Mutual exclusion: Satisfied
  turn can take only 1 value at a time.
• No deadlock: Satisfied
• No starvation: Satisfied
• Starvation in absence of contention: fails
  If a process halts in its non-critical section, the other may be permanently blocked.

Even if both processes are guaranteed to not halt in their non-critical sections, unnecessary waiting may occur. For example, if P1 is in its critical section and P2 is in its non-critical section, P2 must wait for P1 to finish even if P1 has no intention of re-entering its critical section.

Flag Variables

Each process $P_i$ has ci. 0 indicates wants to enter CS, 1 indicates not interested. The flag is set after checking the other process.

For P1:

while (true) {
  // remainder
  while (c2!=1) {
    c1=0;
    // critical section
    c1=1;
  }
}

Fails mutual exclusion if both processes to see the other’s flag as 1, which is not rare.

Flag set at Start of Pre-Protocol

Move ci=0 before checking the other’s flag.

For P1:

while (true) {
    // remainder section
    c1=0;
    while (c2!=1) {}
    // critical section
    c1=1;
}

• Mutual exclusion: Satisfied
  c1 can only become 1 if P1 finishes its critical section.
• No Deadlock: Not satisfied
  If both c1 and c2 is set to 0.