Test Assignment Arena Modeling
Arena modeling test 21/7/2004 (Dining philosophers)
Create two related simulation models for the situations sketched below. Write a report describing your models and containing answers to the italicized questions. Mail your models (*.doe) and report (*.doc or *.txt) to mailto:.
Five philosophers are sitting around a round table with an empty plate in front of each and a bowl of spaghetti in the middle. Between each two adjacent plates lies a fork.
They are busy thinking about difficult problems. Every once in a while, a philosopher gets hungry, stops thinking and wants to eat. In order to do so, he must obtain both adjacent forks to put spaghetti from the bowl to his plate and eat it. After eating, he puts his forks back.
Make a simulation model of the described situation, and run a simulation that answers the following questions:
- How long must each philosopher wait on average after getting hungry to start eating?
- What is the occupation rate of each fork?
The following numerical data are given:
- The event of a philosopher getting hungry is exponentially distributed. On average, each philosopher gets hungry once every 50 minutes.
- Hungry philosophers wait for both forks to become available together; after obtaining them he eats for 18 minutes exactly. His hunger may increase while waiting or eating. If so, he still releases his forks after 18 minutes of eating but he tries to get them back immediately.
The simulation length should be at least 4000 hours. You may obtain unexpected results. If so, indicate the nature and try to explain the cause.
Make a similar simulation model for the case with 4 philosophers and 4 forks, answering the same questions. Try to explain why the average waiting times are shorter in this case.
Note: This is a famous problem in concurrency and programming theory. See e.g. http://www.cs.mtu.edu/~shene/NSF-3/e-Book/MUTEX/TM-example-philos-1.html
Solution:
Clearly, the problem focus is the forks. If adjacent philosophers are hungry, the compete for their shared fork; if one is eating, the other has to wait. It is obvious to treat the forks as resources. Without simulation, we can even predict the occupation rate of the forks. Since each philosopher gets hungry every 50 minutes (on average) and eats for 18 minutes, the occupation rate of any fork equals 36/50 = 72%.
The straightforward Arena model has five resources, fork0 up to fork4. There are five entities hunger0 up to hunger4 that are created with the described frequency, queue for the appropriate forks until both resources are available, eat for 18 minutes and then are disposed of. As described, new hunger entities may occur when a philosopher is waiting or eating, but they are all treated separately. See dinphil5.doe on the simulation webpage.
The fork occupation rate is between 70% and 74% as expected. The average wait times for the philosophers is as follows:
number duration
0 0.94
1 0.85
2 0.97
3 1.09
4 1.66
You notice an asymmetry here: philosopher 4 waits almost twice as long as philosopher 1. The probable reason for this phenomenon is that philosophers queue for forks. The fork queues will be treated by Arena in a fixed order and this causes a bias.
The model with 4 philosophers and forks can be made by a minor modification. It can be found in dinphil4.doe. The fork occupation rate is about 72% as expected. The average wait times for the philosophers is as follows:
number duration
0 0.71
1 0.71
2 0.72
3 0.72
The reason for this improvement is that with five forks, at least one fork is not used at any moment, so the occupation rate of 72% is in fact 90% of the maximum capacity of 80%.
Four forks can be fully occupied and this improves the throughput.