Process Synchronization

A race condition occurs when the result depends on the order in which processes access shared data. The code that accesses shared data is the critical section.

Requirements for a Solution

1. Mutual exclusion: only one process in the critical section at a time.
2. Progress: if none is inside, the choice of who enters next can't be postponed indefinitely.
3. Bounded waiting: there's a limit on how many times others can enter before a waiting process does.

Peterson's Solution (2 processes)

int flag[2] = {0, 0};
int turn;

void process(int i) {
    int j = 1 - i;
    flag[i] = 1;
    turn = j;
    while (flag[j] && turn == j) ;   // busy wait
    /* critical section */
    flag[i] = 0;
    /* remainder section */
}

Semaphores

A semaphore S is an integer accessed only through atomic wait (P) and signal (V).

wait(S):   while (S <= 0) ;   S--;
signal(S): S++;
Binary semaphore: values 0/1 (mutex).  Counting semaphore: any non-negative value.

Producer–Consumer (Bounded Buffer)

semaphore mutex = 1, empty = N, full = 0;

Producer:                    Consumer:
  wait(empty);                 wait(full);
  wait(mutex);                 wait(mutex);
  add item to buffer           remove item from buffer
  signal(mutex);               signal(mutex);
  signal(full);                signal(empty);

Other classic problems: Readers–Writers and Dining Philosophers.