Mutual Exclusion

Mutual exclusion is the requirement that when one process is in a Critical Section that accesses shared resources, no other process may be in a critical section that accesses any of those shared resources.

Also see mutex.

Mutual exclusion methods include:

• Semaphore
• Monitor (OS)
• Message Passing

Buhr's 5 rules — CS343 §5.16 Mutual Exclusion Game

The “game” is writing an entry/exit protocol that holds against an adversarial scheduler. Rule 2 bounds what the adversary is allowed to do; the other four are what your protocol must provide despite it.

1. Safety, only one thread can be in a critical section at a time with respect to a particular object
2. Arbitrary scheduling assumption, threads may run at arbitrary speed and in arbitrary order, while the underlying system guarantees a thread makes progress
3. No blocking from outside, a thread not in the entry/exit code may not prevent other threads from entering
4. Selection cannot be postponed indefinitely, breaking this is indefinite postponement / livelock
5. After a thread starts entry, it must eventually enter, breaking this is starvation

This is what every breaks rule N reference in the CS343 notes points to.

How to implement?

This part talks about how we generally implement a mutual exclusion mechanism. Though I think in practice, these aren’t used??

From a software perspective:

• Dekker’s Algorithm (slow)
• Peterson’s Algorithm

From a hardware perspective:

1. Interrupt Disabling
2. Use hardware instructions (i.e. test_and_set) to realize mutual exclusion and introduce a little bit of busy waiting. Everybody does this in practice.

Advantages of using a hardware implementation

• Applicable to any number of processes on either a single processor or multiple processors sharing main memory
• It is simple and therefore easy to verify
• It can be used to support multiple critical sections

Disadvantages of using a hardware implementation

• Busy-waiting consumes processor time
• Starvation is possible when a process leaves a critical section and more than one process is waiting.
• Deadlock with two resources and two processes, each process holding one resource
• Priority inversion
  • If a low priority process has the critical region and a higher priority process needs, the higher priority process will obtain the processor to wait for the critical region
  • Pipeline stalls

Because of the drawbacks of both the software and hardware solutions, we need to look for other mechanisms → Semaphore.

Using Compare-and-Swap Instruction

/* program mutualexclusion */
const int n = /* number of processes */;
int bolt;
void P(int i) {
  while (true) {
    while (compare_and_swap(bolt, 0, 1) == 1) /* do nothing */;
    /* critical section */;
    bolt = 0;
    /* remainder */;
  }
}
void main() {
  bolt = 0;
  parbegin (P(1), P(2), ... ,P(n));
}

The hardware compare and swap

int compare_and_swap (int *word, int testval, int newval) {
  int oldval;
  oldval = *word
  if (oldval == testval) *word = newval;
  return oldval;
}

Using Exchange Instruction

The software

/* program mutualexclusion */
int const n = /* number of processes */;
int bolt;
void P(int i) {
  while (true) {
    int keyi = 1;
    do exchange (&keyi, &bolt)
    while (keyi != 0);
    /* critical section */;
    bolt = 0;
    /* remainder */;
  }
}
void main() {
  bolt = 0;
  parbegin (P(1), P(2), ..., P(n));
}

Exchange (Hardware level, wouldn’t work in software)

void exchange (int *register, int *memory) {
  int temp;
  temp = *memory;
  *memory = *register;
  *register = temp;
}

• Producer and Consumer Problem
• Semaphore