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.
- 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:
while ( ... )
 b.wait 
- "..." means that arbitrary code could be here
-  is immediately before the while loop starts
-  is at the start of the body of the while loop
-  is immediately before the wait, and  immediately after
-  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.
- 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.
Why do you think they allocated kernel stacks in the user-level
portion of the address space?
Why is this arrangement safe (does not violate user/kernel protection)
given the process model described in the VAX/VMS paper?
Modern operating systems like Linux allocate kernel stacks in the
address space of the OS. Why is it necessary to do so to maintain
- 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.
- 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?
- 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?
- 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?