FREE ELECTRONIC LIBRARY - Thesis, documentation, books

Pages:     | 1 || 3 |

«A Design Strategy for Deadlock-Free Concurrent Systems J.M.R.Martin Oxford University Computing Services, 13 Banbury Road, Oxford OX2 6NN, UK ...»

-- [ Page 2 ] --

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 figure 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 specification, 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 [8].

Note that the client-server ordering does not imply a single direction of dataflow. 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), first move it to a node with the right x coordinate and then, keeping the x coordinate fixed, move it to the right y coordinate. This strategy is easily generalised to an n dimensional grid – see [9].

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 dataflow (by chance). Although the processor configuration 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 [10].

–  –  –

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


It 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 specifications, may be safely incorporated.

However this theorem is too weak in some circumstances. We need to find a generalisation.

We define 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 benefit of Theorems 2 and 3 is that we avoid repeating superfluous information in the diagrams we draw to design our programs. Instances of complex subnetworks are reduced either to single nodes or to simplified representations when theorem 2 is too weak.

4/3/1997 16:59 PAGE PROOFS paper



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 [2] and [3]), 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 [3]. 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 figure 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


Skeleton code for the resulting network is given in figures 8 and 9. The high-valency and irregular communication topology of this program is not a problem for a network of transputers. For first generation (T2/T4/T8) architectures, the Southampton Virtual Channel Router[10] is part of the standard Toolset. For T9000s, the same idea is implemented by hardware in the Virtual Channel Processor. These mechanisms remove the need for communication design to be constrained to 4-valent topologies. This remains true for occam retargetings to non-transputer multi-processors.


Pages:     | 1 || 3 |

Similar works:

«Two-Stroke TUNER’S HANDBOOK By Gordon Jennings Illustrations by the author Copyright © 1973 by Gordon Jennings Compiled for reprint © 2007 by Ken i PREFACE Many years have passed since Gordon Jennings first published this manual. Its 2007 and although there have been huge technological changes the basics are still the basics. There is a huge interest in vintage snowmobiles and their “simple” two stroke power plants of yesteryear. There is a wealth of knowledge contained in this manual....»

«PeakTech® 1240/1245/1255/1260 Bedienungsanleitung / operation manual Digital Oscilloscopes 1. Sicherheitshinweise zum Betrieb des Gerätes Dieses Gerät erfüllt die EU-Bestimmungen 2004/108/EG (elektromagnetische Kompatibilität) und 2006/95/EG (Niederspannung) entsprechend der Festlegung im Nachtrag 2004/22/EG (CE-Zeichen). Überspannungskategorie II; Verschmutzungsgrad 2. Zur Betriebssicherheit des Gerätes und zur Vermeidung von schweren Verletzungen durch Stromoder Spannungsüberschläge...»

«Distribution Agreement In presenting this thesis or dissertation as a partial fulfillment of the requirements for an advanced degree from Emory University, I hereby grant to Emory University and its agents the non-exclusive license to archive, make accessible, and display my thesis or dissertation in whole or in part in all forms of media, now or hereafter known, including display on the world wide web. I understand that I may select some access restrictions as part of the online submission of...»

«1 University of PEI Dietetic Internship Applicant’s Handbook Introduction to the Handbook This handbook was put together to provide information and answer some questions you may have as you consider applying to a dietetic internship program. The handbook provides information on both the graduate application route as well as, the University of Prince Edward Island Integrated Dietetic Internship program. It is important to be knowledgeable about the dietetic profession and the internship...»

«Xputer Inhaltsverzeichnis Geschichte der Prozessoren Die Idee der Xputer Seite 1 Ein Xputer Konzept Seite 2 Das Xputer Prinzip Seite 3 Die Software Seite 6 Die Realisierung Seite 8 Das Kress Array Seite 9 Die rDPU Seite 11 Der Datensequenzer Der Configuration Memory Seite 12 Das Scan Window Seite 13 Scan Pattern Seite 14 Der XC6200 ab Seite 15 Geschichte der Prozessoren Ende der 60er Jahre entwickelten die hiesigen Pioniere der Branche, Ilse und Otto Müller in Konstanz, noch Schaltungstechnik...»

«Rules of Court 1 January 2016 Registry of the Court Strasbourg Note by the Registry This new edition of the Rules of Court incorporates amendments made by the Plenary Court on 1 June and 5 October 2015. The new edition entered into force on 1 January 2016. Any additional texts and updates will be made public on the Court’s website (www.echr.coe.int). Table of Contents Rule 1 – Definitions Title I – Organisation and Working of the Court Chapter I – Judges Rule 2 – Calculation of term...»

«Examination Guide THE CHARTERED INSURANCE INSTITUTE FA5 Certificate in Investment Operations FA5 – Individual Savings Accounts administration Based on the 2013/2014 syllabus examined until 31 August 2014 Examination Guide FA5 – Individual Savings Accounts administration Based on the 2013/2014 syllabus examined until 31 August 2014 Contents Introduction to Examination Guide 3 FA5 Syllabus 6 Specimen Examination 9 Specimen Examination Answers and Learning Outcomes Covered 17 Published in July...»

«ON THE PHONETIC IMPLEMENTATION OF SYLLABIC CONSONANTS AND VOWEL-LESS SYLLABLES IN TASHLHIYT CÉCILE FOUGERON CNRS – Sorbonne Nouvelle cecile.fougeron@univ-paris3.fr RACHID RIDOUANE CNRS – Sorbonne Nouvelle rachid.ridouane@univ-paris3.fr On the phonetic implementation of syllabic consonants. 141 ABSTRACT This paper presents an acoustic and electropalatographic study of how vowel-less syllables and their constituents are phonetically implemented in Tashlhiyt Berber. Three issues are...»

«chapter 3—student reading If you hold a solid piece of lead or iron in your hand, it feels heavy for its size. If you hold the same size piece of balsa wood or plastic, it feels light for its size. The property of an object that causes this effect is called density. The density of an object depends on its mass and its volume. The mass is the amount of matter in the object. The volume is the amount of space that the object takes up in three dimensions. All the objects around you take up a...»

«Forward Analysis of Depth-Bounded Processes Thomas Wies, Damien Zufferey, and Thomas A. Henzinger IST Austria (Institute of Science and Technology Austria) Abstract. Depth-bounded processes form the most expressive known fragment of the π-calculus for which interesting verification problems are still decidable. In this paper we develop an adequate domain of limits for the well-structured transition systems that are induced by depth-bounded processes. An immediate consequence of our result is...»

«Perceptual Constancy Jonathan Cohen∗ Our eyes deceive us when we look down railway tracks, but our brains do not. The rails appear to converge in the distance, but we know that the rails are parallel. We know that they are the same distance apart a mile down the track as they are where we are standing, so the brain says, “The tracks only appear to converge because they are distant.” But how does the brian know that the tracks are distant? The brain answers, “They must be distant because...»

«TILA/RESPA INTEGRATED DISCLOSURES (TRID) RULE CFPB WEBINAR Q&A INDEX INTRODUCTION Through 2014 and 2015, the Consumer Financial Protection Bureau (CFPB) hosted five webinars to discuss the new TILA-RESPA Integrated Disclosures (TRID) Rule. These webinars consisted of presentations from CFPB-prepared slide decks, in both lecture and question-and-answer formats. The CFPB selected the questions and developed scripted responses in advance of the respective webinars. In August 2015, the CFPB...»

<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.