Consider a system consisting of n processes {P0, P1, ...,
Pn−1}. Each process has a segment of code, called a critical section, in which
the process may be changing common variables, updating a table, writing a file,
and so on. The important feature of the system is that, when one process is
executing in its critical section, no other process is allowed to execute in
its critical section. That is, no two processes are executing in their critical
sections at the same time. The critical-section problem is to design a protocol
that the processes can use to cooperate. Each process must request permission
to enter its critical section. The section of code implementing this request is
the entry section. The critical section may be followed by an exit section. The
remaining code is the remainder section. The general structure of a typical
process Pi is shown in Figure below.
The entry section and exit section are
enclosed in boxes to highlight these important segments of code.
A solution to the critical-section problem must satisfy the
following three requirements:
1. Mutual exclusion. If process Pi is executing in its
critical section, then no other processes can be executing in their critical
sections.
2. Progress. If no process is executing in its critical section
and some processes wish to enter their critical sections, then only those
processes that are not executing in their remainder sections can participate in
deciding which will enter its critical section next, and this selection cannot be
postponed indefinitely.
3. Bounded waiting. There exists a bound, or limit, on the
number of times that other processes are allowed to enter their critical
sections after a process has made a request to enter its critical section and
before that request is granted.
We assume that each process is executing at a nonzero speed.
However, we can make no assumption concerning the relative speed of the n
processes.
Peterson’s Solution
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:
int turn;
boolean flag[2];
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 5.2.
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. The 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:
1. Mutual exclusion is preserved.
2. The progress requirement is satisfied.
3. The 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[0] == flag[1] == 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 (“turn == j”).
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 critical section. 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
(bounded waiting).
