CSE 221: Homework 2

Winter 2010

Due: Tuesday, March 2, 2010 at 9:30 AM 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. Exokernel and L4 represent contemporary approaches for providing protection and extensibility. Xen represents a contemporary approach for providing virtualization and isolation (or, alternately, is an extreme version of extensibility since it goes even beyond Exokernel in exposing the hardware interface to unprivileged code). Consider a Web server as a motivating application-level service running on each of these three system structures (indeed, Exokernel and Xen both use Web service in their performance evaluations).

   For each of the three systems, consider the path a network packet containing an HTTP request takes as it travels from the network interface card to a Web server process running at user level:

   1. Identify the various protection domains in the system for this scenario. Which domains are privileged, and which are unprivileged? (Feel free to draw "boxes-and-kernel-boundary" diagrams if you find them helpful.)

      For example, if the system were standard monolithic Linux, the protection domains would be the kernel and the Web server process with its address space. The kernel is privileged, and the server process unprivileged.

   2. Describe the journey of the packet as a sequence of steps through the protection domains identified above. For each protection domain crossing, state the communication mechanism used for that packet to cross protection domains.
   3. Argue which of these systems will likely provide the highest performance Web service without violating protection (e.g., not simply moving the Web server code into the kernel and running it in privileged mode). Justify your argument and be sure to state any assumptions you make.
   4. Further consider the Web server process triggering a page fault on a page in its address space. As with the network packet, trace the propagation of the page fault through protection domains. Which domain handles the page fault? Whose pool of physical memory is used to satisfy the page fault?

      For example, if the system were standard monolithic Linux, the CPU would raise an interrupt, halting the Web server process, and vector to a Linux kernel interrupt handler for page faults. The page fault handler would allocate a physical page from Linux's free physical page list and update the page table entry with the valid mapping. The Linux kernel would then return from the interrupt.