CSE 221: Homework 0

Fall 2009

Due: Tuesday, October 6, 2009 at the start of class (3:30pm)

The purpose of this homework is to dust off your OS knowledge 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 entirely unfamiliar and are struggling to answer them, consider taking CSE 120 this quarter and CSE 221 in the winter.

1. 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. A common pattern in parallel scientific programs is to have a set of threads do a computation in a sequence of phases. In each phase i, all threads must finish phase i before any thread starts computing phase i+1. One way to achieve this synchronization pattern is with barrier synchronization. At the start of a phase, the program initializes a new barrier with the constructor Barrier::Barrier(n), where n is the number of threads in the parallel computation. A thread calls Barrier::Done when it completes the phase, blocking until all of the n threads have called Barrier::Done. Then all threads proceed.

   Sketch an implementation of a Barrier using pseudo-code. You may use either semaphores, or mutexes and condition variables.

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

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

4. Consider a UNIX-style inode with 10 direct pointers, one single- indirect pointer, and one double-indirect pointer only. Assume that the block size is 8K bytes, and that the size of a pointer is 4 bytes. How large a file can be indexed using such an inode?