Due Date: January 16, 2000
Answer: The critical observation is that even if the layer needs no privileged instruction to emulate an instruction in the next upper layer, it needs to return control to that layer, and this returning is a privileged instruction.
Given that, the following diagram summarizes what happens:
When the compiler tries to execute an instruction, it traps; this trap is acted upon by the lower virtual kernel (1). It determines that the instruction was not privileged, and returns control to the upper virtual kernel (2). That also determines the instruction is not privileged and tries to return control to the operating system; that being a privileged instruction, it traps to the lower virtual kernel (3). The lower virtual kernel updates the upper virtual kernel to make it appear that that layer successfully executed the privileged instruction, and then returns control to that layer. In doing so, control actually passes to the next upper layer, which is the operating system (4). This determines the instruction is to be emulated, and does so. No privileged instructions are involved. It then tries to return control to the compiler, and in doing so executes a privileged instruction.
The operating system therefore causes a trap to the lowermost virtual kernel (5), which determines that the instruction was privileged; then the lower virtual kernel updates the upper virtual kernel to make it appear that that layer successfully trapped the privileged instruction (that is, the operating system trapped to the upper, rather than the lower, virtual kernel), and then returns control to that layer (6). That layer determines that the operating system tried to return control to the compiler, and updates the operating system to make it appear that the operating system had done so. It then tries to return control to the operating system (and hence to the compiler); but this traps to the lower virtual kernel, as the instruction is privileged (7). The lower virtual kernel updates the upper virtual kernel to make it appear that that program had correctly executed the privileged instruction; it then returns control to the upper virtual kernel, which has caused control to be passed to the operating system, which has caused control to be passed to the compiler (8).
That means the lower virtual kernel executes 4 "return control" instructions, the upper virtual kernel 2, and the operating system 1. (In the diagram, each line following a short straight line represents an attempt to execute a privileged call.)
c4 := 2; c6 := 2; S1; fork p1; S3; fork p2; S5; goto p4; p1: S2; goto p2; p2: join c4, p3; quit p3: S4; p4: join c6, p5; quit p5: S6 quit
The precedence graph is the following:
For the precedence graph to be properly nested, it must have a sequential or
parallel "innermost block". If it has a sequential innermost block,
there will be some subgraph with an edge connecting two vertices. The source
vertex will have one outgoing edge, and the destination vertex will have one
incoming edge. No such subgraph of the above precedence graph exists. If the
graph has a parallel innermost block, there will be some subgraph like:
In this subgraph, the vertices corresponding to B and C must have exactly one incoming edge (from the same source) and one outgoing edge (to the same destination). Checking the above precedence graph, we see there is no subgraph with this format. Hence the subgraph is that of a program that is not properly nested. Thus the original program is not properly nested and so cannot be written using parbegin ... parend.
waituntil x < 0 or y + z < nThe signal primitive would no longer be needed.
1 buffer: monitor; 2 var slots: array [0..n-1] of item; 3 count, in, out: integer; 4 procedure entry deposit(data: item); 5 begin 6 waituntil count <> n; 7 slots[in] := data; 8 in := in + 1 mod n; 9 count := count + 1; 10 end; 11 procedure entry extract(var data: item); 12 begin 13 waituntil count <> 0; 14 data := slots[out]; 15 out := out + 1 mod n; 16 count := count - 1; 17 end; 18 begin 19 count := 0; in := 0; out := 0; 20 end.
The idea is the same; the only difference is that the monitor checks whether the buffer is full in deposit (line 6), or empty in extract (line 13), by looking at the value of the count variable directly instead of waiting for signals to indicate that the appropriate condition is satisfied.
var x_waiting: integer, x_signaled: boolean;They are initialized as follows.
x_waiting := 0; x_signaled := false;Each occurrence of x.wait is replaced with
x_waiting := x_waiting + 1; waituntil x_signaled; x_signaled := false;Each occurrence of x.signal is replaced with
if x_waiting > 0 then begin x_waiting := x_waiting - 1; x_signaled := true; end;Thus, waituntil is at least as general as Hoare's scheme.
Conversely, we can implement waituntil using wait and signal as follows: for each statement of the form
waituntil exprwhere expr is a boolean expression of variables x1, x2, ..., xn, we make a new condition variable x. We replace the waituntil statement with
if not expr then x.wait;After every statement in the monitor that assigns one of the variables x1, x2, ..., xn, we insert
if expr then x.signal;
Thus, waituntil is equivalent to Hoare's scheme, not more general, since each can be expressed in terms of the other.
Office: 3059 Engineering Unit II Phone: +1 (530) 752-8060
Fax: +1 (530) 752-4767
|Copyright Matt Bishop, 2001. All federal and state copyrights reserved for all original material presented in this course through any medium, including lecture or print.|