Work in progress…

Original problem: https://leetcode.cn/problems/the-dining-philosophers/description/

Solution reference: https://leetcode.cn/problems/the-dining-philosophers/solutions/2130703/li-shun-xian-cheng-zheng-qiang-xin-hao-l-gzb1/

Five silent philosophers sit at a round table, each with a plate of spaghetti. Forks are placed between philosophers on the table (5 philosophers, 5 forks).

Each philosopher alternates between thinking and eating. A philosopher can only eat when they have picked up both the left and right fork. Each fork can only be used by one philosopher at a time. After eating, the philosopher must put both forks back on the table so others can use them. A philosopher may pick up either fork when available, but cannot eat until holding both.

Assume there is an unlimited supply of spaghetti and philosophers can always eat more.

Design a concurrent algorithm (parallel dining rule) such that no philosopher starves — that is, each philosopher can continuously alternate between eating and thinking without any coordination about the others’ intentions.

Philosophers are numbered 0 to 4 clockwise. Implement the function void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork):

• philosopher: the philosopher’s index.
• pickLeftFork / pickRightFork: pick up the left or right fork.
• eat: eat.
• putLeftFork / putRightFork: put down the left or right fork.
• Since a philosopher is either eating or thinking about eating, there is no callback for the thinking action.

You are given 5 threads, each representing one philosopher. Use the same object instance to simulate the process. The function may be called multiple times for the same philosopher before the last call completes.

Solutions

Background

This problem is fundamentally a deadlock problem in thread synchronization. Common synchronization mechanisms include mutexes, condition variables, and semaphores. Semaphores are used here.

• P-V Semaphores

  The classic approach to deadlock prevention. For a semaphore m, P(m) checks if m is 0 — if so, the caller blocks; otherwise m is decremented by 1 (resource acquired). V(m) increments m by 1 (resource released).

• C++ Semaphore Functions

  sem_init, sem_wait, and sem_post are POSIX semaphore functions available in UNIX/Linux environments (part of the Pthreads library), used for inter-thread or inter-process synchronization.

  1. sem_init — Initialize an unnamed semaphore.

     int sem_init(sem_t *sem, int pshared, unsigned int value);
     

     • sem: pointer to the semaphore.
     • pshared: if non-zero, the semaphore is shared across processes; if zero, it is shared only among threads of the creating process.
     • value: initial value of the semaphore.

  2. sem_wait — Decrement the semaphore (P operation). Blocks if the value is zero.

     int sem_wait(sem_t *sem);
     

  3. sem_post — Increment the semaphore (V operation). May unblock waiting threads.

     int sem_post(sem_t *sem);
     

• std::mutex

  The standard library std::mutex provides a basic mutex mechanism for synchronizing multi-threaded access to shared resources.

  1. lock() — Acquire the lock. Blocks if already held by another thread.
  2. unlock() — Release the lock. Only the thread that locked it may unlock it.
  3. try_lock() — Non-blocking lock attempt. Returns true on success, false if already locked.

Approach

Since the five philosophers act independently, five independent (asynchronous) threads are created, numbered 0–4.

The five forks are treated as five separate critical resources (not a single shared one), since each philosopher can only use the two forks directly in front of them. The fork to the left of philosopher i is numbered i; the fork to the right is numbered (i+1) % 5 (with special handling for philosopher 0).

A critical resource may only be used by one thread at a time, so a fork must be locked when in use.

Strategy 1: Allow at Most Four Philosophers to Pick Up a Fork Simultaneously

Limiting concurrency to four ensures that at least one philosopher can always acquire both forks, eat, and release resources — unblocking others.

while(1){
    think()
    hungry()
    p(room)          // at most 4 philosophers may attempt to pick up a fork
    p(left fork)
    p(right fork)
    eat()
    v(left fork)
    v(right fork)
    v(room)
}

Strategy 2: A Philosopher Must Acquire Both Forks Atomically or Not at All

Uses AND-semaphore semantics: all required resources are granted simultaneously or not at all.

while(1){
    think()
    hungry()
    Swait(left fork, right fork)
    eat()
    Spost(left fork, right fork)
}

This approach has lower concurrency.

Strategy 3: Distinguish Odd and Even Philosophers

Odd-numbered philosophers pick up the left fork first, then the right. Even-numbered philosophers do the opposite. This asymmetry guarantees that at least one philosopher can always acquire both forks.

while(1){
    think(i)
    hungry(i)
    if(i % 2 == 0){
        p(left fork)
        p(right fork)
        eat()
        v(right fork)
        v(left fork)
    }
    else{
        p(right fork)
        p(left fork)
        eat()
        v(left fork)
        v(right fork)
    }
}

C++ Implementation

Strategy 1: At Most Four Philosophers Pick Up a Fork

#include<semaphore.h>
class DiningPhilosophers {
public:
    DiningPhilosophers() {
        fork = vector<sem_t>(5);
        sem_init(&room,0,4);
        for(int i = 0;i < 5;i++){
            sem_init(&(fork[i]),0,1);
        }
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        sem_wait(&room);
        sem_wait(&(fork[philosopher]));
        sem_wait(&(fork[(philosopher+1)%5]));
        pickLeftFork();
        pickRightFork();
        eat();
        putRightFork();
        putLeftFork();
        sem_post(&(fork[(philosopher+1)%5]));
        sem_post(&(fork[philosopher]));
        sem_post(&room);
    }
    vector<sem_t> fork;
    sem_t room;
};

Strategy 2: Atomic Acquisition of Both Forks

#include<semaphore.h>
class DiningPhilosophers {
public:
    DiningPhilosophers() {
        fork = vector<sem_t>(5);
        for(int i = 0;i < 5;i++){
            sem_init(&(fork[i]),0,1);
        }
        sem_init(&mutex,0,1);
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        sem_wait(&mutex);
        sem_wait(&(fork[philosopher]));
        sem_wait(&(fork[(philosopher+1)%5]));
        pickLeftFork();
        pickRightFork();
        sem_post(&mutex);
        eat();
        putRightFork();
        putLeftFork();
        sem_post(&(fork[(philosopher+1)%5]));
        sem_post(&(fork[philosopher]));
    }
    vector<sem_t> fork;
    sem_t mutex;
};

Strategy 3: Odd and Even Philosophers

#include<semaphore.h>
class DiningPhilosophers {
public:
    DiningPhilosophers() {
        fork = vector<sem_t>(5);
        for(int i = 0;i < 5;i++){
            sem_init(&(fork[i]),0,1);
        }
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        if(philosopher % 2 == 0){
            sem_wait(&(fork[philosopher]));
            sem_wait(&(fork[(philosopher+1)%5]));
            pickLeftFork();
            pickRightFork();
            eat();
            putRightFork();
            putLeftFork();
            sem_post(&(fork[(philosopher+1)%5]));
            sem_post(&(fork[philosopher]));
        }
        else{
            sem_wait(&(fork[(philosopher+1)%5]));
            sem_wait(&(fork[philosopher]));
            pickLeftFork();
            pickRightFork();
            eat();
            putRightFork();
            putLeftFork();
            sem_post(&(fork[philosopher]));
            sem_post(&(fork[(philosopher+1)%5]));
        }
    }
    vector<sem_t> fork;
};