begin
int i;
procedure x( int a );
begin
i := i + 3; comment -- this makes i = 4 and a = 4 + 2 = 6
i := i + a;
end x;
i := 1;
x( i + 2 );
print i;
end;
The output of this code depends on how the parameter a is passed to the
function x. Pass by reference can't be used because the actual parameter
is an expression. Pass by value would produce the output 7. Pass by name
produces an output of 10 because the actual parameter is not evaluated
until it is actually used in the body of x. To implement this pass-by-name
semantics, this code is rewritten as follows, by the compiler:
begin
int i;
procedure x( int function athunk );
begin
i := i + 3;
i := i + athunk;
end x;
i := 1;
begin
int function thunk;
begin
return i + 2;
end thunk;
x( thunk );
end;
print i;
end;
(Note: I haven't programmed in Algol 60 since around 1971, so the syntax
used above is approximate.)
Note that use of thunks for parameters that may both be evaluated and and assigned to requires passing two thunks. Thus, if f(x) ever assigns a value to x, f(a[i]) will require a pair of thunks to be passed, one to assign values to a[i] and one to inspect the value of a[i].
Since the time thunks were first suggested as a tool for implementing pass-by-name semantics, they have been applied to many other problems. For example, in Microsoft's Windows operating system family, thunks are used to pass parameters to many system calls. Here, the thunk serves to hide the caller's operating mode from the called system function (the x86/Pentium family of machines supports many memory models, and passing a thunk that knows the caller's memory model is more efficient than passing a pointer along with an indication of what model should be used).
A question: Consider the problem of passing parameters by reference to a remote procedure. How can thunks be used in this context?
A more elaborate question: How would you implement a call to a method of an object in Amoeba, where the intended semantics of the call requires that one of the parameters be passed by reference. Your answer is likely to involve thunks. I strongly suggest that you reduce your answer to detailed pseudocode.
cc = nb_read(d, buf, nbytes, done, p)
int cc, d;
char *buf;
int nbytes;
int (*done)(int dcc, void * p);
void * p;
Nb_read() operates exactly like the standard read() system call, except that
it never blocks. Instead, the read operation will take place asynchronously
with the calling process, and when the read operation finishes, termination
will be signalled by a call to (*done)(p). The first 3 parameters are exactly
the parameters used for a normal call to read(); the last two are only used
for termination.
If the standard read() routine would not have blocked, (*done)(0,p) is called immediately, prior to the completion of the return from nb_read(). In this case, cc gives the character count, and dcc is zero.
If, on the other hand, the standard read() routine would have blocked, nb_read() returns the number of characters read prior to the time read() would have blocked, and (*done)(dcc,p) is called asynchronously, after nb_read() has returned, at the time read() would have been unblocked. In this case, the parameter dcc to (*done)() gives the delayed character count such that the sum dcc+cc gives the character count that a normal blocking read() would have returned.
A Question: How would you implement nb_read() as a kernel call? Specifically, what goes in the I/O queues, what code in the kernel calls (*done)(), and how is this call accomplished?
Another Question: How would you use nb_read() to implement thread_read(), as required in Homework 11? Recall that thread_read() has the semantics of the standard blocking read() kernel call, except that it is the user-level thread that is blocked, not the whole process. In thinking about this, you must consider what the done() function parameter does, and you must find an appropriate use for the parameter p.
A good solution to this second question will eliminate the polling loop from the solution given to the homework problem, and it will make effective use of the thread scheduler to wake up the blocked thread when the read completes.
Yet Another Question: Suppose your thread_read() routine is called when there is only one ready thread. What happens? My first solution to this problem incorrectly reported that there was a possible deadlock. If your solution would do this, how can you fix it so it operates correctly?
An elementary question What is the role of unique identifiers this broadcast protocol? (Note that multiple broadcasts may occur, possibly initiated by different machines in the network.)
Another elementary question This protocol computes an optimal spanning tree for the computer network. The structure of this tree is only stored temporarily. How is this tree represented, and with respect to what measurable attribute of the network has it been optimized?
A question In what sense is this protocol fault tolerant? What faults does it tolerate and what faults does it fail to tolerate?
An interesting problem Extend this protocol so that it performs an election.