In this lab you will learn about the consequences of selecting certain strategies for giving access to shared resources to competing processes. The Dining Philosophers problem is a classic model for multi-process synchronization. Using this model you will simulate processes using various strategies and observe what problems can occur. You will then come up with your own strategy to avoid problems that you have encountered.
To understand how operating systems manage processes that compete for resources.
To learn about two specific problems that can occur when processes compete: deadlock and starvation.
To investigate and design allocation strategies.
To better appreciate the importance of the operating system's job.
Create a lab9 subdirectory in your cps001 directory. Copy the file lab9-solutions.html to your ~/cps001/lab9 directory. The .html file is located here:
/afs/acpub.duke.edu/project/web/cps001/labs/lab9/
You should type your solutions for this lab in the spaces indicated. It is completely okay to work in groups, but each person should submit an individual assignment. Put the names of the people in your group in the space provided. You may use Notepad or xemacs as your text editor. Make sure to turn on word wrap in Notepad.
Five philosophers sit around a circular table. Each philosopher spends his life alternately thinking and eating. In the center of the table is a large plate of rice. A philosopher needs two chopsticks to eat a helping of rice. Unfortunately, as philosophy is not as well paid as computing, the philosophers can only afford five chopsticks. One chopstick is placed between each pair of philosophers and they agree that each will only use the chopstick to his immediate right and left. Each philosopher thinks. When he gets hungry, he picks up the two chopsticks that are closest to him. If a philosopher can pick up both chopsticks, he eats for a while. After a philosopher finishes eating, he puts down the chopsticks and starts to think.
Each chopstick is shared by two philosophers and hence a shared resource. The philosophers act as concurrent processes, they will all attempt to eat immediately when they stop thinking. Suppose that two neighboring philosophers get hungry at the same time. They both need the same chopstick to eat. If a philosopher attempts to pick up a chopstick that has already been picked up by his neighbor, we have a race condition - the first philosopher to grab the chopstick gets to eat, the other must wait for him to finish.
If every philosopher sits down about the same time and picks up his left chopstick for example, holding it until he can acquire the right one, we have a circular-wait deadlock. Every philosopher is waiting for his right chopstick, which has already been acquired by his right neighbor, and subsequently all philosophers will starve.
Starvation may also occur without deadlock. Depriving even one philosopher of the chance to eat is a starvation. Suppose two non-neighboring philosophers are fast thinkers and fast eaters, and they both acquire their left and right chopsticks and eat. After they finish eating, they put down their chopsticks and start to think. Since they are fast thinkers they quickly get hungry again and are able to pick up their chopsticks before their neighbors may acquire them - even if their neighbors are waiting for their chopstick! The remaining three philosophers will end up waiting to acquire one or both chopsticks and will never get the opportunity to eat. This is a starvation. It is not a deadlock, however, because two philosophers are actually able to acquire both chopsticks and eat. Note that a philosopher who is thinking is not hungry and thus not starving. A starving philosopher is one who is waiting to acquire a chopstick but can't.
The competition between philosophers for the chopsticks is a paradigm for the sort of competition for resources which goes on inside operating systems. A solution must be proposed in which each philosopher will not starve and in which there will never be a situation of deadlock.
The Dining Philosophers problem is illustrated in the applet below. Philosophers are depicted in yellow when they are thinking, blue when hungry and green when eating. The slider controls the amount of time that a philosopher spends eating and thinking.
This implementation is not free of deadlock or starvation! Moving the slider all the way to the left results in five very fast thinking and fast eating philosophers and the applet often ends up in deadlock. When you move the slider further to the right, the amount of time that a philosopher spends eating and thinking increases, and the applet will generally run for a longer period without deadlock. Deadlock is still possible, however, because no strategy is implemented which prevents all five philosophers from each holding one chopstick. Increasing the thinking and eating times only decreases the probability of deadlock, but does not eliminate the possibility.
The philosophers must cooperate to remain alive. In the remainder of this lab, you will devise strategies to prevent deadlock and starvation.
To gain a better understanding of the problem, we will "pretend" to be the philosophers in the problem and see what happens when we compete for resources. Sit in a circle of five people. If you don't divide up evenly, you can have a sixth person take turns or ask a TA to join a group of four. Each group will be given five chopsticks and a bowl of candy. Place the chopsticks between neighbors and the bowl in the center of the circle as in the applet. You will also each get a coin.
You must follow protocol for obtaining the shared resources. A philosopher may never pick up both chopsticks at once. You must always do one at a time. If you acquire both chopsticks, use them to take a piece of candy from the bowl. Then you may eat the candy, holding onto the chopsticks until you are finished (if you don't want it, then just hold onto the chopsticks for a bit, then put the candy back in the bowl). Put the chopsticks down one at a time. After you put the chopsticks down, you will think. We will use coin flips to determine how long you think - keep flipping the coin until you get two heads in a row. When this happens, you will be hungry again and try to acquire the chopsticks.
One other note about this game: we are not going to discuss right now what happens when you run out of a resource. This means that you should not run out of the objects in the middle of the table. In other words, don't eat all the candy in the first round!
You will try different strategies and study what could happen when following that strategy. The order in which you should pick up and put down the chopsticks is given in each of the strategies.
Assume everyone is initially hungry. This means the first thing you should do is try to acquire both chopsticks in the order specified by the strategy.
Assume everyone is initially thinking. This means the first thing you should do is start flipping your coin. When you get two heads in a row, try to acquire both chopsticks in the order specified by the strategy.
Each philosopher decides if they want to initially think or initially eat.
Suppose some of the philosophers think and eat really fast (don't even flip a coin to think in this case), and others think and/or eat really slow, as described in the "Dining Philosophers" section above.
Make sure to test these cases several times! Is there any difference in the strategies for any particular case?
In Strategy One and Strategy Two, realize that just because your neighbor is waiting for your chopstick doesn't mean he has the right to pick it up first! If you put down your chopsticks, you can pick them up again right away before your neighbor gets the chance.
Strategy One: When a person is hungry, you must first try to get the left chopstick, then the right. You may not reach for both at once! If the chopstick you want is unavailable, wait until it is put down again. If you can get the left chopstick but not the right, hold onto it.Once you have both chopsticks you can eat a piece of candy, then put down first the left chopstick and then the right chopstick. Now spend some time thinking (flip your coin until you get two heads in a row). When you get hungry again, repeat the cycle. Try this strategy and see if it works well. Write a paragraph about your experience. What happens in the four cases described above? Does this strategy result in deadlock? Starvation? Explain your answers.
Strategy Two: Number yourselves in order as philosophers 1 through 5. For this strategy, everyone with an odd number will follow Strategy One, and everyone with an even number will do as follows: When a person is hungry, first try to get the right chopstick, then the left. If the chopstick you want is unavailable, wait until it is put down again. If you can get the right chopstick but not the left, hold onto it. Once you have both chopsticks you can eat a piece of candy. When you are done, put down first the right chopstick and then the left. Now spend some time thinking (flip your coin until you get two heads in a row). When you get hungry again, repeat the cycle. Try this strategy and see if it works well. Write a paragraph about your experience. What happens in each of the four cases described above? Is this strategy preferable to Strategy One? Does this strategy eliminate the possibility of deadlock? Starvation? Explain your answers.
Your Strategy: Come up with a new strategy for the philosophers that eliminates the possibility of both deadlock and starvation. Write (at least) a paragraph describing your strategy. Write a second paragraph to justify why your strategy works. You can get partial credit if you devise and describe a strategy which prevents either deadlock or starvation, but not both.
Extra Credit: Extra credit will be given to strategies which are free of both deadlock and starvation and are also efficient, that is, does your strategy make good use of the available chopsticks? Your strategy is not efficient if it prevents a philosopher from eating when the right and left chopsticks are available. If you believe your strategy is efficient, write a paragraph to justify this.
You should submit your assignment only after you have viewed it using a web browser, just to make sure your formatting looks okay. You can view your file using Internet Explorer by selecting File->Open from the menu bar, clicking Browse, and selecting your acpub account on the P: drive. Make sure to explain and answer all the questions for each strategy.
submit_cps001 lab9/sec# lab9-solutions.html