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.