What is Dining Philosopher’s problem ?

The Dining Philosophers Problem is a classic synchronization problem often used in computer science to illustrate the challenges of resource allocation and concurrent programming. The problem is formulated as follows:

There are N philosophers sitting around a circular dining table. Each philosopher spends their time thinking and eating. There is one chopstick between each pair of adjacent philosophers, and a philosopher needs two chopsticks to eat. The challenge is to design a scheme for the philosophers to pick up and put down chopsticks in a way that prevents deadlock (where no philosopher can proceed because they are all waiting for a chopstick held by another) and avoids starvation (where a philosopher may never get to eat).
Several strategies exist to solve the Dining Philosophers problem, including using different algorithms like the resource hierarchy solution, the arbitrator or waiter solution, or using techniques like deadlock avoidance or prevention. Each solution aims to ensure that ilosopher’s can eat without getting into deadlock or starving while maintaining concurrency.

Main challenges in dinning philosopher

The main challenge in the Dining Philosophers problem is to design a solution that prevents deadlock, starvation, and ensures fair resource allocation. Deadlock can occur when each philosopher picks up one chopstick and waits indefinitely for the other one, effectively blocking each other. Starvation can occur if a philosopher is unable to acquire both chopsticks while others keep acquiring and releasing chopsticks in a manner that prevents the starving philosopher from ever eating.

Dining Philosopher’s problem include

Deadlock: This occurs when each philosopher picks up one chopstick and waits indefinitely for the other chopstick, leading to a situation where no philosopher can proceed with eating, and the system remains in a deadlock state.
Starvation: Even without deadlock, there's a risk of starvation where a philosopher may be indefinitely prevented from accessing the chopsticks and thus unable to eat, while others keep acquiring the resources.
Concurrency control: Ensuring that multiple processes (philosophers) can access shared resources (chopsticks) safely and efficiently is a challenge. This requires proper synchronization mechanisms to prevent issues like deadlock and starvation.

How we can solve it?

Mutexes or Locks: Use mutexes or locks to represent each chopstick. Philosophers must acquire both mutexes (representing both chopsticks) before they can start eating. This ensures that only one philosopher can use a chopstick at a time.
Semaphore Solution: Use semaphores to control access to the chopsticks. Semaphores keep track of the number of available chopsticks. Philosophers must acquire both semaphores (representing both chopsticks) before they can eat, and release them when done.
Resource Hierarchy: Assign a numerical value to each chopstick and establish a hierarchy. Philosophers are required to pick up the lower-numbered chopstick first before attempting to pick up the higher-numbered one. This prevents circular waiting and deadlock.
Asymmetric Solution: Introduce a solution where one philosopher picks up the right chopstick first and the other picks up the left one first. This breaks the symmetry and prevents deadlock.
Chandy/Misra Solution: Use an algorithm where a philosopher must request permission from a neighbour before picking up both chopsticks. This ensures that at least one philosopher can eat at any given time, preventing deadlock.

How Algorithm work ?

Initially, all philosophers are in the thinking state.
When a philosopher gets hungry:

a. For philosophers other than the last one, wait on the left fork and then on the right fork.

b. For the last philosopher, wait on the right fork first, and then on the left fork.

c. If both forks are available, allocate them to the philosopher; otherwise, the philosopher waits.

Once both forks are acquired, the philosopher starts eating.
After eating, the philosopher releases both forks.
To prevent a deadlock when all philosophers get hungry simultaneously, the last philosopher tries to acquire the right fork first before attempting to acquire the left fork. This way, at least one philosopher can acquire both forks and start eating, preventing a deadlock.