CSE 120: Homework #3

Winter 2007

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.

   • Annabelle needs to use the dictionary and a thesaurus to write her paper;
   • Bertrand needs a thesaurus and a coffee cup to write his paper;
   • Chloe needs a dictionary and a thesaurus to write her paper;
   • Dag needs two coffee cups to write his paper (he likes to have a cup of regular and a cup of decaf at the same time to keep himself in balance).

   Consider the following state:

   • Annabelle has a thesaurus and need the dictionary.
   • Bertrand has a thesaurus and a coffee cup.
   • Chloe has the dictionary and needs a thesaurus.
   • Dag has a coffee cup and needs another coffee cup.
   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.