🍽️ Producer-Consumer Problem (Multithreading)

🧠 Problem Statement

A classic synchronization problem where:

• 👨‍🏭 A Producer creates data and adds it to a shared buffer
• 🧑‍🔧 A Consumer takes data from the buffer to process
• 📦 The buffer has a fixed capacity, requiring proper coordination

❗ Constraints

1. Buffer Capacity: Buffer has a fixed maximum size that cannot be exceeded
2. Thread Safety: Must handle concurrent access from producer and consumer threads
3. No Busy Waiting: Threads should not consume CPU while waiting
4. Proper Coordination: Producer must wait when buffer is full, consumer must wait when buffer is empty
5. Data Integrity: No data should be lost or duplicated
6. Fair Access: Both producer and consumer should get reasonable access to the buffer

📥 Input / Output

Input:

• Producer threads generating data items
• Consumer threads requesting data items
• Shared buffer with limited capacity

Output:

• Controlled data flow through the buffer
• Threads properly synchronized without race conditions
• Efficient resource utilization

💡 Intuition About Solving This Problem

The key insight is that we need a shared buffer that both producer and consumer can access safely. The producer should wait when the buffer is full, and the consumer should wait when the buffer is empty. We use synchronization primitives like wait() and notify() or Condition variables to coordinate between threads efficiently.

🚀 Steps to Take to Solve

1. Design the shared buffer: Create a thread-safe data structure with capacity limits
2. Implement producer logic: Add items when space is available, wait when full
3. Implement consumer logic: Remove items when available, wait when empty
4. Add synchronization: Use locks and condition variables for thread coordination
5. Handle waiting: Implement proper wait/notify mechanisms
6. Manage thread lifecycle: Handle thread interruption and shutdown

⚠️ Edge Cases to Consider

1. Buffer overflow: Handle when producer tries to add to full buffer
2. Buffer underflow: Handle when consumer tries to remove from empty buffer
3. Thread interruption: Handle InterruptedException properly
4. Spurious wakeups: Use while loops to check conditions after waking up
5. Multiple producers/consumers: Handle scenarios with more than one of each
6. Shutdown coordination: Properly terminate all threads

💻 Code (with comments)

Solution 1: Using wait() and notify()

import java.util.LinkedList;
import java.util.Queue;

class SharedBuffer {
    private Queue<Integer> queue = new LinkedList<>();
    private int capacity;

    public SharedBuffer(int capacity) {
        this.capacity = capacity;
    }

    public synchronized void produce(int item) throws InterruptedException {
        // Wait until there's space in the buffer
        while (queue.size() == capacity) {
            System.out.println("Buffer is full! Producer is waiting...");
            wait();
        }
        queue.add(item);
        System.out.println("Produced: " + item);
        notify(); // Notify waiting consumer
    }

    public synchronized int consume() throws InterruptedException {
        // Wait until there's data in the buffer
        while (queue.isEmpty()) {
            System.out.println("Buffer is empty! Consumer is waiting...");
            wait();
        }
        int item = queue.poll();
        System.out.println("Consumed: " + item);
        notify(); // Notify waiting producer
        return item;
    }
}

Producer & Consumer Threads

class Producer extends Thread {
    private SharedBuffer buffer;

    public Producer(SharedBuffer buffer) {
        this.buffer = buffer;
    }

