Figure 1: The queues associated with a monitor.
Textbook discussions of synchronization seldom go beyond a brief introduction in terms of classical problems. This paper presents a simulator for the monitor solution of the dining philosophers problem that students can use to experimentally explore how such a solution might behave in practice. The simulator, which can be run remotely from a browser or can be downloaded for running locally, is written in Java so that it can be run on almost any system.
A task can acquire the monitor's lock through one of several monitor queues. It gives up the lock by returning from a monitor method or by blocking on a condition variable.
A condition variable is not a variable at all. In fact it is just a queue that is part of the monitor. Sometimes these are called event queues, but we will use the expression condition variable queue here. A condition variable queue can only be accessed with two monitor methods associated with this queue. These methods are typically called wait and signal. The signal method is called notify in Java.
A task that holds the monitor lock may give it up and enter a condition variable queue by executing the corresponding wait method. A task that holds the monitor lock may revive a task waiting in a condition variable queue with the notify method of that queue. The notify method removes one task from the condition variable queue if the queue is not empty. Since the notifying and notified tasks may not both be active in the monitor simultaneously, at least one of these tasks must block. A task is blocked by putting it in a queue. The behavior of a monitor is determined by the scheduling of four types of queues.
Condition variable queues: There may be any number of condition variable queues for a given monitor. Each queue has associated wait and notify methods for putting tasks in the queue and taking them out.
The entry queue: Each monitor has one entry queue. When a task attempts to access a monitor method, it is put in the monitor's entry queue.
The signaller queue: Each monitor has one signaller queue. When a task performs a notify, it is put in this queue.
The waiting queue: Each monitor has one waiting queue. When a task is removed from one of the condition variable queues, it is put in this waiting queue.
The last three of these queues will be referred to as monitor queues. Processes in the monitor queues are waiting to acquire the monitor lock. A monitor has one of each of these queues, but in some implementations these queues may be combined.
When the monitor lock becomes free (because the task holding the lock returns from a monitor method or enters one of the queues), the tasks in the three monitor queues compete for the lock. The behavior of the monitor is determined by the relative priorities and queue disciplines of the three monitor queues.
In the monitors we will discuss here, the signaller queue will have the highest priority of the three monitor queues. When a task executes a notify method, it is put in this queue and loses the monitor lock. However, since this queue has the highest priority, it immediately regains the lock. This is equivalent to not having lost the lock at all, so for the rest of this paper we will ignore the signaller queue.
The queues of a monitor (ignoring the signaller queue) are shown in Figure 1. The arrows show how tasks can move from one queue to another.
Figure 1: The queues associated with a monitor.
Monitors are classified by the scheduling priorities of the monitor queues. If we ignore the signaller queue, there are three possibilities.
Monitors in which the entry queue has a higher priority than the waiting queue have unacceptable behavior [3] and have not been given a name. We will call these Entry Priority monitors. Monitors in which the waiting queue has a higher priority than the entry queue are generally called Signal and Continue monitors [3,7] and those in which the two queues have equal priority are called Wait and Notify monitors [3,6].
The queuing discipline also affects monitor behavior. For each of the monitor classifications we consider three queueing disciplines: FIFO, LIFO and random.
Several operating systems textbooks give essentially the same monitor solution to this problem [9,11,13]. Most discussions of the dining philosopher's problem require that a solution does not allow a philosopher to starve. For example, Silberschatz and Galvin state the following:
Whether a particular monitor solution avoids starvation may depend on the implementation of the monitor. It may depend on the relative priority of the entry and waiting queues and it may depend on the queue semantics (FIFO, LIFO, random, etc.). Silberschatz and Galvin draw pictures of monitors representing the queues as FIFO queues, but do not explicitly discuss this issue.
Most textbooks present the same monitor solution to the dining philosophers problem. Each philosopher is in one of the states thinking, hungry, or eating. When a philosopher becomes hungry he can begin eating if neither of his neighbors is eating. When a philosopher finishes eating, the neighbors are again checked. A hungry neighbor whose other neighbor is not eating can be changed to the eating state. With this algorithm, a philosopher can starve if one of its neighbors is always eating. An example of this is shown in Section 6.1.
Most standard textbooks ignore the question of starvation, although Stallings [12] does discuss this in an exercise. Hartley [5] gives several solutions to the dining philosophers problem that avoid starvation. One simple idea in avoiding starvation is to not allow a philosopher to eat twice while a neighboring philosopher remains hungry. Figure 2 gives pseudocode for one such solution, which I call the Polite algorithm. It is a modification of the a standard monitor solution given in [11] using the starvation avoidance ideas from [5]. The modifications to the traditional solution are shown in boldface.
monitor diningPhilosophers {
int[] state = new int[5];
boolean[] leftHungry = new boolean[5];
boolean[] rightHungry = new boolean[5];
static final int THINKING = 0;
static final int HUNGRY = 1;
static final int EATING = 2;
condition[] self = new condition[5];
public diningPhilosophers {
for (int i=0;i<5;i++) {
state[i] = THINKING;
leftHungry[i] = false;
rightHungry[i] = false;
}
}
public entry pickUp(int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING)
self[i].wait;
rightHungry(left(i)) = false;
leftHungry(right(i)) = false;
}
ublic entry putDown(int i) {
state[i] = THINKING;
test(left(i));
if (state[left(i)] == HUNGRY)
leftHungry[i] = true;
test(right(i));
if (state[right(i)] == HUNGRY)
rightHungry[i] = true;
}
private test(int i) {
if (state[right(i] != EATING) &&
(state[i] == HUNGRY) &&
(state[left(i)] != EATING) &&
!leftHungry(i) && !rightHungry(i) ) {
state[i] = EATING;
self[i].signal;
}
}
private int left(int i) {
return (i+1)%5;
}
private int right(int i) {
return (i+4)%5;
}
}
Figure 2: The polite monitor solution of the
dining philosophers problem that avoids starvation.
In a theoretical context, starvation usually means indefinite blocking, meaning that there is not a bound to the time (or more precisely, the number of times other philosophers eat) between hungry and eating for a given philosopher. In a practical context, we would like the bound to be reasonably small. If there are five philosophers, the bound should be around 5, not 5000. The Polite algorithm avoids starvation in this sense. However, a price is paid for this in that some philosophers remain hungry longer than they might otherwise have. Another way of saying this is that the solution does not allow as much parallelism as the traditional one.
We take an experimental approach to the problem of starvation here. We give probability distributions for the eating and thinking times for each philosopher and look at the resulting times philosophers are hungry. We can consider starvation to occur when a philosopher is hungry for a given time, or we can compare different algorithms or monitor implementations by examining average hungry times. In Section 6.2 we compare the traditional algorithm, which allows starvation, to the polite algorithm which does not.
Figure 3: A view of the main simulator window.
The round table represents the monitor. Inside the table, near the edge is the condition variable queue, self, for each philosopher. It is represented as a small box of the same color as the philosopher. Each condition variable queue is either empty (filled with white) or has the corresponding philosopher waiting in the queue (filled with the color of that philosopher).
At the center of the table are the entry and waiting queues and the monitor lock. The monitor lock is represented by a small box. When a philosopher task owns the lock, the box is filled with the color of that philosopher. The entry and waiting queues are represented by rectangles. They are filled with strips of color representing the philosopher tasks in the queue.
The simulator is event driven. It uses a virtual time that is an integer shown in the bottom left corner of the window. Each philosopher has a distribution for its thinking and eating times. Available distributions include constant, uniform, and exponential. Values from the exponential distribution are rounded down to an integer.
Three types of monitors are implemented, Signal and Continue, Wait and Notify, and Entry Priority. In the last of these the entry queue has a strictly higher priority than the waiting queue. As mentioned in Section 2 this type of monitor has undesirable properties, but tests show that several Java implementations may have this behavior. Each of these three types of monitors can have three disciplines for the entry and wait queues, FIFO (first-in/first-out), LIFO (last-in/first-out) and random. In the solution to the dining philosophers problem presented, the condition variable queues can each have at most one entry.
The simulator can be used in three ways.
In Single-step Mode the simulator will run one time step. After each step you can examine the state of each philosopher.
In Multiple-step Mode you can run for a given amount of time.
In Run Until Starvation Mode the simulator will run until at least one philosopher has starved.
In any of these modes the simulator can animate the process so you can see a philosopher task move from one queue to another as the philosopher changes from thinking to hungry to eating and back to thinking again.
A class demonstration that uses the simulator in animation mode can illustrate the ideas of monitor implementation and illustrate monitor locks. It can illustrate how the tasks move from the condition variable queues to the waiting queue and how they compete for the monitor lock when they are in the entry and waiting queues.
The simulator can be used to illustrate how to design experiments to test hypotheses or make comparisons. Once a set of characteristics of the philosophers has been chosen (number of philosophers, thinking and eating times, etc.), a comparison can be made between the traditional and polite algorithms or between queue priority schemes or queueing disciplines.
The simulator can be run until a philosopher starves and the time until starvation can be compared. Alternatively, the simulator can be run for a given number of time steps and average or maximum hungry times can be compared.
The simulator uses the Jeli logging facility [10] to store the results of the simulation in HTML format so that it can be viewed by a standard browser. The simulator can produce tables of data giving information about a given philosopher (such as average and maximum time in each state) and summary information. It can trace the states of any philosopher and can produce a Gantt chart showing the state of each philosopher as a function of time.
Figure 4: Gantt charts for the traditional (top) and polite (bottom) algorithms.
Consider the case in which the eating and thinking times times are exponentially distributed (rounded to an integer) with an average of 10. The simulator was run using each algorithm for 100 time steps. Figure 5 shows two tables generated by the simulator, the top one for the traditional algorithm and the bottom one for the polite algorithm. For the polite algorithm the maximum hungry time is 16 compared to 23 for the traditional algorithm, but the average hungry time for the polite algorithm is larger by about 10 percent.
Figure 5: The upper table is for the traditional algorithm and the lower one is for the polite algorithm.
However, if P0 is taken out followed by P3, only P0 and P3 will be allowed to eat and at least one of the philosophers will have to wait through two rounds of eating before he can eat.
The web site [17] contains a number of resources for using the simulator. You can run the simulator directly from the web, storing the output files on our server so that they can be viewed or printed using a standard browser. All of the examples discussed here can be run from the web. The simulator can be downloaded from the web so that it can be run locally. A user's guide is also available on the web page.