Copyright © 2017 Fred Youhanaie
Version: 0.2.0
Authors: Fred Youhanaie (fyrlang@anydata.co.uk).
espace
is an Erlang implementation of the Tuple Spaces
(or Linda) paradigm. Details of the paradigm can be found on
Wikipedia for
Linda
and
Tuple Spaces.
Another good source that describes the paradigm well is the following paper:
Carriero, Nicholas & Gelernter, David. (1989).
How to Write Parallel Programs: A Guide to the Perplexed.
ACM Computing Surveys. 21. 323-357.
espace
allows one to implement parallel algorithms
where tasks (worker processes) running concurrently communicate and
coordinate through the tuple space.
The basic idea behind tuple spaces is that an application is given
a storage pool where tuples are added to it via the out
operation, or taken from the pool via the in/inp
or rd/rdp
operations.
An application created to use this system will have many
concurrently active worker processes that look, and optionally, wait
for tuples that match a desired pattern. The waiting workers will
block until a matching tuple is added to the pool by another worker
using the out
operation.
The worker processes are started via
the espace:worker/1,2
function. A worker can in turn
start further workers by further
calling worker/1,2
.
A typical application will start with a series of out
and eval
oprations. Some of the worker processes will
then, using the in
or rd
operations, pick
the tuples added via the out
operations, process them,
then out
the results. Other worker processes can then
pick the results and process them further.
The implementation provides a space for the tuples, currently
ETS
, along with the six basic
operations, eval
,
out
, in
, inp
, rd
and rdp
.
The eval
operation, as defined in Linda, is expected to behave
the same way as out
, with the exception that if there are any
expressions in the supplied tuple, they will be replaced with their
respective function values before being added to the tuple space.
The espace:eval/1,2
functions in the first implementation of
espace
had a different behaviour. Initially it would take a {Mod,
Fun, Args}
triple or a fun
expression and spawn a child process
to evaluate it. Nothing would be added to the tuple space, unless
explicitly included inside the function.
For some time now, the espace:worker/1,2
functions have provided
the functionality that the original espace:eval/1,2
used to
provide.
We now have a new espace:eval/1,2
function that behaves in a
similar manner to the Linda definition. The current eval
now takes
a tuple, and if the tuple contains any fun
expressions, those
expressions are evaluated before adding the tuple to the tuple
space. The evaluation of the tuple elements is carried out
sequentially in a separate child process.
Only two forms of function elements are recognized: A zero arity
fun
expression, fun () -> expr end
, and a tuple with
two elements, an N
arity fun
expression together with a list of
length N
,
{fun (A, B, ...) -> expr end, [expr, expr, ...]}
. In
the second form, the arity can be zero.
espace
has been built as an OTP
application, espace_app
. Multiple instances of the
application can run concurrently on the same node without
interfering with each other.
The application server can be started
with espace:start/1,2
. Once the server is running, the
client processes can use the espace
module to perform
any of the six operations. In fact, one can kick off the whole
process by calling a purpose written bootstrap function, which can
in turn perform out
and eval
operations.
The top level supervisor started by espace_app
is espace_sup
. This supervisor manages
four gen_server
s and one supervisor
, as
described below:
etsmgr_srv
is a gen_server
that adds
resiliency to the ETS tables, should any of their owner servers
restart due to some fault. See
the project
repo for details.espace_tspool_srv
is a gen_server
that
manages the out/in/rd/inp/rdp
requests. In turn it
passes the requests to espace_tspool_srv
espace_tspace_srv
maintains
the espace_tspace
ETS table, the main tuple space
pool. If a requested pattern does not exist and the request is a
blocking one, i.e. in
or rd
, then the
pattern is forwarded to espace_tspatt_srv
. In case of
an out
request, the tuple is stored in the table,
and espace_tspatt_srv
is notified so that it can
inform all the blocking clients whose requested pattern matches
this tuple to retry the in/rd operation.espace_tspatt_srv
maintains
the espace_tspatt
ETS table, which contains the tuple
patterns that worker processes (clients) are blocked on. It
receives two types of messages
from espace_tspool_srv
, unmatched patterns, which,
along with the client details, are then added to
the espace_tspatt
table, and newly added tuples,
which are matched against the existing patterns in the table and,
if matched, blocked clients are notified.espace_worker_sup
is a supervisor
that
will create a new child process with the {M,F,A}
function supplied with the request. Each worker/1,2
request, is executed within a child process of
the simple_one_for_one
supervisor. At present, no
attempt is made to throttle the number of eval
processes.The tuples are kept in a pair of ETS tables.
The first table, espace_tspace
has two columns, a
unique ref, and the tuple itself. A
single gen_server
, espace_tspace_srv
,
handles all accesses to this table.
For the cases where no matching tuple is found for a given pattern,
a second ETS table espace_tspatt
is used to remember
the pattern, the client PID and a unique reference for this specific
request. The unique reference will be used by the
espace_tspool_srv
client side function to block on a
receive for that reference.
Each out
operation, after inserting the new tuple,
will notify espace_tspatt_srv
of the new
tuple. espace_tspatt_srv
which will then scan the
blocking clients whose pattern matches the newly added tuple. If a
match is found, the waiting client is notified and the client entry
is removed from the table.
Once the waiting client receives the notification, it will attempt
the rd
or in
operation again. Note that
the client is not handed the tuple, but notified to request it
again. If more than one client have waiting patterns that match the
tuple, then they will end up competing for it.
Generated by EDoc