Problem Statement:

The Dining Philosophers Problem is a classic synchronization problem that illustrates
the challenges of avoiding deadlock, livelock, and ensuring fairness when dealing with
concurrent processes.
Scenario: There are five philosophers seated around a circular dining table. In front of
each philosopher, there is a bowl of spaghetti. The philosophers spend their lives
alternating between two activities: thinking and eating.
To eat, each philosopher needs two forks, one from their left and one from their right.
The problem arises because there are only five forks, and each philosopher shares a
fork with their neighboring philosopher. Thus, they need to coordinate the use of forks.
Requirements:
1. Correct synchronization: Ensure that no two philosophers can access the same
fork simultaneously.
2. Deadlock avoidance: Ensure that the philosophers do not get stuck in a state
where they are all waiting indefinitely to acquire forks (deadlock).
3. Starvation prevention: Ensure that no philosopher is starved (i.e., no
philosopher waits indefinitely for the chance to eat).
4. Concurrency: Your solution should allow multiple philosophers to eat
concurrently when possible.
5. Fairness: Philosophers should not hog forks, ensuring others have a chance to
eat.
6. Efficient solution: Design a solution that is efficient, with minimal waiting and
contention.

Test Cases for Dining Philosophers Problem
Test Case 1: Basic Synchronization Test

Marks: 2 (In-lab), 2 (Out-of-lab)

Description:
Ensure that no two philosophers are using the same fork simultaneously.
Hint:
● Run the program with 5 philosophers.
● Each philosopher alternates between thinking and eating, attempting to pick up
the left and right forks when they wish to eat.
● At any given time, a fork should be used by only one philosopher.
● There should be no overlapping "eating" states for neighboring philosophers.

Output:
Philosopher 1 is eating.
Philosopher 3 is eating.
Philosopher 2 is thinking.
Philosopher 4 is eating.
Philosopher 1 has finished eating.
Philosopher 5 is eating.

Test Case 2: Deadlock Avoidance Test
Marks: 2 (In-lab), 2 (Out-of-lab)

Description:
Ensure the solution avoids deadlock, where all philosophers are waiting indefinitely for
forks.

Hint:
● The program should avoid deadlock, ensuring that at least one philosopher
proceeds and releases their forks.
● Philosophers should alternate between thinking and eating without getting stuck.
● If the program keeps running without all philosophers being stuck in a "waiting"
state indefinitely, it passes the deadlock test.
● You may introduce a timeout or log a message if all philosophers eat at least
once.
● If the program keeps running without all philosophers being stuck in a "waiting"
state indefinitely, it passes the deadlock test.
● You may introduce a timeout or log a message if all philosophers eat at least
once.

Test Case:
Philosopher 1 is eating.
Philosopher 2 is waiting.
Philosopher 3 is eating.
Philosopher 4 is waiting.
Philosopher 5 is eating.
......
(Philosophers continue to eat without deadlock)

Test Case 3: Fairness Test (Starvation Prevention)

Marks: 2 (In-lab), 2 (Out-of-lab)

Description:
Ensure that no philosopher is starved, i.e., no philosopher waits indefinitely to eat while
others continue to eat repeatedly.
Hint:
● Every philosopher should get a chance to eat, and the number of times each
philosopher eats should be roughly equal.
● Count the number of times each philosopher eats over a fixed period and ensure
that no philosopher is starved or consistently denied access to the forks.
● Count the number of times each philosopher eats over a fixed period and ensure
that no philosopher is starved or consistently denied access to the forks.

Test Case:
Philosopher 1 ate 10 times.
Philosopher 2 ate 9 times.
Philosopher 3 ate 10 times.
Philosopher 4 ate 9 times.
Philosopher 5 ate 10 times.

Test Case 4: Concurrent Eating Test
Marks: 2 (In-lab), 1 (Out-of-lab)

Description:
Ensure that multiple philosophers can eat concurrently when the forks are available.
Hint:
● At least two non-adjacent philosophers should be able to eat concurrently when
their required forks are available.
● Check the log to ensure that non-adjacent philosophers (who don’t share a fork)
are eating at the same time.
Test Case:
Philosopher 1 is eating.
Philosopher 3 is eating.
Philosopher 5 is eating.
Philosopher 2 is thinking.

Test Case 5: Efficiency and Performance Test

Marks: 2 (In-lab), 1 (Out-of-lab)

Description:
Ensure that the solution is efficient, with minimal waiting times and optimal utilization of
forks.
Hint:

● The waiting times for philosophers should remain minimal, and there should be minimal
contention for the forks.
● The solution should scale efficiently with an increased number of philosophers.
● Measure the time each philosopher waits before eating and ensure it stays within
reasonable bounds.
● Record the percentage of time that philosophers are eating versus waiting.
Test Case:
Philosopher 1 ate 15 times, average wait time: 1.2 seconds.
Philosopher 2 ate 14 times, average wait time: 1.3 seconds.
Philosopher 3 ate 15 times, average wait time: 1.1 seconds.
(etc.)]