Peterson's Solution (Software approach)

• A classic software-based solution to the critical-section problem known as Peterson's solution.
• Does not require strict alternation.
• Peterson's solution is restricted to two processes that alternate execution between their CSs and remainder sections. The processes are numbered $P_0$ and $P_1$.
• Peterson's solution requires two data items to be shared between the two processes:

  int turn;
  boolean flag[2];
  

  • The variable turn indicates whose turn it is to enter its CS. That is, if $turn == i$, then process $P_i$ is allowed to execute in its CS.
  • The flag array is used to indicate if a process is ready to enter its CS. For example, if $flag[i]$ is true, this value indicates that $P_i$ is ready to enter its CS.
• The algorithm for Peterson's solution is seen in Fig. 1.

  Figure 1: The structure of process $P_i$ in Peterson's solution.

  
  • To enter the CS, process $P_i$ first sets $flag[i]$ to be true and then sets turn to the value $j$, thereby asserting that if the other process wishes to enter the CS, it can do so.
  • If both processes try to enter at the same time, turn will be set to both $i$ and $j$ at roughly the same time. Only one of these assignments will last; the other will occur but will be overwritten immediately.
  • The eventual value of turn decides which of the two processes is allowed to enter its CS first.
• Mutual exclusion is preserved.
  • Each $P_i$ enters its CS only if either $flag[j] == false$ or $turn == i$.
  • Also note that, if both processes can be executing in their CSs at the same time, then $flag [0] ==flag [1] == true$. These two observations imply that $P_0$ and $P_i$ could not have successfully executed their while statements at about the same time, since the value of turn can be either 0 or 1 but cannot be both.
  • Hence, one of the processes -say $P_j$ -must have successfully executed the while statement, whereas $P_i$ had to execute at least one additional statement ("$turn == j$").
  • However, since, at that time, $flag [j] == true$, and $turn == j$, and this condition will persist as long as $P_j$ is in its CS, the result follows: Mutual exclusion is preserved.
• The progress requirement is satisfied & The bounded-waiting requirement is met.
  • A process $P_i$ can be prevented from entering the CS only if it is stuck in the while loop with the condition $flag [j] == true$ and $turn == j$; this loop is the only one possible.
  • If $P_j$ is not ready to enter the CS, then $flag[j] == false$, and $P_i$ can enter its CS.
  • If $P_j$ has set $flag [j]$ to true and is also executing in its while statement, then either $turn == i$ or $turn == j$.
  • If $turn == i$, then $P_i$ will enter the CS. If $turn == j$, then $P_j$ will enter the CS.
  • However, once $P_i$ exits its CS, it will reset $flag [j]$ to false, allowing $P_i$ to enter its CS.
  • If $P_j$ resets $flag [j]$ to true, it must also set $turn$ to $i$.
  • Thus, since $P_i$ does not change the value of the variable turn while executing the while statement, $P_i$ will enter the CS (progress) after at most one entry by $P_j$ (bounded waiting).
• 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).

  Figure 2: Peterson's solution for achieving mutual exclusion.

  
• Sleep and wakeup. Peterson's solution has not only the defect of requiring busy waiting but it can also have unexpected effects;
  • Consider a computer with two processes, $H$, with high priority and $L$, with low priority.
  • The scheduling rules are such that $H$ is run whenever it is in ready state.
  • At a certain moment, with $L$ in its critical region, $H$ becomes ready to run (e.g., an I/O operation completes).
  • $H$ now begins busy waiting, but since $L$ is never scheduled while H is running, $L$ never gets the chance to leave its critical region, so $H$ loops forever.
  • This situation is sometimes referred to as the priority inversion problem.
• IPC primitive that blocks instead of wasting CPU time (while loop) when they are not allowed to enter their CRs.One of the simplest is the pair sleep and wakeup.
  • Sleep is a system call that causes the caller to block, that is, be suspended until another process wakes it up.
  • The wakeup call has one parameter, the process to be awakened.