## Dining Philosophers Problem

### 1. Problem statement

This problem is related to the mutual exclusion problem, and we use the notions of thinking, hungry, and eating from there.

There are five philosopher processes, numbered 0, 1, 2, 3, 4. There are five fork variables also numbered 0, 1, 2, 3, 4. ["placed" between the philosophers such that forks i and (i+1 mod 5) are next to philosopher i.] Each philosopher cycles through thinking, hungry, and eating states. To eat, philosopher i needs forks i and (i+1 mod 5). We want to ensure that

1. Neighboring philosophers do not eat at the same time.

2. A hungry philosopher eventually eats provided no philosopher stays eating forever.

3. No busy waiting.

### 2. Solution attempt 1

Guard each fork i with a lock semaphore f[i] initialized to 1. To eat, philosopher i does a P on each of its forks.
```Semaphore fLock[0..4] initially 1;  // fLock[i] controls access to fork i

Phil( i: 0..4 ) {  // code executed by philosopher i
do forever {
think;
// become hungry
P( fLock[i] );          // grab "right" fork
P( fLock[i+1 mod 5] );  // grab "left" fork
eat;
V( fLock[i] );          // release "right" fork
V( fLock[i+1 mod 5] );  // release "left" fork
}
}
```
NOTE:
• Prove that this satisfies all the requirements except for starvation freedom.

• Provide a counter-example for the starvation-freedom requirement (it can deadlock).

### 3. Solution approaches

Here are some approaches to solving the problem:
• Allow at most four philosophers to contend for eating. This can be done as follows: introduce a semaphore, say table, that is initialized to 4; do P(table) before attempting to grab a fork; do V(table) after releasing the last fork.

• Allow philosophers to pick up both forks at once or none. This can be done as follows: let the forks be boolean variables (indicating whether free or not); all access to the forks are in a critical section enforce by a semaphore; if a philosopher finds that the two forks needed are not free, it waits on a semaphore until the forks are free.

• Introduce asymetry: make odd numbered philosophers grab the left fork first and then the right fork; make even numbered philosophers grab the right fork first and then the left fork.

• Introduce asymetry: make one philosopher grab the left fork first and then the right fork; all others grab the right fork first and then the left fork.

• Associate timestamps with hungry philosophers and use them to break contention.