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 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)

Matt Bishop Office: 3059 Engineering Unit II Phone: +1 (530) 752-8060 Fax: +1 (530) 752-4767 Email: bishop@cs.ucdavis.edu

Copyright Matt Bishop, 2001. All federal and state copyrights reserved for all original material presented in this course through any medium, including lecture or print.