CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 4 of 7 · 3 min read

Semaphores

In plain words: Two counters are enough: how many slots are empty and how many are full. A producer takes an empty slot (and waits if there is none), and a consumer takes a full one. Semaphores (page 5) are counters that make threads wait, so each counter is one:

  • empty, initialised to the number of slots, counts free slots.
  • full, initialised to 0, counts items.
  • mu, a mutex, protects the indices.
void put(int v) {
    sem_wait(&empty);                    /* wait for a free slot FIRST */
    pthread_mutex_lock(&mu);
    buf[in] = v;  in = (in + 1) % SLOTS;
    pthread_mutex_unlock(&mu);
    sem_post(&full);                     /* one more item */
}
int get(void) {
    sem_wait(&full);                     /* wait for an item FIRST */
    pthread_mutex_lock(&mu);
    int v = buf[out];  out = (out + 1) % SLOTS;
    pthread_mutex_unlock(&mu);
    sem_post(&empty);                    /* one more free slot */
    return v;
}

A trace with 2 slots (empty starts at 2, full at 0):

Step Action empty full Items
1 producer puts 1 1 1 1
2 producer puts 2 0 2 1, 2
3 producer tries to put 3: sem_wait(empty) sleeps 0 2 1, 2
4 consumer gets 1 1 1 2
5 producer wakes, puts 3 0 2 2, 3

The producer slept at step 3 and woke at step 4 when the consumer freed a slot. empty + full is always the number of slots (2), except during the short moment inside a put or get.

The order matters. The wait on the semaphore comes before the mutex. If the order is reversed (lock the mutex first, then wait for empty), a producer can hold the mutex while it sleeps for a free slot, and the consumer, which needs the mutex to take an item and free a slot, cannot get in. Neither can go on: a deadlock, a group of threads that are all stuck, each needing something that only another one could give (Level 5). The test:

produced 1
produced 2
exit code 124            <- killed by `timeout` after 3 s: the program hung

With a buffer of 2 and the wrong order, the producer filled both slots, took the mutex for the third item, and slept on empty. The consumer woke, passed sem_wait(full) (the value was 2), and then waited for the mutex for ever. The correct order printed all items in the other tests.

Deadlock

A deadlock is a permanent standstill of a group of threads, each blocked while waiting for something that only a different member of the group could provide, so that none of them can ever run again.

Example: a producer holds the mutex while it waits for a free slot, and the consumer that could free a slot waits for that mutex.

Check yourself: 1. What do the values of empty and full show at step 3? 2. Why must the semaphore wait come before the mutex lock? 3. What happened in the test with the wrong order?