Mutual Exclusion with Busy Waiting (Software approach)

• Mutual exclusion is a mechanism to ensure that only one process (or person) is doing certain things at one time, thus avoid data inconsistency. All others should be prevented from modifying shared data until the current process finishes
• Strict Alternation (see Fig. 2.11)
  • the two processes strictly alternate in entering their CR
  • the integer variable turn, initially 0, keeps track of whose turn is to enter the critical region
  • busy waiting, continuously testing a variable until some value appears, a lock that uses busy waiting is called a spin lock
  • both processes are executing in their noncritical regions
  • process 0 finishes its noncritical region and goes back to the top of its loop
  • unfortunately, it is not permitted to enter its CR, turn is 1 and process 1 is busy with its nonCR
  • this algorithm does avoid all races
  • but violates condition 3

  Figure 2.11: A proposed solution to the CR problem. (a) Process 0, (b) Process 1

  
• Petersons's solution (see Fig. 2.12)
  • does not require strict alternation
  • this algorithm consists of two procedures
  • before entering its CR, each process calls enter_region with its own process number, 0 or 1
  • after it has finished with the shared variables, the process calls leave_region to allow the other process to enter
  • consider the case that both processes call enter_region almost simultaneously
  • both will store their process number in turn . Whichever store is done last is the one that counts; the first one is overwritten and lost
  • suppose that process 1 stores last , so turn is 1.
  • when both processes come to the while statement, process 0 enters its critical region
  • process 1 loops until process 0 exists its CR
  • no violation, implements mutual exclusion
  • burns CPU cycles (requires busy waiting), can be extended to work for n processes, but overhead, cannot be extended to work for an unknown number of processes, unexpected effects (i.e.,priority inversion problem)

Figure 2.12: Peterson' solution for achieving mutual exclusion