- 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.
- 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:
- 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.
- Describe what was hidden or exposed in the implementation, and the
software mechanisms that were used to do the hiding or exposing. Be
specific.
- Give a concrete example of how the mechanisms above were used to hide
or expose in the system.
- Describe one problem the authors had in utilizing their mechanism for
their respective purpose, and how the authors dealt with that problem.
Be specific.
- Given the quotes above, discuss the authors' goals in following the design
principle they chose. Did they achieve them? Justify your answer.
- 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:
- 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.
- 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.
- 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.
- 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.