Peterson, Dekker and software solutions

Why it exists

Before the hardware and the operating system provide locks, can two processes protect a critical section using only ordinary variables? Yes, but it is surprisingly easy to get wrong, and each plausible attempt fails in a different way: some let both processes in, some make both wait for ever, some make a process wait for one that is not even competing. Studying the failures teaches the three requirements of the critical-section problem, and Peterson's algorithm is the standard correct solution for two processes. GATE asks you to decide, for a given entry/exit code, which of mutual exclusion, progress and bounded waiting hold, and to explain why Peterson's algorithm works.

Prerequisites

You need the three requirements and the entry, critical, exit, remainder structure from critical section and race conditions.

Precise definitions

Two processes, numbered 1 and 2, each running repeat { remainder; entry; critical section; exit } forever. "Me" is process $i$, "you" is the other, $j$. All loops of the form while (c) ; are busy waits: the process spins until the condition becomes false.

Attempt 1: strict alternation. One shared variable turn.

entry:  while (turn != i) ;
exit:   turn = j;

Mutual exclusion holds. Progress fails: the processes must enter alternately. If process 2 is in a long remainder section and turn = 2, process 1 cannot enter even though the critical section is free and nobody is competing.

Attempt 2: raise your flag, then wait. A shared array flag[2], true meaning "I want to enter".

entry:  flag[i] = true;  while (flag[j]) ;
exit:   flag[i] = false;

Mutual exclusion holds, but if both raise their flags before either tests, each waits for the other for ever: deadlock (progress fails).

Attempt 3: test the other's flag, then raise your own.

entry:  while (flag[j]) ;  flag[i] = true;
exit:   flag[i] = false;

Mutual exclusion fails: both can find the other's flag false and then both raise theirs and enter. The test and the setting are separate steps, so one process can slip in between the other's two.

Peterson's algorithm. Two shared variables: flag[2] and turn.

entry:  flag[i] = true;
        turn = j;
        while (flag[j] && turn == j) ;
exit:   flag[i] = false;

A process announces its wish (flag[i] = true), then politely gives the other the turn (turn = j), and waits only while the other also wants to enter and it is the other's turn. Whoever writes turn last is the one that waits, so exactly one of two simultaneous requesters waits.

Why it works.

• Mutual exclusion. Suppose both are in the critical section. Both flags have been true since each process raised its own, and stay true until it leaves. Each process wrote turn once on its way in, and the two writes happened one after the other: say process $i$ wrote last, so it wrote turn = j, and nobody writes turn again while both are on their way in or inside. Then process $i$'s test flag[j] && turn == j is true, so process $i$ cannot have passed it: a contradiction.
• Progress. A process waits only while the other has its flag raised and has the turn; a process that is in its remainder section has its flag down, so it cannot hold up the other. No deadlock: turn has one value, so one of the two loop conditions is false.
• Bounded waiting. After process $i$ has raised its flag and set turn = j, process $j$ can enter at most once more before $i$ does: when $j$ leaves, and tries again, it sets turn = i and must wait.

The order of the first two instructions matters. If turn = j is executed before flag[i] = true, mutual exclusion fails: the page's animation gives the schedule.

Dekker's algorithm (the first correct two-process solution, historically) uses flag[2] and turn too, but a process whose flag is raised, finding the other also wants to enter and it is not its turn, lowers its flag and waits for turn before trying again. It is more complicated than Peterson's.

Lamport's bakery algorithm solves the problem for $n$ processes. A process takes a ticket number one larger than the largest it sees (like a bakery counter), then waits until every other process holding a smaller number (ties broken by process id) has finished. Shared arrays choosing[n] and number[n] make taking a number safe. It satisfies all three requirements, uses only reads and writes, and gives first come first served.

Properties of busy waiting. The waiting process wastes CPU cycles (a spinlock). Busy-wait solutions are suitable only for very short critical sections or multiprocessor kernels, and they can cause priority inversion (a high-priority spinning process may keep the CPU from a low-priority one that holds the critical section).

Memory ordering caveat. These algorithms assume that reads and writes by one process become visible to the other in program order (sequential consistency). Modern processors buffer and reorder stores, so Peterson's algorithm needs memory barriers or atomic operations to work on real hardware.

How it works

The animations are real schedules found by exploring every interleaving. They follow each algorithm in turn. Strict alternation first: the schedule ends with thread 2 stuck although thread 1 is in its remainder section.

