Peterson's Algorithm

This handout discusses steps towards the development of low-level algorithms for mutual exclusion. They are called low-level because they employ no special system calls or hardware instructions, only standard programming features. In particular, the only permitted accesses of a shared memory variable are reads or writes and all blocking must be done by looping, or spin-blocking.

Peterson's algorithm is considered a standard low-level algorithm for two-thread mutual exclusion. The steps below represent incorrect attempts which we will merge into the final correct version. The following programming template serves as the system model:

Program template for threads accessing a critical section

// initialization of shared variables process to creation of threads 
init();

// now create threads which execute code like this:
while(true) {
     ncs();   // non-critical section prior to entry
 x:  pre();   // pre-protocol to request entry, block if necessary
     cs();    // critical section: interleaving should be prevented
 x1: post();  // post-protocol to signal leaving
}
The code of all sections can employ both shared and non-shared variables. The shared variables are declared and initiliazed in the init section. The code of the pre sections need not be identical for each thread. It is, however, usually similar; same goes for the and post. The cs code is considered abstract; it represents any code for which we want to create mutual exclusion, such as the shared counter increment code:
init) int count = 0   // count is shared

cs)   int r = count;  // r is non-shared
      r = r + 1;
      count = r;
When analyzing an algorithm regarding its suitability for mutual exclusion, refer to these notions:
  1. To say you're at a statement with a certain label means you're about to execute this statement. These are the basic interpretations:
    at x: in non-critical section, prior to starting pre-protocol
    at x1: in the critical section, prior to leaving
  2. A thread may exit only in the non-critical section, i.e., it will remain permanently at x.
  3. Mutual exclusion must prevent more than one thread from being at x1.
  4. Other labels are added and used for reasoning as necessary.

Steps towards mutual exclusion

Suppose we have two threads A and B. Initially consider using a single shared boolean variable
boolean lock;
which is used to "lock" the critical section. Here are the statements we wish to employ:
lock = true [false];  // entry in [exit from] critical section
while (lock) { }      // spin-block when other thread has set lock
while (lock) ;        // same spin-block, written differently
Any ordering of these statements leads to problems as seen below.
init)
boolean lock = false;
Thread A Thread B
pre)
x:  while(lock);
y:  lock = true;
x:  while(lock);
y:  lock = true;
post)
x1: lock = false;
x1: lock = false;
Mutual exclusion fails if the threads interleave the to pre-protocol statements. Consider the following run sequence which illustrates the mutual exclusion failure:
	run   A is at  B is at  lock
	---   -------  -------  -----
  0.            x        x        F
  1.    A       y        x        F
  2.    B       y        y        F
  3.    B       y        x1       T
  4.    A       x1       x1       T
If you try switching the order of statements in the pre-protocol as follows:
x:  lock = true;
y:  while(lock);
this is unequivocally a deadlock scenario regardless of the run sequence.

Two shared lock variables

Adding a second shared lock variable, one for each thread, brings us closer to a correct solution.
boolean lockA, lockB;
Here are the statements we wish to employ:
lockA = true [false];  // A indicates entry into [exit from] critical section
lockB = true [false];  // B indicates entry into [exit from] critical section
while (lockB);         // A's spin-block when B in critical section
while (lockA);         // B's spin-block when A in critical section
This version fails mutual exclusion via a series of steps similar to that discussed previously:
init)
boolean lockA = lockB = false;
Thread A Thread B
pre)
x:  while(lockB);
y:  lockA = true;
x:  while(lockA);
y:  lockB = true;
post)
x1: lockA = false;
x1: lockB = false;
Attempting to switch the order gives:
init)
boolean lockA = lockB = false;
Thread A Thread B
pre)
x:  lockA = true;
y:  while(lockB);
x:  lockB = true;
y:  while(lockA);
post)
x1: lockA = false;
x1: lockB = false;
which can deadlock if the x and y statements are interleaved:
	run   A is at  B is at  lockA  lockB
	---   -------  -------  -----  -----
  0.            x        x        F      F
  1.    A       y        x        T      F
  2.    B       y        y        T      T
  3.    B       y        y        T      T
  4.    A       y        y        T      T
Nevertheless, this last example represents our best effort so far in that, unlike the case of the single boolean variable, it works if this interleaving does not occur.

Turn-taking

