Synchronization: locks and semaphores

Any solution to the critical-section problem (only one thread at a time in the code that uses shared data) must give:

1. Mutual exclusion: at most one thread is in the critical section.
2. Progress: if nobody is inside, one of the threads that want to enter gets in; the choice is not put off forever.
3. Bounded waiting: a thread that asks to enter gets in after a limited number of others have gone first, so nobody starves.

Peterson's solution

For two threads, 0 and 1, with shared flag[2] and turn:

/* thread i; the other thread is j = 1 - i */
flag[i] = 1;                  /* I want to enter */
turn = j;                     /* but you may go first */
while (flag[j] && turn == j)  /* wait while you want in and it is your turn */
    ;
/* critical section */
flag[i] = 0;                  /* I am out */

It meets all three rules using only ordinary memory, which makes it a favourite in exams. On modern CPUs, which reorder memory operations, it fails without special memory barrier instructions, so real systems use the hardware's help instead.

Atomic instructions and mutex locks

CPUs have atomic instructions that read and write a memory word in one step that cannot be interrupted, such as test_and_set and compare_and_swap. With them the OS builds a mutex lock (mutual exclusion):

lock(&m);      /* wait until the lock is free, then take it */
count++;       /* critical section */
unlock(&m);

With the lock, the second thread waits at lock(m) until the first unlocks, so the three steps can no longer interleave and the count always ends at 2. A lock that waits by looping is a spinlock: good for very short waits on a machine with several cores, wasteful otherwise. A blocking lock puts the waiting thread to sleep instead.

Semaphores

A semaphore S is an integer with two atomic operations:

• wait(S) (also P, or down): if S > 0, subtract 1 and go on; otherwise wait until it is.
• signal(S) (also V, or up): add 1, waking a waiting thread if there is one.

A binary semaphore (0 or 1) works like a mutex. A counting semaphore counts free resources: 5 printers means S starts at 5.

Producer and consumer

A producer puts items into a buffer with N slots, and a consumer takes them out. Three semaphores keep them in step: empty (free slots, starts at N), full (filled slots, starts at 0) and mutex (starts at 1, guards the buffer itself):

/* producer */                 /* consumer */
wait(empty);                   wait(full);
wait(mutex);                   wait(mutex);
buffer[in] = item;             item = buffer[out];
in = (in + 1) % N;             out = (out + 1) % N;
signal(mutex);                 signal(mutex);
signal(full);                  signal(empty);

#include <stdio.h>

#define N 3

int buffer[N], in = 0, out = 0;
int empty = N;     /* semaphore: free slots */
int full = 0;      /* semaphore: filled slots */

void produce(int item) {
    if (empty == 0) {                  /* wait(empty) would block */
        printf("producer waits: the buffer is full\n");
        return;
    }
    empty--;                           /* wait(empty) */
    buffer[in] = item;
    in = (in + 1) % N;
    full++;                            /* signal(full) */
}

void consume(void) {
    if (full == 0) {                   /* wait(full) would block */
        printf("consumer waits: the buffer is empty\n");
        return;
    }
    full--;                            /* wait(full) */
    int item = buffer[out];
    out = (out + 1) % N;
    empty++;                           /* signal(empty) */
    printf("consumed %d\n", item);
}

int main(void) {
    produce(10);
    produce(20);
    produce(30);
    produce(40);      /* no free slot */
    consume();
    produce(40);      /* now there is one */
    consume();
    consume();
    consume();
    consume();        /* nothing left */
    return 0;
}

The example acts this out in one thread with N = 3: where a real thread would wait, the program prints that it waits and skips the step. Watch empty and full always add up to 3.

Classic problems

• Readers and writers: many threads may read a shared record at once, but a writer needs it alone. Solutions must decide who goes first, or one side can starve.
• Dining philosophers: five philosophers sit round a table with one chopstick between each pair, and each needs both neighbours' chopsticks to eat. If all pick up their left chopstick at once, nobody can ever pick up a right one: a deadlock, the next lesson's subject. Fixes: let at most four sit at once, or make one philosopher pick up right first.

Mark lesson complete