CSE 221: Homework 2

Winter 2009

Due: Tuesday, February 24, 2009 at 3:30pm in class

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

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

   Notes:
   • "..." means that arbitrary code could be here
   • [1] is immediately before the while loop starts
   • [2] is at the start of the body of the while loop
   • [3] is immediately before the wait, and [4] immediately after
   • [5] is immediately after the while loop

   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.

3. Keeping secrets

   Butler Lampson once gave a set of principles for system design. Among these, he gave two conflicting pieces of advice on the nature of implementations. He said, "Keep secrets of the implementation. Secrets are assumptions about an implementation that client programs are not allowed to make... Obviously, it is easier to program and modify a system if its parts make fewer assumptions about each other." And yet, "One way to improve performance is to increase the number of assumptions that one part of a system makes about another; the additional assumptions often allow less work to be done, sometimes a lot less." That is, on the one hand we should hide an implementation for ease of development, and, on the other, we should expose our implementations for speed. For example, Xen's paravirtualized x86 interface exposed the implementation of the hypervisor to its guest OSes, largely for speed, while Sprite's process migration took advantage of secrets in hiding the distributed nature of its implementation from processes subject to migration. GMS and Exokernel are two more systems which exemplified this advice. For these two systems, explain:

   1. Which advice of Lampson's did the authors follow? That is, describe the service that was implemented, and whether the authors chose to hide or expose in the implementation.
   2. Describe what was hidden or exposed in the implementation, and the software mechanisms that were used to do the hiding or exposing. Be specific.
   3. Give a concrete example of how the mechanisms above were used to hide or expose in the system.
   4. Describe one problem the authors had in utilizing their mechanism for their respective purpose, and how the authors dealt with that problem. Be specific.
   5. Given the quotes above, discuss the authors' goals in following the design principle they chose. Did they achieve them? Justify your answer.