The Dining Philosophers Problem

“A Solution: Breaking the Dependency” improves upon the “Broken Solution”.

The Dining Philosophers problem is a classic concurrency or synchronization problem in Operating Systems. E. Dijkstra posed and solved this problem in 1965. In this problem, there are 5 philosophers around a dining table and 5 forks available for eating. The life of the philosophers consists of alternative period of eating and thinking, and eating needs two forks (left and right). When philosopher gets hungry, he/she tries to acquire two forks, eats for a while, and then puts down the forks and continues to think.

The broken solution is that when the philosopher is hungry, he/she picks up the left fork first and waits for right fork, when gets it eats for a while and put both forks back to the table (Arpaci-Dusseau & Arpaci-Dusseau, 2014). The problem with this solution, because of which it is called “broken”, is that if all philosophers pick up the forks to their left and wait for the ones on the right, nobody will get to eat (as all forks are already acquired) leading to a deadlock. This phenomenon can be said to be “Circular Wait”.

The solution “Breaking the Dependency” improves upon it by changing the way the forks are acquired by one philosopher. More specifically, Philosopher 4 (or any other philosopher) can be made to pick up the right fork first, instead of the one on the left (Arpaci-Dusseau & Arpaci-Dusseau, 2014).  

void getforks() {

if (p == 4) {

sem_wait(forks[right(p)]);

sem_wait(forks[left(p)]);

} else {

sem_wait(forks[left(p)]);

sem_wait(forks[right(p)]);

}

}

This will avoid the deadlock because it will break the “Circular Wait” situation. At least one philosopher will then be able to eat even if all are trying to acquire forks for eating.

An alternate solution to break the dependency would be to test (using a function) if both right and left forks are free, before acquiring them (Tanenbaum, 2007). And this also improves upon the broken solution.

void test(p) {  /* p: philosopher number, from 0 to N−1 */

if (state[p] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING){

state[p] = EATING;

sem_post(forks[left(p)]);

sem_post(forks[right(p)]);

}

}

References:

Arpaci-Dusseau, R., & Arpaci-Dusseau, A. (2014).Semaphore, Operating systems: Three easy pieces. Madison: Arpaci-Dusseau. Retrieved from http://pages.cs.wisc.edu/~remzi/OSTEP/

Tanenbaum, A. S. (2007), Modern operating systems. (2nd ed., pp. 173-176). Prentice Hall PTR.