CSE 120 (Fall 2004) -- Homework #2

Out: 10/12
Due: 10/26

Chapter 4: 4.3
4.3 A DECSYSTEM-20 computer has multiple register sets. Describe the actions of a context switch if the new context is already loaded into one of the register sets. What else must happen if the new context is in memory rather in a register set, and all of the register sets are in use?
Chapter 5: 5.1, 5.2, 5.3
5.1 Provide two programming examples of multithreading that improve performance over a single-threaded solution.
5.2 Provide two programming examples of multithreading that do not improve performance over a single-threaded solution.
5.3 What are the differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?
Chapter 6: 6.8, 6.10
6.8 Many CPU scheduling algorithms are parameterized. For example, the RR algorithm requires a parameter to indicate the time slice. Multilevel feedback queues require parameters to definte the number of queues, the scheduling algorithms for each queue, the criteria used to move processes between queues, etc. These algorithms are thus really sets of algorithms (e.g., the set of RR algorithms for all time slices, etc.). One set of algorithms may include another (in lecture, we talked about using Priority Scheduling to implement SJF). What, if any, relation holds between the following pair of algorithms?
a. Priority and SJF.
b. Multilevel feedback queues and FCFS.
c. Priority and FCFS.
d. RR and SJF.
6.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
Chapter 7: 7.8, 7.9, 7.13
7.8 The Sleeping-Barber Problem. A barbershop consists of a waiting room with n chairs and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.
7.9 The Cigarette-Smokers Problem. Consider a system with three smoker processes and one agent process. Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobaccor, paper, and matches. One of the smoker processes has paper, another has tobacco, and the third has matches. The agent has an infinite supply of all three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then makes and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats. Write a program to synchronize the agent and the smokers.
7.13 Suppose that the signal statement can appear only as the last statement in a monitor procedure. Suggest how the implementation described in Section 7.7 can be simplified.
Chapter 8: 8.4
8.4 Consider the traffic deadlock depicted in Figure 8.8 (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.
The Intel x86 instruction set architecture provides an atomic instruction called XCHG for implementing synchronization primitives. Semantically, XCHG works as follows (although keep in mind it is executed atomically):
```
void XCHG(bool *X, bool *Y) {
  bool tmp = *X;
  *X = *Y;
  *Y = tmp;
}
```
Show how XCHG can be used instead of test-and-set to implement the acquire() and release() functions of the spinlock data structure described in the "Synchronization" lecture.
```
struct lock {
  ...
}

void acquire (struct lock *) {
  ...
}

void release (struct lock *) {
  ...
}
```
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) {
    ...
  }
  ...
}
```

voelker@cs.ucsd.edu