Dining Philosophers Solution in C Using Condition Variables

The Dining Philosophers Problem

Topics

• The Dining Philosophers problem
• Example of how to code a monitor using the POSIX thread synchronization objects, mutexes and condition variables
• Example of the danger of deadlock, and one way to prevent it

What is the Dining Philosophers Problem?

---

This is a classic example of a synchronization problem, described in terms of philosophers sitting around a table, eating noodles with chopsticks. Each philosopher needs two chopsticks to eat, but there are not enough chopsticks to go around. Each must share a chopstick with each of his neighbors, as shown in the figure.

The dining philosophers are a popular theme for people learning to write Java applets. Over the years, I have found several such applets, but when I put links to them in course notes the applets disappeared from the linked locations. However, if you search for keywords "dining philosophers applet" or "dining philosophers animation" you can probably find one.

Significance of this Problem

• Potential for deadlock and starvation
• Academic benchmark for evaluation and comparison of synchronization and mutual exclusion mechanisms
• An example for demonstrating various process and thread synchronization mechanisms
• A good solution has no deadlock or starvation

Possibility of Deadlock

---

If philosophers take one chopstick at a time, taking a stick from the left and then one from the right, there is danger of deadlock, as shown in the figure.

For example, if you run the applet using the link above, you will see that if it runs fast enough it will deadlock.

This possibility of deadlock means that any solution to the problem must include some provision for preventing or otherwise dealing with deadlocks.

Possibility of Starvation

---

If philosophers take two chopsticks at a time, there is a possibility of starvation, as shown in the figure. Philosophers B & E, and A & C can alternate in a way that starves out philosopher D.

This possibility of starvation means that any solution to the problem must include some provision for preventing starvation.

Review of Monitor Concept

• Encapsulated data objects and procedures
  (a.k.a. methods or functions)
• Per-monitor lock enforces mutual exclusion
• Only one thread may be executing in the monitor at a time
• Thread inside the monitor may reliquish the monitor lock to wait for a condition
• POSIX mutex and CVs designed to implement monitors

Dining Philosophers Solution as Monitor

int update_state (int i) { if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) { state[i] = EATING; pthread_cond_signal (&CV[i]); } return 0; } void chopsticks_take (int i) { pthread_mutex_lock (&M); state[i] = HUNGRY update_state(i); while (state[i] == HUNGRY) pthread_cond_wait (&CV[i],&M); pthread_mutex_unlock (&M); } void chopsticks_put (int i) { pthread_mutex_lock (&M); state[i] = THINKING; update_state (LEFT); update_state (RIGHT); pthread_mutex_unlock (&M); }

---

This problem admits to a very simple solution using a monitor, as shown in the figure. The monitor's mutual exclusion is implemented using a POSIX mutex, M. There is a POSIX condition variable, CV for each philosopher. The other monitor data consists of an array of integers, representing the states of the philosophers, which are one of { HUNGRY, EATING, THINKING }. Besides the four entry functions (i.e., those that are callable from outside the monitor and go through the mutex, there is an internal function (which cannot be called from outside the monitor) that is called by the other functions to update the state.

Pay special attention to the update_state procedure. This design encapsulates the code for state updates in a form that can be shared by both entry procedures. If you adopt this style in your solution to the ferry problem, it will be simpler and more likely to work correctly.

The Complete Code

In directory examples/philos

• chopsticks.h, the monitor interface
• chopsticks0.c, the monitor implementation
• philosophers_t.c, the main program

---

The full code for this solution is in the indicated files.

How good is this solution?

1. Is this solution subject to deadlock? If not, why not?
2. Is this solution subject to starvation? Why or why not?

---

After you have finished reading about deadlock, you should be able to answer these questions about the solution.

© 2002, 2006 T. P. Baker ($Id: philos.html,v 1.1 2008/08/25 11:18:48 baker Exp baker $)

Dining Philosophers Solution in C Using Condition Variables

Source: http://www.cs.fsu.edu/~baker/realtime/restricted/notes/philos.html

Share this post