Dining Philosophers Problem

The Dining Philosophers Problem

The Dining Philosophers Problem is a classic synchronization problem in computer science that illustrates challenges in resource allocation and deadlock prevention.

Problem Statement

Five philosophers sit at a round table, alternating between thinking and eating. Between each adjacent pair of philosophers is a single fork. To eat, a philosopher needs both the fork to their left and the fork to their right. The challenge is to design a concurrent algorithm that allows philosophers to eat without causing deadlocks.

Possible Issues

• Deadlock: If all philosophers pick up their left fork simultaneously, none can pick up their right fork, resulting in a deadlock.
• Starvation: Some philosophers might never get to eat if neighbors continuously grab forks.
• Resource contention: Multiple philosophers compete for shared resources (forks).

The Solution Implemented

This simulation uses a resource hierarchy solution with deadlock detection and resolution:

• Philosophers cycle between thinking, hungry, and eating states.
• A philosopher can only eat when both adjacent forks are available.
• When done eating, they release both forks and return to thinking.
• The simulation detects deadlocks (all philosophers hungry but unable to eat).
• When deadlock occurs, it's resolved by having a random philosopher release their fork.

Pseudocode for the Algorithm

function initialize():
    For each philosopher i (0 to NUM_PHILOSOPHERS-1):
        Set state[i] = "thinking"
    For each fork i (0 to NUM_PHILOSOPHERS-1):
        Set forks[i] = false (available)

function leftFork(i):
    return i

function rightFork(i):
    return (i + 1) % NUM_PHILOSOPHERS

function tryToEat(i):
    if state[i] == "hungry" AND
       forks[leftFork(i)] == false AND
       forks[rightFork(i)] == false then:
        
        // Take both forks
        forks[leftFork(i)] = true
        forks[rightFork(i)] = true
        state[i] = "eating"
        log("Philosopher " + i + " starts eating")
        
        // Schedule release of forks after eating
        setTimeout(() => {
            forks[leftFork(i)] = false
            forks[rightFork(i)] = false
            state[i] = "thinking"
            log("Philosopher " + i + " finished eating")
        }, eatingTime)

function philosopherCycle(i):
    if state[i] == "thinking" then:
        // Randomly become hungry
        if random() < 0.3 then:
            state[i] = "hungry"
            log("Philosopher " + i + " is hungry")
    else if state[i] == "hungry" then:
        tryToEat(i)

function checkForDeadlock():
    allHungry = true
    for each philosopher i:
        if state[i] != "hungry" OR
           (forks[leftFork(i)] == false AND 
            forks[rightFork(i)] == false) then:
            allHungry = false
            break
    
    if allHungry AND at least 2 philosophers are hungry then:
        // Deadlock detected!
        randomPhil = random philosopher
        if forks[leftFork(randomPhil)] == true then:
            forks[leftFork(randomPhil)] = false
        else if forks[rightFork(randomPhil)] == true then:
            forks[rightFork(randomPhil)] = false
        log("Deadlock resolved")

function startSimulation():
    For each philosopher i:
        Schedule philosopherCycle(i) to run periodically
        Periodically check for deadlocks