Classical Synchronization Problems in Operating Systems
Process synchronization is one of the trickier aspects of OS design. When multiple processes run at the same time and share resources, things can go wrong quickly.
Over the years, researchers have come up with a handful of classic problems that capture these challenges well. Each one maps directly to real situations in operating systems where processes compete for shared resources like memory, files, and devices.
Dining Philosophers Problem
Picture a round table with philosophers seated around it. Each philosopher spends their time either thinking or eating. Between every two adjacent philosophers sits a single piece of cutlery. To eat, a philosopher needs both the cutlery to their left and the one to their right.
The challenge: how do we make sure no philosopher waits forever (starvation) and that the system never reaches a standstill where everyone is waiting on everyone else (deadlock)?
Dining Philosophers Problem: philosophers around a table with shared cutlery between them.
The Solution
Each piece of cutlery is modeled as a binary semaphore set to 1. A philosopher grabs both cutleries before eating and puts them back once done.
semaphore fork[3] = {1, 1, 1};
semaphore spoon[3] = {1, 1, 1};
void philosopher(int i) {
while (true) {
think();
wait(fork[i]); // Pick up left cutlery
wait(spoon[i]); // Pick up right cutlery
eat(); // Critical section
signal(spoon[i]); // Put down right cutlery
signal(fork[i]); // Put down left cutlery
}
}Producer Consumer Problem
Also called the Bounded Buffer Problem, this one involves two kinds of processes sharing a fixed-size buffer. The producer keeps generating data and pushing it into the buffer, while the consumer pulls data out and processes it.
The tricky part: the producer should not add to a full buffer, and the consumer should not try reading from an empty one.
Producer Consumer Problem: producers adding items to a bounded buffer, consumers removing them.
The Solution
Three semaphores do the job. One tracks empty slots, another tracks filled slots, and a mutex handles mutual exclusion during buffer access.
semaphore empty = N; // Tracks empty slots
semaphore full = 0; // Tracks filled slots
semaphore mutex = 1; // Protects buffer access
void producer() {
while (true) {
item = produce_item();
wait(empty); // Wait if buffer is full
wait(mutex); // Enter critical section
add_item_to_buffer(item);
signal(mutex); // Exit critical section
signal(full); // Signal: one more item available
}
}
void consumer() {
while (true) {
wait(full); // Wait if buffer is empty
wait(mutex); // Enter critical section
item = remove_item_from_buffer();
signal(mutex); // Exit critical section
signal(empty); // Signal: one more slot free
consume_item(item);
}
}Reader Writer Problem
Here we have two groups of processes: readers and writers. Multiple readers can safely access shared data at the same time since they are not modifying anything. Writers, though, need full exclusive access because any overlap with other readers or writers can corrupt the data.
The Solution
A counter keeps track of active readers. The first reader to arrive blocks writers from entering, and the last reader to leave lets writers back in. Writers simply wait for a clear path and proceed once they get it.
semaphore mutex = 1; // Protects read_count
semaphore writeBlock = 1; // Controls writer access
int read_count = 0; // Active readers
void reader() {
wait(mutex);
read_count++;
if (read_count == 1)
wait(writeBlock); // First reader blocks writers
signal(mutex);
read_data(); // Multiple readers can be here
wait(mutex);
read_count--;
if (read_count == 0)
signal(writeBlock); // Last reader unblocks writers
signal(mutex);
}
void writer() {
wait(writeBlock); // Exclusive access
write_data();
signal(writeBlock);
}Sleeping Barber Problem
This one is set in a barbershop with one barber, one barber chair, and a waiting room with N seats. When no customers are around, the barber naps in their chair. A new customer either wakes the barber up or takes a seat in the waiting room if the barber is busy. If all seats are taken, the customer simply walks away.
Sleeping Barber Problem: barber, barber chair, and a waiting room with limited seats.
The Solution
Three semaphores are used. One tracks available waiting room chairs, another manages access to the barber chair, and a third handles the barber's sleep state.
semaphore barberSleep = 0; // Barber starts asleep
semaphore barberChair = 1; // One barber chair
semaphore waitingRoom = N; // N seats in waiting room
void barber() {
while (true) {
wait(barberSleep); // Sleep until a customer arrives
wait(barberChair); // Occupy the barber chair
// --- Cut hair ---
signal(barberChair); // Free the barber chair
}
}
void customer() {
if (tryWait(waitingRoom) == false) {
return; // No seats, leave the shop
}
signal(waitingRoom); // Leave waiting room
wait(barberChair); // Sit in barber chair
signal(barberSleep); // Wake up the barber
// --- Get haircut ---
signal(barberChair); // Free the barber chair
}How They Map to Real Systems
| Classical Problem | Real-World Equivalent | Core Challenge |
|---|---|---|
| Dining Philosophers | Processes competing for multiple shared resources (e.g., two I/O devices needed simultaneously) | Deadlock and starvation avoidance |
| Producer Consumer | Web servers queuing requests, print spoolers, logging pipelines | Buffer overflow/underflow prevention |
| Reader Writer | Database queries vs updates, config file reads vs admin writes | Maximizing read parallelism while protecting writes |
| Sleeping Barber | Thread pools with limited worker threads, network servers with connection limits | Managing a finite service capacity without dropping clients unnecessarily |
These four problems might seem like abstract scenarios, but they map directly to real situations in operating systems where processes compete for shared resources. Getting a handle on these problems builds a solid foundation for writing concurrent code that avoids deadlocks and keeps every process moving forward.