Producer-consumer, readers-writers, dining philosophers
The three classic synchronisation problems, their risk and typical solution: the bounded buffer with two semaphores and a mutex, priority between readers and writers, the dining philosophers and their remedies.
- 23 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
- Understand
A few cards from the deck
Producer-consumer problem: what is it?
Show the answer
Some threads put items into a queue of limited size while others take them out: they must wait when it is full or empty.
Typical solution: two semaphores counting free and occupied slots, and a mutex to protect the buffer indices.
In this version of the producer, what happens when the buffer is full?
```c
P(&mutex);
P(&vide);
deposer(x);
V(&mutex);
V(&plein);`- It sleeps on
videholdingmutex: no consumer can take anything out - It deposits anyway and overwrites the oldest occupied slot of the buffer
P(&vide)fails and the deposit is simply skipped by the producer- Nothing: the consumer removes while the producer sleeps on vide
Show the answer
It sleeps on
videholdingmutex: no consumer can take anything outThe consumer must do P(mutex) to remove, but the producer holds it while asleep. The correct order is P(vide), then P(mutex).
- It sleeps on
In the N-slot bounded buffer, the … semaphore counts the free slots (initialised to N) and the … semaphore counts the occupied slots (initialised to 0).
Show the answer
In the N-slot bounded buffer, the empty semaphore counts the free slots (initialised to N) and the full semaphore counts the occupied slots (initialised to 0).
The producer does P on “empty” then V on “full”; the consumer does the opposite. A third semaphore, the mutex, protects the indices.
Readers-writers problem: what is it?
Show the answer
A piece of data is read by several threads and modified by others: reads may overlap, but a write requires being alone.
The priority choice decides who may starve: favouring readers can starve writers, and the other way round.
A cache is read a thousand times a second and updated once a minute, but the update never goes through. Which classic problem is this?
- Readers-writers: the writer is starved by the readers
- Producer-consumer, with a buffer that is too small for the flow
- Dining philosophers, with a fork missing from the table
- A deadlock between the cache and the service's database
Show the answer
Readers-writers: the writer is starved by the readers
Readers overlap constantly, so the data is never free for the writer. A deadlock would freeze the readers too, yet here they carry on.