CSE 120: Homework #3

Winter 2007

Out: January 30
Due: February 6 at the beginning of lecture
  1. See Section 6.6.3 of the textbook for a description of the Dining Philosopher's Problem.

    You have been asked to review a paper that contains the following proposed solution to the Dining Philosophers problem for n > 1 philosophers. Unfortunately, the authors, being from a somewhat dubious institution, include no proof of its freedom from deadlock. They do state that Allocate(i) uses a first-come, first-served policy for allocation of chopstick i, and that chopsticks are not preemptable: once acquired, a chopstick i can only be released by having the owning process invoke Deallocate(i). The chopsticks and philosophers are numbered from 0 to n-1, and the function Even(i) is a predicate indicating whether the number i is even or odd (zero is considered even).

    Philosopher i:
        int first, second;
        if (Even(i)) { first = i; second = (i + 1) % n; }
        else { first = (i + 1) % n; second = i; }
        while (1) {
            Think;
            Allocate(first);
            Allocate(second);
            Eat;
            Deallocate(first);
            Deallocate(second);
            }

    Is this algorithm indeed a deadlock-free solution for any or all values of n > 1? For those values of n (if any) where it is deadlock-free, give an argument that shows this is the case. For those values of n (if any) where it is not deadlock-free, give an example execution leading to deadlock.

  2. Chapter 5: 5.7, 5.10

    5.7  Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context-switching overhead is 0.1 millisecond and that all processes are long-runing tasks. What is the CPU utilization for a round-robin scheduler when:

        a. The time quantum is 1 millisecond
        b. The time quantum is 10 milliseconds

    5.10  Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes:

        a. FCFS
        b. RR
        c. Multilevel feedback queues

  3. Chapter 7: 7.1

    7.1  Consider the traffic deadlock depicted in Figure 7.9 (see book).

        a. Show that the four necessary conditions for deadlock indeed hold in this example.
        b. State a simple rule that will avoid deadlocks in this system.

  4. A common pattern in parallel scientific programs is to have a set of threads do a computation in a sequence of phases. In each phase i, all threads must finish phase i before any thread starts computing phase i+1. One way to accomplish this is with barrier synchronization. At the end of each phase, each thread executes Barrier::Done(n), where n is the number of threads in the computation. A call to Barrier::Done blocks until all of the n threads have called Barrier::Done. Then, all threads proceed.

    a. Write a monitor that implements Barrier using Mesa semantics.

    monitor Barrier {
      ...
    }
    

    b. Implement Barrier using an explicit mutex and condition variable. The mutex and condition variable have the semantics described at the end of the "Semaphore and Monitor" lecture in the ping_pong example, and as implemented by you in Project 1.

    class Barrier {
      ...private variables...
      void Done (int n) {
        ...
      }
      ...
    }
    

  5. Consider a problem in which there is a producer p and two consumers c1 and c2. The producer produces pairs of values <a, b>. Consumer c1 consumes the a values of these pairs and c2 consumes the b values of these pairs.

    Write a Mesa-style monitor for this problem. It should have three entry methods: void Put(int a, b) that p would use to produce values, int GetA(void) that c1 would use to consume a values, and int GetB(void) that c2 would use to consume b values.

  6. Annabelle, Bertrand, Chloe and Dag are working on their term papers in CSE 120, which is a 10,000 word essay on My All-Time Favorite Race Conditions. To help them work on their papers, they have one dictionary, two copies of Roget's Thesaurus, and two coffee cups.

    Consider the following state:

    1. Is the system deadlocked in this state? Explain using a resouce allocation graph.
    2. Is this state reachable if the four people allocated and released their resources using the Banker's algorithm? Explain.


marzullo@cs.ucsd.edu, voelker@cs.ucsd.edu