# 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.

• 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.
```
```

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