One of the most common concurrent idioms is a fork-join: run two processes concurrently,
and wait for a result from each one. This is very easy to express in Orc. Whenever we write a
declaration, the process computing that value runs in parallel with the rest of the program. So if we write
val declarations, and then form a tuple of their results, this performs a fork-join.
val x = F val y = G # (x,y)
Fork-joins are a fundamental part of all Orc programs, since they are created by all nested expression translations. In fact, the fork-join we wrote above could be expressed even more simply as just:
In Orc programs, we often use fork-join and recursion together to dispatch many tasks in parallel and wait
for all of them to complete. Suppose that given a machine
m and then publishes a signal when initialization is complete. The function
initAll initializes a list of machines.
def initAll() = signal def initAll(m:ms) = ( m.init() , initAll(ms) ) >> signal
For each machine, we fork-join the initialization of that machine (
m.init()) with the initialization
of the remaining machines (
initAll(ms)). Thus, all of the initializations proceed in parallel, and
the function returns a signal only when every machine in the list has completed its initialization.
Note that if some machine fails to initialize, and does not return a signal, then the initialization procedure will never complete.
We can also use a recursive fork-join to obtain a value, rather than just signaling completion. Suppose we
have a list of bidders in a sealed-bid, single-round auction. Calling
b.ask() requests a bid
from the bidder
b. We want to ask for one bid from each bidder, and then return the highest
bid. The function
auction performs such an auction for a list of bidders (
finds the maximum of its arguments):
def auction() = 0 def auction(b:bs) = max(b.ask(), auction(bs))
Note that all bidders are called simultaneously. Also note that if some bidder fails to return a bid, then the auction will never complete. Later we will see a different solution that addresses the issue of non-termination.
Consider an expression of the following form, where F and G are expressions and M and N are sites:
M() >x> F | N() >y> G
Suppose we would like to synchronize F and G, so that both start
executing at the same time, after both
N() respond. This is easily done
using the fork-join idiom. In the following, we assume that
x does not occur
free in G, nor
y in F.
( M() , N() ) >(x,y)> ( F | G )