- Next, we illustrate a
classic software-based solution to the critical-section problem known as
- Because of the way
modern computer architectures perform basic machine-language instructions, such
as load and store, there are no guarantees that Peterson's solution will work
correctly on such architectures.
- However, we present the
solution because it provides a good algorithmic description of solving the
critical-section problem and illustrates some of the complexities involved in
designing software that addresses the requirements of mutual exclusion,
progress, and bounded waiting.
- Peterson's solution is
restricted to two processes that alternate execution between their critical
sections and remainder sections.
- The processes are
numbered P0 and
P1. For convenience, when presenting Pi, we use Pj to denote
the other process; that is, j equals 1 - i.
- Peterson's solution
requires the two processes to share two data items:
- The variable turn
indicates whose turn it is to enter its critical section. That is, if turn ==
i, then process Pi is allowed to execute in its critical section.
- The flag array is used
to indicate if a process is ready to enter its critical section. For
example, if flag [i] is true, this value indicates that Pi is ready to
enter its critical section.
- With an explanation of
these data structures complete, we are now ready to describe the algorithm
shown in Figure 2. 26.
- To enter the critical
section, process Pi 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
critical section, 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.
Figure 2.26 The structure of process Pi in Peterson's solution.
eventual value of turn determines which of the two processes is allowed to
enter its critical section first. We now prove that this solution is correct.
We need to show that:
- Mutual exclusion
- The progress
requirement is satisfied.
bounded-waiting requirement is met.
- To prove property 1, we
note that each Pi enters its critical section only if either flag [j] ==
false or turn == i.
- Also note that, if both
processes can be executing in their critical sections at the same time, then
flag  == flag  ==true.
- These two observations
imply that P0 and P1
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, Pj -must have successfully executed the while statement,
whereas Pi had to execute at least one additional statement
- However, at that time,
flag [j] == true and turn == j, and this condition will persist as long as Pj
is in its critical section; as a result, mutual exclusion is preserved.
- To prove properties 2
and 3, we note that a process Pi can be prevented from entering the
critical section 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 Pj is not
ready to enter the critical section, then flag [j] == false, and Pi can
enter its critical section. If Pj 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 Pi will enter the critical section.
- If turn == j, then Pj
will enter the critical section. However, once Pj exits its critical
section, it will reset flag [j] to false, allowing Pi to enter its
- If Pj resets
flag [j] to true, it must also set turn to i. Thus, since Pi does not
change the value of the variable turn while executing the while statement, Pi
will enter the critical section (progress) after at most one entry by Pj
- The Operating System Concepts by Silberschatz, Galvin, Gagne, 8th Edition
- MODERN OPERATING SYSTEMS by Andrew S. Tanenbaum, Second Edition
Last modified: Sunday, 19 November 2017, 11:58 AM