C++: std::mutex + std::conditional_variable
IntuitionThe Dining Philosophers problem is a classical synchronization challenge that illustrates the need to avoid deadlocks when multiple threads (philosophe
# Intuition
The Dining Philosophers problem is a classical synchronization challenge that illustrates the need to avoid deadlocks when multiple threads (philosophers) compete for limited shared resources (forks).

Each philosopher needs two forks to eat: the one on their left and the one on their right. To avoid deadlock, we ensure that a philosopher only proceeds when both forks are available. By using a shared std::mutex and a std::condition_variable, we coordinate access to the forks so that only one philosopher can pick up any shared fork at a time.

# Approach
* Maintain a shared forks array (std::vector<bool>) of size 5, where false indicates the fork is available and true means it's currently in use.
* Use a single std::mutex to guard access to the forks array.
* When a philosopher wants to eat:
    * Acquire the lock.
    * Wait on the condition variable until both their left and right forks are available.
    * Mark both forks as used and proceed to pick them up.
    * Eat.
    * Release both forks and notify all waiting threads via **cv.notify_all()**.

#### This ensures that:
* A philosopher can only proceed when it's safe to do so.
* Deadlock is avoided by always acquiring forks under a global lock with proper waiting.
* Fairness is reasonably maintained via notify_all().

# Complexity
- Time complexity: $$O(n)$$ due to **notify_all()**

- Space complexity: $$O(n)$$ forks vector.

# Code
```cpp []
class DiningPhilosophers {
    const int n{5};
    std::vector<bool> forks;

    std::mutex mx;
    std::condition_variable cv;

public:
    DiningPhilosophers() : forks(n, false) {
        
    }

    void wantsToEat(int id,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork)
    {
        std::unique_lock<std::mutex> lock{mx};
        cv.wait(lock, [&] { return forks[id] == false && forks[(id + 1) % n] == false; });
        forks[id] = forks[(id + 1) % n] = true;
        
        pickLeftFork(); pickRightFork();
        eat();
        putLeftFork(); putRightFork();

        forks[id] = forks[(id + 1) % n] = false;
        cv.notify_all();
    }
};
```
['C++']