Homework #3
Due Date: February 27, 2001 Points: 70
1. (20 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. (20 points) Show that in the Ricart-Agrawala algorithm, the critical section is accessed according to the increas-
ing 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 times-
tamps? Either show that it does or provide a counterexample. (text, problem 6.5, part 2, p. 149)