CSE 120 (Fall 2002) -- Homework #2

Out: 10/15
Due: 10/24
  1. 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?

  2. 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?

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

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

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

  6. 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 lock data structure described in the "Synchronization" lecture.

    struct lock {
    void acquire (struct lock *) {
    void release (struct lock *) {
  7. [Chase] This problem asks you to implement an Event synchronization primitive similar to the fundamental coordination primitives used throughout Windows NT. Initially, an Event object is in an unsignaled state. Event::Wait() blocks the calling thread if the event object is in the unsignaled state. Event::Signal() transitions the event to the signaled state, waking up all threads waiting on the event. If Wait is called on an event in the signaled state, it returns without blocking the caller. Once an event is signaled, it remains in the signaled state until it is destroyed.

    a. First implement Event using a monitor.

    monitor Event {

    b. Implement Event using an explicit mutex and conditon 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 Event {
      ...private variables...
      void Signal () {