-We propose a compositional framework for analyzing the schedulability of hierarchical scheduling systems. The framework is realized using Parameterized Stopwatch Automata to describe tasks, whereas the schedulability analysis is performed using UPPAAL. The concrete behavior of each periodic preemptive task is given as a list of timed actions to which resources are assigned by SIRAP protocol. Our framework is reconfigurable in which the hierarchical structure, the scheduling policies, the concrete task behavior and the shared resources can all be reconfigured. Finally, we use our framework to analyze the schedulability of a real-time avionics system.
I. INTRODUCTION
In the area of real-time embedded systems, like avionics and automotive, it is primordial to ensure the continually correct behavior of such systems. Avionics and automotive systems consist of both safety-critical and non safety-critical features, which are implemented in components that might share resources (e.g. processors). Resource utilization represents a common challenge for both academics and practitioners, and thus it is important to have an efficient and reliable scheduling policy for the individual parts of the system. Scheduling is a widely used mechanism for guaranteeing that the different components of a system will be provided with the correct amounts of resources.
A scheduling system consists of a set of concurrent tasks (processes) competing resources according to a scheduling policy. Each task has a set of timing requirements to fulfill. A hierarchical scheduling system consists of multiple scheduling systems in a hierarchical structure. A scheduling system is said to be schedulable if all its tasks achieve their jobs without missing any deadline.
Compositional analysis has been introduced [
TimingN onCrcetteNskaNbeha RrceteNtskabeNvhairoesoNuprrcoetoNCcSo1hlsarinSg n o C
HierarchicalN architecture
C2 T1 T2 T3 T4
UPPAALN NetworkNofNHybrid TimedNAutomata SchedulabilityN
analysis )modelNchecking: Fig. 1. Overview of the analysis framework
Our framework is implemented using parameterized
stopwatch automata models. To enable and manage resource
sharing between tasks, we use the SIRAP (Subsystem Integration
and Resource Allocation Policy) protocol [
Thanks to the parameterization, the framework can easily be instantiated for a specific hierarchical scheduling application. Similarly, each scheduling policy (e.g. EDF: Earliest Deadline First, FPS: Fixed Priority Scheduling, RM: Rate Monotonic) is separately modeled and can be instantiated for any component.
We analyze the model in a compositional manner, so that the schedulability of each component is analyzed together with the interface specifications of the level directly below it. In this analysis, we non-deterministically supply the required resources of each component, i.e. each component is guaranteed to be provided its required resources for each period. This fact is viewed by the component entities as a contract by which the component has to supply the required resources, provided by the component parent level, to its sub entities. The main contribution of this paper combines: a compositional analysis approach where the schedulability of a system relies on the recursive schedulability analysis of its individual subsystems. System
EDF
EDF Component1 (100,37)
RM Component2
(70,25)
a reconfigurable schedulability framework where a system structure can be instantiated in different configurations to fit different applications. modeling of concrete task behavior as a sequence of timed actions requiring CPU and resources.
UPPAAL implementation of SIRAP protocol.
informal description of our compositional analysis technique using a running example. Section III includes both the background and the modeling theory of hierarchical scheduling systems. In section IV, we give the UPPAAL models of our framework where we consider concrete behavior of tasks.
Moreover, we show how the compositional analysis can be applied on the models using the UPPAAL verification engine.
Section V shows the applicability of our framework, where we analyze the schedulability of an avionics system. Section VI introduces related work. Finally, section VII concludes our paper and outlines the future work.
II. COMPOSITIONAL SCHEDULABILITY ANALYSIS deadline (d), priority (prio) and preemption (p). The execution time (et) specifies the CPU usage time required by the task execution for each period (prd). Deadline parameter (d) represents the latest point in time at which the task execution must be done. The parameter prio specifies the user priority associated to the task. Finally, p is a Boolean flag stating whether or not the task is preemptive. The task behavior is a sequence of timed actions consuming CPU time and resources.
Moreover, task and component parameters prd, budget and et can be single values or time intervals.
An example of a hierarchical scheduling system is depicted in Fig. 2. For the sake of simplicity, we omit task deadlines and consider them the same as periods. Moreover, we only consider single parameter values instead of time intervals.
In this example, the top level System schedules Component1 and Component2 with the EDF scheduling algorithm. The components are viewed by the top level System as tasks having timing requirements. Component1, respectively Component2, has the interface (100, 37), respectively (70, 25), as period and execution time. The system shown through this example is schedulable if each component, including the top level, is schedulable. Thus, for the given timing requirements Component1 and Component2 should be schedulable by the top level System according to the EDF scheduling policy. The tasks task1 and task2 should be schedulable, with respect to the timing requirement of Component1 (100, 37), also under the EDF scheduling policy. Similarly, task3, task4 and task5 should be schedulable, with respect to the timing requirements of Component2, under the RM scheduling policy.
For a given system structure, we can have many different system configurations. A system configuration consists of an instantiation of the model where each parameter has a specific value. Fig. 2 shows one such instantiation.
In order to design a framework that scales well for the
analysis of larger hierarchical scheduling systems, we have
decided to use a compositional approach [
In this paper, we structure our system model as a set of hierarchical components. Each component, in turn, is the parallel composition of a set of entities (components or tasks) together with a local scheduler. Namely, each component is specified with a period (prd), a budget (budget) stating the execution time that the component should be provided with, A and a scheduling policy (s) to manage the CPU allocation System to the component child entities. The real-time interface of a EDF component consists of prd and budget.
A parent component treats the real-time interface of each A1 A2 one of its child components as a single task with the given Component1 Component2 real-time interface. The component supplies its child entities EDF RM with CPU and resource allocation according to their realtime interfaces. The analysis of a component (scheduling unit) consists of checking that its child entities can be scheduled task1 task2 task3 task4 task5 within the component budget according to the component scheduling policy. A component can be also parameterized EDF,.RM:.scheduling.policies..A,.A1,.A2:.analysis.processes. by a set of typed resources (R) which serve as component Fig. 3. Compositional analysis local resources. One can remark that the CPU can be managed by any scheduling policy s, whereas the sharing of the other The schedulability of each component, including the top resources will be managed by SIRAP. level, is analyzed together with the interface specifications of
Tasks represent the concrete behavior of the system. They the level directly below it. Accordingly, we will never analyze are parameterized with period (prd), execution time (et), the whole hierarchy at once. In Fig. 3, the analysis process A International Conference on Advanced Aspects of Software Engineering
ICAASE, November, 2-4, 2014, Constantine, Algeria. 141
consists of checking whether the two components Component1
and Component2 are schedulable under the scheduling policy
EDF. In this analysis step, we only consider the interfaces of
components in the form of their execution-time (budget) and
period, so that we consider the component as an abstract task
when performing the schedulability analysis of the level above
it. In this way, we consider the component-composition
problem similarly to [
Our compositional analysis approach results in an overapproximation i.e. when performing the analysis of a subsystem, we over-approximate the behavior of the rest of the system. This can result in specific hierarchical scheduling systems that could be schedulable if one considers the entire system at once, but that is not schedulable using our compositional approach. We consider this fact as a design choice which ensures separation of concerns, meaning that small changes to one part of the system does not effect the behavior of other components. In this way, the design of the system is more stable which in turn leads to predictable system behavior.
This over-approximation, which is used as a design choice, should not be confused with the over-approximation used in the verification algorithm inside the UPPAAL verification engine.
Thanks to the parameterization of system entities; scheduling policies, preemptiveness, execution times, periods and budgets can all easily be changed. In order to estimate the performance and schedulability of our running example, we have evaluated a number of different configurations of the system. This allows us to choose the best of the evaluated configurations of the system.
III. BACKGROUND AND THEORY
or more components running on the same execution platform. Each component, in turn, consists of a set of entities that can be developed independently and a local scheduler. Component entities are known by the component workload, and are either components or tasks. The execution platform we consider in our framework is a single processor (CPU). We specify the behavior of each task by a sequence of timed actions (computation steps, input, output, etc) that use CPU and resources. The CPU resource is arbitrated by different scheduling policies such as EDF, RM and FPS, whereas the resource sharing is managed by a resource sharing protocol.
International Conference on Advanced Aspects of Software Engineering ICAASE, November, 2-4, 2014, Constantine, Algeria.
The limitation of resources represents a strong factor in the
setting of any software system, because resources cannot be
duplicated due to their cost. So that the concurrent processes
of a system compete to gain the access to resources in order
to perform their jobs, and only one process is allowed to use
the resource at a time. The mechanism to ensure that only
one process gains the use of a resource at time is known
as mutual exclusion. However in the area of hierarchical
scheduling systems, due to the hierarchy the classical mutual
exclusion mechanisms cannot operate fairly. Resource sharing
protocols have been designed to reasonably share (non-CPU)
resources between system tasks where the system architecture
is hierarchical. Some popular resource sharing protocols are:
Priority Inheritance Protocol (PIP) [
Due to hierarchy, we have chosen to use the SIRAP protocol
[
timed actions. Each timed action can either be a computation step (Compute), access or release of a shared resource (Lock, Unlock) or particular statements marking the end of the period (Pend) or the end of the task execution (End).
Acts = fCompute, Lock, Unlock, Pend, Endg, a CPU and a set of resources R, a timed action A is a one step computation given by the tuple hAct; P roc; BCET; W CET i where:
Act 2 Acts is the action name, P roc fCP U g[R specifies the identifiers of processor the execution time of preemptable tasks. This section gathers and resources that the timed action A requires for its the Parameterized Stopwatch Automata (PSA) models of our execution, framework, as well as the UPPAAL analysis. Due to space BCET and W CET are respectively best case and worst limitations, we only explain important features. case execution times,
By A we denote the set of all timed actions. In fact, the A. PSA Resource Model CPU and resources can be viewed as a multi-core execution platform. Likewise, we define the behavior B of a task as a The hierarchical scheduling system structure is a set of transition system hL; l0; !i specifying the sequence of timed scheduling components, each one includes a single specific actions performed by that task, where L is a set of states, scheduling algorithm and a set of entities (tasks or comlr0el2atiLoni.s St htaeteinsitciaaln stbaeteinantedrp!retedLin Athe Lse misatnhteictrlaenvseiltioans cpoomnepnotssi)t.ioTnoal amnaalnynzeer, ait siisngnleececsosmarpyontoenctonbsyidemretahnes inotferavaluations of the task variables together with the state of rupted behavior of that component by the other concurrent each task (ready, waiting, preempted, done, etc). The behavior components within the same system. However, it is hard to of a component is given by the parallel composition of the capture the interrupting behavior of the other components that transition systems of its nested tasks. influence the component under analysis. For this reason, we
Definition 2 (Task structure): A task T is given by introduce a non-deterministic supplier to model all scenarios hP rd; BCET; W CET; P ri; B; Dlni where P rd is the task that the component under analysis can run. Such a nonperiod, BCET and W CET are respectively best case and deterministic fact simulates the influence of the other system worst case execution times of T , P ri is the priority level components on the execution of the component under analysis. associated to task T , B is the task behavior stated above and The scheduling policy within the component then allocates the Dln is the deadline.
Therefore, the task specification is given by an interface P rd; BCET; W CET; Dln stating the time constraints, a behavior B expressed by a sequence of timed actions and a priority P ri that will be applied for each timed action of the task in question.
Roughly speaking, a component is given by an interface stating its timing requirements and a local policy for scheduling its nested entities (workload). The interface of a component C0 can be viewed by its parent component C as resource requirements that must be supplied by C to C0, and it is viewed by the child entities of C0 as a contract that the component C0 Fig. 4. PSA model of supplier template will provide the amount of resources specified in its interface to its workload. For the sake of simplicity, we do not consider CPU resource to tasks. It also abstracts the possibility that a local resources for each component, i.e. all resource are global task from another component of the system (not part of the and shared by all of the system components. current analysis step) could preempt the execution of tasks of
Definition 3 (Component): A component C is a tuple the current component. hP rd; Budget; P ri; s; he1; ::; enii where: Fig. 4 shows the PSA model of supplier. supplyP rd and P ri are the same as for tasks, ing time[supid] is a stopwatch that measures the CPU time Budget is the amount of CPU time that the component provided by supplier during each period, so that it only guarantees to provide to its workload, progresses when the supplier is at location Supplying. In s 2 fEDF; F P; RM; ::g is a scheduling policy, fact, the supplier keeps traveling between locations Supplyhe1; ::; eni are component entities (workload), either tasks ing and NotSupplying while the budget is not fully proor other components. vided (supplying time[supid] sup[supid].budget) and the slack Similarly, a system is the top level component without tim- time (curTime sup[supid].prd -sup[supid].budget + supplying requirements (P rd; Budget; P ri). We emphasize the fact ing time[supid]) is not expired, until the component budget is that our framework can be instantiated for any combination of fully provided (supplying time[supid] sup[supid].budget) and scheduling algorithms. then starts a new period from location Done.
IV. UPPAAL MODELING AND ANALYSIS
The UPPAAL verification suite provides both symbolic A task model is depicted in Fig. 5. After being started
and statistical model checking (SMC). The models which at location Idle, the task joins location WaitingOffset waiting
in practice can be analyzed statistically, using the UPPAAL until the task offset is expired. From that location, the task
SMC verification engine, are larger and can contain more moves to location ReadingOP where it can read a PEND
features. Stopwatches [
ICAASE, November, 2-4, 2014, Constantine, Algeria. 143 location ReadingOP, the task can also read operations COMPUTE, LOCK SIRAP, and UNLOCK SIRAP from its concrete behavior description. By reading a COMPUTE command, the task checks it own status if it is either READY or RUNNING.
A READY status means that the task is ready to run using the CPU, whereas RUNNING means that the task is still scheduled to use CPU. From location ReqSched, the task updates its status to RUNNING and inserts its Id into the CPU queue. From location CheckingSupply, the task checks whether the supplier is providing the CPU resource. If the supplier is currently providing CPU resource, the task moves to location Executing, otherwise it moves to location Suspended. At location Executing, the task checks if it has been assigned a CPU via function isTaskSched(). If so, the stopwatch proTime[tid] keeps progressing while the wcet and deadline are not reached yet.
The task may keep traveling between locations Executing and Suspended according to whether or not the CPU is supplied.
The task joins location MissDeadline whenever the deadline is missed.
The task execution can be delayed due to the resource managed by SIRAP, once the task requests a resource via command LOCK SIRAP. Such a delay can be one of the followings:
at the component level) allocated to use the resource, but it is not globally allocated for the same resource, i.e. a task from another component is using the resource. At location LocalWaiting, the task is not locally allocated to use the resource.
At location SIRAPWaiting, the task is delayed due to SIRAP protocol, i.e. in the case of a deficit of the remaining resource of the supply for a period.
moves to LocalWaiting by losing the resource allocation, or to location SIRAPWaiting by a deficit of the supplied resource.
By reading a UNLOCK SIRAP command at location ReadingOP, the task withdraw its identifier tid from the resource queue managed by SIRAP.
The schedulability of a task can be checked via the reachability of location MissDeadline using the query: E<>MissDeadline.
In order to avoid checking the schedulability of each task separately, we introduce a global variable error that can be updated to true by any task missing its deadline, so that the schedulability of a component can be checked using the following query: A[] error!=1. checks whether the requesting task is the current scheduled one (sel tid(rid) == req tid(rid)) or not.
If it is not the case, the status of the requesting task will be updated to PENDING RESOURCE and the protocol joins the initial location. Otherwise, the protocol checks that the time left from the component budget of the current task (sup[tstat[sel tid(rid)].pid].budget) covers the amount of resource requested by the task in question. If the budget of the current task supplier is greater than the sum of time supplied by that supplier to its tasks and the resource usage time of the current request (sup[tstat[sel tid(rid)].pid].budget supplying time[tstat[sel tid(rid)].pid] + tstat[sel tid (rid)] .rc time) then the resource request will be satisfied for the current task, otherwise the current requesting task has to wait for the next supply (tstat[sel tid(rid)].status = PENDING BUDGET).
After receiving a request r req[rid] from a task, the CPU template activates the component scheduling policy policy in order to determine to which task the CPU resource should be assigned. rid is the CPU resource identifier. Once the CPU is assigned to a task, at location Assign, such a task keeps using the CPU resource until it is done (finished[rid]?) or a new request (r req[rid]?) to reschedule the CPU appears. Whenever a CPU schedule is done (finished[rid]) and the CPU waiting list is not empty (rq[rid].length>0), the CPU resource moves to location ReqSched and restarts the scheduling process, otherwise it keeps waiting at location Idle until a task requests the CPU resource.
we have modeled the avionics system introduced in [
To share resources between the tasks of a hierarchical computer (MCC) system dedicated to combat and attack
scheduling system, we use SIRAP protocol. In fact, SIRAP aircrafts. The application is a composition of 15 tasks declared
enables the isolation of system components from each other with different priorities and timing requirements, together with
even in the presence of mutually exclusive shared resources. shared resources to perform input and output communications.
We have modeled SIRAP protocol as shown in Fig. 6. Initially, We have used SIRAP protocol [
International Conference on Advanced Aspects of Software Engineering ICAASE, November, 2-4, 2014, Constantine, Algeria. 144 Fig. 5. PSA model of task template
bomb button is being pressed or the time of a scheduled release is reached to drop a weapon.
Radar tracking (T2): it explores a ground map, or performs a ground search or a single-target track. Target tracking (T3): this task captures the target position relative to the aircraft. The radar keeps tracking a target if it is already spotted, and also designated by the aircrew for a potential attack.
Target sweetening (T4): no description provided for this task.
HOTAS Bomb Button (T5): a target is designated as an attack target by activating the Hands-On Throttle And Stick switch.
Aircraft Flight data (T6): it determines the best available estimates of aircraft position, velocity, attitude, motion through air-mass, etc.
HUD display (T7): the Head-Up Display shows the aircraft flight data (airspeed, heading, etc.), the strike point and/or seeker position.
tactical situation, the threat data, a display of stores components interfaces are shown in Fig. 8. In fact, as
commuremaining, radar display information, etc. nication times are given in microseconds we convert the task
Steering (T9): it computes the steering cues for display timing requirements from milliseconds to microseconds. Thus,
based either on way-point steering or target attack steer- the interface of each component is given in terms of period and
ing. budget specified in microseconds. Tasks are gathered together
Weapon trajectory (T10): it computes the weapon trajec- within components based on their features. Component 1
tory (ballistics) one minute before its release based on (Control and Display) includes 4 tasks concerning the graphical
aircraft speed, target range, etc. display of information. Component 2 (Sensor and Navigation)
Threat response display (T11): once the radar warning re- encapsulates 6 tasks concerning the navigation system and
ceiver detects a potential target, the current task analyzes external sensors. Component 3 (Fire and Stores) includes 3
that warning and displays the information for the aircrew. tasks. It manages the firing system and checks periodically the
AUTO/CCIP toggle (T12): the weapon release modes weapons store. Component 4 (Background) encapsulates two
include automatic (AUTO) and continuously computed tasks to check the aircraft devices and potentially reinitiate the
impact point (CCIP) delivery. trajectory. Each of these component has a local FPS scheduling
Poll RWR (T13): the Radar Warning Receiver warns the policy.
aircrew of hostile radar energy being beamed at the To perform the schedulability analysis of each individual
aircraft. component of the avionics system, we have introduced a
nonReinitiate trajectory (T14): this task updates the trajectory deterministic supplier and estimated the minimum budget of
of aircraft based on radar status, aircrew actuation, etc. each supplier. A model-based technique for the computation of
Periodic BIT (T15): the Built-In Test task periodically the supplier (minimum) budget has been introduced in [
A challenge encountered during this application is the estimation of both period and budget of each supplier such that 1) each supplier provides enough resources to its child tasks; 2) the parallel composition of all suppliers is schedulable according to the system level scheduling policy.
VI. RELATED WORK
Hierarchical scheduling systems were introduced in [
Recent research within schedulability analysis increasingly uses model-based approaches, because this allows for modeling more complicated behavior of systems. The rest of the related work presented in this section focuses on model-based approaches.
In [
They constructed an abstract task model as well as scheduling algorithms, where the schedulability analysis of a component does not only consider the timing attributes of that component but also the timing attributes of the other components that can preempt the execution of the component under analysis.
In [
They modeled the concrete task behavior as a sequence of timed actions, each one represents a command that uses processing and system resources and consumes time.
The authors of [
We combine and extend these approaches [
VII. CONCLUSION
We have introduced a compositional framework for the schedulability analysis of hierarchical real-time systems. System tasks are modeled using Parameterized Stopwatch Au
system when analyzing an individual component, we introduced a non-deterministic supplier where the resource supply of one budget can be given on several chunks, simulating then the preemption that the rest of system may perform on the behavior of the component under analysis. We also considered resource sharing between system components and used SIRAP protocol to manage such a sharing. We have applied our schedulability analysis framework on an avionics system where components are analyzed separately even they share communication resources.