Microsoft word - lss98.doc

ACTORS AND COLOURED PETRI NETS IN THE DEVELOPMENT
LIFE CYCLE OF DISTRIBUTED REAL TIME SYSTEMS
Giancarlo Fortino, Libero Nigro, Francesco Pupo
Dipartimento di Elettronica Informatica e Sistemistica Università della Calabria, I-87036 Rende (CS) - Italy Email: {g.fortino,l.nigro,f.pupo}@unical.it Abstract: This paper describes an actor-based framework for the development of distributed real-time systems which centres on a holistic approach to the fulfilment of application functional andtemporal requirements through an application tuneable operating software in the form of a reflectivescheduling structure. The framework makes it possible to prototype and execute a specification of agiven system by Coloured Petri Nets in order to verify behavioural and timing constraints. Themethodology favours a smooth transformation of an analysed system to a design and implementationin popular object-oriented languages like C++ and Java.
Keywords: actors, modularity, timing constraints, Coloured Petri Nets, temporal analysis.
target architecture. The approach ensures a smoothtransition from system analysis to design and In the last years many efforts have been devoted to an implementation in popular object-oriented languages.
exploitation of modularisation and more general softwareengineering principles in the real-time area, e.g., (Bergmans and Aksit, 1996) (Ren et al., 1996). The main difficulty is concerned with a selection of suitableabstractions which can favour modularisation without In the proposed approach (Kirk et al., 1997) (Nigro and impairing fundamental aspects of real time design such as Pupo, 1997) a system is decomposed into a collection of time management (scheduling) and control of the subsystems linked one to another by a (possibly underlying physical architecture. Conventional solutions, deterministic) communications network. A subsystem is e.g., based on plain sequential object-oriented mechanisms the unit of programming in-the-large. Timing constraints or built on top of standard, possibly stripped-down, can be local and/or global. An interaction policy is Operating Systems relying on over-killing concurrent required in general at the system level in order for the facilities (e.g., scheduling driven by priority and pre- subsystems to correctly co-operate in the fulfilment of emption) can be inadequate for real time since they can be lacking of essential abstractions (e.g., concurrency) orcannot be able of guaranteeing a time-predictable A subsystem is structured as a group of actors plus a control machine (see Fig. 1) which is in charge of messagescheduling and dispatching. Actors are the basic building This work claims that an integrated approach based on blocks in-the-small. They interact one to another by user-defined scheduling and selected real time abstractions buffered messages. To help modularisation and time can be the basis for a predictable and modular architecture predictability, a variant of the Actor model (Agha, 1986) is for time critical systems. A methodology is proposed for actually adopted. Actors are modelled as finite state distributed real-time systems which is based on an machines which implement functional behaviour only, i.e., adaptation of the Actor model (Agha, 1986) with a message services. Processing a message consists of a state reflective and time-driven scheduling structure (Kirk et al., transition and the execution of an atomic action. At most a single message can be under processing in an actor at agiven time. As in the Actor model three basic operations The methodology defines a full system development life cycle. Specification and verification activities aresupported by Coloured Petri Nets (CPN) (Jensen, 1992) • new, for the creation of new actors. The data (Nigro and Pupo, 1998) which allow a formal description component of an actor includes as attributes a set of acquaintances, i.e., the known actors (including itself)to which messages can be sent Property analysis, e.g., checking that timing constraints are • send, for transmitting an asynchronous message to a met, rests on prototype execution and simulation. The CPN destination actor. The message can carry data values.
model can be iteratively evaluated during a development as The sender continues immediately after a send more precise timing information is available from the final • become, for changing the actor current state. Each state (EDF) strategy. In a more soft real time context, messages defines a specific behaviour, i.e., a particular way to could simply be timestamped by their dispatch time in a react to expected messages. The processing of an timeline to achieve a control strategy where messages unexpected message can be postponed by storing it in should be delivered as soon as the dispatch time has expired. Minimum timestamp would guide the messageselection process of the Controller. Other solutions are Connection to the controlled environment (e.g., anindustrial plant) rests on terminator actors which have an interface to an I/O device driver and another to regularactors to which normal messages can be transmitted to. Asoften is the case, terminator actors are periodic and can be driven by a scheduler which provide periodic time clauses.
The following describes a CAN based distributed cruise control system (Luqi, 1993) whose goal is, when enabled, to keep a car at a goal_speed by acting on the throttle.
CAN (Kirk, 1995) is a priority bus capable of ensuringdeterministic transmission times for both high and low priority messages (Tindell et al., 1995). It can operate in hostile physical environments and require a preliminarydesign phase of assigning priority to network messages during which each message receives a unique identifierused to resolve conflicts during simultaneous attempts to Actors are not aware of timing aspects. All of this improves reusability since actors can be used according to differentapplication timing scenarios (Nigro and Tisato, 1996).
The example system is partitioned into four subsystems: Timing constraints are handled within reflective actors Motion, Driver, Cruise and Operator. Each subsystem is which act as schedulers in the control machine. A composed of one actor and associated control machine.
scheduler is a filter (Bergmans and Aksit, 1996) which Operator is used to Init (i.e., making ready to run), Start transparently captures local or network originated (i.e., triggering into execution) and Stop (i.e., making no messages and apply to them scheduling actions. Scheduler operating, for safety reasons) the system. Cruise hosts the is also responsible of translating, with the help of control system. Motion reads the speed from a speedometer application actors, from the external network message and acts upon the throttle. Driver senses the buttons Set format into the local format of the subsystem address and Resume, respectively used by the driver to engage cruising at the current speed and to resume cruising to apreviously goal_speed set. Driver is also sensitive to each Actors are concurrent units. Concurrency is ensured, in a use of the Brake and the Accelerator.
subsystem, by message processing interleaving. TheController component of the control machine repeats a Motion includes speed (float), slope (float) and throttle control loop where a message at a time is selected from the (float) data attributes. Cruise has attributes such as speed Message Plan according to a control strategy, anddispatched to the relevant application actor. The latter (float), goal_speed (float), throttle (float) and accelerator provides the service requested by the message and can in turn generate new local or network messages. Localgenerated messages and incoming network messages are The behaviour of the entire system is periodic. The basic eventually scheduled by the Scheduler component by period p1 is dictated by speed sensor technology. In the applying suitable time clauses (Ren et al., 1996) (Nigro following a frequency of 10 readings/sec is assumed, and Pupo, 1997). After that the Controller loop is repeated corresponding to a p1=100 ms.
The overall periodic behaviour is ensured by having the The control machine can be customised through system which is initialised and started “synchronously” by programming. First of all, the Scheduler actor can be the Operator (the character of CAN as a network with a replaced to reflect special application-dependent “virtual zero” transmission time, when comparing the time requirements. In addition, messages can be scheduled in granularity of the application (ms) with the effective the Message Plan according to different timing schemes transmission time of a typical control packet (e.g., 130 µs), and Real Time Clock systems. For example, a time validity should be noted) and by ensuring that Motion and Driver interval [tmin, tmax] can be attached to each message m to express the constraint that m can’t be dispatched beforetmin and should not be dispatched after tmax to avoid a Although Brake, Set, Resume and Accelerator are naturally timing violation. In this case, the selection process of the sporadic sources of messages, for the purposes of the Controller should be based on a Earliest Deadline First example, also considering the physical dynamics of the system, they are polled periodically with a period p2 of 1 s.
Therefore, both Motion and Driver use a local Readmessage for maintaining the reading process.
Different factors, local + global, contribute to ensuring thereal-timeness of an actor system. In the small, message In response to the Read message, Motion and Driver responses (actions) in actors must have a bounded sample the external environment for reading respectively execution time. Therefore some constructs should be the Speed (Motion), Set (Driver), Resume (Driver), Brake avoided (e.g., recursion, loops without bounded iterations, (Driver) and Accelerator (Driver). Motion/Driver will send dynamic data structures . ). In the large, an adequate to Cruise the just read quantity through a suitable Speed, interaction policy among the various control machines must Set, . message. Normally, Driver will find only one be designed which depends on the application external condition verified per period. Indeed, the use of requirements and the assumptions of the adopted Set is mutually exclusive with Resume and so forth. The communications network. For the cruise example over sensed condition is transferred to Cruise by an inter- CAN, an interaction policy results from a priority assignment to network messages and a suitable choice ofthe time clauses within the schedulers. The following As a consequence of a Read message, two transactions or threads of control (chains of causally connected messages)are respectively started in Motion and Driver. The thread ( Stop, Init, D_OkInit, M_OkInit, C_OkInit, Start, Brake, originating into Motion is composed of the Speed message Accelerator, Speed, Throttle, Set, Resume ).
sent to Cruise, followed by the Throttle message generatedby Cruise toward Motion. The second thread ends in the Figure 4 summarises the time clauses embodied by the Cruise subsystem since any sensed variable affects only the different schedulers, in Java syntax. m denotes a “just sent Cruise state (e.g., enabling/disabling cruising).
message”. Scheduling uses time validity intervals formessages (see section 2). m.cause() denotes the message For safety reasons, Brake or Accelerator, which can whose processing generated m. m.iTime() returns the disengage cruising, are to be handled with a tight deadline invocation time of m. now() returns the current time.
of 1 ms measured since the capture time. On the otherhand, during cruising the throttle is required to be acted within a 100 ms deadline. Similarly, a stop command from if( m instanceof Read && m.cause()==m ) the operator is expected to be managed within 1 ms. Figure schedule( m, m.cause().iTime()+p1, m.cause().iTime()+p1 );else schedule( m, now(), now() ); 2 summarises the timing requirements of critical threads.
if( m instanceof Read and m.cause()==m ) schedule( m, m.cause().iTime()+p2, m.cause().iTime()+p2 ); Figure 2: Timing requirements of critical threads.
It is worth noting that the Cruise subsystem acts as a globalsupervisor and is strictly reactive. In addition, timinginformation such as p1 and p2 are fed to the scheduler speed=0.0; goal_speed=0.0;throttle=0.0;become(INITIALIZED); Components of the described actor framework (actors, subsystems, schedulers, control machines, network interfaces and protocols, .) can be formally described by Coloured Petri Nets (CPN) (Jensen, 1992) to enable validation activities (Jensen, 1994). The aim is to build a system specification which can be executed in order to test both functional and temporal properties (Nigro and Pupo, (goal_speed-speed)*30.0;send throttle to Motion; 1998). CPNs can be used in the context of Design/CPN (Jensen et al., 1996) which favours the specification of a complex system by modularising it into subnets (pages) Figure 3: Cruise actor functional behaviour.
The following shows some components of a CPN model forthe cruise control example. Fig. 5 is the topmost level page Object Oriented Analysis (OOA) methods like Shlaer- in the model. It represents the more abstract view of the Mellor, OMT . can directly be used for visualisation system and consists of the four subsystems linked to one purposes of static structure and dynamic behaviour of another by CAN. Each high-level component is modelled actors. Figure 3 summarises the State/Event/Action model by a substitution transition and in turn is Hierarchically of the cruise actor. It should be self-explanatory.
Substituted (HS) in a subpage containing the specialisation details. The substitution operation is accomplished by a Fig. 7 shows the Cruise subsystem subnet. It includes the binding between sockets in the super page and control machine, the Cruise actor and the input/output corresponding ports in the subpage. Fig. 6 depicts a CAN subnet. NBufIn is a port-place linked to all the outputsocket-places in the various subsystems. It is used to The list of the expected external messages is carried by the broadcast a network message. The token-message list in token in the ExpMsgs place. A CAN message is actually NBufIn contains, at any moment, the set of sent messages received by the transition FromCAN which translates and ranked by priority, waiting to be transmitted by CAN.
appends it to the local generated message list (place Transition CANarb models the arbitration process. The CMPIn). An output network message is transmitted by highest priority message is actually selected by CANarb ToCAN transition which inserts it ranked into the message only when the network is idle. Transition CANTrans list of NBufIn place of the CAN net (NBufIn and ToNetP models the message broadcast and its transmission delay.
are mirroring places). The scheduler subnet applies thetime clauses of the Cruise subsystem according to Fig. 4.
The controller subnet implements message selection anddispatching operations of the control machine. Selection isbased on the EDF strategy. The Cruise actor subnet isshown in Fig. 8. The model embodies theState/Event/Action diagram of Fig. 3. It generates CANmessages through the CAToNet place which mirrorsToNetP1 output place of Fig. 7. The time-consumingactivity (action) is implemented by transition CruiseActwhich is in charge of accepting an incoming message andprocessing it by suitable arc inscriptions (ML functions)which update the actor internal status and attributes.
Design/CPN allows both informal and formal analysismethods to be applied to an achieved system model.
Informal analysis can be based on model simulation(specifications testing (Ghezzi et al., 1991)), i.e., byproviding an initial marking and then by tracing one ormore possible resulting behaviours. By observing thesebehaviours the analyst can realise whether or not thespecified system meets functional or temporalrequirements.
Figure 5: Top level CPN model for the Cruise system.
Formal analysis consists in defining general properties ofthe net model which reflect special types of desirable (orundesirable) behaviours of the specified system, and thenusing the specification to formally prove (or disprove) suchproperties. For this purpose the occurrence graph (OG)method (Jensen, 1994) can be used. An OG is a directedgraph which has a node for each reachable marking and anarc for each occurring binding element. An arc links thenode of the marking in which the associated bindingelement occurs to the node of the marking resulting fromthe occurrence. All standard properties like absence ofdead markings, reachability and boundedness analysis .
can be checked on the OG. It is worthy of note that the OGmay become very large, even for relatively small nets, thatit cannot possibly be generated even with the mostpowerful computer. Another limitation is dependency fromthe initial marking: each possible initial marking mayoriginate a different occurrence graph.
Functional analysis of the Cruise system was conducted byusing a simple mathematical model for the motion model(Luqi, 1995) and by tracing the causally connectedmessages of every thread at the Design/CPN graphicaluser-interface, e.g., by a step-by-step simulation.
From the temporal point of view Design/CPN doesn’tprovide specific analysis techniques. However, the generalsupport for functional analysis together with a primitive time notion, ensured by a global clock, can be used to achieve a timing analysis framework for actor systems message from the Plan can require an update of the system (Nigro and Pupo, 1998). Transitions can be assigned a clock to the lower bound of the message time validity delay. Tokens are timestamped by transition fire times.
Generated tokens are frozen in the output places until thesystem clock gets advanced to their timestamp. At any The frozen behaviour of generated tokens is compatible instant the system clock is advanced to the token with the simulation of a distributed system. Different timestamp representing the minimum time increment in the actors into different subsystems/processors are capable of whole CPN model. The timestamp of a token can be concurrent execution. However, the simulated CPN clock modified by a transition predicate or an arc inscription.
is always augmented by the minimum timestamp thus This was exploited in the realisation of the control machine preserving its chronological advancement.
subnet where, in general, the selection of the next dispatch Figure 7: The Cruise subsystem subnet.
Besides querying the OG for standard properties, non standard properties. One such a function can capture specific ML functions can be introduced for checking the verification of a temporal property in positive or negative form, e.g., one like the following: “is it always true that for each instance of a given transition firing(representing, e.g., the beginning of a thread) there This paper describes a computational model based on always (as the OG state space allows) exists an instance actors which makes it possible to develop distributed of the corresponding transition firing (modelling, e.g., real-time systems. The model favours time-predictability the end of the thread) such that the time distance and relies on non-preemptive light-weight concurrency.
between them is less than a fixed time interval (e.g., A distributed system can be formalised by Coloured deadline of thread execution) ?” The negative form of a Petri Nets (CPNs) in order to support functional and property can be more immediate. In this case the temporal validation activities. Ensuring predictability at existence of a single occurrence of a searched event that the system-level strongly depends on the adopted contradicts the property is sufficient to assert that the Directions of current work cover an application of the For the temporal analysis of the Cruise system, the actor actor framework and CPN modelling to challenging transitions were annotated by an estimation of worst- distributed measurement (Grimaldi et al., 1998) and case-action-execution-times, which were 40 msec for the multimedia systems (Fortino et al., 1998) over Internet.
Motion, 0.4 msec for the Cruise and 10 msec for theDriver. The system was then studied by generating its OG for a simulation period where significant activity Work carried out under the financial support of the occurs, e.g., by ensuring that when cruising is enabled Ministero dell'Università e della Ricerca Scientifica e multiple and conflicting threads are interleaved.
Tecnologica (MURST) in the framework of the Project"Methodologies and Tools of High Performance Systems Fig. 9 exemplifies an ML check function that verifies the deadline of cruising under automatic control. Forsimplicity, the transmission of message data is disabled,thus focusing on temporal aspects only. Similar functions can be written for checking the deadline of aBrake or Stop message.
Agha, G. (1986). Actors: A model for concurrent computation in distributed systems, MIT Press.
Bergmans, L. and M. Aksit (1996). Composing synchronisation and real-time constraints. J. of Parallel and DistributedComputing, September.
Grimaldi, D., L. Nigro, and F. Pupo (1998). Java based distributed if ((ArcToTI(a) = TI.MotionActor'MotionAct 1)andalso measurement systems. To appear on IEEE Trans. on (StripTime(Mark.MotionActor'PSNet 1 (DestNode(a))) = Instrumentation and Measurement.
Fortino G. and L. Nigro (1998). QoS centred Java and actor based framework for real/virtual teleconferences. Proc. of SCS EuroMedia98, Leicester (UK), pp. 129-133.
if ArcToBE(b) = Bind.MotionActor'MotionAct(1, Jensen, K. (1992). Coloured Petri Nets - Basic concepts, analysis methods and practical use. Vol. 1: Basic concepts. EATCS
Monographs on Theoretical Computer Science. Springer-Verlag.
then ((OccurrenceTime(b)-OccurrenceTime(a))<100.0) Jensen, K. (1994). Coloured Petri Nets - Basic concepts, analysis methods and practical use. Vol. 2: Analysis methods. EATCS
Monographs on Theoretical Computer Science. Springer-Verlag.
Jensen, K., S. Christensen, P. Huber and M. Holla. (1996).
Design/CPN. A reference manual. Computer ScienceDepartment, Figure 9: Cruise control deadline checking function.
Kirk, B. (1995). Real time protocol design for Control Area Networks. Proc. of Real Time Systems’95, pp. 251-268.
CruiseDeadln() tries to build a list with instances of the Kirk, B., L. Nigro and F. Pupo (1997). Using real time constraints MotionAct transition of Motion actor corresponding to for modularisation. Proc. of Joint Modular LanguagesConference, Springer-Verlag, LNCS 1204, pp. 236-251.
the generation of a Speed message (beginning of thread) Luqi (1993). Real-time constraints in a rapid prototyping which are followed by a causally connected instance of language. Computer Languages, 18(2), pp.77-103.
Nigro, L. and F. Pupo (1997). A modular approach to real time the MotionAct transition corresponding to a Throttle programming using actors and Java. Proc. of 22nd IFAC/IFIP processing (termination of the thread) which doesn’t Workshop on Real Time Programming, Lyon, 15-17 fulfil the deadline. The function always returns an empty Nigro, L. and F. Pupo (1998). Using Design/CPN for the list, thus the property is satisfied.
schedulability analysis of actor systems with timing constraints.
Proc. of Workshop and Tutorial on Practical use of Coloured The CPN model supports incremental development Petri Nets and Design/CPN, University of Aarhus, AarhusDenmark, 8-12 June.
according to a spiral system life cycle (Verber et al., Nigro L. and F. Tisato (1996). Timing as a programming in-the- 1997). As the temporal information (message processing large issue. Microprocessors and Microsystems, 20(4), pp.
times) become more precise, i.e., the project is tuned to the target physical architecture, system timeliness can be Ren, S., G. Agha and M. Saito (1996). A modular approach for programming distributed real-time systems. J. of Parallel and re-checked and requirements possibly adjusted to ensure Distributed Computing, Special issue on Object-Oriented Real- guaranteed schedulability. The key point is that the CPN model closely mirrors the design and implementation Tindell K., A. Burns and A.J. Wellings (1995). Analysis of hard real-time communications. Real-Time Systems, 9(2), pp.147-
models. Conclusions drawn from the analysis model can directly be interpreted at the more low level stages of Verber D., M. Colnaric, A.H. Frigeri and W.A. Halang (1997).
Object orientation in the real-time system lifecycle. Proc. of 22nd IFAC/IFIP Workshop on Real Time Programming, Lyon,15-17 Sept. 1997, pp. 77-82.

Source: http://si.deis.unical.it/fortino/research/publications/conferences/pdf/lss98.pdf