The ingredient needed to create a correct solution is a shared variable which creates turn-taking.
int turn;
The variable turn can assume two different int values named A and B for simplicity. The intended usage is as follows:
turn = A [B];        // allows A [B] to enter c.s.
while (turn != A);   // A's spin-block when it's B's turn
while (turn != B);   // B's spin-block when it's A's turn
Here is the most obvious way to express this idea:
init)
int turn = A;  // or B
Thread A Thread B
pre)
x: while (turn != A);
x: while (turn != B);
post)
x1: turn = B;
x1: turn = A;
This algorithm does provide mutual exclusion but is considered unacceptable because it forces A and B into "lock step" where the whole system runs at the rate of the slowest process. Additionally, if one process exits it effectively blocks the other process after its subsequent turn.

A variation of the previous example in which the post-protocol code is moved into the pre-protocol turns out to be better suited to the development of Peterson's algorithm. The behavior is somewhat different although the overall effect is essentially the same.
init)
int turn = A;  // or B
Thread A Thread B
pre)
x: turn = B;
y: while (turn != A);
x: turn = A;
y: while (turn != B);
post)
/* nothing */
/* nothing */

Two-thread Mutual Exclusion Algorithms

Peterson's Algorithm.

A correct solution is obtained by combining the 2-variable deadlockable solution with the latter turn-taking solution in such a way that turn-taking is used to to prevent the deadlock. The order of the lock setting and turn setting statements is crucial.
init)
boolean lockA = lockB = false;
int turn = A; // or B
Thread A Thread B
pre)
x: lockA = true;
y: turn = B;
z: while( lockB
w:     && turn != A );
x: lockB = true;
y: turn = A;
z: while( lockA
w:     && turn != B );
post)
x1: lockA = false;
x1: lockB = false;
This is optimal in the sense that it provides full fairness whereby a process which starts its pre-protocol will eventually enter the critical section will eventually enter, regardless of the behavior of the other process.

Dekker's Algorithm.

This is presented only for historical interest, being the first correct published solution. It has the same properties as Peterson's algorithm. You can see that it is an enhancement of Example 3 into which a version of turn-taking has been added with the statements z, u, v, w in order to break the deadlock as well as effect the full fairness describe above.
init)
/* same as in Peterson's algorithm */
Thread A Thread B
pre)
x: lockA = true;
y: while(lockB) {
z:   if (turn != A) {
u:     lockA = false;
v:     while(turn != A);
w:     lockA = true;
     }
   }
x: lockB = true;
y: while(lockA) {
z:   if (turn != B) {
u:     lockB = false;
v:     while(turn != B);
w:     lockB = true;
     }
   }
post)
x1: lockA = false;
y1: turn = B;
x1: lockB = false;
y1: turn = A;

Safety and fairness in Peterson's Algorithm

In general a concurrent algorithm is judged by its ability to provide two properties: Safety is the more important of these two since inconsistency can mean data or information corruption. Fairness is somewhat harder to pin down and is subject to many variations. The worst case of unfairness is deadlock, but the lock-step behavior of the simple turn-taking algorithms is also unfair.

With respect to Peterson's algorithm we want to argue these properties:
  1. mutual exclusion: assume that one thread is in the critical section and show that the other can't get into its critical section
  2. full fairness: once a thread starts the pre-protocol, it will eventually enter the critical section regardless of the behavior of the other thread
Mutual exclusion

Due to the symmetry of the algorithm, we can assume that A is in the critical section (i.e., at x1), B is not in its critical sesion (not at x1). We must argue that B cannot get into its critical section.

Because A is in the critical section we know lockA == true and so B will only get in the critical section if turn == B after executing statement w.

Consider the system state prior to A's entering the critical section. Either
lockB == false   (A entered at z)     or     turn == A   (A entered at w)
If lockB == false on A's entry, then B must have been at x, in which case, if it starts its pre-protocol it will set turn = A and thus will not enter its critical section.

Otherwise, if turn == A on A's entry, then no matter where B was at: (y, z or w), it cannot get in the critical section because it cannot set turn = B.

Full fairness
Due to the symmetry of the algorithm, it suffices to argue that if A is at the (z, w) spin loop, it will eventually enter the critical section. Consider where B is at prior to A executing z.
If B is at x (in ncs),
then A can enter at z since lockB == false.
if B is at y,
then B has started the pre-protocol, will set turn = A and so A will after executing w.
If B is at x1 (in cs),
then eventually it will be at x and the other cases apply.
if B is at z or w, then turn cannot be reset until either A or B enters its critical section
if turn is A, then A will enter after executing w
if turn is B, then B will eventually enter its critical section and the other cases apply


© Robert M. Kline