TECHNICAL REPORT SERIES
Series Editor: Dr. B. Shaw Number 63
May, 1974
C 1974 University of Newcastle upon Tyne. Printed and published by the University of Newcastle upon Tyne, Computing Laboratory, Claremont Tower, Claremont Road, Newcastle upon Tyne, NEI 7RU
This paper describes how an extended Path Notation may be used to write solutions to a complex synchronisation problem. The resulting solutions are compared and equivalent descriptions are presented in terms of Petri Nets. The present approach is convenient for systematically analysing synchronisation problems into simpler sub-problems. Solutions to these sub-problems may then be combined to yield solutions to the original problem. The path notation used also permits one to abstract from aspects of the problem irrelevant to synchronisation.
In the present paper, we show how the notation and techniques developed in [1] may be applied to a synchronisation problem. The notation permits the problem to be divided logically into a set of interacting smaller problems about which assertions are made and for which solutions are derived. This allows flexibility in the construction and design of the solutions while maintaining a high level description of the synchronisation involved. The synchronisation expressed by our notation is more general than that described in [5]. However, the transformation rules enable us to describe a machine independent implementation of our solutions in terms of Petri Nets.
The synchronisation problem investigated is the Cigarette Smokers Problem of Patil [2]. This problem has been widely discussed, and will provide a familiar background upon which to exercise the notation. We shall restate both the problem as it was originally posed by Patil, and the solution given by Parnas [3]. Using the same notation throughout, starting from Parnas' solution, we describe a series of other solutions. By modifying the agents and the problem statement we generalize the problem and the solutions. The definitions of the semantics of path expressions and processes by means of Petri Nets permits a comparison of the solutions directly with some of those given by Patil. Finally, we show how our solutions can be alternatively derived by a sequence of refinements of a high level description of the problem.
The program consists of class declarations, instances of those classes, and a set of processes. The class semaphore is used to create path expressions involving two procedures V and P. Semaphore1 is used to replace the semaphores initialised to zero which Patil uses in his statement of the problem. Similarly semaphores is used to replace semaphores initialised to one. Declarations of instances of these classes result in the creation of a path expression, for example :-
Each process consists of a sequence of actions and is cyclic. Within a process the action of executing a P operation on a semaphore tobacco is represented by tobacco.p.
The Smokers problem is that the program may deadlock. For example, agent t may execute paper.V and match.V the smoker with tobacco may then execute paper.P and the smoker with paper may execute match.P. At this point no process is able to proceed and the program is in deadlock. Using the transformations described in the first paper the program of Figure 1 becomes the Petri Net of Figure 2. The thin lines belong to those subnets created from path synchronisation, the thick lines belong to subnets representing the synchronisation of the processes. The net uses abbreviated names for the actions, for example matches.P is written m.P. The deadlock is reproduced in the net by the subnet containing the smoker transitions p.P, t.P and m.P. This subnet can absorb up to three markers from the subnet above, marking all the right hand input places of the transitions p.P, t.P and m.P, without marking any input places to the transitions sm.V, sp.V and st.V. After such a firing sequence of the transitions in this subnet, any further marker from the subnet above will result in marking one of these input places. However, the deadlock occurs because the subnet above will only produce two markers. It cannot produce further markers until the transitions sm.V, sp.V and st.V are enabled by the deadlocking subnet.
Figure 1. A Reformulation of Patil's Cigarette Smokers Problem.
Figure 2. Simulating Net for the Smokers Problem
Figure 3. A Reformulation of Parnas' Solution.
Figure 4. Solution with a Path Expression replacing the semaphore array and index of Parnas.
Figure 5. Net for solution of Parnas.
A reformulation of the solution proposed by ParnaS appears in Figure 3. The solution uses an array of semaphores called C and an index into these semaphores, integer t. The notation used for this solution is adopted from the notation used in the first paper by including a representation for data (integer t) and the array mechanism. It is not immediately possible to transform the solution into a Petri Net because the concept of data is not included in our model of a process. However, by considering the role of t this solution can be represented in another way. The integer t may take the values from 0 to 6 and may be incremented twice successively by 1, 2, or 4; it may not, however, be incremented by the same amount. Following these two increments, only one of the smokers is enabled to execute the P operation on one of the semaphores C[6], C[5] or C[3]. Thus, letting the procedure ti represent an increment of t by i and the procedure Pj represent C[j].P we can write the Path R expression:
Comparing Figure 2 with Figure 5 we see that the subnet which gave rise to a deadlock has been replaced by a subnet which guarantees that given two markers arriving at its input places a marker will be placed on its output place. That is, given transitions matches.P (m.P) and tobacco.P (t.P) which mark the input places to the subnet, a marker will be placed in an output place (the place which enables transition smokerp.V (Sp.V)).
Consider pushert of Figure 3. Pushert accepts tobacco created by an agent and then attempts to execute t1. When pusher t does execute t1 the smoker permitted to use that tobacco is one of the two processes waiting to execute P3 or P5. That is, the tobacco can only be used by the smoker with matches or the smoker with paper. Renaming P3 by matches-smoker and P5 by paper-smoker this synchronisation can be written directly by
Applying the same reasoning to the other pushers we obtain the set of path expressions synchronising the smokers with the arrival of the resources shown in Figure 6. Since a procedure name appears in more than one path expression, the solution involves General Path expressions. Hence, for example, tobacco-smoker cannot be executed by any process unless both a match and paper have already been executed. At this point we remove the class of semaphore and reconstruct the agents to use the structure we have built up for the smokers. The smokers communicate with the agents via 'order' processes, semaphores smokert, smokerp and smokerm. and semaphore s (See Figure 1). The agents communicate to the pushers by semaphores paper, match and tobacco. These communications between smokers and agents can be replaced by the following path expressions
For the agents of Figure 1 :-
| path | (smoker t.V, smoker m.V, smoker p.V); |
|
|
((match.V ; tobacco.V) , (tobacco.V ; paper.V) , |
|
|
(paper.V ; match.V)) end |
| path | (tobacco-smoker, matches-smoker, paper-smoker); |
|
|
(smokert.V , smokerm.V , smokerp.V) end |
where tobacco-smoker is P6, matches-smoker is P3 and paper-smoker is P5. The first path expression eliminates the need for the order processes. Smokert.V , smokerm.V and smokerp.V inform the agents to produce two more resources. Which smoker that information comes from is irrelevant and we remove the distinction by replacing all three by a single action, the execution of a procedure release. We modify the procedure invocations to be consistent between agents and smokers and introduce two new path expressions :-
where release is invoked by a separate process
Finally, since we have now placed all our synchronisations within path expressions, the processes of the agents and smokers can be simplified. The resulting solution is shown in Figure 6. The processes add nothing to the synchronisation. The corresponding Petri Net solution is shown in Figure 7. The subnets describing the processes have for clarity been omitted. The Petri Net is very much simpler in construction than those of Figure 2 and Figure 5.
We introduce three supplier processes and additional path expressions. Instead of the path expression :-
Figure 6. Sequential Production of Resources by Agents.
Figure 7. Net for sequential production of resources by agents.
Figure 8. Solution with Concurrently Executing Agents.
Figure 9. Simulation net of solution with concurrently executing agents.
Figure 10. Compact Solution with Concurrent Agents
Figure 11. Simulating Net of compact solution with concurrent agents
Figure 12. Compact Solution with Sequential Resource Production
Figure 13. Simulation Net of compact solution with sequential resource production
The resulting solution is shown in Figure 8 and the simulating Petri Net is shown in Figure 9. As can be seen from the simulating net, this solution is very similar to Patil's Petri Net solution except for additional subnets. These subnets represent redundant synchronisation caused by having split the problem into very small pieces and describing each piece separately by a path expression. The next solution eliminated this redundant synchronisation. Note that in a similar manner to the way we have allowed the production of resources to occur concurrently, we could allow the smokers to pick up the resources concurrently. However, we refrain from this source of possible solutions because the symmetry of the smokers to the agents suggests that such an investigation will not provide any new insights into the problem.
Next, we condense Figure 8. The path expressions labelled B, C, D) and E, F, G in that solution both share the procedures tobacco, match and paper. We concatenate these path expressions to obtain the solution. shown in Figure 10. The coordinating path expressions disappear as a result of this simplification since the synchronisation they prescribe is already specified completely by the remaining three path expressions. Once again we can apply transformation rules one obtain Figure 11. We have again omitted the processes in this representation as they contribute nothing to the synchronisation. The resulting net has fewer places and transitions than Patil's Petri Net solution but both solutions are essentially the same.
To complete our survey of solutions to the problem, let us condense Figure 4 which is an equivalent solution to that of Parnas. The agents of this solution produce resources in a fixed order (see Figure 1). We shall allow them more flexibility and they will be able to produce resources in any order, provided they do so in sequence.
The pushers of Figure 4 are unnecessary because they replace the arrival of a resource by an increment to t???. We replace t1 tobacco, t2 by paper and t4 by match. The agents can directly produce the resources. Thus, for example, agent t can produce tobaccos that is, it invokes the procedure tobacco. Finally, to be consistent with the names we have adopted in Figure 10 let us call P6 tobacco-smoker, P3 matches-smoker and P5 paper-smoker. The result is shown in Figure 12. The simulation net of Figure 12 appears in Figure 13 and is a simple net which is live and safe by Theorem 2. Processes have been ignored in the net because they add nothing to the synchronisation. If we include these processes, intuitively we would still have a live and safe net, although no longer a simple net.
where
where
and where the choice in 3) is based upon 2) in the following manner :-
This specification of the problem determines the path expressions of Figure 10. Imposing the restriction that resource production cannot occur concurrently we can modify 1) to become :-
Section 2) now disappears as it is made redundant by 1. We can modify 3) to become :-
This specification of the problem determines the path expression of Figure 12.
Imposing the restrictions that we may only use P and V operations and processes without conditional statements, we should be able to modify the sequential statement of the problem above and, by arguments analogous to the ones we use to create Figure 12, arrive at Parnas' solution.
Examination of the original program statement of the problem has enabled us to discuss the deadlock in path notation and in Petri Net form. The deadlock is caused because the agents can create only two resources before expecting a communication from the smokers. However, the smokers may consume from two or four resources before issuing this communication. The structure of the program is characterised by the grouping of the processes into agents, orders and smokers. The Figure 4 reformulation of Parnas' solution avoids the deadlock by introducing pushers which, on receiving two resources, must inform the smokers which, in turn, must inform the agents. The structure of this solution is again indicated by the groupings of the processes. In both programs, this structure is reflected in the Petri Net representation. The next solution presented (Figure 6) transfers most of the synchronisation from the processes to the path expressions. Much of the synchronisation of Figure 4 is unnecessary, and this is reflected in the comparative size of this new solution and its Petri Net. The path expressions structure the program in a differing way to that found in Figure 4 or Figure 1. The choice between which resources should be produced after a 'release' is clearly shown. The result of that decision in terms of which smoker may use the resources is made more obvious. Finally, the communications between the smokers and agents is made direct via a communicator executing release.
Modifying the agents we have permitted them to produce concurrently or in sequence but in any order. The solution with concurrently executing agents factors the modified problem into four. First, there is a path expression which reflects the choice to be made of the resources to be produced. Second, there is a set of three path expressions which, once the choice is made, allow the agents to produce the resources concurrently. Third, a set of three path expressions select the smoker, given the resources. Fourth, the smoker selected communicates that he has used the resources and more may be produced. The Petri Net of this solution resembled the Petri Net solution given by Patil. The extra subnets which are included are a result of factoring the problem into small components. The Petri Net of the compact solution with concurrent agents eliminates these unnecessary subnets. This solution structures the problem into the life history of each resource. Thus each path expression of the solution describes which choice resulted in the production of a resource, the production of that resource, and which smoker consumed that resource. Finally, the compact solution with sequential resource production is unlike Parnas' solution since these resources can be produced in any order. This solution structures the problem into a choice between the possible sequences which may occur. The Petri Net presented in Figure 13 without the subnets of the processes is a solution in its own right, and is a live and safe Simple Net.
The transformation rules have allowed an implementation of each solution to be constructed in terms of a Petri Net. Implementations using synchronisation operations (for example P and V operations [4]) would have been difficult and would possibly have led to defining more powerful and convenient synchronisation operations. In addition, the Petri Net semantic definition of the path and process notation has allowed us to program in our notation without regard for queuing disciplines on semaphores and other details of the implementation of synchronisation primitives. Many of the geometric properties of Petri Nets have been exploited by our transformation rules, for example, the ease with which the Petri Nets can be superimposed. In additions we have made use of the notions of liveness, safeness, enabling and the firing rules of transitions.
[1] P.E. Lauer and R.H. Campbell: A Description of Path Expressions by Petri Nets, University of Newcastle upon Tyne, Computing Laboratory, Technical Report Series No.64 May 1974.
[2] S.S. Patil: Limitations and Capabilities of Dijkstra's Semaphore Primitives for Co-ordination among Processes. Project MAC. Computation Structures Group Memo 57, February 1971.
[3] D.L. Parnas: On a Solution to the Cigarette Smokers Problem (without conditional statements), Department of Computer Science, Carnegie-Mellon University. July 1972.
[4] E.W . Dijkstra: Co-operating Sequential Processes, (in Programming Languages, F. Genuys, ed. Academic Press, New York 1968).
[5] R.H. Campbell and A.N. Habermann: The Specification of Process Synchronisation by Path Expressions. University of Newcastle upon Tyne, Computing Laboratory, Technical Report Series, No. 55, January 1974.
