Figure 1: 5 Philosophers
The Starving Philosophers simulation is based on the classical Dining Philosophers problem. Each philosopher is in one of the states: Thinking, Hungry, or Eating. In this simulation probability distributions are specified for each philosopher giving the eating times and thinking times.
We start with all philosophers thinking and each determines a length of time from its thinking distribution. After that time the philosopher enters the hungry state and the algorithm determines when it can enter its eating state.
When a philosopher enters its eating state, it chooses an eating time from its eating time distribution and stays eating for this time. When the time is up it goes into the thinking state, possibly allowing others to eat.
Simulator times are integers on an arbitrary time scale. The simulator is event driven. As time progresses, the philosopher threads move among various queues as they attempt to gain the monitor lock.
A unique color is used for each philosopher thread. The philosophers appear as boxes of a given color distributed around a black circle which represents the monitor. Inside each philosopher box is a letter (T, H, or E) representing the state of the philosopher. A philosopher thread attempting to enter the monitor is shown as a solid rectangle of the philosopher color. The simulator can animate the movement of this thread among the monitor queues using this rectangle.
Inside the monitor circle are the monitor lock at the center and two monitor queues, the entry queue containing threads which are attempting to execute a monitor routine and waiting for the monitor lock, and the waiting queue consisting of those threads which have executed a condition variable wait and have been awakened.
In the Dining Philosophers algorithms used hear, there is one condition variable per philosopher and only the corresponding philosopher can issue a wait for this condition variable. The queues for these condition variables and therefore have at most one waiting process. These queues are shown as small squares having the color of the corresponding philosopher. When the queue is empty, the box has a white interior. Otherwise, the box is filled with the color of the philosopher.
The philosophers are numbered starting at 0 with the one at 12 o'clock and the numbers increase as you move clockwise around. Figure 1 shows a diagram of 5 philosophers. Philosopher 0 (green) is thinking. Philosophers 1 (red) and 3 (magenta) are hungry and are waiting on their condition variables. Philosophers 2 (blue) and 4 (cyan) are eating.
The simulator can run one of two dining philosophers algorithms and simulate monitors with 3 queue priorities and 3 queue disciplines. Results of the simulation can be logged, graphed, and compared.
One area of interest is how long a philosopher remains in the hungry state. The classical definition of starvation refers to a thread that is postponed indefinitely from a desired activity, in this case changing from hungry to eating. We look at a more practical aspect of starvation, and assign to each philosopher a maximum hungry time. If a philosopher remains in the hungry state longer than this time, we consider the philosopher starved, and therefore no longer active. The simulator can be run either with this type of starvation on or off. The default is off.
The simulator is written using the Jeli library. Information about using the widgets of this library can be found here.
System requirements:
User requirements:
If you are only interested in this simulator, you can download a zip file sp.zip that contains all of the files that you need.
Running in a non-Windows environment:
If you installed the simulator by copying the files from a CD, the
scripts may not have the correct permissions to run. The convert
and runsp files should be executable.
The ASCII files distributed with this distribution are in the Windows format
in which lines end in a carriage return followed by a line feed.
It may be more convenient to have the carriage returns removed.
If you are running under UNIX, Linux, or Mac OSX, it
may be more convenient to have the carriage returns removed.
You can remove all of the carriage returns from these files by executing the
convert script.
If you do a custom installation, you can put the jar files anywhere you want. Modify the runsp.bat (Windows) or runsp (Unix, Linux, Mac OSX) file so that the JARDIR1 or JARDIR2 variables points to the location of the jar files.
If the simulator does not start, make sure you have the Java runtime
executables in your path. In a command window, execute:
java -version
and make sure this displays a version later than 1.0.
Start with the provided spconfig file. The first line starts with the word user. Modify this line so that your name appears after this word. Start the simulator by executing runsp as described above. You should see a window similar to the one shown in Figure 2. The display consists of two parts, a diagram of the philosophers and the monitor as in Figure 1, and a collection of buttons to control the simulation below.
The buttons that control the animation have a light red background. The simulator uses animation and a virtual time that is controlled by the buttons and sliders above the Pause button. Pushing the Animation On button changes it to an Animation Off button and turns off the animation, allowing the simulation to run more quickly. When on, the speed of animation is controlled by the speed slider. The detailed operation of this Jeli slider is described here. When animation is running, the Pause pauses the animation and changes to a Resume button.
The simulation is run by pushing one of the 4 green buttons in the button area. Step Time will run one time step. Step Event will run the next time step in which something happens. Run: 10 will run 10 time steps. It will count down the number of remaining time steps as the simulation progresses. The button below this, Run Count: 10 can be used to change the number of time steps that the Run button executes. Its operation is described here. The last button, Run Until Starvation will run until a philosopher starves (if starvation is on) or forever otherwise. However, running can always be stopped by pushing the abort button. Abort will stop the simulation after the current time step.
The buttons related to logging have a light blue background. The Open Log button will open a log file containing information about the simulation. You can display a Gantt chart showing the states of the philosophers with the Gantt Chart button. If the log is open, the Log button on the Gantt chart will be active, allowing a copy of the Gantt chart to be put in the log file.
When done with the simulation, close the log using the Close Log button (which the Open Log button turned into) and exit the simulator using the Quit button which is in the upper right corner of the philosophers diagram.
The rest of the buttons control the details of the algorithms used in the simulation and the logging facility. Both are described in detail below.
The configuration file consists of lines containing a keyword followed by an optional parameter. The parameter may represent a number, a probability distribution, or a string. The order of the lines in the configuration file is not important except for conflicting options. In this case the later one has precedence.
The probability distributions support are constant, uniform, and exponential.
The probability distributions represent am integral time and cannot be negative.
The probability distributions have one of the following forms:
constant n where n is a positive integer
uniform n m meaning uniformly distributed between n and m inclusive.
exponential x where x and be a floating point
number representing the mean of the distribution. Values from this distribution
are rounded up to an integer.
The following keywords are supported. For the parameter, n and m represent integers, s represents a string, and d represents a distribution as described above.
number n
the number of philosophers
seed n
a seed for the random number generator
eatingdist d
the default distribution used for eating times
thinkingdist d
the default distribution used for thinking times
starvingdist d
the default distribution used for starvation times
user s
the name that appears in the log file.
logfn s
the name the log file.
starving <on,off>
turn starving on or off.
algorithm <polite,classical>
use the algorithm indicated.
animate <on,off>
start with animation on or off.
classification <Signal and Continue, Wait and Notify, Entry Priority>
set the monitor classification giving queue priorities
queueing <fifo, random>
set the queueing discipline.
thinkingdistn d
set the thinking time distribution for
philosopher n.
eatingdistn d
set the eating time distribution for
philosopher n.
statvingdistn d
set the starvation time distribution for
philosopher n.
thinkingdistvaluen m
force a value returned for the thinking time
distribution for philosopher n.
eatingdistvaluen m
force a value returned for the eating time
distribution for philosopher n.
starvingdistvaluen m
force a value returned for the starvation time
distribution for philosopher n.
The classical algorithm is the one described in most textbooks. When a philosopher stops eating, it examines it neighbors and lets them eat if they are hungry and their other neighbor is not eating. The Polite Algorithm does not allow a philosopher to eat twice in a row if a neighbor has been hungry since it last started eating. The default is to use the classical algorithm. This can be changed with a line in the configuration file or by pushing the Algorithm button.
Monitors are classified by the relative priority of their queues. The simulator assumes that the signaler queue has the highest priority. The classification describes the relative priorities of the entry and waiting queues. Monitors in which the waiting queue has the higher priority than the entry queue are called Signal and Continue monitors and those in which the two queues have equal priority are called Wait and Notify monitors. Monitors in which the entry queue has higher priority than the waiting queue are generally thought to have unacceptable behavior and do not have a standard name. They are called Entry Priority monitors here.
The classification of the monitor can be changed with a line in the configuration file or by pushing the monitor classification button which is labeled by the name of the current classification.
The queueing discipline of a queue refers to the order in which items are removed from the queue relative to the order in which they entered. Three queueing disciplines are supported by the simulator, FIFO, LIFO, and Random. These refer to both the entry queue and the waiting queue. The queueing discipline can be changed with a line in the configuration file or by pushing the Queueing button.
The speed of the animation can be controlled by a slider. The relative speed of the animation is shown on the Speed button to the right of the animation button. Normal speed is 1.0. It can be adjusted using the slider to the right. The Round button can be used to round the speed value after it is adjusted with the slider. The Double and Round buttons control the range of the slider.
Below these is the Pause/Resume button. When it says Pause pushing this button will pause the animation which also pauses the simulation. The button is changed to a Resume button which resumes the animation. This button has no effect if animation if off.
The Open Log button will open the log file. This will change it to a Close Log button. When the log is not open, the next two buttons affect what will happen when the log is opened next. The Change Log Filename button can be used to prompt you for a new log filename. The next button toggles between Replace Old Log and Append To Old Log. In the first case, if a file already exists with the same name as the new log file, the old file is lost. In the second case new log information will be appended to the old log file.
When the log is open, the second button becomes a Start/Stop Log button. This can be used to temporarily stop information from being logged without closing the log file. The next button is a Log Comment button which can be used to add a comment to the log file.
The Show Local Log can bring up a browser window with containing the log file. This only works on some systems. If this button does not work automatically, you may have to bring up the browser and open the appropriate URL.
The Gantt Chart button displays a Gantt chart showing the states of the philosophers over time. When the log file is open, the Gantt chart has a Log button which can but am image of the Gantt chart in the log file. The Log Data button becomes active when the log file is open. This puts some tables into the log file containing statistics from the simulation.
The Current State button toggles between Truncate and Ignore. This affects how the statistics handle the current state of each philosopher. The ending time of the current state is no known. In the Ignore mode the current state is not included in the statistics. In the Include mode, the last state is included, assuming it ends at the current time.
The Color/Mono toggles between color and monochrome mode for saving the Gantt chart. In the Mono mode, gray scales are used which might be easier to distinguish when the charts are printed on a black and white printer.
This is a standard Jeli Frame which contains a JeliTextArea with a button to log the contents of the text area.
The buttons at the bottom of the window include:
Hide which hides the window
Show Events which shows the pending events for the simulation
Show Distributions which shows the distributions for all of the philosophers.
Show Entry Queue History which shows the times of all items put in and taken out of the entry queue.
Show Waiting Queue History which shows the times of all items put in and taken out of the waiting queue.
Each philosopher also has a detailed information window which tracks just that philosopher. You can open this window by clicking the mouse inside one of the large philosopher boxes. There is a separate window for each philosopher and you can have as many of these open as you wish.
The buttons at the top of the window, including a Log button are the same as for any JeliTextArea. A colored bar at the bottom of the window matches the color of the corresponding philosopher. Information is not automatically logged in these windows. You must push one of the buttons at the bottom of the window.
Show Distributions lists the three distributions for the philosopher.
Show Times lists the three distributions for the philosopher and the
times used so far from each of these distributions.
Show History shows all of the state changes of this philosopher and when they occurred.
Hide hides the window.
Normally the simulator is started with
java StarvingMain or
java StarvingMain configfile
If instead you use:
java StarvingMain 2 or
java StarvingMain 2 configfile
Two copies of the simulator screen will appear.
Only the first window will contain the buttons for opening and closing the log as the same log will be used for both simulations. An additional button appears which is initially labeled Step Links Enabled. This means that pushing one of the green buttons for one simulation will cause the corresponding button on the other simulation to be pushed.
The Pause/Resume button is now split into two parts, Pause/Resume This and Pause/Resume All, giving the option to simultaneously pause both simulations.