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.

This is a VERY common requirement in concurrency.

I still don’t get how mutual exclusion is implemented in practice. Every solution seems to have drawbacks.

Mutual exclusion methods insclude

• Semaphore
• Monitor (OS)
• Message Passing

Requirements of Mutual Exclusion

Facility providing mutual exclusion must provide the following:

1. Enforcement: Only one process at a time is allowed in the critical section for a resource
2. A process that halts in its noncritical section must do so without interfering with other processes
3. No Deadlock or Starvation
4. A process must not be delayed access to a critical section when there is no other process using it
5. No assumptions are made about relative process speeds or number of processes
6. A process remains inside its critical section for a finite time only

Related

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