CSE 221: Homework 2   (Winter 2016)

Hardcopy due Tuesday, February 16, 2015 at the start of class

Answer the following questions. For questions asking for short answers, there may not necessarily be a "right" answer, although some answers may be more compelling and/or much easier to justify. But I am interested in your explanation as much as the answer itself. Also, do not use shorthand: write your answers using complete sentences.

When grading homeworks, we will grade one question in detail and assign full credit for answers to the others.

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

2. The Levy and Lipman paper on VAX/VMS virtual memory management states that the stack used by the operating system for servicing user process system calls (running in kernel-mode) resides in the user-level address space (the typical practice today is to allocate such a stack in the OS address space):

   "The P1 region [user address space] also contains fixed-sized stacks for use by executive code that executes on behalf of the process." (p. 37)

   This arrangement means that the user-level process has access to the memory region storing stack frames used by the kernel, including local variables with pointers to kernel data structures on the stack as well as return addresses that control where the kernel will execute when returning from a procedure call. Assume such stacks are mapped with read/write access in the user-level address space.

   1. Why do you think they allocated kernel stacks in the user-level portion of the address space?
   2. Why is this arrangement safe (does not violate user/kernel protection) given the process model described in the VAX/VMS paper?
   3. Modern operating systems like Linux allocate kernel stacks in the address space of the OS. Why is it necessary to do so to maintain safety?

3. We have read a number of different papers that describe systems that attempt to make effective use of cluster computer resources, including Sprite, GMS, and the Google Cluster Architecture. Answer each of the questions below in the context of all three designs.
   1. Reliability. What would happen if a memory chip failed in one of the machines? In particular, what is the worst case ramification of such a failure for users of the cluster?
   2. Scale. What data structures and mechanisms would be impacted if the system were deployed on a cluster of 100,000 nodes? Would it be likely to be successful?
   3. Performance. Suppose that you could dramatically improve one particular hardware component in the cluster (e.g., CPU speed, memory size, network speed, etc.) without impacting the cost. Which hardware component would be most helpful to improve?

---