Homework #2

Due Date: February 1, 2001
Points: 60

1. (10 points) Number all the forks in the Dining Philosopher's problem and require that each philosopher request an even-numbered fork before an odd-numbered fork. Will this allocation strategy prevent deadlock and starvation? Is it a form of a well-known strategy (named in section 3.9.3)?
2. (15 points) Using the definitions given in class, prove that "S is not a deadlock state" does not imply that "S is a safe state."
3. (15 points) Assume a system has p processes and r identical units of a reusble resource. If each process can claim at most n units of the resource, show that the system will be deadlock free if, and only if, r >= p(n-1)+1 [text, problem 3.7].
4. (20 points) Prove Theorem 3.6.

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.