# Homework #3

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

**Points**: 90

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

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

Send email to
cs251@csif.cs.ucdavis.edu.
Department of Computer Science

University of California at Davis

Davis, CA 95616-8562

Page last modified on 3/7/2000