Inter-process communication, concurrency and synchronisation

A race condition occurs when the result of a computation depends on the order in which instructions of concurrent processes (or threads) are interleaved on shared data. A statement such as x = x + 1 is not atomic: it compiles to load x into a register, add 1, store the register into x. A context switch between these steps can lose an update.

The critical section (CS) is the part of a process that accesses shared data. Each process has the structure: entry section, critical section, exit section, remainder section. A correct solution must satisfy three requirements.

Two processes P0 and P1 are used, with i the current process and j = 1 - i the other. Assume instructions execute in program order and memory reads and writes are atomic (sequential consistency).

Peterson's solution for process i:

/* shared: bool flag[2] = {false, false}; int turn; */
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
    ;  /* busy wait */
/* critical section */
flag[i] = false;
/* remainder section */

Why it works: if both want to enter, both set turn, and the last write wins. The process whose write was overwritten (turn equals its own index) enters, and the other waits. When it leaves, it clears its flag and the waiter proceeds, so a process waits for at most one entry of the other (bounded waiting).

For n processes, the bakery algorithm is a software solution. A process that wants to enter takes a number one larger than the largest number currently held, and the process with the smallest pair (number, process index) enters. Two processes can take the same number, so ties are broken by the lower process index. It satisfies mutual exclusion, progress and bounded waiting.

Software-only solutions are complex beyond two processes. Hardware offers atomic instructions that read and modify a location as one indivisible step.

Test-and-set (TAS) atomically returns the old value of a boolean and sets it to true:

bool test_and_set(bool *lock) {   /* executed atomically */
    bool old = *lock;
    *lock = true;
    return old;
}

/* shared: bool lock = false; */
while (test_and_set(&lock))
    ;  /* spin */
/* critical section */
lock = false;

The first process to execute TAS sees false and enters; the others see true and spin.

Compare-and-swap (CAS) atomically compares a location with an expected value and, only if they are equal, stores a new value. It returns the original value:

int compare_and_swap(int *v, int expected, int new_val) {   /* atomic */
    int old = *v;
    if (old == expected)
        *v = new_val;
    return old;
}

/* shared: int lock = 0; */
while (compare_and_swap(&lock, 0, 1) != 0)
    ;  /* spin */
/* critical section */
lock = 0;

Swap (exchange) atomically exchanges the contents of two locations. Each process has its own key:

/* shared: bool lock = false; local: bool key; */
key = true;
while (key == true)
    swap(&lock, &key);   /* atomic exchange */
/* critical section */
lock = false;

It behaves like the simple TAS lock: mutual exclusion holds, bounded waiting does not.

A semaphore is an integer variable accessed only through two atomic operations. In the blocking (no busy-waiting) implementation:

wait(S) {            /* P */
    S.value--;
    if (S.value < 0) {
        /* add this process to S.list and block it */
    }
}

signal(S) {          /* V */
    S.value++;
    if (S.value <= 0) {
        /* remove one process from S.list and wake it */
    }
}

Convention used here: a negative value means that many processes are blocked on the semaphore. In the simple busy-waiting form, wait(S) is while (S <= 0) ; S--;, where the last successful test and the decrement happen as one atomic step, and the value never goes below zero.

For mutual exclusion initialise a binary semaphore mutex = 1 and bracket the CS with wait(mutex) and signal(mutex). To force an order (statement A in P1 before statement B in P2), initialise S = 0, put signal(S) after A and wait(S) before B. A mutex lock is used only for mutual exclusion. In typical thread libraries it has an owner: only the thread that locked it may unlock it. A binary semaphore has no owner, so any process may signal it.

Busy waiting versus blocking. Busy waiting (spinlock) burns CPU cycles but avoids a context switch, so it suits very short critical sections on multiprocessors. Blocking puts the process in a wait queue and uses no CPU, but costs two context switches. Misuse of semaphores (wrong order of wait operations, a missing signal) causes deadlock or starvation. For example, with two semaphores taken in opposite orders:

/* shared: semaphore S = 1, Q = 1; */
/* P0 */            /* P1 */
wait(S);            wait(Q);
wait(Q);            wait(S);

If P0 completes wait(S) and P1 completes wait(Q), each then blocks on the semaphore the other holds: deadlock.

A monitor is a language-level construct: shared data plus the procedures that access it, with the guarantee that at most one process is active inside the monitor at a time (mutual exclusion is automatic). Inside, condition variables provide waiting: x.wait() suspends the caller and releases the monitor; x.signal() resumes one process waiting on x. If no process is waiting, x.signal() has no effect. This differs from a semaphore, whose signal is remembered in the value. Since only one process may be active, after a signal either the signaller waits and the woken process runs (signal-and-wait), or the signaller continues and the woken process runs later (signal-and-continue). Under signal-and-continue the condition may have changed, so the woken process re-checks it in a while loop.

Producer-consumer (bounded buffer of N slots). Semaphores: mutex = 1 (buffer access), empty = N (free slots), full = 0 (filled slots).

/* producer */
while (1) {
    produce_item();
    wait(empty);
    wait(mutex);
    insert_item();
    signal(mutex);
    signal(full);
}

/* consumer */
while (1) {
    wait(full);
    wait(mutex);
    remove_item();
    signal(mutex);
    signal(empty);
}

Readers-writers (readers' priority). Many readers may read together; a writer needs exclusive access. Semaphores mutex = 1, wrt = 1, integer readcount = 0.

/* reader */
wait(mutex);
readcount++;
if (readcount == 1)
    wait(wrt);
signal(mutex);
/* read */
wait(mutex);
readcount--;
if (readcount == 0)
    signal(wrt);
signal(mutex);

/* writer */
wait(wrt);
/* write */
signal(wrt);

The first reader locks out writers and the last reader lets them in. Writers can starve if readers keep arriving.

Dining philosophers. N philosophers sit round a table with one chopstick between each pair of neighbours; eating needs both adjacent chopsticks. If every philosopher picks up the left chopstick (wait(chopstick[i])) and then the right one, all can hold one chopstick and wait forever: deadlock.

Inter-process communication (IPC) lets cooperating processes exchange data. There are two models.

Message passing can be direct (the sender names the receiver) or indirect (through a mailbox or port), and blocking (synchronous) or non-blocking (asynchronous). A blocking send waits until the message is received; a blocking receive waits until a message is available. The queue on a link has zero capacity (the sender waits until the receiver takes the message, a rendezvous), bounded capacity (the sender blocks only when the queue is full) or unbounded capacity (the sender never blocks).