Code Implementation

from threading import Semaphore

class DiningPhilosophers:
    def __init__(self):
        # 5 forks, each is a semaphore (binary lock)
        self.forks = [Semaphore(1) for _ in range(5)]

    def wantsToEat(self, philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork):
        left = philosopher
        right = (philosopher + 1) % 5

        # To prevent deadlock, odd philosophers pick right fork first
        if philosopher % 2 == 0:
            self.forks[left].acquire()
            self.forks[right].acquire()
        else:
            self.forks[right].acquire()
            self.forks[left].acquire()
        
        pickLeftFork()
        pickRightFork()
        eat()
        putLeftFork()
        putRightFork()

        self.forks[left].release()
        self.forks[right].release()
      

#include <mutex>
#include <vector>

class DiningPhilosophers {
private:
    std::vector<std::mutex> forks;
public:
    DiningPhilosophers() : forks(5) {}

    void wantsToEat(int philosopher,
                    std::function<void()> pickLeftFork,
                    std::function<void()> pickRightFork,
                    std::function<void()> eat,
                    std::function<void()> putLeftFork,
                    std::function<void()> putRightFork) {

        int left = philosopher;
        int right = (philosopher + 1) % 5;

        if (philosopher % 2 == 0) {
            forks[left].lock();
            forks[right].lock();
        } else {
            forks[right].lock();
            forks[left].lock();
        }

        pickLeftFork();
        pickRightFork();
        eat();
        putLeftFork();
        putRightFork();

        forks[left].unlock();
        forks[right].unlock();
    }
};
      

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

class DiningPhilosophers {
    private final Lock[] forks = new Lock[5];

    public DiningPhilosophers() {
        for (int i = 0; i < 5; ++i) {
            forks[i] = new ReentrantLock();
        }
    }

    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {

        int left = philosopher;
        int right = (philosopher + 1) % 5;

        if (philosopher % 2 == 0) {
            forks[left].lock();
            forks[right].lock();
        } else {
            forks[right].lock();
            forks[left].lock();
        }

        pickLeftFork.run();
        pickRightFork.run();
        eat.run();
        putLeftFork.run();
        putRightFork.run();

        forks[left].unlock();
        forks[right].unlock();
    }
}
      

class Semaphore {
    constructor(count) {
        this.count = count;
        this.waiters = [];
    }
    acquire() {
        return new Promise(resolve => {
            if (this.count > 0) {
                this.count--;
                resolve();
            } else {
                this.waiters.push(resolve);
            }
        });
    }
    release() {
        if (this.waiters.length > 0) {
            const resolve = this.waiters.shift();
            resolve();
        } else {
            this.count++;
        }
    }
}

class DiningPhilosophers {
    constructor() {
        this.forks = Array.from({length: 5}, () => new Semaphore(1));
    }

    async wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) {
        const left = philosopher;
        const right = (philosopher + 1) % 5;

        // Odd philosophers pick up right fork first
        if (philosopher % 2 === 0) {
            await this.forks[left].acquire();
            await this.forks[right].acquire();
        } else {
            await this.forks[right].acquire();
            await this.forks[left].acquire();
        }

        await pickLeftFork();
        await pickRightFork();
        await eat();
        await putLeftFork();
        await putRightFork();

        this.forks[left].release();
        this.forks[right].release();
    }
}
      

Problem Description

The Dining Philosophers problem is a classic concurrency challenge. There are five philosophers sitting around a round table. Each philosopher alternates between thinking and eating. To eat, a philosopher needs to pick up two forks: the one on their left and the one on their right. There are five forks placed between the philosophers, one between each pair. Only one philosopher can hold a fork at a time.

You are to implement a class DiningPhilosophers that provides a method wantsToEat. This method is called by each philosopher when they want to eat and is passed five functions: pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork. The method must ensure that:

• No two philosophers can use the same fork at the same time.
• No philosopher will starve (i.e., the solution avoids deadlock and starvation).

Thought Process

At first glance, it seems straightforward: each philosopher just picks up their left and right forks before eating. However, if all philosophers pick up their left fork at the same time, none will be able to pick up their right fork, and all will wait forever—this is a classic deadlock.

To avoid deadlock, we need to ensure that not all philosophers are waiting for resources held by others. There are several ways to break this cycle:

• Introduce an ordering in picking up forks (e.g., odd philosophers pick up right fork first, even pick up left first).
• Limit the number of philosophers who can try to eat at the same time.
• Use locks (mutexes or semaphores) to control access to forks.

Solution Approach

The solution uses an array of locks (or semaphores), one for each fork. Before eating, a philosopher must acquire (lock) both the left and right forks. To avoid deadlock, we introduce an ordering: philosophers with even numbers pick up the left fork first, then the right; odd-numbered philosophers pick up the right fork first, then the left.

1. Fork Representation: Each fork is represented by a lock (mutex or semaphore) to ensure mutual exclusion.
2. Acquiring Forks: When a philosopher wants to eat, they attempt to acquire both their left and right fork locks. The order of acquisition depends on whether the philosopher's number is even or odd.
3. Executing Actions: After acquiring both forks, the philosopher performs the five actions in order: pick up left fork, pick up right fork, eat, put down left fork, put down right fork.
4. Releasing Forks: After eating, the philosopher releases (unlocks) both forks so others may use them.
5. Deadlock Prevention: By alternating the order in which forks are picked up based on philosopher number, we avoid the scenario where all philosophers are waiting on each other, thus preventing deadlock.

This approach is simple, avoids deadlock, and ensures that all philosophers will eventually be able to eat.

Example Walkthrough

Let's walk through an example with five philosophers (numbered 0 to 4).

1. Philosopher 0 (even) tries to eat: picks up fork 0 (left), then fork 1 (right).
2. Philosopher 1 (odd) tries to eat: picks up fork 2 (right), then fork 1 (left). If fork 1 is held by philosopher 0, philosopher 1 waits.
3. Philosopher 2 (even) tries to eat: picks up fork 2 (left), then fork 3 (right). If fork 2 is held by philosopher 1, philosopher 2 waits.
4. Philosopher 3 (odd) tries to eat: picks up fork 4 (right), then fork 3 (left).
5. Philosopher 4 (even) tries to eat: picks up fork 4 (left), then fork 0 (right).

Because the order of fork acquisition alternates, at least some philosophers will be able to acquire both forks and eat, preventing a deadlock. Once a philosopher finishes eating and releases the forks, waiting philosophers can proceed.

Time and Space Complexity

Brute-force approach:

• If philosophers try to pick up both forks without any ordering or synchronization, the system can deadlock, making time and space complexity irrelevant since progress halts.

• Time Complexity: Each philosopher's wantsToEat call acquires and releases two locks, each operation being O(1). Thus, per call, the time is O(1) plus the time spent waiting for forks (which depends on contention but not on the number of philosophers).
• Space Complexity: We use an array of 5 locks, so the space is O(1).

The solution scales efficiently as the number of philosophers and forks is fixed (5), and the locking mechanism ensures constant-time operations for each eating attempt.

Summary

The Dining Philosophers problem demonstrates the challenges of resource sharing in concurrent systems. By using an array of locks (one per fork) and alternating the order in which forks are picked up based on philosopher number, we elegantly prevent deadlock and ensure fairness. This approach is simple, efficient, and easy to reason about, making it a classic solution to a fundamental concurrency problem.