The Dining Philosophers problem is a classic synchronization problem that demonstrates the challenges of avoiding deadlock while managing shared resources.

In this problem, five philosophers sit around a table and do two things: think and eat. However, they need two forks to eat, and there are only five forks placed between them. The challenge is to design a protocol that allows the philosophers to eat without ever starving (each can eventually eat) and without causing a deadlock.

DiningPhilosophers.java

import java.util.concurrent.Semaphore;
 
public class DiningPhilosophers {
    // Number of philosophers
    private static final int NUM_PHILOSOPHERS = 5;
 
    static class Philosopher implements Runnable {
        private final int id;
        private final Semaphore leftFork;
        private final Semaphore rightFork;
 
        public Philosopher(int id, Semaphore leftFork, Semaphore rightFork) {
            this.id = id;
            this.leftFork = leftFork;
            this.rightFork = rightFork;
        }
 
        @Override
        public void run() {
            try {
                while (true) {
                    think();
                    pickUpForks();
                    eat();
                    putDownForks();
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
 
        private void think() throws InterruptedException {
            System.out.println("Philosopher " + id + " is thinking.");
            Thread.sleep((long) (Math.random() * 1000));
        }
 
        private void eat() throws InterruptedException {
            System.out.println("Philosopher " + id + " is eating.");
            Thread.sleep((long) (Math.random() * 1000));
        }
 
        private void pickUpForks() throws InterruptedException {
            leftFork.acquire();
            rightFork.acquire();
        }
 
        private void putDownForks() {
            leftFork.release();
            rightFork.release();
        }
    }
 
    public static void main(String[] args) {
        Semaphore[] forks = new Semaphore[NUM_PHILOSOPHERS];
        for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
            forks[i] = new Semaphore(1);
        }
 
        Philosopher[] philosophers = new Philosopher[NUM_PHILOSOPHERS];
        for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
            Semaphore leftFork = forks[i];
            Semaphore rightFork = forks[(i + 1) % NUM_PHILOSOPHERS];
            philosophers[i] = new Philosopher(i, leftFork, rightFork);
            new Thread(philosophers[i], "Philosopher " + i).start();
        }
    }
}

Philosopher Class: Represents a philosopher who alternates between thinking and eating. Each philosopher needs access to two forks (left and right) to eat.

Semaphore for Forks: Each fork is represented by a Semaphore. The semaphore ensures that only one philosopher can hold a fork at a time.

pickUpForks and putDownForks Methods: Philosophers pick up the left and right forks before eating and release them after eating. The acquire method on the semaphore is used to pick up a fork, and release is used to put it down.

Avoiding Deadlock: To avoid deadlock, the problem can be addressed by ensuring that one of the philosophers picks up the right fork first, while others pick up the left fork first. This breaks the circular wait condition.

Main Method: Initializes an array of Semaphore objects to represent.

In summary, the implementation of the Dining Philosophers problem in Java using semaphores is a classic example of managing concurrent access to shared resources in a multi-threaded environment.

By using semaphores to represent forks, the program ensures mutual exclusion, preventing more than one philosopher from holding the same fork at a time.

The key to avoiding deadlock in this scenario is to break the circular wait condition, typically by varying the order in which philosophers pick up and put down forks. This problem and its solution are valuable for understanding the complexities and strategies of thread synchronization in concurrent programming.