Homework #3

Due Date: Wednesday, March 15, 2000 at 11:59PM
Points: 90

1. (30 points) Show that in Lamport's algorithm the critical section is accessed according to the increasing order of timestamps. (text, problem 6.7, p. 149)
2. (30 points) Show that in the Ricart-Agrawala algorithm, the critical section is accessed according to the increasing order of timestamps. (text, problem 6.5, part 1, p. 149)
3. (30 points) On p. 145, the text discusses the greedy strategy for Raymond's tree-based algorithm, and notes that it can cause starvation. Please give an example of the application of this algorithm to a situation in which the greedy strategy causes starvation, but the regular algorithm does not.

>Extra Credit

4. (30 points) Does Maekawa's algorithm access the critical section according to the increasing order of timestamps? Either show that it does or provide a counterexample. (text, problem 6.5, part 2, p. 149)