Background: In class we have learned about how operating systems manage processes and provide the user with a virtual environment for computing. Processes are programs that are running, often simultaneously (like your internet browser and a text editor, for example). The operating system acts as the "boss" over competing processes that are often in contention for resources, like memory, processor time, or a shared data structure. Processes are running simultaneously, yet often only one process can have a certain resource at a time. Part of the operating system's job, then, is to decide a strategy for giving access to these resources.
Tasks: In this lab you will learn about the consequences of picking certain strategies for giving access to shared resources to competing processes. You will learn about a very famous model of processes and resources, called the dining philosophers' problem. 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.
Objectives:
The following scenario was given as a metaphor for concurrency problems by Dijkstra in 1965. Five philosophers are sitting at a round table. They each have a plate of spaghetti in front of them, but only one fork. Unfortunately, the spaghetti is slippery and they would need 2 forks to be able to eat it.
Each philosopher spends his/her dinner hour alternately thinking and eating. When the philosopher gets hungry, he/she tries to acquire both forks (one at a time) and then eat. After awhile, he will put down the forks and think for awhile until he is ready to eat again.
Most of the time this problem is restated slightly with chopsticks and rice, because it is more believable that one cannot eat rice with just one chopstick. Also, the rice bowl is often put in the middle of the table to emphasize the idea of shared resources. Remember that there are 5 diners but only 5 chopsticks. Therefore, we have the following setup:
In this problem, the chopsticks are shared resources and the philosophers are concurrent processes. Suppose that two adjacent diners get hungry at the same time. They both need the same chopstick in order to be able to eat, and this is an example of a race condition. The first diner to grab the chopstick gets to eat, the other must wait.
Problems:
Now you will pretend to be the philosophers in the problem and compete for resources. We can't very well eat with the same utensils here, so instead of eating, you will be picking up the objects on the table. You cannot, however, pick them up with your hands, you must grab them with two utensils. Each of you must decide when you want to grab and when you want to think. When you want to grab, you must follow protocol for obtaining the shared resources. (No matter what the rules for the specific problem, a diner may never pick up both utensils at once. You must always do one at a time.) You will try different strategies and study what could happen when following that strategy. 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. Therefore, while you are thinking, please return the items that you grabbed if the supply is low.
Strategy 1) Each time someone wants to grab, he first must get the left utensil, then the right. You may not reach for both at once! If the utensil you want is gone, just wait until it is put down again. Once you have both, grab for awhile, then put down the left utensil and then put down the right utensil. Then think for awhile. When you want to grab again, repeat the cycle. Try not to let the availability of utensils influence how long you grab or how long you think. Try this strategy for awhile and see if it works well. Write a couple of sentences about your experience.
When there is a situation such that everybody is waiting on someone else, and no one can do anything, this is called a dealock situation. For example, suppose that everyone has one utensil and is waiting for the other. The system is then deadlocked. Explain a way in which a system using strategy 1 could deadlock.
Strategy 2) Number yourselves in order around the table. Pick someone as "1" and then number around to the last person. For this strategy, everyone with an odd number will follow Strategy 1, and everyone with an even number will do as follows: when you want to grab, first try to get the right utensil then the left. When you have both, you may grab. When you are done, put down the right then the left utensil. Try this strategy and see if it works well. Write a couple of sentences about your experience.
Does this strategy eliminate the possibility of deadlock? Explain.
Some strategies are undesirable because it is unfair to some process. If there is one or more process that is denied access to some resource for a long time, the strategy is said to cause starvation. In the diners example, a starvation scenario really would cause someone to starve! Explain a way in which a system using this strategy could cause starvation.
Problem) Come up with a new strategy for the diners. You may use numbering strategy as in strategy 2, an extra variable, or just about anything else that you think would be useful in solving the problem (if you're not sure, ask!). You will get full credit if your strategy does not cause deadlock or starvation.
Questions:
Questions marked with (*) are asking for your informed opinion. They will not be judged as right or wrong, but simply given credit for the amount of thought put into the answer. Questions marked with (!) are essential to showing your understanding of the material and will be worth more.
( Theoretical)
1. Suppose that there are many, many processes that are competing
for one or two resources. Is the performance of the system affected?
How?
(Virtual !)
2. Sometimes the operating system manages processes that are of differing
importance. It may be that the priority of the process running should
be taken into account when allocating resources. (For example, there
could be two processes running on a spaceship's computer. One controls
the trajectory of the ship, and the other controls the air conditioning
on the ship. Which should get more processor time?) Describe
a change to the model that includes a bias toward higher priority processes
without starving the other processes.
(Theoretical)
3. Suppose that many processes are sharing one resource, a phone list.
Some processes, called readers, only look up phone numbers, they never
change them. Other processes, called writers, may look up numbers,
but may also change the numbers. How many readers should be allowed
access to the phone list at once? How many writers should be allowed
access to the phone list at once? How many readers should be allowed
access to the phone list while a writer has access?
(Social *) 4.
The idea of having many things going on at the same time is known as multi-tasking.
This idea has infiltrated many parts of our daily lives. For example,
when is the last time that you ate without also watching TV or talking
on the phone? Have you ever walked into a room and been so engrossed
in another thought that you forgot why you went there? Give other
examples of daily multitasking. Do you think that society encourages
us to multitask? How? Do you think this is a good or bad phenomenon?
How hard would it be for you to do only one thing at a time?
(Philo-Ethical)
5. Sometimes viruses attack the operating system and sabotage the
strategy being used for resource allocation. Describe how this can
wreak havoc on your system.
(Technical
!) 6. The operating system has the responsibility to protect
shared resources from misuse (like insuring that your friends do not hog
the utensils!) In some cases, the consequences of misuse can be such
that the shared data is corrupted.
For example, suppose that Mr. Jones goes to the ATM to deposit $100.00 into his account, that currently contains $1,000.00. At the same time, the bank's interest program is adding 1% interest into the account. The following portions of code are run, where JONES_ACCOUNT is stored in one place that is shared by both processes: (The lines are marked for reference only, and do not indicate order.)
| ATM code: | Interest calculator code: |
| :
A) int amount = JONES_ACCOUNT; B) amount = amount + 100; C) JONES_ACCOUNT = amount; : |
:
d) int current = JONES_ACCOUNT; e) current = current * 1.01; f) JONES_ACCOUNT = current; : |