CS 414 Fall 2003: Homework 3 (due Sept. 30)

Please type your solutions.

1. Write a monitor solving the birdfeeder problem. There are n birds, and each bird corresponds to a process. The birds wish to feed at Professor Birman’s backyard bird feeder, which is a cylinder that has five small holes in the sides, each hole having an associated peg on which a single bird can perch. To feed, a bird flies through the air, then lands on one of the pegs sticking out from the feeder. Each peg has an associated “current bird”, or is “empty”.

The bird than feeds by eating one seed at a time, until one of the following events occurs: either the bird becomes full (each bird has a “capacity”, which is the number of seeds it can digest at one time), or a more aggressive bird comes and dislodges it from the feeder. (This is called the “pecking order.” Each bird has a rank, and if the rank of bird A is higher than the rank of bird B, A can dislodge B). A bird will not try to dislodge a bird ranked the same or higher than itself on the pecking order. A dislodged bird will fly around until it can land again and finish feeding. When full, a bird goes off somewhere to digest. Eventually, it may return to feed again.

Finally, the holes on the feeder are ordered from top to bottom. The top holes are preferred (for obvious reasons).

Your solution should include “pseudo-code” for the bird processes. We suggest that you use the following function or procedure names (depending, of course, on whether or not your solution requires that a result be returned): fly, try_to_land_on_perch, eat_a_seed, dislodged_check. You can add additional procedures or functions if needed.

2. Consider a city in which traffic flows into one-lane traffic circles (roundabouts). A car enters the circle from a side road, drives around it until a desired exit point, and then leaves on the exit road. As you are probably aware, sometimes a car wishes to continue around the circle just as some other car wants to enter the circle at the same spot. In such cases, one car must wait for the other. Moreover, when the circle is crowded, no car can move forward until the car in front of it moves forward.

a) Prove that deadlock can occur if cars entering the circle have priority over cars wishing to leave the circle.

b) Prove that deadlock cannot occur if cars leaving the circle have priority over cars wishing to enter the circle.

c) (not graded) What is unusual about Place Victor Hugo and the Etoile in Paris, France?

d) (not graded) Unlike in the United States, most streetcorner intersections in all of Belgium lack traffic lights or stop signs. If two cars are entering the same intersection on roads at right angles to each other, who has priority: the car “to the left” or the car “on the right”? (Hint for potential drivers in Belgium: even a little alley counts as a “road”)

3. To register for classes at Big Red University, students log onto a registration system one or more times. Each time they can add or drop courses until their schedule is satisfactory. They can also swap one course for another as a single “atomic” action; if successful, the student is dropped from one course and added to the other. The system may refuse to let a student add a course (or swap for it) if that course is too full (of course, if the same student checks back later, enrollment may have dropped and the situation could improve). Each student has his or her own goals: some students are interested in lots and lots of possible courses but others need to take very specific courses in order to graduate on time.

a) Is this system deadlock free? Explain.

b) Is the system livelock free? Again, explain.

c) Suppose that students Sally and Tom share a dog. The registrar doesn’t allow dogs, so while Sally is using the system, Tom takes care of the dog, and vice versa. Is the system still deadlock free? Explain.

4. In class on Thursday we saw that one way to prevent deadlocks is to establish some sort of ordering on resources, and then to only request resources in order. Suppose that you are building a system in which it isn’t totally clear what resources are needed until the execution is underway, but you are able to come up with a conservative estimate. Would your program be deadlock free if it requests all the resources it might need (in order) and then, once it has all of them, releases resources it turns out not to need after all? For example, the system could request resources A, B and C, and then while running, decide it doesn’t need B after all, and release B. Explain very briefly.