This chapter provides a gentle introduction to concurrent programming using spaces. The chapter is based on a simple and traditional notion of tuple space, namely a multiset of tuples. The chapter presents the tuple space operations incrementally. The final part discusses how to use tuple spaces to implement basic coordination and synchronisation mechanism. The programming model for tuple spaces in this chapter is strongly based on Linda. The chapter is illustrated with a scenario where a couple of roommates (Alice, Bob, Charlie,) use a tuple space fridge to coordinate their activities.
All programing languages with pSpace libraries provide support for concurrent programming based on some sort of concurrent activities.
Go provides lightweight threads called goroutines that can be used to spawn parallel activities. Suppose that f is an ordinary Go function. A parallel activity f(x,y) can be spawned with
go f(x,y)Concurrency is a bit more cumbersome in thread-based languages like Java. For instance, one of the approaches to deal with threads in Java is by implementing the activities we plan to spawn in parallel as classes implementing the Runnable interface. Following the above example, we would need to write
public class F implements Runnable {
public F(int x, int y) {...}
public void run() { // do what f(x,y) is supposed to do }
}to implement the runnable thread and then invoke it with
(new Thread(new F(x,y)).start();The creation of a Thread in C# is similar:
(new System.Threading.Thread(new System.Threading.ThreadStart(F(x,y)))).Start();with F being a delegate.
For more details on corrency primitives refer to
- Golang tour on concurrency.
- the Java tutorial on starting threads for more details.
- C# How to create threads.
It is worth recalling that most programming languages have a main activity and that the termination of the program and any concurrent activity may differ: for example, a Go program finishes when the main activity completes its execution (without waiting for any concurrent activity) whereas as Java and C# programs will wait for completion of all concurrent activities.
The operation getp seen in the previous chapter is a non-blocking operation: it returns a result whether or not a matching tuple is found in the tuple space. The operation get, instead, is a blocking operation. This means that an operation s.get(T) will block if there is no tuple matching T in space s. For example, if Alice tries to behave as in
fridge.get(new ActualField("milk"), new FormalField(Integer.class));she will get stuck if the fridge space contains no tuple of the form ("milk",n), waiting until a tuple ("milk",n) appears in the tuple space. Blocking operations are key to implement synchronisation among activities.
Most operations on tuple spaces have blocking and non-blocking variants. Non-blocking variants have the same name as their blocking counterparts but are typically suffixed with p. For example, operation getp(t) is pretty much like get(t) but it does not block if the operation fails to retrieve a value and it actually returns a value to notify if a tuple was actually retrieved or not.
In our example, Alice can avoid getting stuck and decide what to do next in either case (some milk tuple, no milk tuple) with
Object[] item = fridge.getp(new ActualField("milk"), new FormalField(Integer.class));
if (item == nil) {
// go shopping
} else {
fridge.put("milk", 1);
}The combination of pattern matching and non-deterministic retrieval allows one to specify loose coordination mechanisms. We are indeed ready to introduce our first coordinated system, where the behaviour of Alice and Bob is
Alice:
fridge.put("milk",2)
fridge.put("butter",1)
...Bob:
while (true) {
Object[] item = fridge.get(new FormalField(String.class), new FormalField(Integer.class));
// go shopping
}The adopted coordination pattern is called consumer/producer. Alice has the role of a producer of tasks (items to be bought). She generates tasks by adding tuples to the tuple space. Bob has the role of a consumer of tasks. He consumes tasks by retrieving tuples from the tuple space. Note that the coordination between Alice and Bob is very loose: they do not need to meet and they do not need to produce or consume the shopping orders in any particular order.
This basic coordination pattern can be easily extended to the case in which there are multiple producers and consumers.
There are many situations in which one would like to inspect the tuple space without actually removing any tuple. A typical example is when the presence of a tuple signals an event and we want to wait until that event happnes. For example, in our case study, Alice and Bob may decide that Bob does not need to go shopping immediately but can wait until Alice decides that the grocery list has enough items, signalled by a tuple ("shop!") as in
Alice:
fridge.put("milk",2);
fridge.put("butter",1);
fridge.put("shop!");Bob:
fridge.get(new ActualField("shop!"));
fridge.put("shop!");
while (true) {
Object[] item = fridge.get(new FormalField(String.class), new FormalField(Integer.class));
// go shopping
}A drawback of this solution is that the check that Bob performs is not atomic. There is hence a moment in which the tuple ("shop!") is removed by Bob which may lead other rooommates. Suppose, for instance, that Alice and Bob are executing their programs while Charlie is executing:
Charlie:
Object[] t = fridge.queryp(new ActualField("shop!"));
if (t != null) {
while (true) {
Object[] item = fridge.get(new FormalField(String.class), new FormalField(Integer.class));
// go shopping
}
} else // relaxThe standard solution to this problem is use the query operation to perform queries atomically. Operation query(T) behaves like get(T) but does not remove the retrived tuple from the space. Now Bob and Charlie can safely check if it is time to shop as follows.
Bob:
fridge.query(new ActualField("shop!"));
while (true) {
Object[] item = fridge.get(new FormalField(String.class), new FormalField(Integer.class));
// go shopping
}Charlie:
Object[] t = fridge.queryp(new ActualField("shop!"));
if (t != null) {
while (true) {
Object[] item = fridge.get(new FormalField(String.class), new FormalField(Integer.class));
// go shopping
}
} else // relaxA unique advantage of introducing the query operation it eases performant implementations of concurrent queries.
At this point we have seen the main operations to interact with a space:
put(t)adds a tupletto a space.get(T)blocks until a tuple is found in the space which matches the templateT. It then returns the matched tuple and removes it from the space.getp(T)is the non-blocking version ofget. In addition to the matching tuple, it returns whether the operation was successful or not.getAll(T)is a non-blocking operation that returns all tuples matching the templateTand removes them from the space.query(T)is the non-destructive version ofget. The operation blocks until a tuple is found in the space which matches the templateT. It then returns the matchedtuple.queryp(T)is the non-blocking version of query. In addition to the matching tuple, it returns whether the operation was successful or not.queryAll(T)is the non-destructive version ofgetAll.
All the above operations may fail (e.g. due to communication errors or denied access) and may return a value stating indicating success or failure.
The above description of the operations intentionally underspecifies the behaviour of simple retrieval operations (get, getp, query and queryp). The following classes of spaces implement a concrete retrieval strategy:
SequentialSpace: retrieval operations return the oldest matching tuple.QueueSpace: retrieval operations return the oldest tuple, if it matches the specified template.StackSpace: retrieval operations must return the newest tuple, if it matches the specified template.PileSpace: retrieval operations must return the newest matching tuple.RandomSpace: retrival operations return any matching tuple, chosen according to a random choice with uniform distribution (equally likelihood of getting any tuple).
Such strategies are implemented in jSpace and other pSpace libraries.
Standard synchronisation mechanisms can be implemented using tuple spaces. Global locks can be used to grant exclusive access to the tuple space and to provide atomicity of complex operations on the tuple space. A lock on a tuple space s can be easily implemented as follows.
First, the lock is represented by a tuple ("lock") that is initally placed in the tuple space s with
s.put("lock")Then, every time a process wants to work on the tuple space it should adhere to the following protocol:
// acquire lock on s
s.get("lock")
// work on tuple space s
// release lock for s
s.put("lock")If all processes respect the protocol, the computations specified between acquiring the lock and releasing the lock are executed atomically.
Suppose, for instance, that Alice needs to increase the number of milk buttles and butter bars atomically. She can proceed as follows:
fridge.get("lock")
Object[] milk = fridge.get(new ActualField("milk"), new FormalField(Integer.class));
Object[] butter = fridge.get(new ActualField("butter"), new FormalField(Integer.class));
fridge.put("milk",milk[1]+1)
fridge.put("butter",butter[1]+1)
fridge.put("lock")Simple locks limit concurrency and may impact the performance of the tuple space. Multiple-readers/single-writer locks mitigate this by allowing for multiple readers to work concurrently on the tuple space, while requiring exclusive access on writers. With this coordination pattern we ensure that either none, at most one writer (and no readers), or multiple readers (but no writer) are accessing the tuple space. This coordination pattern can be implemented using a standard solution based on a counter for the number of readers (represented as a tuple ("readers",n) and two locks: lock (a global lock) and reader_lock (to lock the counter).
Processes that need to modify the tuple space (i.e. writers) have to adhere to the following protocol:
// acquire global lock
s.get("lock")
// update the tuple space with get/put operations
// release global lock
s.put("lock")Processes that just need to search for tuples without modifying the tuple space (i.e. readers) can proceed as follows:
// Increase number of readers and get global lock
s.get("reader_lock")
Object[] readers = s.get(new ActualField("readers"),new FormalField(Integer.class));
s.put("readers",readers[1]+1)
if readers[1] == 0 {
// Get the global lock if I am the first reader
s.get("lock")
}
s.Put("reader_lock")
// Search for tuples with query operations
// Decrease number of readers and release global lock
s.Get("reader_lock")
readers = s.get(new ActualField("readers"),new FormalField(Integer.class));
s.Put("readers",readers[1]-1)
if readers[1] == 1 {
// If I am the last one, realease the global lock
s.put("lock")
}
s.put("reader_lock")Another example is a one-time barrier for N processes, which can be implemented using a tuple counting the number of processes that still need to reach the barrier. The barrier can be intialised with
s.put("barrier",N) ;and when a process reaches the barrier it has to execute the following code
Object[] barrier = get(new ActualField("barrier"), new FormalField(Integer.class));
s.put("barrier",barrier[1]-1);
s.query(new ActualField("barrier"), new ActualField(0));
// move onWe have seen the following operations on spaces:
query: blocks until a tuple is found which matches a given template. It then returns the matched tuple.get: likequerybut also removes the found tuple.
We have seen a set of space classes, each implementing a different retrieval strategy (Sequential, Queue, Stack, Pile, Random).
We have seen the following coordination patterns:
- Producer/consumer: use a tuples space as a bag of tasks. Producers put tuples representing tasks; consumers get tuples representing tasks.
- Global locks: use a tuple to represent the exclusive right to access the tuple space (or a part of it). Only the process with the tuple can access the space.
- Multiple-readers/single-writer locks: use a counter and two locks to allow for multiple process to search for tuples concurrently, or one process to update the tuple space.
- Barriers: use tuples to count how many processses have reached some status in their computation.
A complete example for this chapter can be found here.
- Andrews, G. R. (1999). Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, 1 edition
- Gelernter, D. (1985). Generative communication in Linda. ACM Trans. Program. Lang. Syst., 7(1):80–112
NOTE: The above documents present the original Linda approach to tuple spaces. Linda consists of the set of primivites put, get, query and their respective non-blocking variants. In the paper and and in the literature you will often find that put, get and query are called out, in and rd or read. Asynchronous/non-blocking versions of put, get and query are called eval, inp and rdp.
Move to the next chapter on distributed programing with spaces!