Join Internals
Architecture
Join's internal design consists of 2 parts:
- Low Level Resource Acquisition Core
The core of Join (and similarly
JoCaml/Cw/C#.Joins) is a simple resource acquisiton (and contention
management)
manager which supports atomic acquisition of multiple resources:
- use a bitmap to represent
(global) resource-availability status:
- each bit is used for
status of one resource (available/unavailable) or message
(arrival/missing)
- bitmap -
represent the status of multiple resources
- each acquisition
(behaviour/pattern) is also represented as a bitmap (chord)
- one
acquisition can try to acquire multiple resources (chord bitmap
contains
multiple "1" bits)
- applications can use
multiple concurrent / competing acquisition behaviours(patterns) whose
bitmaps overlap or which
compete for the same global resources
- fast
dispatching / scheduling:
whenever a new resource becomes
available, the global status
bitmap is updated, and the new global status
bitmap is compared with chords' bitmaps; if a chord's bitmap
matches (covered by) the global
status bitmap, this acquisition can be satisfied (or chord is fired):
one item is removed from each resource marked by the bits of chord's
bitmap, and the global status bitmap is updated to reflect new
status of resource availability.
If more than one chord can be fired, we can apply
various scheduling algorithms: round robin, priority based
- a single mutex is used to
protect all
these bitmaps and comparing logic
- multiple threads can try
concurrent acquisitions and contention/conflicts are resolved
atomically and thread-safely
- High Level Messaging Semantics
On top of Join's core
resource-acquisition manager, Join
(Jocaml/Cw/C#.Joins) adds the following high level messaging based
semantics :
- each bit of global resource bitmap is "set" by a port
(messages are the resources to
be
consumed), so each chord/acquisition-pattern is defined
by a set of ports
- each chord/pattern is associated with a callback
(chord-body) which defines how the resources/messages (acquired
by
this chord from ports/ports) are consumed
Two types of port give
different semantics :
- asynchronous: when an asynchronous port is invoked, if no
acqusition bitmaps is satisfied (no chord can fire), arguments/messages
are buffered,
global
resource bitmap is updated and calling thread returns without blocking
- synchronous: when a synchronous port is invoked, if no
acqusition bitmap
is satisfied (no chord can fire), arguments/messages are kept at stack,
global
resource bitmap is updated and calling thread is blocked (a condition variable is
used)
If there exist a chord (acquisition
pattern) which
can fire, depending on the types of acquisition pattern (chord), there
are 2 behaviours:
- if the chord contains a synchronous port, the blocked thread
of synch-call is waked up and the
chord-body
callback is executed by/inside that thread
- if the chord contains all async ports/ports, the chord-body
callback is executed in
"another/different"
thread (which can be
a new thread or from thread-pool), this is how "spawning" is done in
Join
Some facts result from the architecture
- Join's usage of low level synchronization primitives
The rule to get the number of
(mutex, condition variable)
used by a
Join class is simple:
- each joint holds a mutex which is used to protect all
code in async<>/synch<>/chord/joint,
- each synch<> port holds a
condition variable and
- async<> ports hold no synchronization primitive
Although Join's primitives (async<> / synch<> / chord) are
high level, the author's experience has shown that concurrent
applications written with Join usually use almost the same number of
low level synchronization primitives as manually crafted ones.
For example, a manually crafted thread
safe message queue will use a mutex and a condition variable to provide
an asynchronous send/push interface (send and go) and a synchronous
receive/pop interface (blocking wait if no message available).
In Join, a simple thread safe message
queue can be defined as following:
template
<typename msg_type>
class message_queue : public joint {
public:
async<msg_type> send;
synch<msg_type,void> recv;
message_queue() {
chord(recv,
send,
&message_queue::forward);
}
private:
msg_type
forward(void_t r, msg_type s) {
return s;
}
};
Based on the above rule, since this message_queue class inherits from
joint class and has one synch<> port, it will use one mutex
and
one condition variable, using exactly the same number of low level
synchronization primitives as manually crafted.
- Join's expressiveness
Join provides a generic framework to
compose asynchronous and synchronous behaviours in thread safe manner.
Join's special internal design makes it
very expressive in creating concurrent applications:
- Join is expressive in that it can be used to
create most common concurrency / synchronization constructs with
ease, such as monitor, read-write lock, or joints. See tutorials
for detailed coding
- Join is expressive in that it is common and easy to
write
concurrent (thread-safe) applications using solely Join's primitives
(async/synch/chord) without using low level threads, mutex and
condition variables. Again see tutorials for more samples. Please refer
to this Join based
simple
executor implmented sole thru Join's primitives.
- Since Join's core
directly supports atomic acquisition of multiple resources, it helps
nicely multithreaded applications which involve multiple resources:
- Multithreaded applications whose threads acquiring conflicting
sets of multiple resources (or locks) are prone to
dead-locks. The normal way to avoid dead-lock is by enforcing a
consistent (global) order of acquiring resources (locks), as clearly
explained in Herb Sutter's article "Use
Lock Hierarchies to Avoid Deadlock".
Join provides a natural solution to
this issue. We can use async ports/ports to represent the
availability status of resources. The existence of messages at these
async ports represent that resources (locks) are available to be
consumed. Each acquisition pattern is represented as a chord which has
one synch port and multiple async ports. For example, to
resolve the conflicting acquisitions of resources from multiple
threads, we can define the following resource manager:
class resource_manager : joint {
public:
async<void>
resource1;
async<void>
resource2;
async<void>
resource3;
async<void>
resource4;
......
synch<void,void>
acquire1;
synch<void,void>
acquire2;
synch<void,void>
acquire3;
......
resource_manager() {
chord(acquire1, resource1, resource3, resource4,
&resource_manager::handle_acquire1);
chord(acquire2, resource3, resource2, resource1,
&resource_manager::handle_acquire2);
chord(acquire3, resource2, resource4,
&resource_manager::handle_acquire3);
......
resource1();
resource2();
resource3();
......
}
}
The above 3 chords define 3 different acquisition patterns competing
for the same set of resources. Initially a message will be sent on each
of these async ports to mark resource1,2,3 are available. Different
threads will call acquire1() / acquire2() / acquire3(), block waiting
until all of its required resources are available. When a chord is
fired in one thread, that thread will remove a messages from each of
async ports marked in the chord pattern, meaning it consumes these
resources. When this thread is finished with using these resources, it
will call these async ports to mark the resources available again.
Please note that the order of these async ports (resources) defined
in chords are not relevant anymore; since all required async ports
(resources) are acquired atomically.
- In the Futures/Promises concurrency model, one common idiom
(wait_for_all) is using a future to wait for results from multiple
asynchronous computations. Join can also be used to implement Futures
and its wait_for_any and wait_for_all idioms. Please refer to the
following section on futures/promises
for more detailed discussions.