CSE 120 -- Homework #2

1. Chapter 2: 8, 11, 21, 26, 35, 38, 50
2. 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 *) {
     ...
   }
   

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

4. [Silberschatz] 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?
   • Multilevel feedback queue and RR.
   • Multilevel feedback queue and FCFS.
   • Priority and FCFS.
   • RR and SJF.