▶remainder section
while (turn != 1) ;
critical section
turn = 2

▶remainder section
while (turn != 2) ;
critical section
turn = 1

Raise the flag, then wait: the shortest schedule that ends in deadlock.

▶remainder section
flag1 = true
while (flag2) ;
critical section
flag1 = false

▶remainder section
flag2 = true
while (flag1) ;
critical section
flag2 = false

Test, then set: the shortest schedule that puts both threads in the critical section.

▶remainder section
while (flag2) ;
flag1 = true
critical section
flag1 = false

▶remainder section
while (flag1) ;
flag2 = true
critical section
flag2 = false

Peterson's algorithm with both threads competing. T2 writes turn last and so it is T2 that waits; after T1 leaves, T2 enters.

▶remainder section
flag1 = true
turn = 2
while (flag2 && turn == 2) ;
critical section
flag1 = false

▶remainder section
flag2 = true
turn = 1
while (flag1 && turn == 1) ;
critical section
flag2 = false

And the same algorithm with its first two entry instructions swapped, which breaks mutual exclusion.

▶remainder section
turn = 2
flag1 = true
while (flag2 && turn == 2) ;
critical section
flag1 = false

▶remainder section
turn = 1
flag2 = true
while (flag1 && turn == 1) ;
critical section
flag2 = false

Worked examples

#include <stdio.h>
#include <string.h>
 
/* Two threads, 0 and 1. A state is (pc0, pc1, flag0, flag1, turn). The program explores EVERY reachable state of each algorithm. */
enum alg { ALTERNATE, FLAG_FIRST, CHECK_THEN_SET, PETERSON, PETERSON_SWAPPED };
struct st { int pc[2], flag[2], turn; };
 
/* instruction numbers: 0 remainder section, then the entry code, the critical section, the exit code (which returns to 0) */
static int cs_pc(enum alg a) { return a == ALTERNATE ? 2 : a == FLAG_FIRST || a == CHECK_THEN_SET ? 3 : 4; }
static int wait_pc(enum alg a) { return a == ALTERNATE ? 1 : a == FLAG_FIRST ? 2 : a == CHECK_THEN_SET ? 1 : 3; }
 
/* returns 1 and fills *out if thread i can take a step, 0 if it is blocked at a loop */
static int move(enum alg a, const struct st *s, int i, struct st *out) {
    int j = 1 - i, pc = s->pc[i];
    *out = *s;
    switch (a) {
    case ALTERNATE:      /* 0 rem, 1 while (turn != i), 2 cs, 3 turn = j */
        if (pc == 1 && s->turn != i) return 0;
        if (pc == 3) { out->turn = j; out->pc[i] = 0; return 1; }
        out->pc[i] = pc + 1; return 1;
    case FLAG_FIRST:     /* 0 rem, 1 flag[i] = 1, 2 while (flag[j]), 3 cs, 4 flag[i] = 0 */
        if (pc == 1) out->flag[i] = 1;
        if (pc == 2 && s->flag[j]) return 0;
        if (pc == 4) { out->flag[i] = 0; out->pc[i] = 0; return 1; }
        out->pc[i] = pc + 1; return 1;
    case CHECK_THEN_SET: /* 0 rem, 1 while (flag[j]), 2 flag[i] = 1, 3 cs, 4 flag[i] = 0 */
        if (pc == 1 && s->flag[j]) return 0;
        if (pc == 2) out->flag[i] = 1;
        if (pc == 4) { out->flag[i] = 0; out->pc[i] = 0; return 1; }
        out->pc[i] = pc + 1; return 1;
    default:             /* Peterson: 0 rem, 1 and 2 the two entry writes, 3 while (flag[j] && turn == j), 4 cs, 5 flag[i] = 0 */
        if (pc == 1 || pc == 2) {
            int first_is_flag = a == PETERSON ? pc == 1 : pc == 2;
            if (first_is_flag) out->flag[i] = 1; else out->turn = j;
        }
        if (pc == 3 && s->flag[j] && s->turn == j) return 0;
        if (pc == 5) { out->flag[i] = 0; out->pc[i] = 0; return 1; }
        out->pc[i] = pc + 1; return 1;
    }
}
 
static int code(const struct st *s) { return (((s->pc[0] * 6 + s->pc[1]) * 2 + s->flag[0]) * 2 + s->flag[1]) * 2 + s->turn; }
 
