Homework #1

Due Date: Tuesday, February 8, 2000 at 11:59PM
Points: 100

  1. (20 points) The following table shows domains and ranges for a system of processes along with known precedence constraints:
    process p1 p2 p3 p4 p5 p6 p7
    domain v5       v1, v7 v4       v4, v8 v2       v3       v4      
    range v4, v7 v5 v6 v2 v1, v3 v5 v5, v8
    preceded by   p1 p1 p2 p3 p3 p4, p6
    Add the minimum number of precedence constraints to make this system of processes determinate. Do not remove any constraints.

  2. (26 points) For a semaphore s, define:
    init[s] is the initial value of s;
    start_down[s] is the number of times down(s) has been started;
    end_down[s] is the number of times down(s) has been completed; and
    end_up[s] is the number of times dowupn(s) has been completed.
    A useful semaphore invariant is:
    end_down[s] = min(start_down[s], init[s] + end_up[s]);
    Show that
    0 < end_down[empty] - end_down[full] < n
    for the version of the producer-consumer solution using semaphores in the handout Process Synchronization and Communication, p. 11.

  3. (14 points) Indicate how each of the following items could be incorporated in the monitor mechanism (a sentence or two for each is sufficient; you do not have to show an implementation).
    1. type of request
    2. times at which the requests were made
    3. request parameters
    4. process information
    5. priority relation
    6. local state of resource
    7. history information

  4. (20 points) Show that the ordered request policy of Havender prevents deadlocks (text, problem 3.4).

  5. (20 points) 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.

Extra Credit

  1. (10 points) (Tanenbaum) Cinderella and the Prince are getting divorced. To divide their property, they have agreed on the following algorithm. Every morning, each one may send a letter to the other's lawyer requesting one item of property. Since it takes a day for letters to be delivered, they have agreed that if both discover that they have requested the same item on the same day, the next day they will send a letter cancelling the request. Among their property is their dog, Woofer, Woofer's doghouse, their canary Tweeter, and Tweeter's cage. The animals love their houses, so it has been agreed that any division of property separating an animal from its house is invalid, requiring the whole division to start over from scratch. Both Cinderella and the Prince desperately want Woofer. So they can go on (separate) vacations, each spouse has programmed a personal computer to handle the negotiation. When they come back from vacation, the computers are still negotiating. Why? Is deadlock possible? Starvation? Discuss.

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 1/26/2000