Introduction
Operating systems textbooks use a handful of classical problems to illustrate synchronization techniques because they capture recurring patterns found in real systems: bounded buffers between pipeline stages, shared data structures with many readers and occasional writers, and circular resource-sharing that can lead to deadlock. The three most common are the Producer-Consumer (Bounded-Buffer) problem, the Readers-Writers problem, and the Dining Philosophers problem.
Cricket analogy: A curator studies recurring match situations - the death-over slog, the new-ball swing, a batting collapse chasing a target - the same way OS courses distill concurrency into Producer-Consumer, Readers-Writers, and Dining Philosophers.
Explanation
Producer-Consumer: one or more producer threads generate items and place them into a fixed-size shared buffer; one or more consumer threads remove and process items. The classic solution uses three synchronization primitives: a counting semaphore empty initialized to the buffer capacity N (tracks free slots), a counting semaphore full initialized to 0 (tracks filled slots), and a binary semaphore/mutex to protect the buffer indices during the actual insert/remove. Producers wait on empty, lock the mutex, insert, unlock, then post full; consumers wait on full, lock the mutex, remove, unlock, then post empty. Readers-Writers: multiple reader threads may access shared data concurrently since reads do not conflict, but a writer needs exclusive access. The classic first solution uses a mutex to protect a read_count variable and a semaphore/mutex rw_lock that guards actual access to the resource: the first reader to arrive locks rw_lock (blocking writers), the last reader to leave unlocks it; writers simply wait on and post rw_lock directly. This basic version favors readers and can starve writers; variants add a write_lock or turnstile to give writers fairness. Dining Philosophers: five philosophers sit around a table with one fork between each pair; each needs both adjacent forks to eat. Naively having everyone pick up the left fork first can deadlock (each holds one fork and waits forever for the other). Standard fixes include: an asymmetric ordering (odd-numbered philosophers pick up left-then-right, even-numbered pick up right-then-left), allowing at most N-1 philosophers to attempt eating simultaneously via a counting semaphore, or acquiring both forks atomically via a single mutex guarding the pickup decision.
Cricket analogy: Like a scoreboard runner who can only hand the umpire a new total once a slot opens (empty) and the umpire can only read one once posted (full), while only one runner touches the board at a time (mutex) - and five fielders sharing two spare gloves must avoid every fielder grabbing the left glove first and waiting forever, so captains stagger who reaches first.
Example
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#define BUFFER_SIZE 5
#define ITEMS 10
int buffer[BUFFER_SIZE];
int in = 0, out = 0;
sem_t empty_slots; /* counts free slots, starts at BUFFER_SIZE */
sem_t full_slots; /* counts filled slots, starts at 0 */
pthread_mutex_t buf_mutex = PTHREAD_MUTEX_INITIALIZER;
void *producer(void *arg) {
for (int i = 0; i < ITEMS; i++) {
sem_wait(&empty_slots); /* wait for a free slot */
pthread_mutex_lock(&buf_mutex);
buffer[in] = i;
printf("Produced %d at slot %d\n", i, in);
in = (in + 1) % BUFFER_SIZE;
pthread_mutex_unlock(&buf_mutex);
sem_post(&full_slots); /* signal one more filled slot */
}
return NULL;
}
void *consumer(void *arg) {
for (int i = 0; i < ITEMS; i++) {
sem_wait(&full_slots); /* wait for a filled slot */
pthread_mutex_lock(&buf_mutex);
int item = buffer[out];
printf("Consumed %d from slot %d\n", item, out);
out = (out + 1) % BUFFER_SIZE;
pthread_mutex_unlock(&buf_mutex);
sem_post(&empty_slots); /* signal one more free slot */
}
return NULL;
}
int main(void) {
pthread_t prod, cons;
sem_init(&empty_slots, 0, BUFFER_SIZE);
sem_init(&full_slots, 0, 0);
pthread_create(&prod, NULL, producer, NULL);
pthread_create(&cons, NULL, consumer, NULL);
pthread_join(prod, NULL);
pthread_join(cons, NULL);
sem_destroy(&empty_slots);
sem_destroy(&full_slots);
return 0;
}Analysis
In the bounded-buffer solution, empty_slots and full_slots never let the producer overrun a full buffer or the consumer read from an empty one, because sem_wait blocks until the corresponding count is positive; the mutex additionally ensures in/out updates and buffer writes are not interleaved if multiple producers or consumers exist. The same pattern of 'counting semaphores for capacity, mutex for the critical section' recurs in the Readers-Writers solution (mutex protects read_count; a semaphore guards actual resource access) and underlies why Dining Philosophers needs either asymmetry or a bounded number of concurrent diners to avoid the circular-wait deadlock pattern.
Cricket analogy: Just as a scoring app blocks updates until a slot genuinely opens rather than guessing, the empty/full semaphores block producers and consumers until slots truly exist, while the mutex ensures only one scorer edits the innings total at once, and Dining Philosophers needs the same discipline to avoid five fielders deadlocked over gloves.
Key Takeaways
- Producer-Consumer uses two counting semaphores (empty, full) plus a mutex to safely manage a bounded circular buffer.
- Readers-Writers allows concurrent readers but exclusive writers; a read_count variable guarded by a mutex controls when the shared resource lock is acquired/released.
- The basic Readers-Writers solution favors readers and can starve writers unless fairness is added.
- Dining Philosophers illustrates deadlock via circular wait: all philosophers picking up the left fork simultaneously can deadlock.
- Deadlock in Dining Philosophers is avoided by breaking symmetry (asymmetric pickup order), limiting concurrent diners to N-1, or acquiring both forks atomically.
Practice what you learned
1. In the classic bounded-buffer Producer-Consumer solution, what is the initial value of the 'full' semaphore?
2. In the Readers-Writers problem, why is a separate mutex used to protect the read_count variable?
3. What classic problem does 'each philosopher picks up the left fork first, then the right fork, with no other coordination' risk?
4. Which technique is a standard fix for the Dining Philosophers deadlock?
Was this page helpful?
You May Also Like
Mutex and Semaphores
Compare mutexes and binary/counting semaphores as tools for enforcing mutual exclusion and coordinating threads.
Introduction to Deadlocks
Get a high-level preview of what deadlock is and the four necessary conditions that must all hold for it to occur.
Interprocess Communication
How independent processes with separate address spaces exchange data and coordinate using OS-provided IPC mechanisms.