static void explore(enum alg a, const char *name) {
    static unsigned char seen[6 * 6 * 8];
    static struct st queue[6 * 6 * 8];
    memset(seen, 0, sizeof seen);
    int head = 0, tail = 0, states = 0, me = 0, dead = 0, prog = 0;
    struct st start = {{0, 0}, {0, 0}, 0};
    queue[tail++] = start; seen[code(&start)] = 1;
    while (head < tail) {
        struct st s = queue[head++], n;
        states++;
        if (s.pc[0] == cs_pc(a) && s.pc[1] == cs_pc(a)) me = 1;
        int moved = 0;
        for (int i = 0; i < 2; i++) {
            if (move(a, &s, i, &n)) {
                moved = 1;
                if (!seen[code(&n)]) { seen[code(&n)] = 1; queue[tail++] = n; }
            } else if (s.pc[1 - i] == 0 && s.pc[i] == wait_pc(a)) prog = 1;   /* stuck at its wait while the other is outside the competition */
        }
        if (!moved) dead = 1;
    }
    printf("%-22s states %2d  mutual exclusion violated: %d  deadlock: %d  waits for a thread in its remainder section: %d\n", name, states, me, dead, prog);
}
 
int main(void) {
    explore(ALTERNATE, "strict alternation");
    explore(FLAG_FIRST, "flag first");
    explore(CHECK_THEN_SET, "check then set");
    explore(PETERSON, "Peterson");
    explore(PETERSON_SWAPPED, "Peterson, swapped");
    return 0;
}

strict alternation     states 16  mutual exclusion violated: 0  deadlock: 0  waits for a thread in its remainder section: 1
flag first             states 21  mutual exclusion violated: 0  deadlock: 1  waits for a thread in its remainder section: 0
check then set         states 25  mutual exclusion violated: 1  deadlock: 0  waits for a thread in its remainder section: 0
Peterson               states 42  mutual exclusion violated: 0  deadlock: 0  waits for a thread in its remainder section: 0
Peterson, swapped      states 72  mutual exclusion violated: 1  deadlock: 0  waits for a thread in its remainder section: 0

Cheat box

Traps and GATE patterns

Connections

These solutions are the base on which hardware instructions such as test-and-set and the semaphore are justified. A circular wait is the cause of the deadlock in "flag first" (deadlock). The need for memory barriers comes from stores being buffered and reordered between processor and memory, as in the write buffers of the cache.

PYQs

Consider the following proposed solution for the
critical section problem. There are n processes:
P0...Pn-1. In the code, function pmax returns an integer
not smaller than any of its arguments. For all i, t[i] is
initialized to zero.

Code for Pi:

do {

c[i]=1; t[i] = pmax (t[0],...,t[n-1]) +1; c[i]=0;

           for every j ≠ i in {0,...,n-1} {

  while (c[j]);

  while (t[j]! = 0 && t[j]<=t[i]);

 }

Critical Section;

t[i]=0;

Remainder Section;

} while (true);

Which one of the following is TRUE about the above
solution?

Consider the following two-process synchronization
solution.

Process 0
Process 1
Entry: loop while
(turn == 1);
Entry: loop while (turn == 0);

(critical section )
( Critical section)
Exit: turn = 1;
Exit: turn = 0;

The shared variable turn is initialized to zero. Which
one of the following is TRUE?

Two processes X and Y need to access a critical
section. Consider the following synchronization
construct used by both the processes.

Here, varP and varQ are shared variables and both
are initialized to false. Which one of the following
statements is true?

Consider the methods used by processes P1 and P2
for accessing their critical sections whenever
needed, as given below. The initial values of shared
Boolean variables S1 and S2 are randomly
assigned.

Method Used by P1
Method Used by P2
while (S1 == S2);
while (S1! = S2);
Critical Section
Critical Section
S1 = S2;
S2 = not (S1);

Which one of the following statements describes the
properties achieved?

Two processes, P1 and P2, need to access a critical
section
of
code.
Consider
the
following
synchronization construct used by the processes:

/* P1 */
while (true) {
    wants1 = true;
    while (wants2 == true);
    /* Critical Section */
    wants1 = false;
}
/* Remainder section */

/* P2 */
while (true) {
    wants2 = true;
    while (wants1 == true);
    /* Critical Section */
    wants2 = false;
}
/* Remainder section */

Here, wants1 and wants2 are shared variables,
initialized to false.

Which one of the following statements is TRUE
about the above construct?

Self-check

Revision card

References