CSE 120 -- Homework #2

Out: 10/12/00
In: 10/19/00 10/24/00

  1. Chapter 5, Section 5.18: 1, 8
  2. What resources are used when a thread is created? How do they differ from when a process is created?
  3. What are the differences between user-level threads and kernel-level threads? Under what circumstances is one type better than another?
  4. 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 *) {
      ...
    }
    
  5. [Silberschatz] 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 of the chairs are occupied, then the customer leaves the shop. If the barber is busy, but chairs in the waiting room 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 customers.
    ...shared variables...
    
    void Barber () {
      ...
    }
    
    void Customer () {
      ...
    }
    
  6. [Chase] This problem asks you to implement an Event class 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.

    Implement Event using a 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 () {
        ...
      }
      void Wait () {
        ...
      }
    }
    


voelker@cs.ucsd.edu