A Practical Approach
to Mode Change in Real-Time Systems
Authors: Hans Søndergaard
Anders P. Ravn
Bent Thomsen
Martin Schoeberl
Technical Report 08-001
Department of Computer Science
AalborgUniversity
Created April28th, 2008
A Practical Approach to Mode Change in Real-Time Systems
Hans Søndergaard
UniversityCollege
Vitus Bering Denmark
Denmark
Anders P. Ravn, Bent Thomsen
Department of Computer Science
AalborgUniversity
Denmark
{apr, bt}@cs.aau.dk
Martin Schoeberl
Institute of Computer Engineering
ViennaUniversity of Technology
Austria
Abstract
We present a contract for consistent mode change in a real-time system for control applications. The contract between the control engineer and the software developer guarantees that when a mode change is signalled, it will occur at a specific instant thereafter, and that the task sets for the modes are never mixed. The concept is illustrated by small examples, and efficient implementations in Safety Critical Java on two platformsare demonstrated.
1. Introduction
Many hard real-time systems control physical systems and are therefore often safety critical. This has motivated development of scheduling theory as a discipline with close links to control engineering. However, both control theory and scheduling theory have traditionally considered systems in a steady state, where a fixed control law is implemented by a set of periodic and sporadic tasks. In practice, the physical system does change between modes, e.g. a vehicle may be stopping, starting or changing direction, or an instrument may be idle or active. Yet, these changes are assumed to occur infrequently, and the transients are handled in ad-hoc ways. For many systems, this is not a valid assumption, because in order to have efficient, fault-tolerant and self-configurable controllers, the control laws must change more often and thus mode changes have to be considered when analyzing the total system for stability, optimality etc. A concrete example is a four wheel drive, four wheel steer vehicle for rugged terrain [2]. In order to have a no-slip, no-skid operation with arbitrary trajectories (Figure 1), e.g. where the vehicle is rotating around its axis, it has to change between control modes, as shown in Figure 2.
Figure 1. Trajectory for a vehicle. A complex vehicle trajectory (from [2]) that forces the vehicle to rotate (Stateflow simulation).
Such dynamic systems with a non-trivial interaction between discrete transitions (mode changes) and continuous evolutions are the topic of Hybrid System Theory, a discipline which is the theme of special sessions on most control conferences, and which has fostered interdisciplinary work between control theory and computer science.
From the last-mentioned point of view, the challenge is to find clean ways of modelling solutions to the mode changes so that the developers of real-time systems easily are able to implementsuch solutions.
There is extensive literature on mode change protocols (see section 5). However, most previous studies assume mode change to be implemented by an operating system.
Figure 2. Control modes for the vehicle. The vehicle has two start/stop modes (to the left) and three operating modes (forward/backward, rotating, cross drive) – figure adapted from [2].
The target for our work is smaller embedded hard real-time systems with periodic and sporadic tasks where the controller typically has no operating system.
The contributions of this paper are thus
- an event-triggeredsynchronous mode change contract between the control engineers and the software developers
- a model of a software solution targeted at smaller embedded hard real-time systems with periodic and sporadic tasks only
- implementation of the mode change solution in Safety Critical Java on two different processors.
The remainder of this paper is structured as follows: In Section 2 the mode change contract is defined. In Section 3 we model our solution. Section 4 describes our implementations in Safety Critical Java. In Section 5 our solution is compared to related work. Section 6 completes the paper with a conclusion and future work.
2. The Synchronous Mode Change Contract
A mode defines the system under certain working conditions, and is represented by a collection of periodic and sporadic tasks with information about scheduling parameters and logic to execute.
Different modes means different working conditions of the system and can be represented by a state machine where a node represents a mode (a state) and an edge represents a mode change (a transition) from one mode to another mode. Figure 3 shows the genericstate diagram(Figure 2 showsa specific example).
modei {m1, m2,.., mn}
Figure 3. A generic state diagram for mode change.
Mode change requirements.A transition from mode mi to the next mode mjmust satisfy:
R1.When a Mode Change Request (MCR) hasoccurred, a transition from mode mi to mode mj must take place.
R2.Continuing tasks belonging to both mode mi and mode mj are permitted.
R3.A mix of old tasksfrom mode mi and new tasks from mode mj must not be concurrently active, cf. Figure 4.
R4.All real-time requirements of the system must be met (deadlines, periods, etc.).
R5.The mode changes of the system must happen within a bounded timet.
Figure4. Inconsistent mode change with a mix of activities during the transition within the bounded time interval t(mi).
Mode change contract.These requirements are met by the following contract (also see Figure 5):
C1.Each mode m in {m1,..,mn} has a fixed set of periodic or sporadic tasks (m)which are individually schedulable under a given scheduling discipline.
C2.A specific event,MCR, is designated as request to change from a current mode mito a new mode mj.
C3.When aMCR occurs, the task set (mi) of the current mode mi remains active ina time-interval, tidle, with a maximal durationt(mi), after which the task set (mj)of mode mjis active.
C4.Periodic and sporadic tasks that occur in both mi and mjremain active over the mode change.
We will call this contract the event-triggered synchronous mode change contract.
Figure 5. Consistent mode change when CPU is idle.
The mode change contract meets the requirements.It is obvious that the contract satisfies the requirements:
Contract point C3 ensures that R1 is satisfied. C4 ensures that R2 is met. C3 implies that R3 is satisfied, because the tidleinstant divides the active tasks in mode mi from the active tasks in mode mj. C1 and C4 ensure R4. Finally, R5 is met by C3.
Mode change contract during development.It is the obligation of
- the developer of the control laws
- to define the modes and the task sets
- for each mode change to check that the mode change delays, t, are admissible for the control laws.
- the software developer to provide
- a correct implementation of the mode change
- an algorithm for computing t for each mode.
3. Modelling a Software Solution
With the mode change contract in place, let us
consider correct implementations and algorithms
computingt for each mode.
3.1. Mode change
The target for our mode change contract is hard real-time systems with periodic and sporadic tasks only, where all the tasks have deadlines, - besides periods/minimuminter-arrival times, and priorities.
This means that the scheduling algorithm must ensure that all the deadlines are met during the transition from mode mi to mode mj.
Therefore, we will use the most widely used scheduling algorithm for real-time systems: Fixed-Priority Scheduling (FPS) with preemptive task switch to higher-priority tasks.
Apriority inversion control mechanism is also feasible, e.g. the priority ceiling protocol.
Here, mode change managementcan easily be done by a sporadic task with a priority less than all the other tasks in the system.
This sporadic mode change task we call mc.The parameters of mc have to be determined, i.e. priority Pmc, minimum inter-arrival time Tmc, and deadline Dmc:
- Pmc= min(P)-1, for all tasks in thecurrent mode
- Tmc = Rmc
- Dmc= Tmc
where Rmcis the worst-case response time of task mc.
This worst-case response time isdeterminedin the following section3.2.
A different approach is to support the mode change by the runtime system itself, as it is proposed for JOP. In that case the scheduler itself is responsible for performing the mode change and there is no need for a mode change task.
3.2. Time analysis
When a Mode Change Request (MCR) occurs, see Figure 6, the transition to the next mode can take place the first timeafter MCR when the system has some CPU-idle time,tidle, with
tR – tStidle (1)
where ts and tR are the Start time and Response time of the mode change respectively, cf. Table 1.
By this, the mode change, executed by mc, does not interfere with the other tasks because mc has the lowest priority.
Figure 6. Time line for mode change.
Notation / DescriptiontMCR / Time of MCR
tS / Start time of mode change
tR / Response time of mode change
Smc / Worst-case start time (relative to tMCR) of the mode changing taskmc
Rmc / Worst-case response time (relative to tMCR) of the mode changing taskmc
Tj / Period of task j (or minimum inter-arrival time, if a sporadic task)
Cj / Worst-case execution time (WCET) of
task j
Table 1. The applied notation.
The worst-case delay, from a MCR to the mode change is completed, is determined by (2). If the mode change algorithm takes less than one time unit, this completes the analysis. This will often be the case in practice. However, if there is a fine-grained clock, the algorithm may take more than one time unit, and we should compute its response time using (3).
Smc = Cj (2)
Rmc = Cmc+Cj (3)
where= number of releases of task j within the time interval [tMCR,Smc), and (m)is the set of tasks for mode m.
If the calculations of Smc and Rmc show that
Rmc = Smc + Cmc (4)
then the mode change can take place consistently using a low priority task. And Rmcis exactly our desiredt. Please observe that it depends on the active task set.
3.3. Instrument example
The FOSS WineScan™ Systemis an example of an industrial instrument which works in different modes during the analysis of wine. The system uses Fourier Transform Infrared Spectropy for the analysis, where up to 20 main quality parameters are determined in each grape sample [5].Figure 7 shows the modes of the WineScan system.
Start Stop
Figure 7. Typical modes of the WineScan™ System
The Initialized mode includes warming up the instrument to a specific temperature; in the WaitForSample mode, the system is waiting for a wine grape sample; the Measure mode is the most time critical with up to 105 detector readings in 30 secs. When it is finished analysing the samples, the system can change to Terminate mode (cooling down the instrument, etc.), before the instrument is stopped.
The system has different periodic and sporadic tasks, of which the most important are shown in Table 2.
# Tasks / Type / T(ms) / D (ms) / C
(ms)
1 Detector reading / sporadic / 0.33 / 0.2 / 0.04
4 Temperature reading / periodic / 200 / 10 / 1
4 Temperature regulation / periodic / 1000 / 100 / 2.5
1 Monitoring / periodic / 333 / 30
1 Watchdog / periodic / 8000 / 80
1 External comm, output / periodic / 333 / 15
1 External comm, input / sporadic / 500 / 25
Table 2. WineScan tasks with time requirements.
T is the period or minimum inter-arrival time, D is deadline, C is worst-case execution time. If no deadline, D = T is assumed.
The periods and deadlines have been defined by the company based on earlier generations of the instrument, while the worst case execution times have been measured in a prototype implementation [3]. In the prototype implementation, all the tasks are active, and mode change is part of the application code, because the Ravenscar-Java Profile [18] does not support mode changes.
Deadline monotonic priority assignment is used, and response time analysis shows that the system is schedulable. However, a few changes to the set up will make concurrent detector reading and output communi- cation infeasible.
Thus a more robust implementation would have thedetector reading task only active in the Measure mode, where the output communication task would be excluded. It would be confined to the WaitForSample mode. However, the four temperature reading tasks and the four temperature regulation tasks have to be active in all but the stop mode, and they should not be reset during mode changes.
4. Implementation ofthe Mode Change
In this section we will show how to implement our mode change contract in Java.
Software profile.The implementation is carried out in Safety Critical Java (SC-Java) [8] using the proposal of [16].
The specification of SC-Java started July 2006 as a Java Specification Request, JSR 302, under the Java Community Processat Sun.
It builds on the Real-Time Specification for Java (RTSJ) [4] which is a general framework for solving a wide variety of real-time programming problems.
However, because RTSJ is a general real-time framework, it is very complex. To overcome this complexity problem, the SC-Java specification creates a J2ME capability, based on RTSJ, containing minimal features necessary for safety critical systems capable of certification, e.g. DO-178B [9].
SC-Java inherits the scheduling algorithm from RTSJ which has the fixed-priority preemptive scheduling algorithm (FPS) as default. Furthermore, a priority inversion control mechanism is included. In SC-Javapriority ceiling emulation is the only available protocol.
By this the scheduling approach in Section 3.1 is met.
Hardware profile.Two different processors are used: aJ-100, a commercial Java processor from aJile Systems [6], and JOP, a research FPGA implemented Java processor created by Martin Schoeberl [15].
Mode change modelling. Modelling the modes can be done in at least two ways [11]:
- All the modes have the same set of tasks, (5a)
but with different logics attached to a task depending of the mode.
- Each mode has its own set of tasks (5b)
See Figure 8 with sequence diagrams modelling the two ways of mode change.
Figure8. Sequence diagrams modelling mode changes.
In the first case, a task executes a doNothing-logic when it is "not-active" in a specific mode. This way to implement the modes is described in [17] and can easily be implemented at the application level.
On aJ-100, the periodic threads for all the modes must be defined and started at the beginning, because a cyclic scheduling table known as the “piano roll” must be initialized with priority bit masks for allthe periodic threads before start. Therefore an implementation of the above mentioned type (5a) is applied.
On JOP it is possible to activate and deactivate the tasks, so that an implementation of type (5b) can be used.
In both cases all the tasks are created when the system is started.
A Mode class is defined in connection with the classes from SC-Java [16], see Figure9.
Figure 9.Class diagram of SC-Java with Mode class
The other classes of the diagram are part of SC-Java. The RealtimeSystem class is a singleton class, representing the runtime system. The system is started by calling the start(Mode startMode) method, wherestartMode defines in which mode to start. The changeModemethodchanges the mode: it is to be used by the MCR of Section 2.
The RealtimeThreadclass has thetwo subclasses PeriodicThread and SporadicThread. All three classes are abstract. The abstractrun method specifies the periodic or sporadic behavior of the threads and is implemented in the concrete application-dependent subclasses ofPeriodicThread and SporadicThread.
The modes can be represented in different ways, depending of the way we choose to implement the modelling described in (5a) and (5b).
4.1. aJ-100 implementation using (5a)
In this implementation,the Mode class is a typesafe enum pattern [10] as shown in Figure 10.
public class Mode
{
private static int numberOfModes = 0;
private static Vector modes =
new Vector();
private int ordinal; //ordinal and
private String name; //name of the mode
private static Mode currentMode = null;
private static int currentModeIdx = -1;
public Mode (String name){
this.name = name;
ordinal = numberOfModes++;
modes.addElement(this);
}
private static Object mutex =
new Object();
public static void changeMode(
Mode newMode)
{
synchronized (mutex) {
currentMode = newMode;
currentModeIdx =
newMode.getModeIdx();
}
}
public static int size() {..}
public static Mode getMode() {..}
public static int getModeIdx() {..}
}
Figure 10. classMode on aJ-100.
The mode change can be done by a sporadic thread (mcThread), having a priority less than all the other threads in the current mode, cf. Section 3.1.
When it receives an event (a MCR), it is readied; but because it has the lowest priority, it is delayed until all the periodic and sporadic threads with higher priorities are in their wait state (waiting for next period or for next event).
Now, when the CPU is idle, mcThread can run and must change the mode in an atomic operation. This is ensured by the priority inversion control mechanism; and the above mentioned analysis, Section 3.2, ensures that it can be done consistently.
The minimum inter-arrival time Tmcof mcThread is set to:
Tmc = Rmc
Dmc = Tmc, - deadline equal T.
The sporadic thread, mcThread, which carries out the mode change has the run logic of Figure 11.
run()
{
Mode.changeMode(newMode);
}
Figure 11. run method of the sporadic mcThread.
This sporadic thread is created and initialized by the system during initialization, including determination of its priority and minimum inter-arrival time.