MODELLING AND ANALYSIS OF CONCURRENT PROGRAMS - Modelling with Generalised Stochastic Petri Nets - page 235

rendez-vous with B (A), then the superposition of t A with t B is all what we
need (Fig. 10.4( b)). Moreover the actual communication requires the logical
action of the rendez-vous plus the time for transmission. This is reflected
in the GSPN by expanding the immediate transition into the sequence im-
mediate transition - place - timed transition, as shown in Fig. 10.4( c); the
delay associated with the transition depends on the estimated amount of
exchanged information.
When several input (?) and output (!) statements on the same channel
exist in the code of the concurrent program, they can yield many rendez-
vous. Without making any assumption on the program behaviour we can
only say that each input statement on the same channel x can represent a
rendez-vous with any output statement on the same channel x. Therefore,
we need to superpose each transition that represents an input from x with
all transitions which represent an output on x. In terms of PNs this oper-
ation is a superposition of nets on transitions [22] and it leads to as many
transitions as the product of the input and output statements. Each im-
mediate transition is then expanded into the sequence immediate transition
- place - timed transition, as in the previous case. Fig. 10.5 shows a case
of this more complex situation. Part (a) shows two processes that commu-
nicate on a single channel. Transitions i 1 and i 2 represent input from the
channel and o 1 and o 2 represent output on the channel. Part (b) shows the
two processes with the rendez-vous modelled explicitly. Since either of the
two inputs can be combined with either of the two outputs, we obtain four
possible combinations represented by transitions i 1 o 1 ,i 1 o 2 ,i 2 o 1 ,i 2 o 2 . Each
transition is then expanded as in Fig. 10.4( c).
Let us make a few comments on the di culties of this translation procedure.
The first step requires a preprocessor that produces the process schemas:
this is already a standard feature of many compilers. The second step re-
quires a simple translator based on the rules of Figs. 10.2 and 10.3. The

first two steps can thus be easily automated.
The third step can be problematic if the language allows direct or indirect
recursion of processes within a PAR construct, i.e. if the language allows
dynamic instantiation of processes, which is not the case for Occam. The
fourth step is simple and can be easily automated, but the nets produced in
this manner can be cluttered with arcs if there are many inputs and outputs
on the same channel.

10.3 An Example of Translation

We now introduce an example program to illustrate the translation process.
The program realizes a “printer spooler” that accepts the print requests
of two user programs P 1 and P 2 . The structure of the spooler and of the
user programs P 1 and P 2 is depicted in Fig. 10.6, where Chan 1 and P 1 Sp