Dining Philosophers Problem - Java Code

COMP124 Lectures 2021-04-28

Code

Philosopher Thread

public void run() {
	while (alive) {
		think();
		stick[i].get();
		stick[(i + 1) % 5].get();
		eat();
		stick[i].put_down();
		stick[(i + 1) % 5].put_down();
	}
}

Chopstick Class

class Chopstick {
	private volatile boolean in_use = false;
	
	public synchronized get() {
		while(in_use) {
			try {
				wait();
			}
			catch {
				...;
			}
		}
		in_use = true;
	}
	public synchronized put_down() {
		in_use = false;
		notify();
	}
	...
}

In comparison to a producer-consumer model, we don’t have to wait to release the resource. We also only notify() when we release the resource.

Explanation

• Each chopstick object has a lock associated with it.
• This prevents two philosophers grabbing a chopstick simultaneously.
• If a philosopher needs a chopstick, but it is already in use, the philosopher is moved into the wait set.
• When the chopstick is put down, the waiting philosopher is notified and can pick it up.

Deadlocks

Suppose each philosopher picks up the chopstick to their right simultaneously.

• Then nobody can pick up the stick on the left, and all philosophers move to the wait state.

Since nobody is releasing a stick, all philosophers wait forever.

This situation is called a deadlock.

More generally deadlock occurs in a concurrent system when each participant is waiting on others to do something.

Solution

• Allow only $n-1$ philosophers to dine simultaneously.
• Introduce asymmetry:
  • Even indices pick up chopstick in order right then left.
  • Odd indices use left then right.
• Insist that both chopsticks are claimed at the same time.
  • In the same critical region.

All of the above complicate the code.

Starvation

1. Suppose $P_0$ and $P_2$ grab their chopsticks first.
   • Then $P_1,P_3$ and $P_4$ have to wait
2. If $P_0$ and $P_2$ put down their stick and them immediately claim them again, the others will never eat.
   • Even if $P_0$ and $P_2$ take turns, $P_1$ cannot eat.

More generally, starvation occurs when one or more of the participants in a concurrent system is denied access to resources.