In the design of critical real-time embedded systems, predictability in timing behavior and in system resource usage is necessary. Vestal's mixed-criticality task model and the Predictable Execution Model (PREM) help achieve these objectives in diferent ways. Under Vestal's model, multiple worst-case execution time (WCET) estimates are considered for each task, with corresponding degree of confidence, and associated with a diferent criticality level. The schedulability analysis can derive the appropriate timing safety guarantees for each task without using more conservative estimates than needed, thereby avoiding overengineering. The adaptive variant of Vestal's model also allows for system modes, with some tasks idled at mode change and more conservative WCET estimates thereafter assumed for remaining tasks. Meanwhile, the 2-phase PREM model, via compiler support, first fetches from memory (into the cache) all the locations that a task will access, and only subsequently proceeds with computation. This removes a lot of the uncertainty in WCET estimation stemming from the cache state and memory access delays, leading to better predictability and tighter WCET estimates. Vestal's model and the PREM model, however, were independently conceived, and never combined. In this work, we explore diferent possibilities about how these two models could be combined. We focus on the semantics of multiple (static or probabilistic) per-task estimates of processor computation time and number of memory accesses, how these can be derived, the associated compiler and O/S support required, and the implications for timing analysis.
The criticality of a computing task reflects the severity of the consequences of its failure; and a deadline miss is a form of failure. Higher-criticality tasks are developed according to stricter methodologies, require stronger safety guarantees and, traditionally, ran on separate hardware from lower-criticality tasks. However, size, weight and cost concerns, currently motivate (e.g., in automotive or avionics systems) mixed-criticality systems, where tasks of diferent criticality can coexist on the same platform. Often, commercialof-the-shelf (COTS) hardware is used, which ofers good performance for its cost but is not very timing-predictable. Researchers try to deal with that in diferent ways, two of which are Vestal’s mixed-criticality task model and the Predictable Execution Model (PREM). The present work highlights alternatives ways for combining those two models.
Vestal’s model [
The Predictable Execution Model (PREM) is a way of dealing with intercore interference on accessing shared resources. PREM tasks are structured as sequences of scheduling intervals, which are of two types: predictable or compatible. A predictable interval is non-preemptible and it has a memory phase, followed by a computation phase. In the memory phase, all the data required during the computation phase is prefetched into the cache. This ensures that the computation phase is cache-miss-free and removes the need to analyse the cache state during WCET analysis, and the resulting pessimism.
In this work, we explore diferent ways in which PREM and the adaptive mode-based mixed-criticality model could be combined. For each alternative, we summarise the semantics, challenges and implications, in terms of analysis, compiler and O/S support.
Vestal’s paper [
Deployment of real-time systems (single- or mixed-criticality) on COTS hardware gives
rise to predictability concerns, as diferent tasks access shared resources (i.e., caches, buses
and memory). There exist diferent approaches in the literature that try to alleviate and/or
upper-bound such interference, e.g., via regulation-based arbitration [
Consider a set of independent sporadic tasks, i.e., = { 0, 1, 2, · · · , −1}. For
a task , , and ≤ denote its criticality, minimum inter-arrival time and
deadline, respectively. Each task is a sequence of non-preemptive predictable scheduling
intervals, as in PREM [
We assume that each memory access (cache miss) has a fixed latency. This allows us to simplify the notation, by using that latency as the unit of time. Then, an interval , can be modeled as { , , , , , | }; the first two scalars are estimates of memory | , , accesses in the memory phase and the latter two are WCET estimates for the execution phase. (Diferent semantics for the pairs { , , , } are explored in Section 4.)
Consider a multicore platform composed of identical cores { 0, 1, · · · , −1}. The
main memory is accessed through a single shared memory controller and interconnect,
whose combined scheduling policy is round-robin, as in [
Analogously to existing works based on Vestal’s adaptive mixed-criticality model, the idea is for the system to undergo mode switch whenever some L-estimate by some scheduling | ) is exceeded. However, we have not yet defined how L- and interval (e.g., , or , H-estimates relate to each other, nor what happens at mode switch. Diferent conceivable options for that exist. We next briefly examine four alternative models.
For better illustration and comparison, we do so via an example task set, consisting of four tasks (see Table 1). Two of these tasks are high-criticality ( 2, 3) while the other two ( 0, 1) of low-criticality. We consider a dual-core platform, with 3 tasks ( 1 to 3) assigned to core 1 and 0 assigned to 0. On core 1, task 3 has the lowest priority and 1 the highest one. The trace of execution for diferent PREM-MCS scheduling models is depicted in Figures 1 to 5. For easier illustration, we assume that memory accesses from diferent cores are served by the memory controller in a round-robin manner. (This is not part of the PREM-MCS model, which is agnostic w.r.t. the scheduling policy of the memory controller. We just had to assume one such policy, when drawing the schedules.) Definition 4.1 (Transition scheduling interval). If a mode switch is triggered by an overrunning task during the execution of scheduling interval , of task , then , is a transition scheduling interval.
Definition 4.2 (Transition job).
A job with a transition scheduling interval.
Definition 4.3 (Compute-interfered scheduling interval). A transition interval that is in (or at the start of) its processor computation phase at the time of a mode switch. Definition 4.4 (Memory-interfered scheduling interval:). A transition interval that is in (or at the start of) its memory phase at the time of a mode switch.
This variant uses, for a scheduling interval of an H-task, a single memory access estimate in both modes (i.e., , = , ). This is conservatively derived, therefore it cannot be exceeded, triggering a mode switch. A mode switch can only be triggered by a processor execution overrun. The mode switch semantics are: • Initially the system is in L-mode. • A mode switch is triggered if any scheduling interval overruns its , | . | estimates • At the mode switch, all L-tasks are dropped and, for H-tasks, their , are henceforth assumed, for the transition scheduling interval, subsequent scheduling intervals of transition jobs and all future jobs.
As shown in Figure 1, as soon as the mode switch is triggered by 0,1: 2,1 (2nd job of
task 2) executing on 1 and all subsequently-executed scheduling intervals of all tasks,
execute with more conservative H-mode estimates. This model is straightforward and
requires no changes to the existing PREM compiler and its timing analysis could be
based on that in [
This model can ofer improved schedulability, compared to previous one (T).
Probabilistic worst-case analysis techniques could be used to obtain the L-estimates. Static
worst-case analysis techniques would only be used for H-estimates (safe but pessimistic).
The existing PREM compiler [
The diference from the previous variant (K) is that the assumption/requirement of no cache misses during the computation phase is relaxed. In the L-mode (i.e., as long as the L-estimates are not overrun), this is still guaranteed by design. However, in the H-mode, under this variant, cache misses are possible. Figure 4 shows the execution pattern of the example task set as per the PREM-MCS P-model. The cache misses in the computation phase after the mode switch are represented as boxes with grid fill pattern.
This model violates the core assumption of PREM that computation phases are
cache-miss-free. Contention therefore arises from memory accesses generated during the
computation phase of H-tasks. If only few cache misses can occur, this can be managed
via hardware servers, as in [
The distinguishing feature of this variant is that, for compute-interfered transition intervals, the computation phase is interrupted at the moment of mode changes, and a supplementary memory phase (with , − , accesses) is executed; afterwards, the computation phase resumes from where it was interrupted. This is a significant departure from some of the assumptions in PREM.
This arrangement seeks to optimise for the common case: instead of prefetching memory locations that a task will rarely, if ever, need, only do this reactively, when indications arise that there is a chance of needing them. A mode switch triggered by another task can be such an indication. The case of the task itself triggering the mode switch, by exceeding its computation phase L-WCET merits some discussion.
In the general case, the computation phase of a scheduling interval , overruning its , might be purely down to control flow, and will not necessarily indicate that an access to a memory location other the , locations prefetched by the corresponding memory phase is imminent. Similarly, if the computation phase of , needs to access a memory location other than the , locations prefetched by the corresponding memory phase, this would not necessarily be preceded by an exceedance of its , estimate. In any case, the mode change semantics might be justified out of abundant caution.
Another possible way to justify the arrangement is by selecting the , memory locations accessed during the memory phase and the computation phase L-mode WCET , in conjunction such that (verifiably, by ofline static analysis), under any control lfow, no access to a memory location other than those , occurs, unless (previously, in the same control flow) there is an overrun of the , computation phase WCET estimate. Then, at mode switch, the supplementary memory phase fetches , − , additional locations, in case they are needed; and this ensures the compuation phase will be cache-miss-free, in any case.
These semantics require significant changes both to the existing PREM compiler and scheduler. Under the PREM model, it is assumed that no system calls or interrupt service routines are served during predictable intervals. (These are only served under compatible intervals – the other type of scheduling intervals that we don’t consider here.) However, for a transition interval, an interrupt-based method is required, to immediately initiate the supplementary memory phase and to subsequently return control to the computation phase, at the point of interruption.
Some of the potential implications, in terms of complexity, on the static, ofline timing
WCET analysis have been mentioned above. From the schedulability analysis perspective,
the interference and stall from the additional memory phase need to be quantified and
incoroprated into the schedulability analysis. The specifics will difer, depending, e.g.,
on whether there is memory access regulation [
In the example of Figure 5, an additional memory phase (with 2,2 − 2,2 = 2 - 1 = 1 access) takes place during the computation phase of 2,2.
Achieving both predictability and eficient resource utilisation for real-time systems deployed on COTS multicore platforms is challenging because of shared resources. In this work, we have proposed the combination of Predictable Execution model (PREM) and the Adaptive Mixed-Criticality model (AMC), as a promising way of dealing with such challenges. We outlined four possible ways of combining the semantics of those two models, especially regarding mode changes. Each of those has diferent advantages and implications, w.r.t. compiler support, run-time support and ofline timing analysis.
This work is a first step in combining PREM and adaptive mixed-criticality scheduling. As a next step, weighing all the options, we will settle on the appropriate model semantics, and work on the corresponding schedulability analysis.
This work was partially supported by National Funds through FCT/MCTES (Portuguese Foundation for Science and Technology), within the CISTER Research Unit (UIDP/UIDB/04234/2020); by the Operational Competitiveness Programme and Internationalization (COMPETE 2020) under the PT2020 Partnership Agreement, through the European Regional Development Fund (ERDF), and by national funds through the FCT, within project PREFECT (POCI-01-0145-FEDER-029119); by FCT through the European Social Fund (ESF) and the Regional Operational Programme (ROP) Norte 2020, under grant 2020.08045.BD. This work is partially supported by Connecting Education and Research Communities for an Innovative Resource Aware Society (CERCIRAS) COST Action CA19135 funded by European Cooperation in Science and Technology (COST) Association.