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
5Working / How It Works
- Producer-Consumer Pseudocode Solution:
// 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:
- Allow at most 4 philosophers to sit at the table simultaneously.
- Allow a philosopher to pick up forks only if both left and right forks are available (within an atomic critical section).
- 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 toread_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.
- FooBar Alternate (
7Solved Examples / Problems
Problem: Write a C++ synchronization method for the FooBar Alternate Problem using std::mutex and std::condition_variable.
Solution:
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:
emptystarts at ,fillstarts at . - In Readers-Writers: Multiple readers read concurrently; first reader locks
wrt, last reader unlockswrt. - The Odd-Even Rule eliminates circular wait in the Dining Philosophers Problem.
10Test Your Understanding
- MCQ: In the Producer-Consumer problem with a buffer of size , what are the initial values of the
emptyandfillcounting semaphores?- A)
empty = 0,fill = N - B)
empty = N,fill = 0 - C)
empty = 1,fill = 1 - D)
empty = N,fill = N
Show answer
B. - A)
- Conceptual Question: Explain the Odd-Even Rule protocol used to eliminate deadlocks in the Dining Philosophers problem.
- Application Question: Trace how the Readers-Writers semaphore solution ensures that a writer cannot enter while readers are actively reading.
