Simulating the Dining Philosophers Problem and Solving Deadlocks

Welcome to another chapter in your concurrency journey! This lesson covers the fascinating Dining Philosophers Problem, a classic concurrency illustration. In our previous lesson, we tackled the Producer-Consumer problem, managing concurrent access to shared resources. Now, we'll focus on handling multiple threads competing for resources in a circular arrangement. This lesson builds upon previous concepts and enhances your ability to prevent deadlocks in complex systems.

In this lesson, you will understand and solve the Dining Philosophers Problem and how to prevent deadlocks in multithreaded applications.

Let's break down the key concepts you'll explore:

1. Dining Philosophers Problem: Understand the problem statement and its real-world implications.
2. Deadlocks: Learn about deadlocks and how they occur in multithreaded applications.
3. Solving Deadlocks: Explore strategies to prevent deadlocks and ensure system stability.

Imagine a group of philosophers sitting around a circular table, each with a plate of spaghetti and a fork between them. The philosophers alternate between thinking and eating, using two forks to consume their meal. However, there's a catch: the philosophers can only eat when they have both forks. This constraint leads to a potential deadlock scenario if each philosopher picks up one fork and waits indefinitely for the other.

The Dining Philosophers Problem is a classic synchronization problem that illustrates the challenges of resource sharing and deadlock prevention in concurrent systems. It highlights the need for careful resource allocation and synchronization to avoid deadlocks and ensure system stability.

Let's simulate the Dining Philosophers Problem and explore strategies to prevent deadlocks in multithreaded applications using C++:

class Philosopher {
public:
    Philosopher(int id, std::mutex* leftFork, std::mutex* rightFork, std::mutex* coutMutex)
        : id_(id), leftFork_(leftFork), rightFork_(rightFork), coutMutex_(coutMutex) {}

    void dine() {
        for (int i = 0; i < 10; ++i) {
            think();
            eat();
        }
    }

private:
    void think() {
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }

    void eat() {
        std::unique_lock<std::mutex> lockLeft(*leftFork_, std::defer_lock);
        std::unique_lock<std::mutex> lockRight(*rightFork_, std::defer_lock);

        // Try to lock both forks, prevent deadlock by retrying if unsuccessful
        std::lock(lockLeft, lockRight);

        {
            std::lock_guard<std::mutex> lock(*coutMutex_);
            std::cout << "Philosopher " << id_ << " is eating." << std::endl;
        }
        std::this_thread::sleep_for(std::chrono::milliseconds(100));

        {
            std::lock_guard<std::mutex> lock(*coutMutex_);
            std::cout << "Philosopher " << id_ << " finished eating. Thinking..." << std::endl;
        }
    }

    int id_;
    std::mutex* leftFork_;
    std::mutex* rightFork_;
    std::mutex* coutMutex_;
};

Let's understand the code snippet above:

• The Philosopher class represents a philosopher thread that thinks and eats.
• The dine method simulates the philosopher's routine of thinking and eating.
• The think method pauses the philosopher for a while to simulate thinking.
• The eat method acquires locks on both forks using std::lock and std::unique_lock to prevent deadlocks.
  • We use std::defer_lock to defer locking until both forks are acquired.
  • The std::lock function ensures that both forks are locked simultaneously to prevent deadlocks.
  • The std::lock_guard ensures that the philosopher releases the forks after eating.
  • The coutMutex_ ensures that output is synchronized to prevent interleaved messages.

The code snippet above illustrates how a philosopher tries to acquire locks on two forks using std::lock to prevent deadlocks and std::unique_lock for flexibility. The philosophical journey of thinking and eating is safeguarded by acquiring these locks wisely.

Now, let's see how we can use this in the main function to simulate the dining philosophers problem:

int main() {
    const int numPhilosophers = 5;
    std::vector<std::mutex> forks(numPhilosophers);
    std::vector<std::thread> philosophers;
    std::mutex coutMutex;

    for (int i = 0; i < numPhilosophers; ++i) {
        std::mutex* leftFork = &forks[i];
        std::mutex* rightFork = &forks[(i + 1) % numPhilosophers];
        philosophers.emplace_back(&Philosopher::dine, Philosopher(i, leftFork, rightFork, &coutMutex));
    }

    for (auto& philosopher : philosophers) {
        philosopher.join();
    }

    return 0;
}

In the main function:

• We create a vector of mutexes representing the forks on the table.
• We create a vector of philosopher threads, each with a left and right fork.
• We use the emplace_back function to create philosopher threads and call the dine method.
• We ensure that each philosopher has a unique left and right fork to prevent deadlocks.
• Finally, we join all philosopher threads to synchronize their dining experience.