CSE 221: Homework 0

Fall 2014

Due: Tuesday, October 7th, 2014 at the start of class (11am)




 The purpose of this homework is to dust off your OS skillz and
provide you with a mechanism for self-evaluation.  CSE 221 assumes
from the start that you are already familiar with the OS concepts in
these problems.  As such, you should feel relatively comfortable
answering them.  If, however, you find the concepts unfamiliar and are
struggling to answer them, you should likely take CSE 120 before
taking CSE 221. 



    


  1.  (Hardware/software interaction) Which of the following instructions should be privileged?  Very
briefly, why?
    
a) Set value of timer
    
b) Read the clock
    
c) Clear memory
    
d) Turn off interrupts
    
e) Switch from user to kernel mode
    


    

  2.  (Synchronization)

Microsoft .NET provides a synchronization primitive called a
CountdownEvent.  Programs use CountdownEvent to synchronize on the
completion of many threads (similar to CountDownLatch in Java).  A
CountdownEvent is initialized with a count, and a
CountdownEvent can be in two states, nonsignalled and
signalled.  Threads use a CountdownEvent in the nonsignalled
state to Wait (block) until the internal count reaches zero.
When the internal count of a CountdownEvent reaches zero, the
CountdownEvent transitions to the signalled state and wakes up
(unblocks) all waiting threads.  Once a CountdownEvent has
transitioned from nonsignalled to signalled, the CountdownEvent
remains in the signalled state.  In the nonsignalled state, at any
time a thread may call the Decrement operation to decrease the
count and Increment to increase the count.  In the signalled
state, Wait, Decrement, and Increment have no
effect and return immediately.


    

      


    1.  Use pseudo-code to implement a thread-safe CountdownEvent using
  locks and condition variables by implementing the following methods:


      class CountdownEvent {
  ...private variables...
  CountdownEvent (int count) { ... }
  void Increment () { ... }
  void Decrement () { ... }
  void Wait () { ... }
}

      


        


      •  The CountdownEvent constructor takes an integer
  count as input and initializes the CountdownEvent counter
  with count.  Positive values of count cause the
  CountdownEvent to be constructed in the nonsignalled state.  Other
  values of count will construct it in the signalled state.


      •  Increment increments the internal counter.


      •  Decrement decrements the internal counter.  If the counter
  reaches zero, the CountdownEvent transitions to the signalled state
  and unblocks any waiting threads.


      •  Wait blocks the calling thread if the CountdownEvent is
in the nonsignalled state, and otherwise returns.


      


      

    2.  Semaphores also increment and decrement.  How do the semantics
 of a CountdownEvent differ from a Semaphore?


      

    3.  Consider a common Barrier synchronization primitive with a
  constructor Barrier(n) and a method Done().  A group of
  n threads cooperate on a task.  After completing the task,
  they wait for each other before proceeding by calling Done.
  Once all threads have called Done, all threads on the Barrier
  wake up and return from Done.  Implement a Barrier using a
  CountdownEvent.


      class Barrier {
  ...private variables...
  Barrier (int n) { ... }
  void Done () { ... }
}

      


    




    

  3.  (Virtual memory) Consider when a process issues a read instruction to a virtual
address on page P in its address space.  Assume that the page
table entry (PTE) for P is not in the translation lookaside
buffer, that P has been paged out to disk, and that the process
has read permission on P.  Describe the steps taken by a modern
CPU and operating system to ensure that the read instruction
successfully completes.  State any assumptions you feel you have to
make, including whether you assume a hardware or software-managed TLB.


















savage@cs.ucsd.edu