CSE 221: Homework 2

Winter 2006

Due: Monday, March 20, 2006 at noon

  1. Consider the V system, and a client that reads a file F sequentially. The file is not initially cached; the data needs to come from the disk. The file is 4,000 blocks long. The blocks are not necessarily arranged sequentially on disk.

    Assume that the disk block size for the disks on a file server was increased by a factor of four. The file size remains the same, the file is read one block at a time, and, even with the larger block size, a single ReplyWithSegment is used to transfer the block of data. In qualitative terms, what would be the effect on the client's execution time in reading file F (again, not cached)?

  2. In 1999, Wang et al. proposed a disk drive architecture supporting a service called "eager write". Rather than update a block in place, as with normal disks, an eager writing disk simply writes to the next free block near the disk head (the disk internally keeps track of this mapping by maintaining a table mapping "logical" disk blocks to physical disk blocks). Argue whether using such a disk would improve the performance of a Log-Structured File System, hurt its performance, or make little difference.

  3. Many of the papers we have read can be placed into one of two categories: papers that attempt to virtualize a resource to provide transparency to the underlying implementation, and papers that attempt to expose a resource to allow applications to improve their performance. For the following systems, describe which resource is virtualized or exposed and what they hoped to accomplish by doing this:

    1. Scheduler Activations
    2. GMS
    3. Exokernel
    4. Sprite

  4. The Hoare Monitors paper describes assertions before and after the operations wait and signal in terms of the monitor invariant I and condition B.

    (a) Describe similar assertions for wait and signal using Mesa monitors and briefly explain why.

    (b) The Mesa Monitors paper describes how programmers should test and wait for conditions using Mesa monitors:

    while ( ... )
       [3] b.wait [4]

    Considering the code snippet above, create a table with five rows corresponding to the five placeholders in the code and two columns corresponding to the invariant I and condition B. For each entry in the table, write "hold", "!hold", or "unknown" depending upon what can be assumed about the invariant or condition, respectively, at each point in the code snippet.

  5. [Chase] Many implementations of Sun's Network File Service (NFS) use the following Work Crew scheme on the server side. The server node's incoming network packet handler places incoming requests on a shared work queue serviced by a pool of server threads. When a server thread is idle (ready to handle a new request), it examines the shared queue. If the queue is empty, the server thread goes to sleep. The incoming packet handler is responsible for waking up the sleeping server threads as needed when new requests are available.

    (a) Show how to implement the NFS server-side synchronization using a monitor with Mesa semantics. For this problem you may assume that the incoming packet handler is a thread rather than an interrupt handler.

    (b) Early NFS server implementations used broadcast as a wakeup primitive for the server threads, because no signal primitive was available in Unix kernels at that time (around 1985). This was a common performance problem for early NFS servers. Why is signal more efficient than broadcast here?