Classical Synchronization Problems

These problems appear in almost every OS interview. Mastering them shows you understand how to apply synchronization primitives to real concurrency challenges.

1. Producer-Consumer (Bounded Buffer)

Setup: Producers add items to a fixed-size buffer. Consumers remove items. The buffer has N slots.

Constraints:

• Producer must not add to a full buffer
• Consumer must not remove from an empty buffer
• Both must not modify the buffer simultaneously

Solution (three semaphores):

Semaphore	Initial value	Purpose
empty	N	Counts empty slots — producer waits, consumer signals
full	0	Counts filled slots — consumer waits, producer signals
mutex	1	Mutual exclusion for buffer access

Producer:                          Consumer:
wait(empty)                        wait(full)
wait(mutex)                        wait(mutex)
// add item to buffer              // remove item from buffer
signal(mutex)                      signal(mutex)
signal(full)                       signal(empty)

2. Readers-Writers

Setup: Multiple readers can read simultaneously. Only one writer can write. While a writer writes, no readers can read.

First variant (reader-preference): Readers can keep entering as long as no writer is active. Writer starvation is possible.

Second variant (writer-preference): Once a writer is ready, no new readers can start. Readers are allowed to finish, then writer proceeds.

Key trick: A read_count variable tracks active readers, protected by its own mutex. The writer needs a different semaphore.

3. Dining Philosophers

Setup: Five philosophers, five chopsticks. Each needs both left and right chopsticks to eat.

Deadlock scenario: All five pick up left chopstick simultaneously → all wait for right forever.

Solutions:

• Allow only 4 philosophers at the table (prevents circular wait)
• Pick up both chopsticks only if both are available
• Odd philosophers pick left first, even pick right first (asymmetric)

void philosopher(int i) {
    while (true) {
        think();
        pickup(forks[i]);          // left
        pickup(forks[(i+1)%5]);    // right
        eat();
        putdown(forks[i]);
        putdown(forks[(i+1)%5]);
    }
}