«A Design Strategy for Deadlock-Free Concurrent Systems J.M.R.Martin Oxford University Computing Services, 13 Banbury Road, Oxford OX2 6NN, UK ...»
The CSP communication patterns for the component processes may be extracted as
It is straightforward to see that each process obeys the basic client-server protocol.
Clearly no individual process would ever terminate, deadlock or diverge if run in isolation (rule (a)). Whenever a FARMER or FOREMAN process attempts to communicate on a
server request channel it offers the complete choice of such channels to its environment (rule (b)). The WORKER processes are pure clients so rule (b) does not apply to them. Each process communicates on each of its client request-acknowledgement pairs in alternating sequence (rule (c)). And whenever a WORKER or FOREMAN process communicates on a client request channel it immediately becomes ready to communicate on the corresponding acknowledgement channel, and remains so until this communication takes place (rule (d)).
The FARMER is a pure server process for which rule (d) does not apply.
The client-server digraph of this network is illustrated in ﬁgure 3. It has no circuits and, hence, the network is guaranteed deadlock-free.
It is usually safe to represent communication events in occam2 purely by their channel names in the CSP speciﬁcation, as was done here. The one exception is when using a variant protocol on a particular channel. If the inputting process is unwilling to accept the type of datum offered by the outputting process, a local deadlock may ensue. However, if an exhaustive case list is offered by the inputting process there is no problem – but this may be impractical. This issue is discussed in more detail in .
Note that the client-server ordering does not imply a single direction of dataﬂow. A client-server bundle may contain both an input channel and an output channel.
A Message Router
Figure 4 shows the client-server digraph of a message routing program for a network of processors. The processor topology illustrated is a square. Each processor is connected to its horizontal and vertical neighbours by a link in each direction. Each processor runs a separate process to control each of its input and output links. It also runs two interface processes. One of these collects messages which have arrived at their destination, and passes them to the local application program. The other routes messages from the local application destined for other processors. The following routing strategy is employed. In order to send a message to a processor with grid coordinates (x, y), ﬁrst move it to a node with the right x coordinate and then, keeping the x coordinate ﬁxed, move it to the right y coordinate. This strategy is easily generalised to an n dimensional grid – see .
In this case, each client-server bundle consists of a single drip channel, which makes it particularly easy to verify adherence to the protocol – rules (c) and (d) not being relevant. In fact each arrow in the client-server digraph corresponds to dataﬂow (by chance). Although the processor conﬁguration contains circuits, the client-server digraph of the processes contains none, so the router is deadlock-free.
Note: The fact that the routing program is itself deadlock-free does not guarantee that any program that incorporates it will not deadlock. Great care still needs to be taken .
In other words the client and server bundles of V are those of the component processes Pi which are not paired off.
We represent a composite client-server process by a single vertex in a client-server digraph. The following result shows that this is consistent with the composition rule governing basic processes.
Theorem 2 (Client-Server Closure) A client-server network, composed from composite client-server processes, which has a circuit-free client-server digraph, is deadlock-free.
Proof. Consider the total client-server digraph formed when each composite process is expanded back into its basic components. Since there are no cycles in the sub-digraphs contributed by the composite processes and there is no cycle in the top-level digraph, there can be no cycles in the total digraph. Theorem 1 allows us to conclude that the composite network is deadlock-free. Q.E.D.
4/3/1997 16:59 PAGE PROOFS paper
A DESIGN STRATEGY FOR DEADLOCK-FREE CONCURRENT SYSTEMSIt is important to note that any basic client-server process is itself composite client-server (although the reverse is not true). Hence we can apply the result to mixtures of composite and basic processes. This theorem is clearly useful for designing networks hierarchically.
Complex subnetworks may be reused with ease. Black-box processes, that have been shown to abide by the composite client-server speciﬁcations, may be safely incorporated.
However this theorem is too weak in some circumstances. We need to ﬁnd a generalisation.
We deﬁne a dependency relationship between the server bundles and client bundles of a composite process V. If x 2 servers(V) and y 2 clients(V) then x y means that there is a path from the process with server bundle x to that with client bundle y, in the client-server digraph of V.
We construct an exploded client-server digraph of a network containing composite processes in the following way. A node representing any composite process V is removed.
In its stead is placed a set of nodes – one for each server or client bundle of V. Each of these is joined to its corresponding arc (that was formerly incident to the node representing V). Then we draw an arc from the node representing (server) bundle i to that representing (client) bundle j if, and only if, i j in V.
Theorem 3 (Exploded Client-Server Closure) A client-server network, composed from composite client-server processes, which has a circuit-free exploded client-server digraph, is deadlock-free.
Proof. As in Theorem 2, consider the total client-server digraph formed when each composite process is expanded back into its basic components. As before, there are no cycles in the sub-digraphs contributed by the composite processes. Therefore, if there were a cycle in the total digraph, the construction rules for the exploded digraph mean that the latter would also contain a cycle. Since the exploded digraph has no cycles, neither does the total digraph and, by Theorem 1, the whole client-server network is deadlock-free. Q.E.D.
Figure 6 displays two representations of a network constructed from six copies of TRIANGLE (with suitably relabelled channels): the client-server digraph, and an exploded client-server digraph. The former contains a circuit, so we cannot use theorem 2 to show that the network is deadlock-free. However the latter contains none. So the network is deadlock-free by theorem 3.
Figure 6. Client-Server Digraph and Exploded Client-Server Digraph Note: when “exploding” a composite process, it is not always necessary to allocate a new node to every client or server bundle.
Sometimes we can use a single node to represent several client or server bundles, without losing any information. This depends on the structure of the relation.
Therefore for deadlock-free design with composite client-server processes, we only need to be told their client bundles, server bundles, and the dependency relation between them.
The beneﬁt of Theorems 2 and 3 is that we avoid repeating superﬂuous information in the diagrams we draw to design our programs. Instances of complex subnetworks are reduced either to single nodes or to simpliﬁed representations when theorem 2 is too weak.
4/3/1997 16:59 PAGE PROOFS paper
A DESIGN STRATEGY FOR DEADLOCK-FREE CONCURRENT SYSTEMS
5 ADDING A CLIENT-SERVER INTERFACE TO AN ARBITRARY NETWORK
5.1 Hybrid Networks Theorems 2 and 3 make available a hierarchical approach to deadlock-free software construction, based on multiple layers of the client-server model.
However client-server mechanisms are not appropriate for all types of system or subsystem. It would be nice to be able use other paradigms to design deadlock-free subnetworks (such as described in  and ), and then wrap them up with a client-server interface for inclusion in a wider context.
We start with a deadlock-free network V = hP1, : :, Pn i, where each process Pi is itself divergence-free, deadlock-free and non-terminating. We want to add external communications to the components of this network to make it behave like a single basic client-server
process. The resulting network will be called V0, where:
0 hP 0, : :, P 0 i V= 1 n
The basic rule of thumb is that we may freely add client connections to any component process Pi, but we may add server connections to at most one such process. The following
rules must be obeyed:
1. The additional channels of each process Pi 0 are partitioned into client and server bundles, and Pi 0 must obey the basic client-server protocol on these bundles.
2. It is not permitted for more than one process Pi 0 to have server connections.
3. It is necessary to ensure that the new connections added to each process Pi do not interfere with its internal behaviour. If communication on those channels were concealed, P0 should behave identically to Pi, i.e.
0n( 0; Pi ) = Pi Pi Pi
The client-server bundles of V 0 are taken to be the disjoint union of those of each component. It is clear that V 0 will adhere to rules (c) and (d) of the basic client-server protocol (see section 3), since Rule 1 stipluates that each process Pi 0 does. Rule 2 ensures that V 0 obeys rule (b) of the basic protocol. Rule 3 guarantees that V 0 is deadlock-free, divergence-free and non-terminating – rule (a) of the basic client-server protocol. Hence, V 0 may now be treated as a basic client-server process for the construction of client-server networks that are automatically deadlock-free (provided the construction obeys the premise of one of the theorems in this paper).
Rule 3 needs a little further explanation in the context of actual programming. In occam2 it means that if each communication on a client or server channel by Pi 0 were replaced by SKIP, then Pi 0 would follow an identical communication pattern to P i.
4/3/1997 16:59 PAGE PROOFS paper 14 J.M.R. MARTIN and P.H. WELCH
5.2 Polling on a Server Channel The technique of polling on a channel is a means by which a process can attempt to communicate on a channel without the risk of becoming blocked. If the communication fails within a certain time, the process gives up and does something else. In occam2 polling is usually performed using a PRI ALT construct which has either SKIP or timer input alternatives.
While a process is attempting to poll a channel its state is unstable. If the processes which constitute a network only ever communicate on external server request and drip channels by polling, then rule 2 for adding a client-server interface to a network may be overlooked.
In this way we may add external server connections to as many processes as we wish in a network, and then safely embed it within a client-server system.
5.3 Example – Bunjee Jump Simulation We consider an occam2 program for modelling the action of an elastic rope in the simulation of a “bunjee-jump”. The rope is modelled by N copies of a process ROPE, each simulating the motion of a section of the rope. These processes interact with their neighbours according to the I/O-PAR paradigm . This is a very simple design rule which runs as follows. In any network where each process behaves cyclically and communicates on each of its channels exactly once on each cycle in parallel, deadlock can never occur.
Figure 7. Client-Server Digraph for the Bunjee-Jump Simulation In order that we may visualise this simulation, a graphics handling process, GRAPHICS, is added to the I/O-PAR network using client-server connections.
This process acts as a server to each ROPE process along a single input channel. In this way, the position of each rope section is periodically communicated to the graphics handler.
We also add a process USER.INTERFACE which communicates with each of the rope elements as a client. To each rope process is added a corresponding polled server connection. This mechanism is used to allow interactive keyboard control of the simulation.
USER.INTERFACE also has a server connection to a keyboard interface process KEYBOARD.
The client and server channels which were added to each component in the I/O-PAR subnetwork of rope elements do not effect its internal communication pattern. Although it has multiple disjoint server connections, they are only initiated by polling and so are
-- construct the network
CHAN OF BYTE keyboard:
[n]CHAN OF PARAMS new.parameters:
[n]CHAN OF ACK acknowledge:
[n+1]CHAN OF COORDS to.left, to.right:
[n]CHAN OF DISPLAY display:
non-blocking. It follows that the subnetwork formed from the ROPE processes behaves as a single client-server process in relation to its environment. The client-server digraph for the complete system is given in ﬁgure 7 – note that the I/O-PAR subnetwork should be regarded as a single vertex. This digraph is free of circuits so the system is deadlock free.
4/3/1997 16:59 PAGE PROOFS paper