Topic 5.3 · Process Synchronization & Concurrency Problems

Classic Concurrency Problems (Producer-Consumer, Readers-Writers, Dining Philosophers & Code Problems)

4 min read1 question to test yourself

1Definition

Classic Concurrency Problems are fundamental benchmark synchronization challenges—including the Producer-Consumer (Bounded-Buffer) Problem, Readers-Writers Problem, and Dining Philosophers Problem—used to evaluate the correctness, safety, and efficiency of thread synchronization primitives.

2Simple Explanation

  • Producer-Consumer: A Producer thread generates data and puts it into a fixed-size buffer slot. A Consumer thread removes data from the buffer. The Producer must sleep if the buffer is full; the Consumer must sleep if the buffer is empty. Both must share access safely.
  • Readers-Writers: Multiple threads access a database. Multiple Readers can read simultaneously without issue. However, if a Writer is updating data, no other Readers or Writers can access the database at the same time.
  • Dining Philosophers: 5 philosophers sit around a round table with 5 forks. Each philosopher needs two adjacent forks (left and right) to eat. If all 5 grab their left fork simultaneously, everyone waits forever for their right fork—resulting in Deadlock.

3Real-Life Example / Analogy

  • Producer-Consumer: A bakery delivery truck (Producer) filling shelf slots at a grocery store, while customers (Consumers) purchase items off the shelf slots.
  • Readers-Writers: A Wikipedia page where millions of readers can read the article at once, but when an editor submits an update (Writer), the page locks momentarily.
  • Dining Philosophers: Five coders sharing five dual-handed controllers; everyone needs two controllers to start playing.

4Diagram / Visual Representation

Adds item

Removes item

Controls access and availability

Producer thread

Shared bounded buffer
Slot 1 · Slot 2 · … · Slot N

Consumer thread

Semaphores
mutex = 1 · empty = N · fill = 0

Philosopher 1

Fork 1

Philosopher 2

Fork 2

Philosopher 3

Fork 3

Philosopher 4

Fork 4

Philosopher 5

Fork 5

5Working / How It Works

  • Producer-Consumer Pseudocode Solution:
C
Code
// PRODUCER THREAD                       // CONSUMER THREAD
do {                                     do {
    // produce item in next_produced          wait(fill);  // Wait if buffer empty (fill == 0)
    wait(empty); // Wait if buffer full       wait(mutex); // Lock buffer
    wait(mutex); // Lock buffer               // remove item from buffer to next_consumed
    // add item to buffer                     signal(mutex);
    signal(mutex);                            signal(empty); // Increment empty slots
    signal(fill);  // Increment filled slots  // consume item
} while (true);                          } while (true);
  • Dining Philosophers Deadlock Prevention Rules:
    1. Allow at most 4 philosophers to sit at the table simultaneously.
    2. Allow a philosopher to pick up forks only if both left and right forks are available (within an atomic critical section).
    3. Odd-Even Rule: Odd-numbered philosophers pick up their left fork first, then right fork; Even-numbered philosophers pick up their right fork first, then left fork.

6Types / Components / Characteristics

  • Readers-Writers Variables:
    • mutex: Binary semaphore protecting modifications to read_count.
    • wrt: Binary semaphore shared between readers and writers ensuring mutual exclusion for writing.
    • read_count: Integer tracking active reader threads inside critical section.
  • LeetCode Concurrency Problem Benchmarks:
    • FooBar Alternate (printFoo() / printBar()): Synchronized via binary flags and condition variables.
    • Zero-Even-Odd: Coordinates three threads printing 010203... using state turn variables.
    • Building H2O: Coordinates two Hydrogen threads and one Oxygen thread to form water molecules using semaphore counters.

7Solved Examples / Problems

Problem: Write a C++ synchronization method for the FooBar Alternate Problem using std::mutex and std::condition_variable. Solution:

C++
Code
class FooBar {
private:
    int n;
    std::mutex m;
    std::condition_variable cv;
    bool turn = false; // false = Foo's turn, true = Bar's turn
public:
    FooBar(int n) { this->n = n; }
    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            std::unique_lock<std::mutex> lock(m);
            cv.wait(lock, [this]() { return turn == false; });
            printFoo();
            turn = true;
            cv.notify_all();
        }
    }
    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            std::unique_lock<std::mutex> lock(m);
            cv.wait(lock, [this]() { return turn == true; });
            printBar();
            turn = false;
            cv.notify_all();
        }
    }
};

8Advantages, Disadvantages & Applications

  • Advantages: Proves algorithm correctness across race conditions and deadlock scenarios.
  • Disadvantages: Naive semaphore solutions can easily cause deadlocks if resource acquisition orders differ.

9Important Points to Remember

  • In Producer-Consumer: empty starts at NN, fill starts at 00.
  • In Readers-Writers: Multiple readers read concurrently; first reader locks wrt, last reader unlocks wrt.
  • The Odd-Even Rule eliminates circular wait in the Dining Philosophers Problem.

10Test Your Understanding

  1. MCQ: In the Producer-Consumer problem with a buffer of size NN, what are the initial values of the empty and fill counting semaphores?
    • A) empty = 0, fill = N
    • B) empty = N, fill = 0
    • C) empty = 1, fill = 1
    • D) empty = N, fill = N
    Show answer
    B.
  2. Conceptual Question: Explain the Odd-Even Rule protocol used to eliminate deadlocks in the Dining Philosophers problem.
  3. Application Question: Trace how the Readers-Writers semaphore solution ensures that a writer cannot enter while readers are actively reading.

Finished this topic?

0 of 27 topics read in Operating Systems

Handwritten notes for the exam

Unit-wise SPPU notes and PYQs for this subject.

Helpful? Share it with your class

Free for everyone, no login needed.

Share topic