client server ------ ------ ... ... send receive (service request) [wait] [do requested service] receive send (back results) ... ...
in statement.
For example:
in name1(a, b, c) returns d st condition1 -> d := a + b - c [] name2(x, y) st condition2 -> save := x * y [] name3(z) returns q -> q := compute(z) ni
Here is the bounded buffer object (resource) implemented with an
in statement instead of with semaphores.
Replace the other resource with this one.
The rest of the program (driver, producer process, consumer process)
remains unchanged, one of the strengths of the SR language.
Bounded Buffer Using Rendezvous.
Here is a replacement dining philosophers server resource implemented
with the in statement.
Dining Philosophers Using Rendezvous.
Ditto the database readers and writers.
Readers and Writers Using Rendezvous.
in Statementsin statements, as is done in this
example program simulating bank deposits and withdrawals.
When a large withdrawal comes along, a nested in accepts only
deposits until the balance is high enough to allow the large withdrawal.
This prevents large withdrawals from starving, from being blocked for
an arbitrarily long time, while smaller withdrawals are processed.
This example also shows that an in statement
can have an else clause; it is executed if there are no
calls to named branches of the in with true guards.
An op can be implemented with multiple in
and receive statements, as this example shows.
SR Program: Multiple ins Implementing an op.
? Function?
that can be used with the in
statement.
When ? is applied to an operation name,
it returns the number of outstanding (unserviced) invocations of that operation.
This can be used in such-that (st) clauses on the operation names
implemented in the in statement to give priority to one name over
another.
For example we could modify the outer in statement in the
nested-in example program to be
# priority to servicing invocations of increment over decrement
in increment(amount) ->
...
[] decrement(amount) st ?increment = 0 ->
...
ni
Then an increment would be given priority
since no decrement could be accepted
if there were an outstanding increment invocation.
? function.
in statement's invocation queue
each time the in statement is invoked (called or sent to)
and each time the in statement is executed
(for example, it might be inside a `do forever' loop).
However, the guards are not automatically re-evaluated
each time any variable in the boolean-valued expression
comprising the guard changes value,
unless that variable is changed inside a branch of the in
statement and the in is executed again because it is
inside a loop.
So, an in statement may remain blocked even though it has
a true guard until the in statement is invoked again and the
guards re-evaluated.
This example shows such a thing happening.
SR Program: Guard Evaluation in `in' Statements.
Can we do anything about this?
Yes, we can put a dummy branch in the in statement
that we can use to ``nudge'' the in.
We must also make sure the in statement is inside a
`do forever' loop so the messages for the dummy branch in the invocation
queue will be cleared out.
This example shows such nudging.
SR Program: Nudging Guard Reevaluation in `in' Statements.
It is important to realize exactly when such a dummy branch is needed.
If a variable in a guard is changed inside a branch of the in
statement and the in is executed again because it is inside
a loop (a `do forever' for example),
then no such dummy branch is needed.
However, if the in is blocked because that are no invocations
in the queue with true guards,
and a guard variable is changed
outside the in statement,
then the in will remain blocked unless a dummy branch is
added to it and invoked.
in hungry() -> ...
if ~haveR -> send needR() fi
if ~haveL -> send needL() fi
do ~haveR or ~haveL # i.e. until have both forks
in passL() -> ...
[] passR() -> ...
[] needL st dirtyL -> ... # if dirtyL, dirtyR are left out then
[] needR st dirtyR -> ... # starvation is possible -- forks can
ni # oscillate between philosophers
od
send eat()
receive release_forks()
[] needR() -> ... # for deadlock to occur, each phil has
[] needL() -> ... # one fork, needs one fork, all phils
ni # are hungry, and the fork each phil
# has is not dirty
Here is the complete SR program.
SR Program: Distributed Dining Philosophers.
forward takes the place of the fork.
invocation service (operation) effect
---------- ------------------- ------
(function) call local procedure local procedure call
(function) call remote proc remote procedure call
(nonblocking) send local or remote proc dynamic process creation
(nonblocking) send (blocking) receive asynchronous message passing
(function) call (blocking) receive synchronous message passing,
simple rendezvous
(function) call in statement extended rendezvous
Each SR program has one main resource, which is created automatically when the program is run.
This resource may then create or ``enliven'' other resources declared and compiled with the main one.
A resource may contain procedures that can be referenced from within the resource or from other resources.
A resource may contain one or more processes.
A process can call a procedure (a proc or procedure) in the same resource, analogous to procedure calling in a sequential high-level language.
A process can call a procedure (a proc) in a different resource.
This is a remote procedure call.
A process wanting to call a procedure in another
resource needs a capability for that resource. The process can be given
that capability when the process is created,
e.g., create Strangelove(pc) in
SR Program: Multiple Resources,
or when the resource containing the called procedure is created,
e.g., fac_cap := create factorial() in
SR Program: Two Resource Factorial Program.
SR provides facilities for processes to communicate:
the send and receive statements.
The latter is a special form of the in statement.
All receives and ins are blocking.
The send operation is non-blocking,
giving us (asynchronous) message passing.
To rendezvous with another process,
use call instead of send.
A process can send to a procedure in another resource,
performing dynamic process creation.
receive name(a, b, ..., c) is an abbreviation for
in name(x, y, ..., z) ->
a := x
b := y
...
c := z
ni
General counting semaphores are a special case of send and receive.
There are three kinds of operation invocations:
send rcap.some_name1(a, b, c, ...)
call rcap.some_name2(a, b, c, ...)
x = rcap.some_function(a, b, c, ...)
The rcap capability is only needed to call or send from one resource to another.
There are three kinds of operation implementations:
proc some_name3(p, q, r, ...)
returns y # needed only for functions
...
end some_name3
receive some_name4(p, q, r, ...)
in some_name5(p, q, r, ...) st condition ->
...
[] some_name6(u, v, w, ...) returns d ->
...
[] some_name7(u, v, w, ...) returns d st condition ->
...
[] ...
...
[] else ... # optional
ni
If some_name2 or some_function matches
some_name3,
then we have a (possibly remote) procedure or function call.
If some_name1 matches some_name4,
then we have asynchronous message passing.
If some_name2 matches some_name4,
then we have synchronous message passing.
If some_name1 matches some_name3,
then we have dynamic thread creation.
If some_name2 or some_function
matches one of some_name5, some_name6, etc.,
then we have the Ada rendezvous. The in in SR is like the Ada accept and
the SR st condition is like the Ada select.
Complete animation.
XTANGO Animation of Distributed Dining Philosophers.
SJH shartley@mcs.drexel.edu