dining philosophers problem - TarisMajor/5143-OpSystems GitHub Wiki

The Dining Philosophers Problem is a classic synchronization problem in computer science that illustrates the challenges of resource allocation and deadlock prevention in a concurrent system. The problem was introduced by Edsger Dijkstra in 1965 and involves a scenario where philosophers sit at a table with a fork placed between each pair of philosophers. The goal is to ensure that each philosopher can eat without causing a deadlock or resource contention.

1. Philosophers and Forks: The problem involves a number of philosophers (typically five) sitting at a circular table, with a fork placed between each pair of philosophers. Each philosopher needs both forks adjacent to them to eat.
2. States of Philosophers: Philosophers alternate between thinking and eating. They think for some time, then attempt to pick up both forks to eat. After eating, they put down the forks and resume thinking.
3. Resource Allocation: The problem requires careful allocation of resources (forks) to prevent deadlocks and ensure all philosophers get a chance to eat.

1. Deadlock: A deadlock can occur if each philosopher picks up one fork and waits indefinitely for the other fork, resulting in a situation where no philosopher can eat.
2. Starvation: A philosopher may starve if they are repeatedly unable to acquire both forks, while other philosophers continue to eat.
3. Concurrency Control: Proper synchronization is required to ensure that philosophers can pick up and put down forks without causing race conditions or deadlocks.

1. Using Semaphores: Semaphores can be used to control access to the forks, ensuring mutual exclusion and preventing deadlocks.

   Pseudocode:

   // Shared semaphore initialization
   Semaphore forks[5];
   
   // Philosopher process
   void philosopher(int i) {
       while (true) {
           think(); // Thinking
           wait(forks[i]); // Pick up left fork
           wait(forks[(i+1) % 5]); // Pick up right fork
           eat(); // Eating
           signal(forks[i]); // Put down left fork
           signal(forks[(i+1) % 5]); // Put down right fork
       }
   }

   This solution may lead to deadlock if all philosophers pick up their left fork simultaneously.

2. Preventing Deadlock with Ordered Fork Pickup: One approach to prevent deadlock is to impose an ordering on the resources and require philosophers to pick up the forks in a specified order.

   Pseudocode:

   // Philosopher process with ordered fork pickup
   void philosopher(int i) {
       while (true) {
           think(); // Thinking
           if (i % 2 == 0) {
               wait(forks[i]); // Pick up left fork first
               wait(forks[(i+1) % 5]); // Then right fork
           } else {
               wait(forks[(i+1) % 5]); // Pick up right fork first
               wait(forks[i]); // Then left fork
           }
           eat(); // Eating
           signal(forks[i]); // Put down left fork
           signal(forks[(i+1) % 5]); // Put down right fork
       }
   }

   This approach ensures that deadlock does not occur by preventing circular wait.

3. Using Monitors: Monitors provide a higher-level abstraction for synchronization by encapsulating the shared resources and synchronization mechanisms.

   Pseudocode:

   class DiningPhilosophers {
       private final Condition[] forks;
       private final boolean[] forkAvailable;
       private final Lock lock = new ReentrantLock();
   
       public DiningPhilosophers(int numPhilosophers) {
           forks = new Condition[numPhilosophers];
           forkAvailable = new boolean[numPhilosophers];
           for (int i = 0; i < numPhilosophers; i++) {
               forks[i] = lock.newCondition();
               forkAvailable[i] = true;
           }
       }
   
       public void pickUpForks(int i) throws InterruptedException {
           lock.lock();
           try {
               while (!forkAvailable[i] || !forkAvailable[(i+1) % numPhilosophers]) {
                   forks[i].await();
               }
               forkAvailable[i] = false;
               forkAvailable[(i+1) % numPhilosophers] = false;
           } finally {
               lock.unlock();
           }
       }
   
       public void putDownForks(int i) {
           lock.lock();
           try {
               forkAvailable[i] = true;
               forkAvailable[(i+1) % numPhilosophers] = true;
               forks[i].signalAll();
               forks[(i+1) % numPhilosophers].signalAll();
           } finally {
               lock.unlock();
           }
       }
   }
   
   // Philosopher process
   void philosopher(int i, DiningPhilosophers dp) throws InterruptedException {
       while (true) {
           think(); // Thinking
           dp.pickUpForks(i); // Pick up forks
           eat(); // Eating
           dp.putDownForks(i); // Put down forks
       }
   }

   In this example, the DiningPhilosophers class uses condition variables and a lock to synchronize access to the forks, ensuring mutual exclusion and preventing deadlocks.

• Operating System Concepts by Abraham Silberschatz, Peter B. Galvin, and Greg Gagne
• Dining Philosophers Problem - GeeksforGeeks
• Modern Operating Systems by Andrew S. Tanenbaum
• Wikipedia - Dining Philosophers Problem
• ChatGPT