Dining Philosophers Problem

operating-systems concurrency

Definition

Dining Philosophers Problem

The dining philosophers problem is a classic synchronisation exercise designed to illustrate challenges in avoiding deadlock and starvation in concurrent systems.

Five philosophers sit around a circular table. Each philosopher spends their time either thinking or eating. Between each pair of philosophers sits a single fork. To eat, a philosopher must acquire two forks (the ones immediately to their left and right).

Potential Problems

• Deadlock: If every philosopher picks up their left fork simultaneously, no forks will be available on the right, and everyone will wait indefinitely.
• Starvation: A philosopher might never get to eat if their neighbours alternate eating such that at least one fork is always taken.

Solutions

Solution 1: Limiting Concurrency (Counting Semaphore)

Allow at most four philosophers to sit at the table simultaneously using a counting semaphore initialised to 4. This ensures that at least one philosopher will always be able to acquire two forks.

Solution 2: Asymmetric Resource Acquisition

Instruct odd-numbered philosophers to pick up their left fork first, while even-numbered philosophers pick up their right fork first. This breaks the circular wait condition.

Solution 3: M-Semaphores (Atomic Multiple Acquisition)

Use M-Semaphores (Multiple Semaphores) to pick up both forks in a single atomic operation. The wait(S1, S2, ..., Sn) operation on an M-semaphore only proceeds if all listed semaphores are available (greater than 0). If any are unavailable, the process blocks without decompressing any values.

// Example with monitor
monitor DiningPhilosophers
    enum state {THINKING, HUNGRY, EATING}
    state[5] philosopher_state;
    condition[5] self;
 
    procedure pickup(i)
        philosopher_state[i] := HUNGRY;
        test(i);
        if philosopher_state[i] != EATING then cwait(self[i]);
 
    procedure putdown(i)
        philosopher_state[i] := THINKING;
        test((i+4) mod 5); // Check left neighbour
        test((i+1) mod 5); // Check right neighbour
 
    procedure test(i)
        if (philosopher_state[(i+4) mod 5] != EATING and
            philosopher_state[i] == HUNGRY and
            philosopher_state[(i+1) mod 5] != EATING) then
                philosopher_state[i] := EATING;
                csignal(self[i]);