Race condition example; Peterson's algorithm

Race condition

A race condition is a situation where two or more processes (or threads) read and write shared data, and the final result depends on the exact order in which the processes are scheduled.

Example: a shared counter count = 5. Process P1 executes count++ and process P2 executes count--. In machine code each is three steps: load into register, change the register, store back.

P1: R1 = count      (R1 = 5)
P1: R1 = R1 + 1     (R1 = 6)
   -- context switch --
P2: R2 = count      (R2 = 5)
P2: R2 = R2 - 1     (R2 = 4)
P2: count = R2      (count = 4)
   -- context switch --
P1: count = R1      (count = 6)

The correct final value is 5, but here it is 6 (or 4 with another order). Another example is the print spooler, where two processes pick the same slot in and one file is overwritten.

Peterson's algorithm

Peterson's algorithm (1981) is a software solution of the mutual exclusion problem for two processes (0 and 1), which uses two shared variables: turn (whose turn it is to enter) and interested[2] (flags showing who wants to enter).

#define N 2
int turn;                      /* whose turn is it? */
int interested[N];             /* all values initially FALSE */

void enter_region(int process) {       /* process is 0 or 1 */
    int other = 1 - process;           /* the other process */
    interested[process] = TRUE;        /* show interest */
    turn = process;                    /* set the flag */
    while (turn == process && interested[other] == TRUE)
        ;                              /* busy wait */
}

void leave_region(int process) {
    interested[process] = FALSE;       /* departure from region */
}

Working: before entering its critical region, a process calls enter_region with its number. It sets its interested flag and sets turn to itself. If the other process is not interested, the loop condition is false and it enters at once. If both call at the same time, both set turn, but only the last store survives; the process whose store came first sees turn != itself and enters, while the last one loops until the first calls leave_region.

Properties: it guarantees mutual exclusion, progress and bounded waiting, and needs no special hardware. Disadvantages: it works for two processes only, and it uses busy waiting (wasting CPU, and risking priority inversion).