Skip to main content

7. Concurrency (2)

18/10/22

Mutual Exclusions​

  • Software based: Peterson's solution
  • Hardware based: disabling interrupts, test_and_set(), swap_and_compare()
  • OS based: Mutexes, Semaphones
  • Monitors: Software construct within the programming langues

Peterson's Solution​

Software solution​

  • Peterson solution is a software based solution which worked well on older machines.
  • Two shared variables are used:
    • turn: indicates which process is next to enter its critical section
    • boolean flag[2]: indicates that a process is ready to enter its critical section.
  • Can be generalised to multiple processes

Peterson's solution for process i

do{
    flag[i] = true; // i wants to enter critical section
    turn = j; // allow j to access first
    while (flag[j] && turn == j);
    // CRITICAL SECTION, e.g. counter++
    flag[i] = false;
    //reminder section
} while (...);

Peterson's solution for process j

do{
    flag[j] = true; // j wants to enter critical section
    turn = i; //allow i to access first
    while (flag[i] && turn == i);
    // CRITICAL SECTION, e.g. counter++
    flag[j] = false;
    // reminder section
} while (...);

Mutexes is a spin block which will apply a wait time

Mutual exclusion requirement​

  • Peterson's solution for two processes satisfies all "critical section requirements" (mutual exclusion, progress, fairness)
  • Only want one process on the thread accessing the critical section at once
  • Mutual exclusion requirement: the variable turn can have at most one value at a time
    • Both flag[i] and flag[j] are true when they want to enter their critical section
    • Turn is a singular variable that can store only one value
    • Hence, either while(flag[i] && turn == i) or while(flag[j] && turn == j) is true and at most one process can enter its critical section (mutual exclusion)

Progress requirement​

  • Progress: any process must be able to enter its critical section at some point in time
    • Process/threads in the "remaining code" do not influence access to critical sections
    • If process j does not want to enter section:
flag[j] == false
while(flag[j] && turn == j) //will terminate for process i 
//i Enters critical section

Fairness/bounded waiting​

Fairly distributed waiting times/processes cannot be made to wait indefinitely

Disable interrupts​

  • Disable interrupts whilst executing a critical section and prevent interruption.
  • Disabling interrupts may be appropriate on a single CPU machine.
  • This is insufficient on modern multi-core/multi processor machines

Atomic Instructions​

  • Implement test_and_set() and swap_and_compare() instructions as a set of atomic (= uninterruptible) instructions
    • Reading and setting the variables is done as one "complete" set of instructions
    • If they are called simultaneously, they will be executed sequentially

Mutual Exclusion​

  • test_and_set() and swap_and_compare() are hardware instructions and (usually) not directly accessible to the user. OS hides the bare metal from the user
  • Other disadvantages include:
    • Busy waiting is used
    • Deadlock is possible
  • The OS uses the hardware instructions to implement higher level mechanisms/instructions for mutual exclusion i.e mutexes and semaphores