**Due Date**: Thursday, March 23, 2000 at 6:00PM (the end of the
reglar final exam period for this class)

**If you want to submit this electronically, please email it to me at
bishop@cs.ucdavis.edu.**

- Suppose that, instead of a first-come
first-served semaphore queueing discipline, queueing is last-come,
first-served. However, we still want to implement
*safe*mutual exclusion for the critical sections of*n*cyclic processes.*Safe*means that no process can block indefinitely while other processes cycle arbitrarily often. For example, processes*p*_{1}and*p*_{2}can block*p*_{3}forever if*p*_{3}arrives second and*p*_{1}and*p*_{2}cycle alternately through their critical sections.Consider a binary tree with

*n*leaves, one for each process. Each internal node has an associated semaphore. The processes desiring to enter their critical sections perform down operations on successive semaphores from their leaves to the root of the tree, execute their critical section, and perform up operations in reverse order back down the tree.- Show this scheme implements safe mutual exclusion.
- Discuss how the shape of the binary tree can affect the relative speeds of the processes and enforce a priority scheme.

- This problem asks you to apply a
modification of Havender's ordered resource policy to processes, rather
than resources. Given that the mutual exclusion, hold and wait, and no
preemption conditions are in place, consider the following strategy:
All processes are given unique priorities. When more than one process
is waiting for a resource and the resource becomes available, allocate
the resource to the waiting process with the highest priority. Either
prove this prevents deadlock or give an example in which this strategy
does not prevent deadlock.
- Use Holt's graph-based model to prove
that the collective requests policy, in which a process requests and
acquires all its needed resources at once, prevents deadlock.
- Prove that Maekawa's distributed mutual
exclusion algorithm prevents deadlock.
- Show that Byzantine agreement cannot
always be reached among four processors when
*two*processors are faulty.

Send email to cs251@csif.cs.ucdavis.edu.

Department of Computer Science

University of California at Davis

Davis, CA 95616-8562