CSE 221: Homework 0

Winter 2013

Due: Thursday, January 10, 2013 at the start of class (8am)

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.

(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
(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 () { ... }
}
```
(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.
(File systems) The Unix kernel routine that performs path name resolution is called namei. namei takes as input a path name and returns the location on disk of the inode for the last element of the path.
To speed up path name resolution, namei uses a cache of previously resolved paths. When resolving a path, namei caches all prefixes of the path as well. For example, when resolving "/one/two", namei will cache resolutions for "/", "/one", and "/one/two". Furthermore, when resolving a path name, namei will match in its cache the longest prefix of the path name that it can before making disk requests. For example, if "/one" is in the cache and namei needs to resolve "/one/two", it will start with the cached value for "/one" to resolve "/one/two". For the problems below, you may assume that the master block is already in memory and no disk I/O is required to read it. Further assume that all directories and files are one block in size.
1. Assuming that the namei cache is empty, succinctly describe what steps Unix will take, in terms of the disk data structures it must read, in order to resolve the path name "/a/b/c" and read the first byte of the file "c". How many disk reads are required?
2. Assuming "/a/b/c" has been resolved previously, now describe the steps Unix will take to resolve "/a/b/x" and read the first byte of the file "x". How many disk reads are required?
3. A common use of the command "grep" is to search all files in a directory for a string. Assume that the directory "/a/b" has n files. Assuming further that the namei cache starts out empty, how many disk reads are required to search all files using "grep /a/b/*"? State your answer as an expression involving n.
4. Now assume that we are using a file buffer cache as well. The file buffer cache will keep in memory all file, directory, and inode blocks that have been previously accessed. When they are accessed again, no disk I/Os are required. Assuming that both the file buffer cache and the namei cache start out empty, how many disk reads are required for the grep command in the previous problem now that we are using a file buffer cache as well?
5. Ignoring the issue of space (cache capacity), describe an example situation when an entry in the namei cache should be invalidated?

voelker@cs.ucsd.edu