CSE 221: Homework 2

Fall 2014

Due: Thursday, Dec 2, 2014 at 11am in class

1. GMS Design

   In the GMS paper, only "clean" pages are written to global memory ("dirty" pages must be written to disk before they can participate in the GMS pool).

   1. Why did GMS chose this restriction? What problem does it solve?
   2. Describe how you might change GMS to safely allow it to write dirty pages to global memory.

   Similarly, it is assumed that all nodes in the GMS workstation cluster are trusted.

   1. Why does GMS require trusted nodes? What risks would be exposed by an untrusted node?
   2. Describe how you might change GMS to work with untrusted nodes?

2. Transparency vs optimization

   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 (transparency), and, on the other, we should expose our implementations for speed (optimization).

   Consider this issue for each of the following three systems -- Sprite, Xen, Grapevine. For each system:

   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.

3. Lazy evaluation

   When implementing some service a common tradeoff is between "eager evaluation" -- performing an action immediately when it is requested (hopeing to amortize that cost against future accesses) and "lazy evaluation" -- defering the requested action until some later point in time (assuming that it will cost less or may not need to be done in the future). What choice to make depends both on the cost of the operation and the expected workload. For each of the following systems, identify an important operation that uses eager or lazy evaluation as an optimization, explain what the operation is and what the required semantics are for it to be correct, decribe how the implementation is eager or lazy (including any mechanisms used to ensure correctness) and why this is expected to provide an optimization in the common case. Finally, decribe a workload scenario in which this implementation will not be an optimization.

   1. Mach
   2. Exokernel
   3. Xen
   4. Vax/VMS