Claus Assmann
Department of Computer Science
University of Kiel
Preusserstr. 1-9
D- 24146 Kiel
Germany
e-mail: ca@informatik.uni-kiel.de
Phone: +49 431 560457
FAX: +49 431 566143
Keywords: distributed computing, cooperating processes, coloured petri nets, formal verification
The specification of programs for distributed computer systems is still a difficult task. There are many proposals to solve this problem or at least to ease this task and to support programmers. The two extreme approaches are on the one hand those which completely rely on a compiler, and on the other hand those that lay control completely in the hand of programmers. The first one might be the best way for the future, but current compiler technology works only for a subclass of applications, e.g., numeric computations on arrays. The second one is barely manageable and very error prone, since it is at least one order more complex than sequential programming, due to timing problems, unwanted non-determinism, deadlocks, etc.
Since both extreme approaches contain several problems,
most programming systems for distributed computing
are based on a compromise.
They offer either a restricted model for concurrent execution
to minimize the number of possible errors,
or they use annotations to guide the compiler
to generate efficient code for distributed computer systems.
An interesting class of approaches consists of the
so-called coordination languages.
These programming systems provide a specification level in which
the communication between conventional (sequential)
programs can be expressed,
either in textual form like in
PCN
[FOT92],
or by graphical representations like in HeNCE [BDG
92]
and in Enterprise [LLM
92].
This approach has some promising features:
it allows for the re-use of existing (sequential) programs,
with no or only little changes,
it provides a clean separation between
communication and computation,
such that both can be investigated and optimized
without too much interaction.
Our proposal K2 includes a restricted communication paradigm, which greatly simplifies the task of the programmer without giving up too much expressive power. It provides two clearly separated specification levels: one for the computation and another one for the communication. The communication structure is specified by a variant of coloured Petri-nets [Rei85,Jen91], for the algorithmic specification well-known conventional languages like C, FORTRAN, etc. can be used.
K2 is based on a variant of coloured Petri-nets. A Petri-net is a directed, bipartite graph composed of transitions (processes) and of places (streams).
We restrict ourselves to synchronization graphs, e.g., streams connect just one producing and one consuming process. This restriction excludes conflicts which decidedly simplifies the execution model. Although synchronization graphs allow only for the modeling of deterministic systems, a controlled form of non-determinism is introduced in K2 by additional process types.
Petri-nets have several advantages for system modeling, among which are: the well-defined semantics makes them amenable for formal analysis, a concept of true concurrency, i.e., concurrent events may occur in any order, and the possibility of interactive simulations which allow for the validation of the model.
The process systems perform the computations defined by the inscriptions of the net components. Inscriptions assigned to
Figure 1: Simple process with input and output streams
Fig. 1 shows a simple process Comp together with its input and output streams, which act as FIFO-queues with finite capacities. If we assume C as the programming languages for the process, the input parameters I1, ..., In can be of any valid type, as long as they correspond to those of the streams. The output parameters O1, ..., Om should have a pointer type to serve as result values. A process (transition) is enabled iff there are enough tokens on the input streams and there is sufficient free space on the output streams. This is a property which can be easily checked. If a process is enabled, it can ``fire'', i.e., consume a set of input tokens, perform a computation on them, and produce a set of output tokens. In our example the function would be called with the first token from each input stream and pointers to tokens for each output stream. After the computations finishes, the result values would be send to the output streams.
Since the simple firing rule is too restrictive for general communication patterns, some additional process types are introduced. These include SPLIT which sends tokens from an input stream to one of its output streams and SELECT which selects one of its input streams for the output stream, both depending on the value of a control token. The process type MERGE introduces a controlled form of non-determinism, e.g., for client/server systems. It non-deterministically selects a token from its input streams and assigns it to the output stream.
So far we have described atomic processes which are the basic building blocks of K2 . To specify larger process systems, abstraction mechanisms as in conventional programming languages must be available. K2 provides for this purpose hierarchical processes which compose multiple processes into a new one whose external behaviour is similar to that of an atomic process. This gives the desired compositionality of process systems, which is an essential for the design of large systems, since each component can be verified or validated on its own.
Figure 2: A hierarchical process
An example for a hierarchical process is depicted in fig. 2. It is shown in two variants: on the right the abstraction, i.e., just the input/output interface, on the left its internal structure with four local processes. The vertical double bars of the refinement serve as synchronization of the input and output tokens, respectively. For each hierarchical process the programmer can specify a maximum number of concurrently active invocations, which will operate as a pipeline. This is shown in fig. 2 by the two lower streams of the refinement (one inside and one outside the box) whose capacities put an upper limit onto the number of active processes. This synchronization distance might be further reduced by the capacities of the internal streams, since they control the activation conditions for the internal processes.
To specify dynamically expanding process systems, recursive processes can be used. A hierarchical process which refers to itself will be recursively expanded when invoked. The control over the recursion can be done with the SPLIT and SELECT process types, similar to an IF-THEN-ELSE construct in a conventional programming language. By using recursive processes specification regular communication structures can be composed which may adopt according to the actual workload or load balancing requirements.
The implementation is based on
the message passing system
PVM [GBD
94],
since the re-invention of existing communication packages would
only delay the realization.
To simplify the implementation each user specified process is embedded in a wrapper which manages the connected streams, checks the activation conditions, feeds the input values to the user defined process, and sends the result values to the output streams.
Since each process usually has input and output streams, these must be part of the wrapper. A stream connects at most two processes, so we need to decide where to place the buffer for the streams.
The buffers of the input streams are associated with the processes to allow for a fast invocation of the user defined process but the output streams are not, since they are the input streams of the consumer processes. The input stream data type contains complete data to manage a stream, e.g., its maximum capacity, the current number of tokens in the stream, an identifier for the connected process, a tag which encodes the type of the message and the number of the stream at the opposite end, and a counter for flow control.
The user defined process is activated iff there are enough tokens on the input streams and there is sufficient free space on the output streams. To check these conditions, the wrapper maintains two activation counters ( not_I_act, not_O_act) which are initialized with the number of input and output streams, respectively. They are possibly modified during input/output operations and represent the number of still not activated input/output streams. If both reach zero, the process is activated.
Since streams have a finite capacity, a flow control mechanism must be established. To minimize communication overhead each side of a stream maintains its own flow control counters ( I_FC, O_FC), which will be only exchanged when necessary. The counters are initialized with the capacity of the stream and are updated each time a token is send or received. For an output stream it represents the maximum number of token which still can be send without interchange of control information. If this flow control counter reaches zero, the activation will be disabled. The input side of a stream will send a new value for this flow control counter if its own counter reaches a lower watermark. This counter is always greater than or equal to the corresponding counter at the producer.
The algorithm realized by the wrapper is given below:
while not terminated:
get input from any source (blocking); switch on MsgTag:
IsData? put received data into buffer, decrement I_FC
possibly decrement not_I_act
IsControl? add received value to O_FC, possibly decrement not_O_act
while activated:
get data from stream buffers, possibly increment not_I_act
perform flow control
perform computation
send results to output streams, decrement O_FC, possibly increment not_O_act
The algorithm has two interlocked loops, the outer loop finishes when the whole process system stops, the inner loop runs as long as the activation condition is satisfied. In the outer loop data and control information is received from other processes and processed according to its type, which is encoded in MsgTag. This might change the activation counters such that the inner loop will be entered. In this case the user defined process is called with the appropriate values from the streams and after finishing, the result values are sent to the output streams. This might disable the activation condition in which case the inner loop will be left.
A more sophisticated version of the system will include a compiler which performs some optimizations to minimize communication overhead. E.g., there will be no simple processes which just redistribute data, but these will be integrated into others.
Other possibilities for optimization arise from special cases, e.g., when the capacity of a stream equals one, or if a process has only one input and one output stream.
We have presented a coordination language K2 which enables programmers to specify the communication between conventional (sequential) programs. As long as compilers are not able to create efficient programs for distributed memory computers, there must be some support by programmers. Most available programming systems cause too much problems due to the complexity of specifying computations and communications within the same program. This includes timing problems, unwanted non-determinism, deadlocks, etc.
Even though PCN, Enterprise, and our proposal K2 all belong to the class of coordination languages, the approaches differ substantially. PCN uses a separate programming language for the specification of the communication structure, Enterprise offers a predefined set of skeletons similar to those found in organizations, and K2 relies on a variant of coloured Petri-nets for this task.
Of these three approaches only K2 is amenable to formal analysis, since it is based on Petri-nets for which such tools exist. Moreover, it allows for the interactive execution of the specified systems such that a simple validation method (for debugging purposes) is available, too.
The advantage of coordination languages in general and in particular of the approach taken by K2
is the clear separation of communication structure and algorithmic specification. This allows for their independent optimization, e.g., the communication structure may be adopted to different computer architectures without influencing the algorithmic specification. If both parts are interwoven this is far more complicated, it maybe requires a complete rewrite. Coordination languages allow to apply well known techniques to each specification level for optimization, validation, and verification. Existing sequential programs can be re-used for the algorithmic specification of (atomic) processes.
One disadvantages of this approach is the fact that some communication structures are difficult to specify, and especially for K2 its restricted communication model. To perform a computation a set of token must be consumed from all input streams, and thereafter the generated values are send to all output streams. This sometimes require the re-formulation of an algorithm to adhere to this restriction. E.g., if an algorithm requires communication during a computation, the algorithm has to be split up in (two or more) parts, such that communication only occurs when the process is started and when it finishes.
92
94
92
Specifying Systems of Cooperating Processes
This document was generated using the LaTeX2HTML translator Version 95.1 (Fri Jan 20 1995) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -address ca@informatik.uni-kiel.de -split 0 -dir /tmp/l2h t.tex.
The translation was initiated by Claus Assmann on Wed May 24 16:55:23 MET DST 1995