Real-Time Syst (2007) 35:181-208
DOI 10.1007/s11241-006-9007-9
Modeling distributed real-time applications with specification PEARL
Roman Gumzej · Shourong Lu
Published online: 6 December 2006
?C Springer Science + Business Media, LLC 2007
Abstract The methodology of hardware/software co-design of embedded control systems with Specification PEARL is presented. Hardware and software are modeled with the language Specification PEARL, which has its origins in standard Multipro-cessor PEARL. Its usefulness is enhanced for modeling hierarchical and asymmetri-cal multiprocessor systems, and by additional parameters for schedulability analysis. Graphical symbols are introduced for its constructs to enable graphical modeling while maintaining the semantical background. It is meant to be a superlayer for pro-grams, based on the PEARL programming model. To model program tasks, Timed State Transition Diagrams have been defined. The model of a co-designed system is verified for feasibility with co-simulation. The resulting information should be used when considering changes in a current design with the goal of producing a temporally feasible model. To support dynamic re-configurations, configuration management is introduced into the models. Since UML is becoming a de facto standard also for de-signing embedded control systems, and since Timed State Transition Diagrams and State Chart Diagrams share great similarity, an interface of the methodology to UML 2 is defined, using UML's extension mechanisms.
Keywords Specification languages . Application modeling . Co-design . Co-simulation . Configuration management . PEARL . UML
R. Gumzej (?)
Faculty of Electrical Engineering and Computer Science, University of Maribor, 2000 Maribor, Slovenia
e-mail: roman.gumzej@uni-mb.si
S. Lu
Chair of Computer Engineering, Fernuniversit¨at in Hagen, 58084 Hagen, Germany e-mail: shourong.lu@fernuni-hagen.de
Springer
182 Real-Time Syst (2007) 35:181-208
1 Introduction
For real-time systems timeliness and safety issues are just as important as functional correctness. Hence, they should be designed holistically, considering all their compo-nents and functional properties, as well as their subsequent verification.
To enable verification, often formal languages and/or mathematical notations are used, for which subsequently a proof can be worked out (e.g., formal languages and timed automata (Agha, 1991), graphical techniques with the same expressive power as their formal language counterparts (Dietz, 1997), and combinations of conventional CASE methods and statecharts (Traore et al., 1997)). While enabling formal verification, most of these methods lack the versatility of basic constructs and user friendliness. Therefore, graphical formalisms with richer sets of basic con-structs have been defined (e.g., CSR/CCSR by Lee et al., 1991, and GCSR by Ab-dallah, 1996, TTM/RTTL by Ostroff, 1997), while keeping enough "strictness" to enable verification. Dedicated state transition automata like CRSM (Shaw, 1992) are often used as basic internal computation models (e.g., POLIS (Balarin et al., 1997)).
An example for the wide variety of verification methods, which can be used for embedded real-time systems, is the VHDL language, for which verification meth-ods have been devised, ranging from formal methods to simulation with fault in-sertion and combinations thereof (e.g., Khalil et al., 1998). For pragmatic reasons and to avoid combinatorial explosion with formal verification or exhaustive test-ing, simulation is often used to check the correctness of a designed system or parts thereof. Co-designing systems with time limitations led to the introduction of real-time scheduling strategies into their co-design and co-simulation (e.g., Mooney, 1998).
Some novel object-oriented design techniques have been devised for different as-pects of real-time systems design (cp. Henzinger et al., 2003; Hylands et al., 2003; Licht, 2004; Gausemeier et al., 2004; Schr¨oter et al., 2003; Bitsch et al., 2005), which are partly based on UML and its real-time profiles RT-UML (Douglass, 1999) and UML-RT (Selic and Rumbaugh, 1998). To explicitly address real-time issues in UML 2, the Profile for Schedulability, Performance and Time (OMG, 2005) has been defined by OMG.
In this article, the features of the Specification PEARL (S-PEARL) hardware/soft-ware co-design methodology are presented, namely, the specification language and notation, which represent hardware/software architectures, timed state transition di-agrams, which represent the program tasks of a real-time application, configuration management for dynamic system (re-) configuration, and co-simulation to check the temporal feasibility of designs.
After the description of the S-PEARL modeling approach, it is shown how an interface of the S-PEARL methodology to UML (OMG, 2004) can be built. Since UML, being a prominent methodology for designing information systems, is also used to design embedded systems, an interface from Specification PEARL is defined to enable S-PEARL-like design in UML. Combining both methodologies could en-able larger-scale S-PEARL-oriented design of real-time systems in combination with UML's versatile diagrammatic features.
Springer
Real-Time Syst (2007) 35:181-208 183
ARCHITECTURE; STATIONS;
NAMES: KP;
PROCTYPE: MC68370 AT 20 MHz; WORKSTORE: SIZE 65536 SPACE 0 - 'FFFF'B4
READ/WRITE WAITCYCLES 1; WORKSTORE: SIZE 32768 SPACE 0 - '7FFF'B4
READONLY WAITCYCLES 1; INTERFACE: KP_IO (DRIVER: KPINOUT;
DIRECTION: INPUT; SPEED:20971520 BPS; UNIT:FIXED);
STATEID: (NORMAL, CRITICAL); STATIONTYPE: KERNEL; SCHEDULING: EDF; MAXTASKS: 20;
MAXSEMA: 5;
MAXEVENT: 15;
MAXEVENTQ: 5;
MAXSCHED:30;
TICK: 1E-3 SEC;...
SYSTEM;
NAMES: KP;
KP.KP_IO INOUT;
NAMES: Sensor 1;
Sensor1.S1 OUT;
NAMES: Sensor 2; ...
NAMES: TP1;
TP1.S1 IN;
TP1.TP1_IO INOUT;
NAMES:TP2; ...
SYSEND;
CONFIGURATION;
COLLECTION KP_WS;
PORTS KP_TP1-lin, KP_TP2-lin;
CONNECT KP_WS.KP-TP1_lin INOUT TP1-WS.TP1_KP_lin VIA KP.KP_IO;
CONNECT KP_WS.KP_TP2_lin INOUT TP2_WS.TP2_KP_lin VIA KP.KP_IO;
COLEND;
COLLECTION TP_WS;
PORTS S1, TP1_KP_lin;
CONNECT TP1_WS.S1 IN VIA TP1.S1;
CONNCET-TP1_WS.TP1_KP_lin INOUT
KP_WS.KP_TP1_lin VIA TP1.TP1_IO;
MODULES TP1_WS_M1;
EXPORTS(Side 1);
TASK Side1
TRIGGER PORT S1;
DEADLINE 100;
TASKEND;
MODEND;
COLEND;...
CONFEND;
ARCHEND;
NET;
KP.KP_IO <-> TP1.TP1_IO;
KP.KP_IO <-> TP2.TP2_IO;
TP1.TP1_IO<-> Sensor1.S1;
TP2.TP2_IO<-> Sensor2.S2;
NETEND;
Fig. 1 Example of an S-PEARL textual architecture description based on Multiprocessor PEARL (note additional parameters)
2 Specification PEARL methodology
The Specification PEARL co-design methodology is based on the notation of standard Multiprocessor PEARL (DIN 66253, Part 3 Multiprocessor PEARL, 1989), where a textual (e.g., Fig. 1) system architecture description consists of divisions, which de-scribe different aspects of a system's design. It enables the construction of conceptual system models, whereby the hardware and software architectures may be described in parallel. A system model is built and can be checked for coherence with the Spec-ification PEARL methodology by running the associated CAD tools (cp. Gumzej, 2004). For more information on the constructs, their properties and notation of the Specification PEARL language cp. (Gumzej, 1999). Benefits of using the S-PEARL methodology are the abilities to
reason on system integration at an early stage,
introduce timing constraints wherever applicable into a design, and check the temporal feasibility of a design before implementation.
2.1 Modeling of software/hardware architecture
In the mentioned methodology, hardware and software architectures are described conjunctly.
Springer
184 Real-Time Syst (2007) 35:181-208
STATION LAYER COMPONENT LAYER
BASIC PROCTYPE
KERNEL WORKSTORE
TASK DEVICE
COMPOSITE BUS
CONNECTION
CONNECTION
Fig. 2 Hardware architecture constructs of S-PEARL
COLLECTION LAYER MODULE LAYER TASK LAYER
MODULE TASK
COLLECTION
CONNECTION
Fig. 3 Software architecture constructs of S-PEARL
A hardware model consists of STATIONs, being the processing nodes of the system. Their components (see Fig. 2) are chosen from a list of general components such as processors, memories, or interfaces. These components determine the structure of stations and, on the other hand, they also represent their resources and provide the necessary timing information for schedulability analysis.
A software model is composed of COLLECTIONs, which are mapped to the STA-TIONs of the hardware model, depending on their state information (see Fig. 3). They consist of MODULEs of TASKs. At any time, there is exactly one collection assigned to run on a station. Thus, the collection is also the unit of dynamic re-configuration.
To administer collections, a Configuration Manager (CM) is required, which forms a layer between the real-time operating system (RTOS), if any, and the applications. Its rˆole is to function as (1) a hardware abstraction layer, (2) a hardware/software interface, and (3) as an "Inter-Collection" co-operation agent. In order to form executable units, the CM is joined with the application model and compiled for the target platform, or additionally joined with the co-simulation environment for temporal feasibility checking (as shown in Fig. 4).
2.2 Task modeling
According to (Mok, 1991), the computational model of most applications running in the real-time mode can be written in the form of the following "equation":
Springer
Real-Time Syst (2007) 35:181-208 185
HW specification SW specification
CM Module
Specification
PEARL Coherency
check Virtual machine
HW/SW architecture +
Task representation
Specification PEARL model
Execution Co-simulation
Return information
Fig. 4 Interrelations between hardware/software models
Real ? time program model
= Dataflow model + State automaton + Timing limitations
The tasks of an application represent the processes in a running system. They are mainly characterised by activation conditions and timing limitations as well as by be-ing part of certain collections. This information is sufficient to build a coarse program model, but it is not enough to determine its feasibility. Therefore, timed state transition diagrams have been introduced to represent them (cp. Gumzej and Colnari?c, 2003). Their synchronisation and inter-communication are realised by calls to the config-uration manager and/or the real-time operating system of the station executing the task.
Task State Transition Diagrams (TSTD) are hierarchical finite state automata con-sisting of
start states: task activation conditions and initialisation actions, working states: atomic activities with possibly predictable duration,
super states: non-atomic activities - hierarchical decomposition of working states, and
final states: finalisation actions.
Every state contains the following data:
state type: start-, working-/super- and final state,
pre-condition for the state's execution: activation condition in case of a start state, time frame: shortest and maximum execution times,
timeout action: the action executed in case a state exceeds its time frame, connection(s) to the next state(s) in case the execution continues successfully, and activities carried out within the execution of this state: program code with PEARL
system calls.
Springer
186 Real-Time Syst (2007) 35:181-208
The connections between states represent the progress of tasks in time. All connec-tions are local (i.e., bound to the states of one task). Inter-task co-operation is modeled by the state actions, i.e., system calls to the operating system, through the configuration manager. These also trigger the continuation pre-conditions of the states. Operating system and configuration manager are visible to the designer through their system calls (API) and system configuration, which is defined by setting the parameters of the corresponding STATION, only.
Trigger conditions differ slightly depending on the state type. Only start states have the possibility of explicit (on-demand) activation. Other state types rely on the following types of pre-conditions:
external events (int(no)), representing interrupts, internal events (sig(no)), representing signals,
timers (timer(at,every,during), representing timer signals,
general conditions (cd(expression)), i.e., expressions returning Boolean results from the evaluation of internal system/program states or data structures of the operating system.
Only final states may progress automatically (without a pre-condition; upon suc-cessful completion control is returned to (an) initial/start state(s)). Upon fulfilling the pre-condition of a superstate, control is automatically transferred to the start state of its subchart. If the condition to proceed to the next state is fulfilled by the maximum time frame (maxT) of the current state, the corresponding connection for successful continuation is followed. If a minimum time frame is foreseen (minT), it is not checked whether the continuation conditions are fulfilled, before the specified time has elapsed. The timeout condition is set to the maximum time frame at the beginning of each state's execution. In case a timeout occurs before the requested resources are available (the next state's pre-condition is fulfilled), the appropriate on-timeout action is executed. If it is not specified, an error has occurred (and is logged in the co-simulation). The activities within a state are a set of actions, which are carried out while a task is in this state. It is assumed that the actions form a single block of program statements including system service calls to the operating system and/or configuration manager, around which the control structure is formed by transforming the chart to program code. Their execution times are estimated by the designer and used in setting the time frames for each state.
2.2.1 Guidelines for task modeling
The rˆole of a "task" is the same in the Specification PEARL methodology as it is in the programming language PEARL (DIN 66253 Parts 1, 2; 1981, 1982)-any procedure, which needs to be carried out within a given time frame, is a task. The problem in trying to break down the operations of tasks into states is that simple tasks have only three states: start, working and final. New states are only introduced
(1) if a time-limited atomic (sub) operation is identified, (2) if synchronisation or communication between tasks is necessary, or (3) to define branching into different continuation paths depending on the pre-conditions of successor states. The following criteria were selected to form task states:
Springer
Real-Time Syst (2007) 35:181-208 187
a state represents a single logical activity, which is only dependent on its pre-conditions and whose execution time can be determined or predicted,
any task must have at least one start-state, one or more working/superstates, and final states,
in order to ease good decomposition, a complex operation shall be broken down into individual states by introducing a superstate on the current level and defining its operations in a subchart.
2.2.2 Translation from TST-diagrams to program tasks
TSTD task models are translated to program tasks in two forms:
1. target platform oriented, as it can be compiled by a corresponding compiler and executed on a specified hardware architecture, and
2. simulation oriented, as it is used and interpreted by co-simulation in a simulation environment.
The main difference between the two forms is the way external events are handled. In the first case, they are generated by the environment and handled as hardware interrupts (by the interface device drivers), whereas in the second one, they are generated in the co-simulation environment and handled as software signals (by the stub device drivers) through the RTOS.
The forms of diagram representation and storage as well as the mechanism to trans-late TST diagrams to program task prototypes are discussed and illustrated throughout the following example. The general form of task prototypes, obtained from TSTDs, is shown in Fig. 5.
2.2.3 Example of a translation from TSTD to task
This example is to illustrate the use of TSTDs on a simple task model to control a traffic light at a pedestrian crossing. The traffic light is controlled by a simple logic with the output to set the lights and a relay switch to request pedestrian crossing. The execution according to Table 1 is cyclic and can be represented with the series of steps as depicted in Fig. 6. While starting at Step 1 initially, the series starts upon pressing the button for pedestrian crossing, or after 3 min after the last cycle. The following demands and restrictions need to be observed: Step 1 is delayed 180 sec (unless the pedestrian relay switch is pressed beforehand), Step 2 is delayed 10 sec, Step 3 is delayed 30 sec, Step 4 is delayed 20 sec, and the execution continues at Step 1. The initial conditions are: red light is turned on for pedestrians, green light is turned on for cars (Step 1), and the relay switch is reset.
The TSTD textual representation shown in Fig. 6 consists of fragments of ini-tialisation code for each of the TSTD states. A "Pre-condition" represents the trigger condition for its state. As mentioned previously, there are four types of pre-conditions, which can be used here. The maxT and minT parameters have the purpose to deter-mine the time frame for a state's execution. The "Action" and "OnTimeout" parts are represented by program statements, PEARL system calls and comments, which are delimited by the "END;" keyword.
Springer
188 Real-Time Syst (2007) 35:181-208
MODULE module_name; SYSTEM;
! interrupts, signals and system variables definitions PROBLEM;
task_name : PROCEDURE (state_id REF INT); DCL timeout BIT;
/* initialisation of all global structures timeout:='0'B1; ! timeout indicator
WHILE '1'B1 REPEAT CASE state_id
ALT (0) ! START state:
IF timeout EQ '1'B1 THEN
/* perform OnTimeout=action(s); state_id:=0; timeout:='0'B1; NEXT state_id;
ELSE
/* RESUME task after fulfillment of the
timeout:='1'B1; DELAY maxT;
/* perform the appropriate start states /* check if any of the next working / super / end states' /* if they are fulfilled, set timeout to false and
NEXT state_id; FIN;
ALT (1) ! for a WORKING state: IF timeout EQ '1'B1 THEN
/* perform OnTimeout=action(s); state_id:=0; timeout:='0'B1; NEXT state_id;
ELSE
DELAY minT; timeout:='1'B1; DELAY maxT;
/* perform Action=statements; /* check if any of the next working / super / end states' /* if they are fulfilled, set timeout to false and
NEXT state_id; FIN;
ALT (2) ! for a SUPER state: IF timeout EQ '1'B1 THEN
/* perform OnTimeout=action(s); state_id:=0; timeout:='0'B1; NEXT state_id;
ELSE
/* set the state_id variable to the start state of
NEXT state_id; FIN;
ALT (3) ! for a SUPER state (as addition) - "return to" state:
/* set the state_id variable to the next state /* for a SUPER state (the sub-diagram states numbered
NEXT state_id; ALT (n) ! END state: DELAY minT;
/* perform Action=statements;
state_id:=0;
/* reset task state (state_id = super_state + 1)
NEXT state_id;
timeout:='0'B1; ! reset timeout indicator
FIN; END;
END;
MODEND;
#include "module_name.h"
/* interrupts, signals and system variables definitions */
void task_name(int &state_id;) { bool timeout;
*/
timeout=false; /* timeout indicator */ while (1) {
switch (state_id) {
case 0: { /* START state: */ if (timeout) {
*/
state_id=0; timeout=false; Next(state_id);} else {
trigger conditions; */ timeout=true; Delay(maxT);
Action=statements; */ pre-conditions are fulfilled; */
set the state_id variable accordingly; */ Next(state_id);
} }
case 1: { /* for a WORKING state: */ if (timeout) {
*/
state_id=0; timeout=false; Next(state_id);} else {
Delay(minT); timeout=true; Delay(maxT);
*/
pre-conditions are fulfilled; */
set the state_id variable accordingly; */ Next(state_id);
} }
case 2: { /* for a SUPER state: */ if (timeout) {
*/
state_id=0; timeout=false; Next(state_id);} else {
the super state's sub-diagram; */ Next(state_id);
} }
case 3: { /* for a SUPER state (as addition) - "return to" state: */
*/ consecutively) */
Next(state_id); }
case n: { /* END state: */ Delay(minT);
*/
state_id=0;
in case of a return from a sub-diagram */ Next(state_id);
timeout=false; /* reset timeout indicator */ }
}
}
}
* DELAY and NEXT are there for simulator control. DELAY represents a "busy wait'" while NEXT instructs the simulator to dispatch ("preemption point").
Fig. 5 Representations of a TSTD in PEARL and annotated C
While the graphical TSTD representation is mainly meant to be used in CASE design tools, the textual representation is meant for storage and automatic translation to a program (source code) prototype (cp. Fig. 5).
For easier interpretation/compilation of program tasks in/to the simulation/target platform environments, in the current implementation of the Specification PEARL co-design environment (Gumzej, 2004). the annotated C programming language is used. The algorithmic form of task prototypes remained the same, merely the commands,
Springer
Real-Time Syst (2007) 35:181-208 189
Table 1 Logical execution table for traffic light control
Traffic light
pedestrians Traffic light cars
Step Red Green Red Yellow Green
1 1 0 0 0 1
2 1 0 0 1 0
3 0 1 1 0 0
4 1 0 1 1 0
representing system calls, were replaced by appropriate calls to the CM/RTOS of the Specification PEARL environment.
2.3 Development environment, configuration manager and operating system
Most co-design methodologies do not consider the target operating systems. Those which do, and produce executable code, use off-the-shelf operating systems, in which case the tools are strictly bound to the target environments, from which they also inherit their limitations in expressing the real-time properties of applications.
From this point of view, it appeared appropriate to use as orientation a real-time operating system with a rich set of system calls supporting real-time operation such as the PEARL RTOS (http://www.irt.uni-hannover.de/rtos/rtosfble.html) in order to support programmers and designers in expressing real-time behaviour of applica-tions. Since our RTOS (cp. Gumzej, 1999) is not off-the-shelf, but rather a part of the designed system model, its source code can be compiled for any hardware platform.
The S-PEARL development environment, which encompasses modeling and co-simulation tools, runs under Microsoft Windows 2000 and XP (cp. Gumzej, 2004). It enables cross-development for the defined hardware architectures through cross-compilation of its target platform models.
The Configuration Manager (CM) represents the hardware abstraction layer which is, as configured by a hardware architecture model, mainly used to define the structure, timing properties and interfaces of each STATION. The considered RTOS, being an op-tional part of the CM, supports the tasking model and system calls of the programming language PEARL as well as the deadline-driven scheduling strategy (later enhance-ments for other strategies are foreseen). Its resources are pre-determined (e.g., number of tasks, synchronisers, signals, events, or queued events) by setting the parameters of a KERNEL STATION.
2.3.1 Configuration manager's functionality
The execution at each processing node (station) starts with initiating the Configuration Manager (CM) object. Initially, it loads the collections of task objects, and activates the initial collection by triggering the latter's initialisation-task objects. In stations without a real-time operating system, the main task of the collection is started and delegated control to by the CM, whereas otherwise the CM acts as a front-end to
Springer
190 Real-Time Syst (2007) 35:181-208
S
S2
S3
S3.S
S3.Step2
S3.Step3
S3.Step4
S3.E
[State types]
START=0
TRANSIENT=1
SUPER=2 [State types]
END=3
START=0
[States] TRANSIENT=1
SUPER=2
S=START
END=3
S1=WORK
S2=WORK [States]
S3=SUPER
S3.S=START
E=END
S3.Step2=WORK
[S] S3.Step3=WORK
S3.Step4=WORK
Precondition=
S3.E=END
minT=0
maxT=0 [S3.S]
Next=S1; S2;
Precondition=
Action= ! Step1 lights setting
minT=0
END;
maxT=0
[S1] Next= S3.Step2;
OnTimeout= END;
Precondition=tm(180 SEC)
Action=DISABLE button;
minT=0
END;
maxT=0
Next=S3; [S3.Step2]
OnTimeout=END;
Precondition=
Action= END;
minT=10 SEC
[S2] maxT=
Next= S2.Step3;
Precondition=ev(button : INT)
OnTimeout= END;
minT=0
Action= ! Step 2 lights setting
maxT=0
END;
Next=S3;
OnTimeout= END; [S3.Step3]
Action= ! reset button
Precondition=
END;
minT=30 SEC
[S3] maxT=
Next= S2.Step4;
Precondition=
OnTimeout= END;
minT=0
Action= ! Step3 lights setting
maxT=0
END;
Next=S;
OnTimeout= END; [S3.Step4]
Action=S3;
Precondition=
END;
minT=20 SEC
maxT=
Next= S3.E;
OnTimeout=END;
Action= ! Step4 lights setting
END;
[S3.E]
Precondition=
minT=
maxT=
Next=
OnTimeout= END;
Action=ENABLE button;
END;
Fig. 6 Example graphical and textual TSTD representations
the operating system functions, and uses appropriate system calls and system ports to transfer system requests to/from RTOS-enabled nodes to schedule the collection's tasks.
Besides local execution, the CM is also responsible for communication with other stations, and for co-operation among the tasks of the same collection. Hence, it must establish port-to-port connections through the interfaces of the station. Synchronisa-tion and system service requests are serviced on the same station, in case the station is configured to run a real-time operating system. Otherwise, these requests are for-warded to the appropriate station through a proprietary port.
The application programming interface of the CM has the following functions:
(Re-) Configuration:
Cm Init(S) - to initialise the station S and load the initial software configuration, and
Springer
Real-Time Syst (2007) 35:181-208 191
Cm Reset(S) - to restart the station with the initial software/hardware configuration.
Station state monitoring:
Cm Getstate(S) - to retrieve the current state of station S, and
Cm Setstate(S, state) - to change the current state of station S to "state".
Inter-station communication:
Cm Transmit(T C Bi, portID, msg buff []) - message transmission through a connec-tion,
Cm Reply(T C Bi, portID, msg buff []) - response message transmission through a connection, and
Cm Receive(T C Bi, portID, msg buff []) - message receipt through a connection, where TCBi denotes the index of the task's control block (TCB), portID the name of the port, and msg buff[] the buffer for the message.
The connections are established through ports of the software architecture and associated devices of the hardware architecture. The attributes of ports represent the communication parameters (smallest package, protocol, etc.) and routing parameters (VIA/PREFER). Routing affects the way the hardware communication devices are used. The attribute VIA determines the exact line to be used, while PREFER is usually assigned to the most trusted line in a list. Lines represent connections between hardware architecture devices (e.g., interfaces).
In asymmetrical architectures, direct calls to real-time operating system functions are not always possible. Hence, substitute RTOS API functions are called, to generate appropriate system request messages to the CM of the RTOS's processing (supervisor) node. The parameters of such system requests are extracted from the transferred mes-sages in concordance with a pre-defined coding scheme also used in the construction of the parameter set.
To enable uniform handling of system requests, the RTOS API has been designed in a way enabling the transformation of system calls to parameter strings, which can be routed to the RTOS interface procedure directly, or sent to the KERNEL station for handling. Two additional internal functions have been introduced in the CM interface for this reason:
Cm SysRequest(S, sys par []) - send system call parameters for processing to the RTOS, and
Cm SysResult(S) - store result from the RTOS (result of the system call and possible context switch request for the local dispatcher routine of the CM (C M System(S)).
3 Verification of specification PEARL system models
Verification of temporal feasibility of S-PEARL models is based on co-simulation with earliest deadline first (EDF) scheduling and time boundaries. It is primarily meant to check the timing properties of models designed for feasibility. A design is transformed into an internal representation for simulation, whose primary result is a successful execution or failure, whereas the secondary result is an execution trace, from which additional information can be extracted. This information is then used to discover bottlenecks and unreachable states, and to fine-tune the timing parameters of model and specifications. For a successful verification, after having carried out intermediate
Springer
192 Real-Time Syst (2007) 35:181-208
checks of the system architecture, the model is subjected to the following coherency checks:
completeness check: all components are present and fully described,
range and compatibility check: parameter compatibility among components, and software to hardware mapping check: complete coverage and consideration of resource
limits.
These checks are in preparation to verify temporal feasibility, which is described in the forthcoming sections.
3.1 System model
The system model used is an internal representation of the system designed in form of "architecture data" and simulation nodes referring to parts of these "data". The hardware model consists of STATION nodes being the top-level simulation nodes with resources having specified properties. The software model consists of COLLECTION nodes, which are mapped to the STATION nodes based on their (initial) state. They are composed of TASK nodes, having the semantics of TSTD program representations. Co-simulation is based on the following presumptions.
There is only one global simulation clock in the system, and all STATION real-time clocks (timers) relate to it (by perfect synchronisation).
The time events relate to the corresponding station's real-time clock.
Tasks are assigned deadlines for their execution (the only exception are short ini-tialisation tasks).
Task states (TSTD) are assigned time frames (minimum and maximum time) for the activities being performed within the states (in real-time clock time units).
All simulation nodes are derived from a common simulation unit type.
3.1.1 Hardware model
There are three possible basic types of STATION simulation nodes: BASIC (general purpose - program and RTOS), TASK (program), and KERNEL (RTOS). They may have one or more communication lines attached to them for information exchange with other STATION nodes. The attributes of the stations' internal devices provide the parameters for the parameterisation of the stations' configuration manager (CM) and RTOS. A COMPOSITE STATION would merely represent a supersimulation node, composed of two or more STATION simulation nodes, hence only their constituent nodes take part in the co-simulation.
3.1.2 Software model
COLLECTION simulation nodes are linked as subnodes to associated STATIONs, whereas TASK simulation nodes are linked to their COLLECTIONs. For communi-
Springer
Real-Time Syst (2007) 35:181-208 193
Simulation units
HW architecture model
parameters
t
Simulator
Program statements, PEARL system calls, natural language comments
Fig. 7 The course of simulation
CM/
RTOS
cation between tasks at different STATIONs the appropriate COLLECTION's PORTS are used. A STATION's CM determines when a certain COLLECTION is active and dispatches its messages accordingly.
3.1.3 Task (TSTD) model
TASKs are represented by Timed State Transition Diagrams (TSTD) (Gumzej, 1999, 2001), whose program representations are used to "drive" TASK simulation nodes. During simulation their execution is responsible for advances in time and state spaces.
3.1.4 Configuration manager and operating system model
The CM represents an inter-station/collection co-operation agent. It has information on the system software and hardware architectures, which originate from the S-PEARL system architecture specification.
Functionally, the CM/RTOS has the same rˆole in co-simulation (Fig. 7) asin exe-cution on the target platform. The main differences lie in the global real-time clock, which is maintained by the simulation environment, and the context switches, which are performed on the higher level only in the case of simulation (the context refers to task states - not processor registers).
Each RTOS processing node maintains a real-time clock. In a simulation envi-ronment, all these clocks are perfectly synchronised with the global simulation time, which in an execution environment should be implemented by an independent global time source and predictable time dissemination.
Pre-emption points in the simulation and in the target platform implementation are task state transfers. The resource access functions and interface device drivers of a STATION perform virtual functions in case of simulation, and concrete functions in case of target platform implementation.
The time required to execute the operating system itself (schedule and dispatch cycle) is assumed to be constant. The time needed to service the system calls is considered as being included in the time frame of the calling TASK's state. Their sole function is to change the state of internal data structures of the (operating) system and to trigger tasks and states, whose trigger conditions relate to them.
Springer
194 Real-Time Syst (2007) 35:181-208
3.2 Verification of temporal feasibility
3.2.1 Criteria function
Any verification method requires the definition of a criteria function expressing when a system fails, i.e., what the limits of the "normal" execution of a system being checked are. The concept of correctness for the verification method, described here, is defined as follows: "A system fails if during co-simulation it reaches an undefined state, or if its pre-defined time frame is violated and no timeout-action is defined."
By trying the shortest and taking the longest transition times through the TSTD states, it is assumed that the time domain can be covered sufficiently to be able to generalise the results to an arbitrary transition instant within the (minT, maxT) interval for each state and, herewith, also the TASK as a whole.
3.2.2 Co-simulation with EDF scheduling
In simulation, the station clock rate is translated into the relative speed of the station, and may be used when the next event time is calculated (e.g., rsi = max{si }/si and tn = ti · rsi ).
For verification, next critical event simulation and Earliest-deadline-first (EDF) scheduling are used. The next critical instant is always determined by the simulation unit whose activation time is the closest. This time is forwarded to all its parent units and, finally, becomes the next global critical instant. For each step it is checked, whether timing errors occurred. A "timeout" represents a controlled program fault, which is handled by the "timeout action", and by transition into the initial state. If this action is not defined for the current state, the system fails. Co-simulation EDF next-event scheduling is based on the following timing information (see Fig. 8):
A: task activation time,
R: accumulated task run time (updated with the next critical event),
E: task end time (the time when the normal task end is expected based on its maximum run time; upon a context switch the current time t1 needs to be remembered, because to re-run the task this parameter needs to be reset based on the current time t2 and
the formula E? = E + (t2 ? t1)),
D: task deadline (set, when A is known).
A task is re-scheduled when it is activated due to a scheduled event or on request. The task with the earliest deadline is chosen for execution, and its current state determines the next critical moment based on the current time t. The states of the tasks are executed atomically-a context switch is not performed before the task state is worked out. The
A R CS CS' E E' D
t
t2 - t1
t1
t2
Fig. 8 Task run with a single context switch (see text for abbreviations)
Springer
Real-Time Syst (2007) 35:181-208 195
RTOS scheduler is responsible for task scheduling (determining the most urgent task), while the simulator is responsible for determining the next critical moment for the current operation (task state or external event).
While re-scheduling, the following criteria (failure conditions) need to be checked for all active tasks:
t < Z = D ? (E ? ( A + R)), where Z represents the latest time when the task needs to start/continue in order to meet its deadline;
t < E ? D must be true for all active tasks, since otherwise they have missed their deadlines.
Tasks can be scheduled to be executed on external events. For simulation purposes, they are assigned occurrence times. They are represented as native station unit events, whose next critical time instants are taken from an occurrence table, which lists inter-rupt numbers with their corresponding occurrence times. When they occur, they are handled by the station's RTOS (being a part of the CM), waking up appropriate tasks.
During co-simulation, the time of progression to the next state is calculated in two variants for each state:
1. RTC + minT to check the pre-conditions, and
2. RTC + maxT for transition to a new state.
If in critical instant (2) the pre-condition for the transition to any further state is not fulfilled, the system fails and the on-timeout action is executed. If it is not defined, the system fails. During simulation, the parameters E and D are set for each task when it is activated (the parameter A is set). When a critical instant is reached, it is checked if herewith the time frame, given for the task, has been violated, which results in the following consequences: (1) subtraction of the overhead from the task's slack time, or
(2) the system fails as the task deadline is being missed.
The simulation results are logged during the execution of each simulation unit, and every step is accounted for within all parent simulation units, too. This means that every task state logs its action into the TASK log, whereas a task logs its state changes into the COLLECTION log. A collection logs the time when it was first allocated to a station, possible subsequent re-loads, and the changes of states which triggered them into the STATION log. The stations and collections also log the times when they were communicating among each other. All exceptions are logged, where they are discovered.
The temporal feasibility, determined by co-simulation, retains its validity if the execution times foreseen do not change when the software model is extended to fully functional programs.
4 UML profile for specification PEARL
The Unified Modeling Language (UML) provides constructs to deal with varying levels of modeling abstraction to visualise and specify both the static and dynamic aspects of systems (OMG, 2004). Its notation defines the semantics of an object meta-model to capture and communicate object structure and behaviour. In its metamodel
Springer
196 Real-Time Syst (2007) 35:181-208
architecture, UML supports the following extension mechanisms: stereotypes, tagged values and constraints, which allow to tailor it to fit the needs of specific domains.
A UML profile is a pre-defined set of extension mechanisms for a particular domain, technology, or methodology, which provides a connection of how to apply and spe-cialise UML to this domain. A stereotype provides a way to define virtual subclasses of UML metaclasses with additional semantics. It can set additional constraints over its base metamodel class as well as tags to define additional properties. A constraint is a semantic restriction represented as a text expression, which is usually formulated in the Object Constraint Language (OCL). Constraints are attached to one or more model elements. Tag definitions specify new kinds of properties as part of a stereo-type definition. The actual properties of individual model elements are specified using tagged values.
The process of defining a general UML profile for a given platform or application domain can be summarised as follows:
First, we need to define a set of elements that will comprise the platform or system, and the relationships between them, which can be expressed in terms of a metamodel, i.e., the metamodel includes the definition of the domain entities, the relationships between them, and the constraints that govern both structure and behaviour of these entities.
Once the domain metamodel is built, we are ready to define the UML profile, in which a set of stereotypes are defined for each relevant element of the metamodel. Tagged values should be defined as attributes that appear in the metamodel. They include the corresponding types and initial values. The domain restrictions are ex-pressed with constraints.
Here, we build a UML profile to describe the constructs and capture the essential semantic concepts of S-PEARL. In S-PEARL, STATION and COLLECTION are defined as basic entities in terms of the corresponding UML stereotypes, as shown in Fig. 9. The entities (stereotypes) will be used to define the class diagrams that specify the compositional model of S-PEARL, i.e., the structure and relationships between the model entities. The compositional model can be used for application frameworks built with S-PEARL elements.
4.1 Mapping S-PEARL architecture constructs to UML
As described earlier, S-PEARL includes elements to describe hardware and software configurations of distributed systems. To map the S-PEARL constructs onto UML elements, it is indispensable to compare UML and S-PEARL constructs, to be able to choose appropriate base elements and define UML stereotypes for S-PEARL elements. The essential point of this mapping is the S-PEARL architecture, its real-time features, and its runtime constraints. Figure 10 showsthe main defined stereotypes for S-PEARL.
4.1.1 Station
In S-PEARL, hardware and its deployment is introduced on the station layer. The processing nodes (stations) of a system are treated as black boxes with connections for information exchange. On their subordinate layers, stations are described by the
Springer
Real-Time Syst (2007) 35:181-208 197
Profile
baseClass: Node baseClass: Class
<