CSE 120: Homework #3

Spring 2009

1. (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
   

2. (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. (7.1)  Consider the traffic deadlock depicted in Figure 7.9 in the 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. You may assume that the process allocates a new Barrier for each iteration, and that all threads of the program will call Done with the same value.

   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) {
       ...
     }
     ...
   }
   

   c. A more socially conscious implementation of the Mating Whale problem in the first Nachos project would allow any three whales that call their respective Whale methods to mate. Solving this form of the problem is very straightforward using a Barrier. Implement the Whale class with these semantics using a Barrier, where the Male, Female, and Matchmaker methods in Whale simply make a call to a Barrier. (Hint: The implementation should be trivial.)

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>. The producer does not have to wait in Put for a consumer, and the monitor will have to accumulate the values in auxiliary data structures to ensure nothing gets lost (you can assume the use of lists or arrays). Assume that Put can accumulate at most k pairs of values. Consumer c1 consumes the a values of these pairs and c2 consumes the b values of these pairs. A consumer consumes only one value per call.

   Hint: This problem is very similar to the producer/consumer problem — it just so happens that objects are produced in pairs, and each part of a pair is consumed individually.

   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. For synchronization, you should only use condition variables.

   An example sequence of calls could be:

   Put(10,20)
   GetA() -> returns 10
   Put(300,400)
   GetA() -> returns 300
   GetB() -> returns 20
   GetA() blocks the caller
   

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.