CSE 221: Homework 2

Fall 2005

Due: Section A (Marzullo): Wednesday, November 2, 2005 at the start of class (5pm)
Due: Section B (Voelker): Thursday, November 3, 2005 at the start of class (9:30am)

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. What would be the effect on the client's execution time in reading file F (again, not cached)?

2. Sprite and LOCUS are two systems that provide network file systems with improved performance, functionality, and reliability over popular network file systems today (NFS and Windows). Indeed, many new network file systems have been proposed over time that improve over what we use today. Given that users perceive longer delays when using networked file systems, and occasionally annoying failures, why do you think that we still use network file systems that do not have these additional optimizations and features?

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

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

   [1]
   while ( [2] )
   {
      [3]
      b.wait
      [4]
   }
   [5]
   

   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.

4. [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?