    public void run() {
        int item = 1;
        while (true) {
            try {
                buffer.produce(item++);
                Thread.sleep(1000); // Simulate production time
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

class Consumer extends Thread {
    private SharedBuffer buffer;

    public Consumer(SharedBuffer buffer) {
        this.buffer = buffer;
    }

    public void run() {
        while (true) {
            try {
                buffer.consume();
                Thread.sleep(2000); // Simulate consumption time
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

Main Method

public class ProducerConsumerExample {
    public static void main(String[] args) {
        SharedBuffer buffer = new SharedBuffer(5);
        new Producer(buffer).start();
        new Consumer(buffer).start();
    }
}

Solution 2: Using ReentrantLock and Condition

import java.util.LinkedList;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

class ProducerUsingLock implements Runnable {
    private final LinkedList<Integer> queue;
    private final int capacity;
    private final Lock lock;
    private final Condition notFull;
    private final Condition notEmpty;

    public ProducerUsingLock(LinkedList<Integer> queue, int capacity, Lock lock, Condition notFull, Condition notEmpty) {
        this.queue = queue;
        this.capacity = capacity;
        this.lock = lock;
        this.notFull = notFull;
        this.notEmpty = notEmpty;
    }

    @Override
    public void run() {
        int item = 0;
        try {
            while (true) {
                lock.lock();
                try {
                    // Wait until there's space in the buffer
                    while (queue.size() == capacity) {
                        notFull.await();
                    }

                    queue.add(item);
                    System.out.println("Produced: " + item++);
                    notEmpty.signal(); // Signal waiting consumer
                } finally {
                    lock.unlock();
                }
                Thread.sleep(1000);
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

class ConsumerUsingLock implements Runnable {
    private final LinkedList<Integer> queue;
    private final Lock lock;
    private final Condition notFull;
    private final Condition notEmpty;

    public ConsumerUsingLock(LinkedList<Integer> queue, Lock lock, Condition notFull, Condition notEmpty) {
        this.queue = queue;
        this.lock = lock;
        this.notFull = notFull;
        this.notEmpty = notEmpty;
    }

    @Override
    public void run() {
        try {
            while (true) {
                lock.lock();
                try {
                    // Wait until there's data in the buffer
                    while (queue.isEmpty()) {
                        notEmpty.await();
                    }

                    int item = queue.removeFirst();
                    System.out.println("Consumed: " + item);
                    notFull.signal(); // Signal waiting producer
                } finally {
                    lock.unlock();
                }
                Thread.sleep(2000);
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

Main Method for Lock-based Solution

public class ReentrantLockProducerConsumer {
    public static void main(String[] args) {
        LinkedList<Integer> queue = new LinkedList<>();
        int capacity = 5;
        Lock lock = new ReentrantLock();
        Condition notFull = lock.newCondition();
        Condition notEmpty = lock.newCondition();

        new Thread(new ProducerUsingLock(queue, capacity, lock, notFull, notEmpty)).start();
        new Thread(new ConsumerUsingLock(queue, lock, notFull, notEmpty)).start();
    }
}

🔍 Dry Run Example

Scenario: Buffer capacity 3, 1 producer, 1 consumer

Initial State:

• Buffer: [] (empty)
• Producer: ready to produce
• Consumer: waiting for data

Step 1: Producer produces item 1

• Check: buffer.size() < capacity → true (0 < 3)
• Add item 1 to buffer
• Buffer: [1]
• Notify consumer
• Consumer wakes up and consumes item 1
• Buffer: []

Step 2: Producer produces item 2

• Check: buffer.size() < capacity → true (0 < 3)
• Add item 2 to buffer
• Buffer: [2]
• Notify consumer
• Consumer consumes item 2
• Buffer: []

Step 3: Producer produces items 3, 4, 5

• Buffer: [3, 4, 5] (at capacity)
• Producer tries to produce item 6
• Check: buffer.size() < capacity → false (3 >= 3)
• Producer waits

Step 4: Consumer consumes item 3

• Buffer: [4, 5]
• Notify producer
• Producer wakes up and produces item 6
• Buffer: [4, 5, 6]

Result: Producer and consumer coordinate properly, buffer never exceeds capacity.

⏱️ Time Complexity / Space Complexity

Time Complexity:

• Production: O(1) - constant time to add item to buffer
• Consumption: O(1) - constant time to remove item from buffer
• Waiting: O(1) - constant time to block/unblock threads

Space Complexity:

• Buffer storage: O(n) where n is the buffer capacity
• Thread overhead: O(1) - constant space for producer and consumer threads
• Lock overhead: O(1) - constant space for synchronization objects

---

🚧 Challenges

• 🧵 Race conditions between threads
• 🔄 Avoiding busy waiting (inefficient CPU usage)
• ✅ Ensuring thread-safe access to the buffer

💡 wait() and notify() must be used inside synchronized blocks!

---

🧠 Key Concepts

• 🛑 Producer waits when buffer full
• ❗ Consumer waits when buffer empty
• 🔁 notify() wakes a waiting thread

---

🆚 notify() vs notifyAll()

• notify(): Wakes one waiting thread (could be producer or consumer)
• notifyAll(): Wakes all threads
• 🔄 Use notifyAll() for complex conditions or multiple consumers/producers

---

📌 Summary

Feature	wait/notify	ReentrantLock & Condition
Simplicity	✅ Easy to learn	❗ Slightly complex
Flexibility	❌ Less control	✅ Fine-grained control
Performance	✅ Efficient	✅ Efficient
Best Use Case	Simple scenarios	Complex coordination

---

🧪 Sample Output

Produced: 1
Produced: 2
Consumed: 1
Produced: 3
Consumed: 2
...

---

📚 Interview Tip

Be ready to explain:

• Why buffer coordination matters
• Difference between intrinsic locks (synchronized) vs ReentrantLock
• When to use notifyAll() instead of notify()