Dining Philosopher in OS

Introduction

The Dining Philosophers Problem is a classic synchronization problem in computer science that illustrates challenges in resource allocation and deadlock avoidance. It was formulated by Edsger Dijkstra in 1965.

Problem Statement

• 5 philosophers sit around a circular table.
• Each philosopher alternates between thinking and eating.
• To eat, a philosopher needs two forks (left and right).
• Forks are shared between adjacent philosophers.
• Goal: Design an algorithm to allow philosophers to eat without deadlock/starvation.

Key Challenges

1. Deadlock: All philosophers pick up one fork and wait indefinitely for the other.
2. Starvation: A philosopher never gets access to both forks.
3. Concurrency: Forks are shared resources requiring mutual exclusion.

Solutions to the Problem

1. Resource Hierarchy (Partial Ordering)

Approach

• Assign a global order to forks (e.g., numbered 0–4).
• Philosophers pick up the lower-numbered fork first, then the higher-numbered one.
• Breaks the circular wait condition (prevents deadlock).

Pseudocode

procedure philosopher(i):
    while true:
        think()
        if i < (i+1) % 5:
            pick up fork i
            pick up fork (i+1) % 5
        else:
            pick up fork (i+1) % 5
            pick up fork i
        eat()
        put down forks

Example Table: Fork Acquisition Order

2. Arbitrator (Waiter/Mutex)

Approach

• Introduce a mutex semaphore (waiter) to allow only N−1 philosophers to pick up forks simultaneously.
• Ensures at least one philosopher can always eat.

Pseudocode

semaphore mutex = 4  // Allows 4 philosophers to attempt eating

procedure philosopher(i):
    while true:
        think()
        wait(mutex)
        pick up fork i
        pick up fork (i+1) % 5
        eat()
        put down fork i
        put down fork (i+1) % 5
        signal(mutex)

Example Table: Safe State with Mutex

3. Chandy-Mishra Algorithm (Asymmetric)

Approach

• Forks are requested and released via messages.
• Forks are “dirty” or “clean”:
  • Initially, all forks are dirty.
  • A philosopher cleans a fork before handing it over.

Steps

1. Philosopher requests forks if hungry.
2. If neighbor is not using the fork, send it.
3. If neighbor is using it, wait until it’s cleaned.

Example Table: Fork Transfer

4. Monitor-Based Solution

Approach

• Use a monitor to encapsulate fork states.
• Philosophers request forks through the monitor, which grants access only if both are available.

Pseudocode

monitor DiningPhilosophers:
    enum {THINKING, HUNGRY, EATING} state[5]
    condition self[5]

    procedure pickup(i):
        state[i] = HUNGRY
        test(i)
        if state[i] != EATING:
            self[i].wait()

    procedure putdown(i):
        state[i] = THINKING
        test((i-1) % 5)  // Notify neighbors
        test((i+1) % 5)

    procedure test(i):
        if state[i] == HUNGRY &&
           state[(i-1) % 5] != EATING &&
           state[(i+1) % 5] != EATING:
            state[i] = EATING
            self[i].signal()

Example Code (C/POSIX Semaphores – Mutex Solution)

#include <semaphore.h>
#include <stdio.h>
#include <pthread.h>

#define N 5

sem_t forks[N];
sem_t mutex;

void *philosopher(void *arg) {
    int id = *(int *)arg;
    while (1) {
        printf("Philosopher %d is thinking...\n", id);

        sem_wait(&mutex);
        sem_wait(&forks[id]);
        sem_wait(&forks[(id + 1) % N]);
        sem_post(&mutex);

        printf("Philosopher %d is eating!\n", id);

        sem_post(&forks[id]);
        sem_post(&forks[(id + 1) % N]);
    }
    return NULL;
}

int main() {
    pthread_t threads[N];
    int ids[N];
    sem_init(&mutex, 0, 1);
    for (int i = 0; i < N; i++) sem_init(&forks[i], 0, 1);

    for (int i = 0; i < N; i++) {
        ids[i] = i;
        pthread_create(&threads[i], NULL, philosopher, &ids[i]);
    }

    for (int i = 0; i < N; i++) pthread_join(threads[i], NULL);
    return 0;
}

Analysis of Solutions

Conclusion

The Dining Philosophers Problem highlights the challenges of resource allocation in concurrent systems. Solutions like resource hierarchy and mutex arbitrators prevent deadlock but may not avoid starvation. Advanced methods like Chandy-Mishra or monitors provide fairness at the cost of complexity. The choice depends on system requirements (e.g., real-time vs. general-purpose).