Exercises | Concurrency: State Models and Java Programs

11.1 N processes are required to synchronize their execution at some point before proceeding. Describe a scheme for implementing this barrier synchronization using Linda tuple space. Model the scheme using TUPLESPACE and generate a trace to show the correct operation of your scheme.
11.2 Describe a scheme for implementing the Supervisor – Worker architecture using rendezvous message-passing communication rather than tuple space.
(Hint: Make the Supervisor a server and the Workers clients.)
Model this scheme and show absence of deadlock and successful termination. Modify the Java example program to use Entry rather than TupleSpace.
11.3 A process needs to wait for an event from either announcer A or announcer B, for example events indicating that button A or button B has been pressed, i.e.
```
 (buttonA -> P[1] | buttonB -> P[2]).
```
Sketch the implementation of a Java thread that can block waiting for either of two events to occur. Assume initially that the Java events are handled by the same listener interface. Now extend the scheme such that events with different listener interfaces can be accommodated.

11.4 Provide a Java class which implements the following interface and has the behavior of EVENTMANAGER:

 class Listener {    public action(int event); } interface EventManager {    void announce(int event);    void register(Listener x);    void deregister(Listener x):    }

11.5 Each filter in a pipeline examines the stream of symbols it receives for a particular pattern. When one of the filters matches the pattern it is looking for the entire pipeline terminates. Develop a model for this system and show absence of deadlock and correct termination. Outline how your model might be implemented in Java, paying particular attention to termination.
11.6 A token ring is an architecture which is commonly used for allocating some privilege, such as access to a shared resource, to one of a set of processes at a time. The architecture works as follows:
A token is passed round the ring. Possession of the token indicates that that process has exclusive access to the resource. Each process holds on to the token while using the resource and then passes it on to its successor in the ring, or passes on the token directly if it does not require access.
Develop a model for this system and show absence of deadlock, exclusive access to the resource and access progress for every process. Is the system “buffer tolerant”? Outline how your model might be implemented in Java.
11.7 Consider a ring of nodes, each of which acts as a simplified replicated database (Roscoe, 1998). Each node can autonomously update its local copy. Updates are circulated round the ring to update other copies. It is possible that two nodes perform local updates at similar times and propagate their respective updates. This would lead to the situation where nodes receive updates in different orders, leading to inconsistent copies even after all the updates have propagated round the ring. Although we are prepared to tolerate copy inconsistency while updates are circulating, we cannot accept inconsistency that persists. To ensure consistent updates in the presence of node autonomy and concurrency, we require that, when quiescent (no updates are circulating and no node is updating its copy), all copies should have the same value.
In order to achieve this, we assign a priority to each update according to an (arbitrary) ordering of the originating node. Thus, in the case of clashes due to two simultaneous updates by different nodes, node i has priority over node j if i<j. Simultaneity is recognized by a node receiving an update while still having an outstanding update.
Develop a model for this system and show absence of deadlock and consistent values when quiescent.
(Hint: In order to keep the problem simple, let each node deal with only a single value. Updates are passed round the ring in the form: [j][x] where j=originator and x=update value. Nodes should be connected by channels which can be modeled as follows.)
```
 const N=3                 // number of nodes range Nodes = 0..N-1 const Max = 2             // update values range Value = 0..Max-1 CHANNEL = (in[j:Nodes][x:Value]->out[j][x]->CHANNEL). 
```