875 lines
109 KiB
Plaintext
875 lines
109 KiB
Plaintext
Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
|
||
Contents lists available at ScienceDirect
|
||
|
||
|
||
Journal of Systems Architecture
|
||
journal homepage: www.elsevier.com/locate/sysarc
|
||
|
||
|
||
|
||
|
||
EDF-based Energy-Efficient Probabilistic Imprecise Mixed-Criticality
|
||
Scheduling
|
||
Yi-Wen Zhang ∗, Jin-Long Zhang
|
||
College of Computer Science and Technology, Huaqiao University, Xiamen, 361021, China
|
||
|
||
|
||
|
||
ARTICLE INFO ABSTRACT
|
||
|
||
Keywords: We focus on Mixed-Criticality Systems (MCS), which involves the integration of multiple subsystems with
|
||
Imprecise Mixed-Criticality varying levels of criticality on shared hardware platforms. The classic MCS task model assumes hard real-time
|
||
Energy management constraints and no Quality-of-Service (QoS) for low-criticality tasks in high-criticality mode. Many researchers
|
||
DVFS
|
||
have put forward a range of extensions to the classic MCS task model to make MCS theory more applicable in
|
||
Probabilistic schedulability
|
||
industry practice. In this paper, we consider an Imprecise MCS taskset scheduled with Earliest Deadline First
|
||
algorithm on a uniprocessor platform, and propose an Energy-Efficient Task Execution Model that guarantees
|
||
(deterministic or probabilistic) schedulability, allows degraded QoS to low-criticality tasks in high-criticality
|
||
mode, and applies Dynamic Voltage and Frequency Scaling to save energy.
|
||
|
||
|
||
|
||
1. Introduction
|
||
In this paper, we consider all the above different aspects within
|
||
Mixed-Criticality Systems (MCS) [1] involve the integration of mul- a unified framework. We consider an Imprecise MCS probabilistic
|
||
tiple sub-systems with varying criticality levels on a shared hardware taskset scheduled with Earliest Deadline First (EDF) algorithm on a
|
||
platform. For example, the automotive safety certification standard ISO uniprocessor platform, and propose an Energy-Efficient Task Execution
|
||
26262 and the avionics safety certification standard DO-178C. Since Model that guarantees (deterministic or probabilistic) schedulability,
|
||
the introduction of the MCS concept by Vestal [2], there has been allows degraded QoS to LO tasks in HI mode, and applies DVFS to
|
||
considerable research conducted on this topic [1,3,4]. Many researchers save energy. Although the work in [7] is the closest to ours, there are
|
||
several key differences. Firstly, it schedules tasks under non-preemptive
|
||
have put forward a range of extensions to the classic MCS task model
|
||
fixed-priority (NPFP) [8] scheduling policy while our work schedules
|
||
to make MCS theory more applicable in industry practice, including:
|
||
tasks with a preemptive EDF. Secondly, it uses probabilistic WCET
|
||
(pWCET) to determine the probability of mode transition and uses a
|
||
• To reduce the pessimism in task worst-case execution time
|
||
deterministic schedulability analysis while our work includes determin-
|
||
(WCET) estimation and system schedulability analysis,
|
||
istic or probabilistic schedulability analysis. Finally, it uses the response
|
||
researchers have proposed probabilistic schedulability analysis
|
||
time analysis to determine the schedulability analysis while our work
|
||
techniques where the task WCETs (and/or periods) are repre-
|
||
uses Demand Bound Function (DBF) to determine the schedulability
|
||
sented by random variables, and the system is allowed to miss analysis. In short, the work is first to address the energy issue and
|
||
deadlines with a small probability [5]. schedulability test of the Imprecise MCS probabilistic taskset MCS
|
||
• The original assumption that all low-criticality (LO) tasks are taskset scheduling under EDF.
|
||
discarded in high-criticality (HI) mode is likely to be undesirable The remainder of the paper is organized as follows. We present
|
||
in industry practice, hence researchers have proposed various background and related work in Section 2. Section 3 presents prelim-
|
||
approaches to allow a certain level of degraded Quality-of-Service inaries. Section 4 presents our probabilistic IMC scheduling; Section 5
|
||
(QoS) to LO tasks in HI mode [1]. presents the Energy-Efficient Task Execution Model; Section 6 presents
|
||
• To address energy-constrained safety–critical systems, researchers experimental results; Section 7 discusses practical issues. Finally, Sec-
|
||
have proposed power and energy-aware scheduling algorithms tion 8 presents conclusions and future work.
|
||
with Dynamic Voltage and Frequency Scaling (DVFS) for MCS [6].
|
||
|
||
|
||
|
||
∗ Corresponding author.
|
||
E-mail addresses: zyw@hqu.edu.cn (Y.-W. Zhang), sang_yunl@stu.hqu.edu.cn (J.-L. Zhang).
|
||
|
||
https://doi.org/10.1016/j.sysarc.2025.103361
|
||
Received 11 September 2024; Received in revised form 3 February 2025; Accepted 4 February 2025
|
||
Available online 12 February 2025
|
||
1383-7621/© 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
|
||
Y.-W. Zhang and J.-L. Zhang Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
|
||
2. Background and related work 2.2. The classic MCS task model
|
||
|
||
2.1. Background and motivation The MCS taskset 𝛤 includes 𝑛 independent sporadic tasks 𝛤 =
|
||
{𝜏𝑖 |1 ≤ 𝑖 ≤ 𝑛} [13,14]. Although there may be multiple (4–5) criticality
|
||
Resource-constrained embedded systems. In order to motivate levels in general, we present the task model assuming a dual-criticality
|
||
the need for probabilistic scheduling and DVFS addressed in this paper, system with criticality levels LO and HI for the sake of simplicity. The
|
||
we first discuss the issue of hardware resource constraints in real- taskset 𝛤 includes two subsets: LO tasks 𝛤𝐿𝑂 = {𝜏𝑖 ∈ 𝛤 |𝐿𝑖 = 𝐿𝑂} and
|
||
time embedded systems, including but not limited to MCS, which HI tasks 𝛤𝐻 𝐼 = {𝜏𝑖 ∈ 𝛤 |𝐿𝑖 = 𝐻 𝐼}. Each task 𝜏𝑖 ∈ 𝛤 is described by
|
||
are especially pertinent for mass-produced consumer products such (𝐿𝑖 , 𝑇𝑖 , 𝐷𝑖 , 𝐶𝑖𝐿𝑂 , 𝐶𝑖𝐻 𝐼 ):
|
||
as ground vehicles and drones (Unmanned Aerial Vehicles), due to
|
||
monetary cost as well as Size, Weight, and Power (SWaP) constraints. • 𝐿𝑖 ∈ {𝐿𝑂, 𝐻 𝐼} denoted its criticality level.
|
||
Automotive Electrical/Electronic (E/E) systems typically have stringent • 𝑇𝑖 denoted its period.
|
||
hardware resource constraints. In modern high-end vehicles, there can • 𝐷𝑖 denoted its relative deadline.
|
||
be up to 100 ECUs (Electronic Control Units) embedded within them, • 𝐶𝑖𝐿𝑂 denoted its WCET in LO mode.
|
||
and each model can be sold millions of times. An overall savings of • 𝐶𝑖𝐻 𝐼 denoted its WCET in HI mode for HI tasks (𝐿𝑖 = 𝐻 𝐼), with
|
||
millions of dollars may be achieved by saving a few dollars per ECU. 𝐶𝑖𝐻 𝐼 ≥ 𝐶𝑖𝐿𝑂 .
|
||
Hence, a designer of E/E systems should choose the cheapest ECU
|
||
according to their application’s needs. The monetary cost pressure on Task execution model of classic MCS. The system is first ini-
|
||
relatively cheap consumer drones is even higher. Next, let us consider tialized to be in LO mode. LO tasks 𝜏𝑖 ∈ 𝛤𝐿𝑂 are monitored at run
|
||
the issue of SWaP, which lumps together three factors that are closely time and their execution is no more than their 𝐶𝑖𝐿𝑂 . The system is
|
||
correlated due to the same underlying cause of hardware resource schedulable in LO mode if all tasks 𝜏𝑖 ∈ 𝛤 can complete their LO mode
|
||
constraints. The significance of SWaP is obvious in battery-powered WCETs 𝐶𝑖𝐿𝑂 within their respective deadlines. If any HI task 𝜏𝑖 ∈ 𝛤𝐻 𝐼
|
||
mobile devices like drones and mobile robots, where operating time executes beyond its 𝐶𝑖𝐿𝑂 , the system enters HI mode while all LO tasks
|
||
and physical constraints are limited. However, SWaP considerations in 𝛤𝐿𝑂 are abandoned. The system is schedulable in HI mode if all HI
|
||
are equally applicable to ground vehicles that are equipped with siz- tasks 𝜏𝑖 ∈ 𝛤𝐻 𝐼 can complete their HI mode WCETs 𝐶𝑖𝐻 𝐼 within their
|
||
able battery systems. Electronics within autonomous vehicles consume respective deadlines. The system switches back to LO mode at an idle
|
||
substantial power, impacting the range of electric vehicles or the fuel instant if no jobs wait for executions at this time [15]. The system is
|
||
consumption of gasoline vehicles. Size and weight affect consumer schedulable if both modes are schedulable.
|
||
acceptance, e.g., an autonomous vehicle with a trunk full of electronics The state-of-the-art scheduling algorithms for the classic MCS task
|
||
is not likely to be acceptable to the average consumer. The issue of model include Fixed-Priority scheduling [14], and Earliest-Deadline
|
||
significant hardware resource constraints in MCS has motivated a line First with Virtual Deadline (EDF-VD) [16] for Dynamic-Priority
|
||
of work on processing and memory resource optimization algorithms scheduling on uniprocessor systems. Subsequently, many extensions to
|
||
for MCS [9]. the classic MCS task model have been proposed, as discussed next.
|
||
Motivation for probabilistic schedulability analysis. Recently,
|
||
Akesson et al. [10] investigated 120 industry practitioners in real-time 2.3. Degraded QoS for LO tasks
|
||
embedded systems, and results indicated that soft or firm real-time
|
||
constraints are prevalent even in safety–critical application domains. The degraded QoS of LO tasks in HI mode is achieved by decreasing
|
||
A minority (15%) of the surveyed systems were considered strictly execution time budgets [17] or adding the task period [18] for LO tasks.
|
||
hard real-time (no deadlines to be missed). Thus, designing the timing Liu et al. [17] proposed the Imprecise Mixed-Criticality (IMC) task
|
||
behavior of a system function to ensure a much lower failure rate did model in which a HI task 𝜏𝑖 (𝐿𝑖 = 𝐻 𝐼) is assigned a greater estimated
|
||
not affect the system’s total schedulability. WCET compared to its estimation in LO mode (𝐶𝑖𝐿𝑂 ≤ 𝐶𝑖𝐻 𝐼 ), while a
|
||
Industry safety certification standards specify acceptable failure LO task 𝜏𝑖 (𝐿𝑖 = 𝐿𝑂) is assigned a smaller estimated WCET in HI mode
|
||
rates depending on the system’s criticality levels such as each ASIL has compared to the estimation in LO mode (𝐶𝑖𝐿𝑂 ≥ 𝐶𝑖𝐻 𝐼 ). They considered
|
||
a permitted failure probability of 10−9 for ASIL D, 10−8 for ASIL C EDF-VD scheduling on a single processor system, and presented two
|
||
and B, and 10−7 for ASIL A in the automotive standard ISO-26262 [5]. schedulability tests, one based on the utilization bound test, and the
|
||
Relaxing the hard real-time assumption can help reduce pessimism other based on the Demand Bound Function (DBF). Davis et al. [19]
|
||
in task WCET estimation and system schedulability analysis and in- addressed the IMC task model under fixed-priority scheduling, and pre-
|
||
crease schedulable utilization significantly. Von der Brüggen et al. [11] sented a Compensating AMC Scheduling scheme and two schedulability
|
||
demonstrated large gains in processor utilization with experiments tests. Jiang et al. [20] presented a concrete implementation of the
|
||
using randomly-generated workloads, e.g., a gain of at least 12% IMC task model in the form of a configurable processor floating point
|
||
schedulable utilization for an acceptable worst-case deadline failure unit hardware design, as well as schedulability analysis and optimized
|
||
probability of 10−6 . This motivates probabilistic schedulability analysis priority assignment algorithms based on fixed-priority scheduling.
|
||
as an effective technique for reducing analysis pessimism and increase
|
||
processor utilization in resource-constrained embedded systems. 2.4. Energy-aware scheduling for MCS
|
||
Motivation for not dropping LO tasks in HI mode. Consider
|
||
the automotive standard ISO-26262, where ASIL determination of haz- DVFS dynamically adjusts the processor supply voltage and speed
|
||
ardous events is based on three parameters: ‘‘severity’’, ‘‘probability of (frequency) based on the system’s workload, which is an effective
|
||
exposure’’ and ‘‘controllability’’. An individual’s vulnerability to harm energy-saving technique [21]. Most modern microprocessors, including
|
||
in a potentially hazardous situation is determined by severity. Proba- those used in embedded systems, provide support for DVFS. Our recent
|
||
bility is the likelihood that harm will occur, while controllability is the survey paper [6] provided an overview of recent developments in
|
||
ability to avoid harm or damage through prompt action by the agents energy-aware real-time scheduling for MCS, predominantly focusing on
|
||
involved (e.g. a driver of the vehicle). It cannot always be assumed that DVFS.
|
||
a software function that is part of a high ASIL functionality is more Recently, power and energy-aware real-time scheduling for MCS
|
||
important than one that is part of a lower ASIL functionality, as both has attracted significant attention [6]. Huang et al. [22] proposed a
|
||
may be safety–critical, and each function’s failure may cause severe scheduling algorithm for MCS based on EDF-VD [16]. This scheduling
|
||
damage [12]. algorithm reduces energy consumption by optimizing virtual deadlines
|
||
|
||
2
|
||
Y.-W. Zhang and J.-L. Zhang Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
|
||
and processor speeds. Zhang [23] used the dynamic slack time gener- Table 1
|
||
Related work on probabilistic Scheduling for MCS. Abbreviations: Prob. (Probabilistic);
|
||
ated from late arrival tasks to reduce energy consumption. This work
|
||
S.A. (Schedulability Analysis).
|
||
is extended to MCS with fixed-priority preemptive scheduling [24] and
|
||
Work Sched. Prob. Energy- LO tasks
|
||
dynamic priority non-preemptive scheduling [25]. Zhang et al. [26] Algo. S.A. Aware dropped in
|
||
tackled the issue of MCS with shared resources and proposed a dual- HI Mode
|
||
speed scheduling algorithm. This algorithm ensured both the system Santinelli and George (2015) [33] EDF Y N Y
|
||
schedulability and mutually exclusive access to shared resources. How- Maxim et al. (2017) [34] FP Y N Y
|
||
ever, it assumed that all tasks execute with their WCET. Zhang [27] Singh et al. (2020) [35] NPFP Y N Y
|
||
used the difference between the actual execution time and WCET Draskovic et al. (2021) [36] FP Y N N
|
||
Guo et al. (2021) [37] EDF Y N Y
|
||
to save energy. These works focus on the classic MCS task model.
|
||
Bhuiyan et al. (2020) [7] NPFP N Y Y
|
||
Zhang [28] focused on the IMC task model in which LO tasks allow This work EDF Y Y N
|
||
Qos in HI mode and proposed an energy-aware scheduling algorithm
|
||
(EA-IMC).
|
||
There has been a small number of recent works on energy-aware
|
||
MCS on multiprocessors. Narayana et al. [29] considered the energy probability that its WCET is equal to 𝑒𝑡.1 Given the PMF 𝑓𝑖 (⋅), we
|
||
minimization problem for multiprocessor MCS based on DVFS. They can easily obtain the corresponding Cumulative Distribution Function
|
||
∑
|
||
first proposed an optimal solution and an effective lightweight heuristic (CDF) 𝐹𝑖 (⋅), where 𝐹𝑖 (𝑒𝑡) = 𝑃 (𝑖 ≤ 𝑒𝑡) = 𝑥≤𝑒𝑡 𝑓𝑖 (𝑥). The Complemen-
|
||
on a uniprocessor, then extended these results to multicore systems. tary Cumulative Distribution Function (1-CDF) is defined as 𝐹̄𝑖 (𝑒𝑡) =
|
||
Ranjbar et al. [30] proposed a heuristic algorithm for online peak 𝑃 (𝑖 > 𝑒𝑡) = 1 − 𝐹𝑖 (𝑒𝑡).
|
||
power and thermal management of a multicore MCS by using the slack We consider the MCS taskset 𝛤 including 𝑛 independent periodic
|
||
time and per-cluster DVFS. Recently, some researchers [31] studied the tasks 𝛤 = {𝜏𝑖 |1 ≤ 𝑖 ≤ 𝑛} scheduled with preemptive EDF on
|
||
IMC task model on multiprocessors in which LO tasks allow QoS in HI a single processor platform. (It is a special case of EDF-VD with a
|
||
mode and proposed the partitioned scheduling algorithm. In addition, deadline scaling factor 𝑥 = 1.) We assume a dual-criticality system with
|
||
this work is extended to shared resource scheduling [32]. However, the criticality levels LO and HI for the sake of simplicity. The taskset 𝛤
|
||
above studies assume that tasks execute with their deterministic WCET. consists of two subsets: LO tasks 𝛤𝐿𝑂 = {𝜏𝑖 ∈ 𝛤 |𝐿𝑖 = 𝐿𝑂} and HI tasks
|
||
𝛤𝐻 𝐼 = {𝜏𝑖 ∈ 𝛤 |𝐿𝑖 = 𝐻 𝐼}. Each task 𝜏𝑖 ∈ 𝛤 is described by a tuple of
|
||
2.5. Probabilistic scheduling for MCS parameters ⟨𝐿𝑖 , 𝑇𝑖 , 𝐷𝑖 , 𝑖 , 𝑖𝐿𝑂 , 𝑖𝐻 𝐼 , 𝐶𝑖𝑑 𝑒𝑔 ∨ 𝐶𝑖𝑡ℎ𝑟 ⟩:
|
||
|
||
• 𝐿𝑖 ∈ {𝐿𝑂, 𝐻 𝐼} denotes its criticality level.
|
||
Santinelli and George [33] presented an initial solution to proba-
|
||
bilistic schedulability analysis for EDF scheduling of MCS based on the • 𝑇𝑖 denotes its period.
|
||
concept of probabilistic C-Space. Maxim et al. [34] presented a prob- • 𝐷𝑖 denotes its constrained deadline (𝐷𝑖 ≤ 𝑇𝑖 ).
|
||
abilistic fixed-priority schedulability analysis [14]. Singh et al. [35] • 𝑖 is its nominal pWCET, a discrete random variable with 𝐾
|
||
considered a novel MCS task model with job-level mode switching, discrete values characterized by PMF 𝑓𝑖 (⋅) and CDF 𝐹𝑖 (⋅). It has
|
||
and presented a graph-traversal-based analytic framework for non- the minimum value 𝐶𝑖𝑚𝑖𝑛 with index 𝑖𝑛𝑑(𝐶𝑖𝑚𝑖𝑛 ) = 0 and maximum
|
||
preemptive job-level fixed-priority probabilistic schedulability analysis. value 𝐶𝑖𝑚𝑎𝑥 with index 𝑖𝑛𝑑(𝐶𝑖𝑚𝑎𝑥 ) = 𝐾 − 1 among the 𝐾 discrete
|
||
Draskovic et al. [36] proposed metrics that are inspired by industry values of 𝑖 .
|
||
safety standards, including the probability of deadline miss per hour, • 𝑖𝐿𝑂 is its pWCET in LO mode, characterized by PMF 𝑓 𝐿𝑂 (⋅) and
|
||
𝑖
|
||
the expected time before degradation happens, and the duration of the CDF 𝐹 𝐿𝑂 (⋅).
|
||
𝑖
|
||
degradation, and presented a system-wide approach to probabilistic • 𝑖𝐻 𝐼 is its pWCET in HI mode, characterized by PMF 𝑓 𝐻 𝐼 (⋅) and
|
||
𝑖
|
||
scheduling of MCS. Guo et al. [37] proposed a new task model in CDF 𝐹 𝐻 𝐼 (⋅).
|
||
𝑖
|
||
which a new parameter is added to characterize the distribution of the
|
||
• 𝐶𝑖𝑑 𝑒𝑔 is valid for LO tasks (𝐿𝑖 = 𝐿𝑂), and denotes its Degraded
|
||
WCET estimations for each task. They presented efficient algorithms for
|
||
WCET in HI mode 𝐶𝑖𝑑 𝑒𝑔 with index 𝑖𝑛𝑑(𝐶𝑖𝑑 𝑒𝑔 ) ∈ [0, 𝐾 − 1].
|
||
MCS scheduling under this task model for both independent tasks and
|
||
failure-dependent tasks. • 𝐶𝑖𝑡ℎ𝑟 is valid for HI tasks (𝐿𝑖 = 𝐻 𝐼), and denotes its Threshold
|
||
We are aware of only one related work that addressed energy- WCET in LO mode 𝐶𝑖𝑡ℎ𝑟 with index 𝑖𝑛𝑑(𝐶𝑖𝑡ℎ𝑟 ) ∈ [0, 𝐾 − 1].
|
||
aware scheduling in MCS assuming probabilistic task execution times. Task execution model. The system is first initialized to be in LO
|
||
Bhuiyan et al. [7] proposed a probabilistic technique to derive an mode. If any HI task 𝜏𝑖 ∈ 𝛤𝐻 𝐼 executes beyond its 𝐶𝑖𝑡ℎ𝑟 , the system
|
||
energy-efficient processor speed that minimized the average energy switches from LO mode to HI mode. At the mode switch instant 𝑡𝑠 , if
|
||
consumption with DVFS, while ensuring deadlines of all tasks in MCS. jobs of LO tasks have run for longer than their 𝐶𝑖𝑑 𝑒𝑔 , any such jobs will
|
||
This work used non-preemptive fixed-priority scheduling and determin- be dropped, without suppressing future arrivals thereof. In addition, if a
|
||
istic schedulability test based on Worst-Case Response Time analysis, LO job has executed for less than 𝐶𝑖𝑑 𝑒𝑔 by the switch time instant, these
|
||
instead of probabilistic schedulability analysis. It is not directly com- carry-over jobs that have an arrival time before 𝑡𝑠 and have absolute
|
||
parable to our work due to the different task models and analysis deadlines after 𝑡𝑠 will continue to execute the leftover execution up to
|
||
techniques. 𝐶𝑖𝑑 𝑒𝑔 . While in HI mode, each LO task 𝜏𝑖 ∈ 𝛤𝐿𝑂 executes no more than
|
||
Table 1 summarized related work on probabilistic Scheduling for its 𝐶𝑖𝑑 𝑒𝑔 , i.e., it is dropped if its execution time exceeds 𝐶𝑖𝑑 𝑒𝑔 . The system
|
||
MCS. switches from HI mode to LO mode at an idle instant if no jobs wait
|
||
for executions at this time. Moreover, incomplete tasks are dropped at
|
||
3. Preliminaries their deadlines, hence there does not exist a backlog of outstanding
|
||
execution at the end of each hyper-period (this is a common assumption
|
||
3.1. Task model in industry practice [10].
|
||
The pWCET of a LO task in LO mode, or the pWCET of a HI task
|
||
Our task model is inspired by the IMC task model [17], with in HI mode, is the same as its nominal pWCET 𝑖 . The pWCET of a HI
|
||
extensions to the probabilistic scheduling scenario. We first introduce
|
||
some basic notations for probabilistic scheduling. A task 𝜏𝑖 ’s probabilistic
|
||
WCET (pWCET) 𝑖 is a random variable characterized by a Probability 1
|
||
Calligraphic letters are used to represent distributions while non
|
||
Mass Function (PMF) 𝑓𝑖 (⋅), where 𝑓𝑖 (𝑒𝑡) = 𝑃 (𝑖 = 𝑒𝑡) denotes the calligraphic letters are for scalars.
|
||
|
||
|
||
3
|
||
Y.-W. Zhang and J.-L. Zhang Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
|
||
task 𝜏𝑖 in LO mode is trimmed with the upper bound 𝐶𝑖𝑡ℎ𝑟 to have the Table 2
|
||
Taskset parameters of 𝛤1 , with 𝐶1𝑑 𝑒𝑔 = 1, 𝐶2𝑡ℎ𝑟 = 1.
|
||
conditional PMF 𝑓 𝐿𝑂 (𝑒𝑡) = 𝑃 (𝑖 = 𝑒𝑡 ∣ 𝑒𝑡 ≤ 𝐶𝑖𝑡ℎ𝑟 ). The pWCET of a LO
|
||
𝑖
|
||
Task 𝐿𝑖 𝑇𝑖 = 𝐷𝑖 𝑖 𝑖𝐿𝑂 𝑖𝐻 𝐼 𝑖𝐿𝑂 𝑖𝐻 𝐼
|
||
task 𝜏𝑖 in HI mode is trimmed with the upper bound 𝐶𝑖𝑑 𝑒𝑔 to have the
|
||
conditional PMF 𝑓 𝐻 𝐼 (𝑒𝑡) = 𝑃 (𝑖 = 𝑒𝑡 ∣ 𝑒𝑡 ≤ 𝐶𝑖𝑑 𝑒𝑔 ). In other words, 𝐶𝑖𝑑 𝑒𝑔 ⎛1 2⎞ ⎛1 2⎞ ⎛1⎞ ⎛0.5 1.0⎞ ⎛0.5⎞
|
||
𝑖 𝜏1 LO 2 ⎜0.5 0.5⎟ ⎜0.5 0.5⎟ ⎜1.0⎟ ⎜0.5 0.5⎟ ⎜1.0⎟
|
||
is LO task 𝜏𝑖 ’s execution time budget in HI mode, and 𝐶𝑖𝑡ℎ𝑟 is HI task ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
|
||
⎝0.5 1.0⎠ ⎝0.5 1.0⎠ ⎝1.0⎠ ⎝0.5 1.0⎠ ⎝1.0⎠
|
||
𝜏𝑖 ’s execution time budget in LO mode. This is inspired by the IMC task ⎛1 2⎞ ⎛1⎞ ⎛1 2⎞ ⎛0.5⎞ ⎛0.5 1.0⎞
|
||
𝜏2 HI 2 ⎜0.5 0.5⎟ ⎜1.0⎟ ⎜0.5 0.5⎟ ⎜1.0⎟ ⎜0.5 0.5⎟
|
||
model [17,19,20]. They are computed with Eqs. (1) and (2): ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
|
||
⎝0.5 1.0⎠ ⎝1.0⎠ ⎝0.5 1.0⎠ ⎝1.0⎠ ⎝0.5 1.0⎠
|
||
∀𝜏𝑖 ∈ 𝛤𝐿𝑂 ∶ 𝑓 𝐿𝑂 (𝑒𝑡) = 𝑓𝑖 (𝑒𝑡), (1)
|
||
𝑖
|
||
|
||
⎧∑ 𝑑 𝑒𝑔
|
||
⎪ 𝑒𝑡′ ≥𝐶 𝑑 𝑒𝑔 𝑓 𝐿𝑂 (𝑒𝑡′ ), 𝑒𝑡 = 𝐶𝑖
|
||
⎪ 𝑖 𝑖 • [[𝐴]]0 stands for max(𝐴, 0).
|
||
𝑓 𝐻 𝐼 (𝑒𝑡) = ⎨𝑓 𝐿𝑂 (𝑒𝑡), 𝑒𝑡 < 𝐶𝑖𝑑 𝑒𝑔 • 𝑡𝑠 stands for the mode-switch time.
|
||
𝑖
|
||
⎪ 𝑖 𝑡−𝐷 𝑡
|
||
⎪0, 𝑒𝑡 > 𝐶𝑖𝑑 𝑒𝑔 • 𝑚𝑖 = ⌊ 𝑇 𝑖 ⌋ and 𝑘𝑖 = ⌊ 𝑇𝑠 ⌋ are the number of jobs for 𝜏𝑖 in the
|
||
⎩ 𝑖 𝑖
|
||
interval [0, 𝑡) and [0, 𝑡𝑠 ), respectively.
|
||
• 𝐷𝐵 𝐹𝐿 (𝜏𝑖 , 𝑡) stands for the processor demand of any task 𝜏𝑖 ∈ 𝛤
|
||
∀𝜏𝑖 ∈ 𝛤𝐻 𝐼 ∶ 𝑓 𝐻 𝐼 (𝑒𝑡) = 𝑓𝑖 (𝑒𝑡) (2) within [0, 𝑡) in LO mode.
|
||
𝑖
|
||
∑ • 𝐷𝐵 𝐹 (𝐽𝐿 , 𝑡) and 𝐷𝐵 𝐹 (𝐽𝐻 , 𝑡) stand for the processor demand of a
|
||
⎧ 𝑒𝑡′ ≥𝐶 𝑡ℎ𝑟 𝑓 𝐻 𝐼 (𝑒𝑡′ ), 𝑒𝑡 = 𝐶𝑖𝑡ℎ𝑟
|
||
⎪ 𝑖 𝑖
|
||
carry-over job released by task 𝜏𝑖 ∈ 𝛤𝐿𝑂 and 𝜏𝑖 ∈ 𝛤𝐻 𝐼 within [0, 𝑡),
|
||
𝑓 𝐿𝑂 (𝑒𝑡) = ⎨𝑓 𝐻 𝐼 (𝑒𝑡), 𝑒𝑡 < 𝐶𝑖𝑡ℎ𝑟
|
||
𝑖
|
||
⎪ 𝑖 respectively.
|
||
⎩0, 𝑒𝑡 > 𝐶𝑖𝑡ℎ𝑟 • 𝑟𝑖 stands for the arrival time of the carry-over job that arrives
|
||
before 𝑡𝑠 and has a deadline after 𝑡𝑠 .
|
||
Since task 𝜏𝑖 ’s period 𝑇𝑖 is a constant in both LO and HI modes, its • 𝐷𝐵 𝐹𝐿𝐻 (𝜏𝑖 , 𝑡) stands for the processor demand of a LO task 𝜏𝑖 within
|
||
probabilistic Worst-Case Utilization (pWCU) can be obtained by dividing 𝐻 (𝜏 , 𝑡) stands for the processor
|
||
[0, 𝑡) in HI mode, while 𝐷𝐵 𝐹𝐻 𝑖
|
||
its pWCET by its period: 𝑖 = 𝑖 ∕𝑇𝑖 , 𝑖𝐿𝑂 = 𝑖𝐿𝑂 ∕𝑇𝑖 in LO mode, and
|
||
demand of a HI task 𝜏𝑖 within [0, 𝑡) in HI mode.
|
||
𝑖𝐻 𝐼 = 𝑖𝐻 𝐼 ∕𝑇𝑖 in HI mode. The pWCU of a taskset can be obtained by
|
||
summing the pWCUs of all tasks in the taskset. Fig. 1 illustrates a carry-over job and the mode switch. The down-
|
||
ward arrow represents the job arrival time. If the execution time of 𝜏𝑖
|
||
Example 1. A taskset 𝛤1 with two tasks is shown in Table 2. Each task exceeds 𝐶𝑖𝐿𝑂 without signaling completion, the system switches from
|
||
𝜏𝑖 ’s nominal pWCET 𝑖 is shown in matrix form defined in Eq. (3). For LO mode to HI mode. 𝐽𝐻 is a carry-over job.
|
||
the matrix form, the first row denotes each discrete value of 𝑖 ; the
|
||
According to the Task Execution model, the processor demand
|
||
second row denotes probability values of the PMF 𝑓𝑖 (⋅); and the third
|
||
of LO carry-over jobs is always less than or equal to 𝐶𝑖𝐿𝑂 , while the
|
||
row denotes cumulative probability values of the CDF 𝐹𝑖 (⋅).
|
||
processor demand of HI carry-over jobs is always less than or equal to
|
||
⎛ 𝐶0 𝐶1 … 𝐶𝐾−1 ⎞
|
||
𝐶𝑖𝐻 𝐼 . Therefore, 𝐷𝐵 𝐹 (𝐽𝐿 , 𝑡) can be calculated as follows:
|
||
⎜ 𝑓 (𝐶0 ) 𝑓 (𝐶1 ) … 𝑓 (𝐶𝐾−1 ) ⎟ (3) {
|
||
⎜ 𝑖 𝑖 𝑖 ⎟ 𝐶𝑖𝐿𝑂 , 𝑟𝑖 + 𝐷𝑖 ≤ 𝑡
|
||
⎝𝐹𝑖 (𝐶0 ) 𝐹𝑖 (𝐶1 ) … 𝐹𝑖 (𝐶𝐾−1 )⎠ 𝐷𝐵 𝐹 (𝐽𝐿 , 𝑡) = (5)
|
||
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒.
|
||
The PMF of 𝜏𝑖 ’s pWCET in LO mode 𝑖𝐿𝑂 is obtained by Eq. (2); the
|
||
PMF of its pWCET in HI mode 𝑖𝐻 𝐼 is obtained by Eq. (1). For the toy and 𝐷𝐵 𝐹 (𝐽𝐻 , 𝑡) can be calculated as follows:
|
||
{
|
||
example, the LO task 𝜏1 ’s nominal pWCET 1 has two possible values 𝐶𝑖𝐻 𝐼 , 𝑟𝑖 + 𝐷𝑖 ≤ 𝑡
|
||
1 and 2, each with probability 0.5; its pWCET in LO mode 1𝐿𝑂 is the 𝐷𝐵 𝐹 (𝐽𝐻 , 𝑡) = (6)
|
||
0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒.
|
||
same as 1 ; its pWCET in HI mode 1𝐻 𝐼 is obtained by trimming 1 with
|
||
the upper bound 𝐶1𝑑 𝑒𝑔 = 1 and 𝑖𝑛𝑑(𝐶1𝑑 𝑒𝑔 ) = 0 (assuming the index starts
|
||
from 0), with one possible value of 1 with a probability 1.0. The HI From [3,17], we have the following Theorems.
|
||
task 𝜏2 ’s nominal pWCET 2 has two possible values 1 and 2, each with
|
||
probability 0.5; its pWCET in LO mode 2𝐿𝑂 is obtained by trimming Theorem 1. A deterministic IMC taskset 𝛤 is schedulable under EDF in
|
||
2 with the upper bound 𝐶2𝑡ℎ𝑟 = 1 and 𝑖𝑛𝑑(𝐶2𝑡ℎ𝑟 ) = 0, with one possible LO mode, if 0 < ∀𝑡 ≤ 𝑡𝑚𝑎𝑥 ,
|
||
value of 1 with a probability 1.0; its pWCET in HI mode 2𝐻 𝐼 is the ∑
|
||
𝐷𝐵 𝐹𝐿 (𝜏𝑖 , 𝑡) ≤ 𝑡, (7)
|
||
same as 2 . The matrix that denotes 𝜏𝑖 ’s pWCU is obtained by dividing 𝜏𝑖 ∈𝛤
|
||
each term in the first row of its pWCET matrix by its period 𝑇𝑖 .
|
||
where 𝐷𝐵 𝐹𝐿 (𝜏𝑖 , 𝑡) = [[𝑚𝑖 + 1]]0 ⋅ 𝐶𝑖𝐿𝑂 , and 𝑡𝑚𝑎𝑥 is a hyper-period.
|
||
Eq. (4) shows the definitions of pWCU for the subset of LO tasks
|
||
𝛤𝐿𝑂 in LO mode. (As mathematical background, the addition of two
|
||
discrete random variables and results in a new random variable
|
||
Theorem 2. A deterministic IMC taskset 𝛤 is schedulable under EDF in
|
||
with PMF computed by the convolution of the two PMFs and ,
|
||
⨂ ∑ HI mode, if 0 < ∀𝑡 ≤ 𝑡𝑚𝑎𝑥 , 0 < 𝑡𝑠 < 𝑡,
|
||
i.e., = , where 𝑃 ( = 𝑧) = ∞ 𝑘=−∞ 𝑃 ( = 𝑘)𝑃 ( = 𝑧 − 𝑘). ∑ ∑
|
||
⨂ ⨂ 𝐷𝐵 𝐹𝐿𝐻 (𝜏𝑖 , 𝑡𝑠 , 𝑡) + 𝐷 𝐵 𝐹𝐻 𝐻
|
||
(𝜏𝑗 , 𝑡𝑠 , 𝑡) ≤ 𝑡, (8)
|
||
𝐿𝑂 𝐿𝑂 𝐻𝐼
|
||
𝐿𝑂 (𝛤 ) = 𝑖 , 𝐻 𝐼 (𝛤 ) = 𝑖𝐻 𝐼 , (4) 𝜏𝑖 ∈𝛤𝐿𝑂 𝜏𝑗 ∈𝛤𝐻 𝐼
|
||
𝜏𝑖 ∈𝛤𝐿𝑂 𝜏𝑖 ∈𝛤𝐻 𝐼
|
||
|
||
𝐿𝑂 (𝛤 ) denotes pWCU of 𝛤
|
||
where 𝐿𝑂 𝐻𝐼 where 𝐷𝐵 𝐹𝐿𝐻 (𝜏𝑖 , 𝑡𝑠 , 𝑡) = 𝑘𝑖 𝐶𝑖𝐿𝑂 + 𝐷𝐵 𝐹 (𝐽𝐿 , 𝑡) + 𝑐𝑖 𝐶𝑖𝐻 𝐼 , and 𝐷𝐵 𝐹𝐻
|
||
𝐻 (𝜏 , 𝑡 , 𝑡)
|
||
𝑖 𝑠
|
||
𝐿𝑂 in LO mode; 𝐻 𝐼 (𝛤 ) denotes
|
||
can be determined as follows:
|
||
pWCU of 𝛤𝐻 𝐼 in HI mode. {
|
||
𝐻 𝐷𝐵 𝐹 (1), 𝐷𝑖 ≤ 𝑡 − 𝑡𝑠 ;
|
||
𝐷 𝐵 𝐹𝐻 (𝜏𝑖 , 𝑡𝑠 , 𝑡) = (9)
|
||
3.2. Existing deterministic IMC scheduling max{𝐷𝐵 𝐹 (1), 𝐷𝐵 𝐹 (2)}, 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒,
|
||
|
||
Liu et al. [17] have studied the schedulability test for deterministic where 𝐷𝐵 𝐹 (1) = 𝑏𝑖 𝐶𝑖𝐿𝑂 + 𝐷𝐵 𝐹 (𝐽𝐻 , 𝑡) + 𝑎𝑖 𝐶𝑖𝐻 𝐼 , 𝐷𝐵 𝐹 (2) = 𝑘𝑖 𝐶𝑖𝐿𝑂 +
|
||
𝑡 −(𝑡−𝐷𝑖 −𝑚𝑖 𝑇𝑖 )
|
||
IMC task model and proposed the sufficient conditions of the schedu- 𝐷𝐵 𝐹 (𝐽𝐻 , 𝑡), 𝑎𝑖 = [[𝑚𝑖 − 𝑏𝑖 ]]0 , 𝑏𝑖 = [[⌊ 𝑠 𝑇
|
||
⌋]]0 , and 𝑐𝑖 = [[𝑚𝑖 − 𝑘𝑖 ]]0 .
|
||
𝑖
|
||
lability under EDF-VD. We first introduce the following notations.
|
||
|
||
|
||
4
|
||
Y.-W. Zhang and J.-L. Zhang Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
|
||
|
||
|
||
Fig. 1. Carry-over job.
|
||
|
||
|
||
4. Probabilistic IMC scheduling
|
||
According to [3,17], we should consider two cases to determine the
|
||
4.1. Schedulability analysis probabilistic processor demand of any task 𝜏𝑖 ∈ 𝛤𝐻 𝐼 within [0, 𝑡) in HI
|
||
mode.
|
||
Before presenting the schedulability analysis, let us introduce a few Case 1: 𝐷𝑖 ≤ 𝑡 − 𝑡𝑠 . The maximum demand of a job released by the
|
||
notations. HI task 𝜏𝑖 is generated while its deadline coincides with 𝑡. According
|
||
to Eq. (9) in Theorem 2, the probabilistic processor demand of any
|
||
• max{} stands for the maximum value of random variable .
|
||
task 𝜏𝑖 ∈ 𝛤𝐻 𝐼 within [0, 𝑡) in HI mode is equal to (1) = ((𝑏𝑖 ) ⊙
|
||
⎛𝑥⎞ ⨂ ⨂
|
||
𝑖𝐿𝑂 ) (𝐽𝐻 , 𝑡) ((𝑎𝑖 ) ⊙ 𝑖𝐻 𝐼 ).
|
||
• (𝑥) = ⎜1⎟, where 𝑥 is a constant.
|
||
⎜ ⎟ Case 2: 𝐷𝑖 > 𝑡 − 𝑡𝑠 . The HI task 𝜏𝑖 has at most one job with a
|
||
⎝1⎠
|
||
processor demand 𝐶𝑖𝐻 𝐼 . If the deadline of this job is 𝐷𝑖 , the probabilistic
|
||
• 𝐿 (𝜏𝑖 , 𝑡) stands for the probabilistic processor demand of any
|
||
processor demand is the same as (1). Moreover, the only way to
|
||
task 𝜏𝑖 within [0, 𝑡) in LO mode.
|
||
increase the demand of the HI task 𝜏𝑖 is to add a new job in the interval.
|
||
• (𝐽𝐿 , 𝑡) and (𝐽𝐻 , 𝑡) stand for the probabilistic processor
|
||
In other words, the first job of the HI task 𝜏𝑖 arrives at time 0. Therefore,
|
||
demand of a carry-over job released by the task 𝜏𝑖 ∈ 𝛤𝐿𝑂 and
|
||
the processor demand includes two parts: one part is the demand of
|
||
𝜏𝑖 ∈ 𝛤𝐿𝑂 within [0, 𝑡), respectively.
|
||
all jobs before 𝑡𝑠 , and the other part is the demand of a carry-over
|
||
• 𝐻 𝐿 (𝜏𝑖 , 𝑡) stands for the probabilistic processor demand of a LO job 𝐽𝐻 . In this case, the probabilistic processor demand is equal to
|
||
task 𝜏𝑖 within [0, 𝑡) in HI mode, while 𝐻 ⨂
|
||
𝐻 (𝜏𝑖 , 𝑡) stands for the (2) = ((𝑘𝑖 ) ⊙ 𝑖𝐿𝑂 ) (𝐽𝐻 , 𝑡).
|
||
probabilistic processor demand of a HI task 𝜏𝑖 within [0, 𝑡) in HI In short, the probabilistic processor demand of any task 𝜏𝑖 ∈ 𝛤𝐻 𝐼
|
||
mode. within [0, 𝑡) and 𝐷𝑖 ≤ 𝑡 − 𝑡𝑠 in HI mode can be determined as follows:
|
||
• 𝐿 (𝑡) stands for the probabilistic processor demand of all tasks {
|
||
within [0, 𝑡) in LO mode. (1), 𝐷𝑖 ≤ 𝑡 − 𝑡𝑠 ;
|
||
𝐻 (𝜏
|
||
𝐻 𝑖 , 𝑡) = (15)
|
||
• 𝐻 (𝑡) stands for the probabilistic processor demand of all tasks , 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒,
|
||
within [0, 𝑡) in HI mode. where can be determined as follows:
|
||
𝑡𝑚𝑎𝑥
|
||
• 𝛱𝑡=1 𝑡 = 1 × 2 × ⋯ × 𝑡𝑚𝑎𝑥 . {
|
||
(1), max{ (2)} ≤ max{ (1)};
|
||
= (16)
|
||
According to [3,17,33], the probabilistic processor demand of any (2), 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒.
|
||
task 𝜏𝑖 ∈ 𝛤 within [0, 𝑡) in LO mode can be calculated as follows:
|
||
𝐿 (𝜏𝑖 , 𝑡) = ([[𝑚𝑖 + 1]]0 ) ⊙ 𝑖𝐿𝑂 , (10) Therefore, the probabilistic processor demand of all tasks within
|
||
[0, 𝑡) in HI mode is determined by the following:
|
||
where ⊙ denotes the Hadamard product, where each element in the 𝑖th ⨂ ⨂ ⨂
|
||
𝐻 (𝑡) = ( 𝐻𝐿 (𝜏𝑖 , 𝑡)) ( 𝐻
|
||
𝐻 (𝜏𝑖 , 𝑡)). (17)
|
||
row of the right matrix is multiplied by the element on the 𝑖th row of
|
||
𝜏𝑖 ∈𝛤𝐿𝑂 𝜏𝑖 ∈𝛤𝐻 𝐼
|
||
the left vector.
|
||
In addition, the probabilistic processor demand of all tasks within
|
||
[0, 𝑡) in LO mode can be calculated as follows: Theorem 3. An IMC taskset 𝛤 is deterministically schedulable under EDF,
|
||
⨂
|
||
𝐿 (𝑡) = 𝐿 (𝜏𝑖 , 𝑡). (11) if 0 < ∀𝑡 ≤ 𝑡𝑚𝑎𝑥 , 0 < 𝑡𝑠 < 𝑡,
|
||
𝜏𝑖 ∈𝛤
|
||
max{ 𝐿 (𝑡)} ≤ 𝑡, 𝑎𝑛𝑑 max{ 𝐻 (𝑡)} ≤ 𝑡, (18)
|
||
The probabilistic processor demand of a carry-over job released by It is probabilistically schedulable if the maximum probability that the pro-
|
||
LO task 𝜏𝑖 within [0, 𝑡) can be calculated as follows: cessor demand of all tasks in both LO mode and HI mode exceeds 𝑡 does
|
||
{
|
||
𝑖𝐿𝑂 , 𝑟𝑖 + 𝐷𝑖 ≤ 𝑡 not exceed the permitted system failure probability 𝐹𝑠 ,2 expressed as:
|
||
(𝐽𝐿 , 𝑡) = (12) 𝑡
|
||
(0), 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒. 1 − 𝛱𝑡 𝑚𝑎𝑥
|
||
𝑘=𝑡 𝐹 𝐿 (𝑡𝑘 ) (𝑡𝑘 ) ≤ 𝐹𝑠 , 𝑎𝑛𝑑 (19)
|
||
𝑡
|
||
1 − 𝛱𝑡 𝑚𝑎𝑥 𝐹 (𝑡 ) ≤ 𝐹𝑠 .
|
||
The probabilistic processor demand of a carry-over job released by 𝑘 =𝑡 𝐻 (𝑡𝑘 ) 𝑘
|
||
HI task 𝜏𝑖 within [0, 𝑡) can be calculated as follows:
|
||
{
|
||
𝑖𝐻 𝐼 , 𝑟𝑖 + 𝐷𝑖 ≤ 𝑡
|
||
(𝐽𝐻 , 𝑡) = (13)
|
||
(0), 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒. 2
|
||
Chen et al. [38] pointed out that there are certain flaws in the probabilis-
|
||
tic WCRT based on critical instant instances. However, our work focuses on the
|
||
The probabilistic processor demand of any task 𝜏𝑖 ∈ 𝛤𝐿𝑂 within [0, 𝑡)
|
||
overall distribution of all task behaviors within a task’s hyper-period, rather
|
||
in HI mode can be calculated as follows: than relying solely on a single critical instant and considers the probability
|
||
⨂ ⨂
|
||
𝐻 𝐿𝑂
|
||
𝐿 (𝜏𝑖 , 𝑡) = ((𝑘𝑖 ) ⊙ 𝑖 ) (𝐽𝐿 , 𝑡) ((𝑐𝑖 ) ⊙ 𝑖𝐻 𝐼 ). (14) distribution of all possible processor demand throughout the hyper-period.
|
||
|
||
|
||
5
|
||
Y.-W. Zhang and J.-L. Zhang Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
Table 3 𝐿 (𝜏2 , 𝑡) = (0), and 𝐿 (𝜏3 , 𝑡) = 3𝐿𝑂 . In addition, we have
|
||
Taskset parameters of 𝛤2 , with 𝐶1𝑑 𝑒𝑔 = 3, 𝐶2𝑡ℎ𝑟 = 1, 𝐶3𝑑 𝑒𝑔 = 3. ⎛ 3 4 ⋯ 8 9 10 ⎞
|
||
Task 𝐿𝑖 𝑇𝑖 = 𝐷𝑖 𝑖𝐿𝑂 𝑖𝐻 𝐼 ⎜ ⎟
|
||
𝐿 (𝑡) = = ⎜0.008645 0.273 ⋯ 0.00266 0.000384 0.000001⎟
|
||
⎛ 1 3 4 5 ⎞ ⎛ 1 3 ⎞ ⎜0.008645 0.281645 ⋯ 0.999615 0.999999 1.0 ⎟⎠
|
||
⎜0.455 ⎝
|
||
𝜏1 LO 10 0.54 0.004 0.001⎟ ⎜0.455 0.545⎟
|
||
⎜ ⎟ ⎜ ⎟ from Eq. (11). Moreover, from (17), we have 𝐻 (𝑡) = .
|
||
⎝0.455 0.995 0.999 1.0 ⎠ ⎝0.455 1.0 ⎠
|
||
⎛ 0.5 1 ⎞ ⎛ 0.5 1 2 3 ⎞ When 10 < 𝑡 < 20, 𝑚1 = 0, 𝑚2 = −1, 𝑚3 = 0, 𝑎𝑖 = 0, 𝑐𝑖 = 0, and
|
||
𝜏2 HI 20 ⎜0.49 0.51⎟ ⎜0.49 0.5 0.009 0.001⎟
|
||
⎜ ⎟ ⎜ ⎟ 𝑏𝑖 = 0 (𝑖 = 1, 2, 3). According to Eq. (11), we have 𝐿 (𝑡) = . If
|
||
⎝0.49 1.0 ⎠ ⎝0.49 0.99 0.999 1.0 ⎠
|
||
𝑡𝑠 < 10, 𝑘𝑖 = 0 (𝑖 = 1, 2, 3). According to Eq. (17), we have 𝐻 (𝑡) =
|
||
⎛ 2 3 4 5 ⎞ ⎛ 2 3 ⎞
|
||
𝜏3 LO 10 ⎜0.019 0.6 0.38 0.001⎟ ⎜0.019 0.981⎟ and max{ 𝐻 (𝑡) ≤ 𝑡}. If 10 ≤ 𝑡𝑠 < 𝑡, we have 𝑘1 = 1, 𝑘2 = 0,
|
||
⎜ ⎟ ⎜ ⎟
|
||
⎝0.019 0.619 0.999 1.0 ⎠ ⎝0.019 1.0 ⎠ and 𝑘3 = 1. According to Eq. (14), we have 𝐻 𝐿𝑂 and
|
||
𝐿 (𝜏1 , 𝑡) = 1
|
||
𝐻 (𝜏
|
||
𝐿 3 , 𝑡) = 𝐿𝑂 . We calculate 𝐻 (𝜏 , 𝑡) = (0) from Eq. (15).
|
||
3 𝐻 2
|
||
In addition, we have 𝐻 (𝑡) = from Eq. (17). Therefore, we have
|
||
max{ 𝐻 (𝑡)} ≤ 𝑡 and max{ 𝐿 (𝑡)} ≤ 𝑡.
|
||
When 𝑡 = 20, 𝑚1 = 1, 𝑚2 = 0, 𝑚3 = 1. According to Eq. (10), we
|
||
have 𝐿 (𝜏1 , 𝑡) = (2) ⊙ 1𝐿𝑂 , 𝐿 (𝜏2 , 𝑡) = 2𝐿𝑂 , and 𝐿 (𝜏3 , 𝑡) =
|
||
Proof. The IMC taskset 𝛤 is deterministically schedulable under EDF if it
|
||
(2) ⊙ 3𝐿𝑂 . In addition, we have
|
||
is deterministically schedulable in both LO mode and HI mode. The condi-
|
||
tion for deterministic schedulability in LO mode and HI mode Eq. (18) ⎛ 6.5 ⋯ 19 20.5 21 ⎞
|
||
𝐿 (𝑡) = ⎜0.00423605 ⋯ 0.00019584 0.00000049 0.00000051⎟
|
||
is self-evident, because it can be directly derived from Theorems 1 and ⎜ ⎟
|
||
2. In addition, the IMC taskset 𝛤 is probabilistically schedulable under ⎝0.00406315 ⋯ 0.999999 0.99999949 1.0 ⎠
|
||
EDF if it is probabilistically schedulable in both LO mode and HI mode. from Eq. (11). If 𝑡𝑠 < 10, 𝑎1 = 1, 𝑎2 = 0, 𝑎3 = 1, 𝑐1 = 1, 𝑐2 = 0,
|
||
The condition for probabilistic schedulability (Eq. (19)) states that the 𝑐3 = 1, 𝑘𝑖 = 0, and 𝑏𝑖 = 0 (𝑖 = 1, 2, 3). From Eq. (17), we have
|
||
probability that the processor demand of all tasks in both LO mode and max{ 𝐻 (𝑡)} = 19. If 10 ≤ 𝑡𝑠 < 𝑡, 𝑘1 = 1, 𝑘2 = 0, 𝑘3 = 1, 𝑏1 = 1,
|
||
HI mode exceeds 𝑡 is less than or equal to 𝐹𝑠 , hence it is probabilistically 𝑏2 = 0, 𝑏3 = 1, 𝑎𝑖 = 0 and 𝑐𝑖 = 0 (𝑖 = 1, 2, 3). According to Eq. (17),
|
||
schedulable with system failure probability not exceeding 𝐹𝑠 . (Note that we have max{ 𝐻 (𝑡)} = 23. Therefore, we have max{ 𝐿 (𝑡)} > 𝑡
|
||
the condition of deterministic schedulability in Eq. (18) is a special and max{ 𝐻 (𝑡)} > 𝑡 (10 ≤ 𝑡𝑠 < 𝑡), but 1 − 𝐹 𝐿 (𝑡) (𝑡) ≤ 𝐹𝑠
|
||
case of the condition of probabilistic schedulability in Eq. (19), with and 1 − 𝐹 𝐻 (𝑡) (𝑡) ≤ 𝐹𝑠 . According to Theorem 3, the taskset 𝛤 is
|
||
permitted system failure probability equal to 0 (𝐹𝑠 = 0).) Q.E.D. probabilistically schedulable.
|
||
In the deterministic analysis, the processor demand grows in a
|
||
stepwise manner based on the interval length. The processor demand 5. Energy-efficient task execution model
|
||
is affected only when the increase in interval length is a multiple of the
|
||
task period. When we switch to probabilistic analysis, the probability We present in sequence the power model, the calculation of energy-
|
||
distribution of processor demand also increases in a stepwise manner to efficient processor speeds in LO mode, and the Energy-Efficient Task
|
||
maintain consistency. In other words, during deterministic analysis, the Execution Model in this section.
|
||
processor demand does not change in the given time intervals, and in
|
||
probabilistic scheduling analysis, the values in its probability distribu- 5.1. Power model
|
||
tion of processor demand also remain unchanged. Specifically, there are
|
||
some 𝑡𝑘 values that can generate the same probability distribution of We adopt the state-of-the-art processor power model [39–41]
|
||
processor demand. The values of 𝐹 𝐿 (𝑡𝑘 ) (𝑡𝑘 ) and 𝐹 𝐻 (𝑡𝑘 ) (𝑡𝑘 ), which
|
||
𝑃 = 𝑃𝑠 + ℎ(𝑃𝑖𝑛𝑑 + 𝐶𝑒𝑓 𝑠𝑚 ), (20)
|
||
correspond to the same probability distribution of processor demand,
|
||
should not be computed repeatedly in Eq. (19). Therefore, we only where 𝑃𝑠 is a static power and 𝑃𝑖𝑛𝑑 is the frequency-independent active
|
||
calculate once. In addition, If 𝑡1 , 𝑡2 and 𝑡𝑙 (𝑡1 < 𝑡2 < 𝑡𝑙 ) can generate power. ℎ = 1 if the system is active (defined as having computation in
|
||
the same probability distribution of the processor demand for all tasks progress); otherwise, ℎ = 0. 𝐶𝑒𝑓 is an effective switching capacitance
|
||
in both modes. We choose the minimum value 𝑡1 among these values, and 𝑚 is system-application-dependent constant. 𝑠 is the normalized
|
||
which corresponds to 𝐹 𝐿 (𝑡1 ) (𝑡1 ) and 𝐹 𝐻 (𝑡1 ) (𝑡1 ). This is because it processor speed (frequency). Like [39], we ignore a static power (𝑃𝑠 =
|
||
is the value that maximizes the probability of the processor demand 0) and set 𝑃𝑖𝑛𝑑 = 0.01, 𝐶𝑒𝑓 = 1, 𝑚 = 3.
|
||
exceeding the interval length. Considering our task model, the expected energy consumption of a
|
||
single job of task 𝜏𝑖 is [42–44]:
|
||
4.2. Example 2 𝑥
|
||
𝐸 𝑖 = (𝑃𝑖𝑛𝑑 + 𝐶𝑒𝑓 𝑠𝑚 ) ⋅ 𝑖 (21)
|
||
𝑠
|
||
We present a taskset 𝛤2 , with the parameters shown in Table 3. ∑
|
||
(The nominal pWCET 𝑖 is omitted for brevity.) We assume that 𝐹𝑠 = where 𝑥𝑖 = 𝐾−1 𝑘 𝑘
|
||
𝑘=0 𝐶𝑖 ⋅ 𝑓𝑖𝐿𝑂 (𝐶𝑖 ) with the normalized processor speed
|
||
1.0 × 10−6 . 𝑆𝑚𝑎𝑥 = 1. In addition, the processor speed 𝑠 should not be lower than
|
||
In this example, 𝑡𝑚𝑎𝑥 = 20. 0 < 𝑡 < 10, 0 < 𝑡𝑠 < 𝑡, we have 𝑆𝑐 𝑟𝑖𝑡 , where 𝑆𝑐 𝑟𝑖𝑡 (𝑆𝑐 𝑟𝑖𝑡√< 𝑆𝑚𝑎𝑥 ) is an energy-efficient speed while it can
|
||
𝑡−𝐷 𝑡 𝑃𝑖𝑛𝑑
|
||
𝑚𝑖 = −1 (𝑚𝑖 = ⌊ 𝑇 𝑖 ⌋), 𝑘𝑖 = 0 (𝑘𝑖 = ⌊ 𝑇𝑠 ⌋), 𝑎𝑖 = 0, 𝑐𝑖 = 0, and be computed 𝑆𝑐 𝑟𝑖𝑡 = 𝑚 [39].
|
||
𝑖 𝑖 (𝑚−1)⋅𝐶𝑒𝑓
|
||
𝑏𝑖 = 0 (𝑖 = 1, 2, 3). According to Eq. (10), 𝐿 (𝜏𝑖 , 𝑡) = (0). In To facilitate comparisons between task sets with varying hyper-
|
||
addition, we have 𝐿 (𝑡) = (0) from Eq. (11). From Eq. (12), we periods, we utilize the definition of normalized energy consumption of
|
||
have (𝐽𝐿 , 𝑡) = (0) for LO tasks 𝜏1 and 𝜏3 . Moreover, we have task set 𝛤 within its hyper-period [22] (i.e., its power consumption):
|
||
(𝐽𝐻 , 𝑡) = (0) for HI task 𝜏2 from Eq. (13). Therefore, we have ℎ𝑖
|
||
1 ∑𝑛 ∑
|
||
𝑥
|
||
𝐻 𝐻
|
||
𝐿 (𝜏1 , 𝑡) = (0) and 𝐿 (𝜏3 , 𝑡) = (0) from Eq. (14). Due to 𝑁 𝐸(𝛤 ) = (𝑃 + 𝐶𝑒𝑓 𝑠𝑚 ) ⋅ 𝑖 (22)
|
||
𝑘2 = 0, 𝑎2 = 0, 𝑏2 = 0 and 𝐷2 > 𝑡−𝑡𝑠 , we have (1) = (0), (2) = 𝐻 𝑃 (𝛤 ) 𝑖=1 𝑗=1 𝑖𝑛𝑑 𝑠
|
||
(0), and max{ (2)} ≤ max{ (1)}. According to Eq. (15), we ∑𝑛
|
||
𝑥𝑖
|
||
have 𝐻 𝐻 (𝜏2 , 𝑡) = (0). We calculate 𝐻 (𝑡) = (0) from Eq. (17).
|
||
= (𝑃𝑖𝑛𝑑 + 𝐶𝑒𝑓 𝑠𝑚 ) ⋅ ,
|
||
𝑖=1
|
||
𝑠 ⋅ 𝑇𝑖
|
||
Therefore, we have max{ 𝐿 (𝑡)} ≤ 𝑡 and max{ 𝐻 (𝑡) ≤ 𝑡}.
|
||
When 𝑡 = 10, 𝑚1 = 0, 𝑚2 = −1, 𝑚3 = 0, 𝑘𝑖 = 0, 𝑎𝑖 = 0, 𝑐𝑖 = 0, and where ℎ𝑖 = 𝐻 𝑃 (𝛤 )∕𝑇𝑖 is the number of jobs of task 𝜏𝑖 ∈ 𝛤 released in
|
||
𝑏𝑖 = 0 (𝑖 = 1, 2, 3). According to Eq. (10), we have 𝐿 (𝜏1 , 𝑡) = 1𝐿𝑂 , the hyper-period 𝐻 𝑃 (𝛤 ).
|
||
|
||
6
|
||
Y.-W. Zhang and J.-L. Zhang Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
|
||
5.2. Calculating energy-efficient processor speeds Table 4
|
||
Taskset parameters of 𝛤3 , with 𝐶1𝑑 𝑒𝑔 = 1.5, 𝐶2𝑡ℎ𝑟 = 2, 𝐶3𝑑 𝑒𝑔 = 2.
|
||
|
||
We determine the energy-efficient processor speed in LO mode 𝑆𝐿 Task 𝐿𝑖 𝑇𝑖 = 𝐷𝑖 𝑖𝐿𝑂 𝑖𝐻 𝐼
|
||
and schedule the tasks with 𝑆𝑚𝑎𝑥 = 1 in HI mode if an IMC taskset 𝛤 is ⎛1 1.5 2 2.5 ⎞ ⎛1 1.5⎞
|
||
𝜏1 LO 10 ⎜0.1 0.4 0.35 0.15⎟ ⎜0.1 0.9⎟
|
||
deterministically schedulable by EDF on a single processor. ⎜ ⎟ ⎜ ⎟
|
||
⎝0.1 0.5 0.85 1.0 ⎠ ⎝0.1 1.0⎠
|
||
A taskset 𝛤 running on a processor with speed 𝑆𝐿 is equivalent
|
||
⎛ 1 2 ⎞ ⎛ 1 2 4 5 ⎞
|
||
to the taskset 𝛤 ∗ running on a processor with speed 𝑆max = 1 with 𝜏2 HI 20 ⎜0.01 0.99⎟ ⎜0.01 0.49 0.45 0.05⎟
|
||
⎜ ⎟ ⎜ ⎟
|
||
proportionally-scaled execution times 1∕𝑆𝐿 times of each task in 𝛤 . ⎝0.01 1.0 ⎠ ⎝0.01 0.5 0.95 1.0 ⎠
|
||
Therefore, the probabilistic processor demand of any task 𝜏𝑖 ∈ 𝛤 with ⎛1.5 2 2.5 3⎞ ⎛1.5 2⎞
|
||
𝜏3 LO 10 ⎜0.2 0.3 0.4 0.1⎟ ⎜0.2 0.8⎟
|
||
speed 𝑆𝐿 within [0, 𝑡) in LO mode can be calculated as follows: ⎜ ⎟ ⎜ ⎟
|
||
⎝0.2 0.5 0.9 1.0⎠ ⎝0.2 1.0⎠
|
||
𝐿 (𝜏𝑖 , 𝑡) = ([[𝑚𝑖 + 1]]0 ) ⊙ ((1∕𝑆𝐿 ) ⊙ 𝑖𝐿𝑂 ), (23)
|
||
|
||
The probabilistic processor demand of a carry-over job released by
|
||
LO task 𝜏𝑖 with speed 𝑆𝐿 within [0, 𝑡) can be calculated as follows: the energy-efficient task execution model based on DVFS as shown below.
|
||
{
|
||
(1∕𝑆𝐿 ) ⊙ 𝑖𝐿𝑂 , 𝑟𝑖 + 𝐷𝑖 ≤ 𝑡 Energy-efficient task execution model in probabilistic IMC. The
|
||
(𝐽𝐿 , 𝑡) = (24) system is first initialized to be in LO mode with processor speed 𝑆𝐿 . If
|
||
(0), 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒.
|
||
any HI task 𝜏𝑖 ∈ 𝛤𝐻 𝐼 executes beyond its 𝐶𝑖𝑡ℎ𝑟 ∕𝑆𝐿 , the system switches
|
||
The probabilistic processor demand of any task 𝜏𝑖 ∈ 𝛤𝐿𝑂 with speed into HI mode, with processor speed 𝑆𝑚𝑎𝑥 = 1. As the mode-switch
|
||
𝑆𝐿 within [0, 𝑡) in HI mode can be calculated as follows: instant, if jobs of LO tasks have run for longer than their 𝐶𝑖𝑑 𝑒𝑔 ∕𝑆𝐿 , the
|
||
⨂
|
||
𝐻 𝐿𝑂
|
||
𝐿 (𝜏𝑖 , 𝑡) =((𝑘𝑖 ) ⊙ ((1∕𝑆𝐿 ) ⊙ 𝑖 )) (25) jobs will be stopped until new released. In addition, if the execution
|
||
⨂ time of LO jobs is less than 𝐶𝑖𝑑 𝑒𝑔 ∕𝑆𝐿 by the switch time instant, these
|
||
𝐻𝐼
|
||
(𝐽𝐿 , 𝑡) ((𝑐𝑖 ) ⊙ 𝑖 ).
|
||
carry-over jobs will continue to execute the leftover execution up to
|
||
In addition, the system schedules tasks with 𝑆𝐿 in LO mode and 𝐶𝑖𝑙𝑒𝑓 𝑡𝑜𝑣𝑒𝑟 after the switch time instant and before their deadlines, where
|
||
𝑆𝑚𝑎𝑥 = 1 in HI mode, (1) and (2) in Eq. (16) are calculated 𝐶𝑖𝑙𝑒𝑓 𝑡𝑜𝑣𝑒𝑟 is the leftover execution time at the nominal processor speed
|
||
by Eqs. (26) and (27), respectively. 𝑆𝑚𝑎𝑥 = 1. While in HI mode, each LO task 𝜏𝑖 ∈ 𝛤𝐿𝑂 executes no more
|
||
⨂ than its 𝐶𝑖𝑑 𝑒𝑔 if it is started in HI mode, or its 𝐶𝑖𝑙𝑒𝑓 𝑡𝑜𝑣𝑒𝑟 if it is a leftover
|
||
(1) =((𝑏𝑖 ) ⊙ ((1∕𝑆𝐿 ) ⊙ 𝑖𝐿𝑂 )) (26)
|
||
⨂ job started in LO mode. The system switches back to LO mode, with
|
||
𝐻𝐼
|
||
(𝐽𝐻 , 𝑡) ((𝑎𝑖 ) ⊙ 𝑖 ). processor speed 𝑆𝐿 , at an idle instant if no jobs wait for executions at
|
||
this time. In addition, incomplete tasks are dropped at their deadlines,
|
||
⨂ hence there does not exist a backlog of outstanding execution at the
|
||
(2) = ((𝑘𝑖 ) ⊙ ((1∕𝑆𝐿 ) ⊙ 𝑖𝐿𝑂 )) (𝐽𝐻 , 𝑡). (27) end of each hyper-period.
|
||
|
||
6. Experimental evaluation
|
||
Theorem 4. Given an IMC taskset 𝛤 that is deterministically schedulable
|
||
by EDF on a single processor, it remains deterministically schedulable with
|
||
We evaluate our approach based on two performance metrics: the
|
||
the energy-efficient processor speed 𝑆𝐿 in LO mode and 𝑆𝑚𝑎𝑥 = 1 in HI
|
||
schedulability ratio, which represents the proportion of schedulable task
|
||
mode if 0 < ∀𝑡 ≤ 𝑡𝑚𝑎𝑥 , 0 < 𝑡𝑠 < 𝑡
|
||
sets (either deterministically or probabilistically schedulable) out of all
|
||
max{ 𝐿 (𝑡)} ≤ 𝑡, 𝑎𝑛𝑑 max{ 𝐻 (𝑡)} ≤ 𝑡, (28) task sets; and the normalized energy consumption of each task set, as
|
||
defined in Eq. (22).
|
||
where 𝑆𝑐 𝑟𝑖𝑡 ≤ 𝑆𝐿 ≤ 1, 𝐿 (𝜏𝑖 , 𝑡), (𝐽𝐿 , 𝑡), 𝐻
|
||
𝐿 (𝜏𝑖 , 𝑡), (1) and
|
||
We generate synthetic tasksets based on the following experiment
|
||
(2) are given in Eqs. (23)–(27), respectively.
|
||
settings:
|
||
|
||
Proof. Theorem 4 can be directly derived from Theorem 3. • Number of tasks in each taskset 𝛤 is set to 𝑛 = 4.
|
||
• Number of HI tasks in 𝛤 is set to 𝑛 ⋅ 𝐶 𝑃 , where the Criticality
|
||
Proportion 𝐶 𝑃 is set to 𝐶 𝑃 = 0.5.
|
||
5.3. Example 3
|
||
• Number of discrete values of each task 𝜏𝑖 ’s nominal pWCET 𝑖 is
|
||
set to 𝐾 = 4.
|
||
Let us consider the task set 𝛤3 that consists of tasks with the param-
|
||
• Each of the 𝐾 probability values in the PMF of 𝑖 is selected
|
||
eters presented in Table 4. The processor has tens discrete normalized
|
||
randomly from [0, 1) while ensuring that they sum to 1 (similar
|
||
processor speed, i.e., [0.1, 0.2, … , 1.0] [45]. According to Theorem 3, the
|
||
to [46,47]).
|
||
taskset is deterministically schedulable in both modes. We calculate
|
||
• For each LO task 𝜏𝑖 ∈ 𝛤𝐿𝑂 , the index of the Degraded WCET 𝐶𝑖𝑑 𝑒𝑔
|
||
𝑆𝐿 = 0.8 on the basis of Theorem 4, by iteratively trying out the
|
||
among the 𝐾 discrete values of 𝑖 is set to 𝑖𝑛𝑑(𝐶𝑖𝑑 𝑒𝑔 ) = 0.5𝐾−1 = 1.
|
||
available speeds, from lowest to highest, until we find the minimum
|
||
speed that satisfies all constraints. According to Eq. (21), we have
|
||
• For each HI task 𝜏𝑖 ∈ 𝛤𝐻 𝐼 , the index of the Threshold WCET 𝐶𝑖𝑡ℎ𝑟
|
||
𝑥̄ 1 = 1.775, 𝑥̄ 2 = 1.99, 𝑥̄ 3 = 2.2. In addition, we can then use Eq. (22) to
|
||
among the 𝐾 discrete values of 𝑖 is set to 𝑖𝑛𝑑(𝐶𝑖𝑡ℎ𝑟 ) = 0.5𝐾 − 1 = 1.
|
||
obtain the taskset’s normalized energy consumption to be 0.3242925
|
||
with processor speed 𝑆𝐿 = 0.8 with DVFS, and 0.50197 with processor
|
||
• 𝑇𝑖 is randomly selected the set {10, 20, 40, 50, 100, 200, 400, 500,
|
||
speed 𝑆max = 1 for EDF without DVFS, which represents significant
|
||
1000} [48].
|
||
energy savings.
|
||
• To control taskset processor utilization, max{𝐿𝑂𝐿𝑂 (𝛤 )} is varied
|
||
|
||
from 0.1 to 0.9, in steps of 0.1, while max{𝐻𝐻𝐼𝐼 (𝛤 )} is chosen
|
||
5.4. Energy-efficient task execution model
|
||
randomly from the range [0.1, 1.0].
|
||
Assuming that the system is deterministically schedulable in both (Each task 𝜏𝑖 ’s pWCET 𝑖 and period 𝑇𝑖 are implicit, since both sys-
|
||
modes, we can use DVFS to reduce the processor speed to 𝑆𝐿 in LO tem schedulability and normalized energy consumption are dependent
|
||
mode, and set to 𝑆𝑚𝑎𝑥 = 1 in HI mode, while maintaining schedulability on the utilization values only, i.e., pWCU equal to pWCET divided by
|
||
in both modes. We modify the task execution model in Section 3.1 to be period.) Note that the time overhead of the proposed method is mainly
|
||
|
||
7
|
||
Y.-W. Zhang and J.-L. Zhang Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
|
||
|
||
|
||
Fig. 2. Impact on the schedulability ratio by varying the permitted system failure
|
||
𝐿𝑂
|
||
probability 𝐹𝑠 and max{𝐿𝑂 (𝛤 )}.
|
||
|
||
|
||
|
||
|
||
spent on the schedulability test, with significant time consumption
|
||
arising from the calculation of the probabilistic processor demands for
|
||
the task set, which involves a large number of convolution operations.
|
||
As the number of tasks increases, the time overhead grows exponen-
|
||
tially. To maintain the accuracy of the scheduling test, we have not
|
||
yet identified better methods to reduce the time overhead. Hence, we
|
||
have limited the number of tasks to four. In the future, we will strive
|
||
to reduce the time overhead associated with convolutions.
|
||
In the first experiment, we vary 𝐹𝑠 from 10−1 to 10−9 with a step
|
||
size of 10 by multiplication, i.e., 𝐹𝑠 is plotted with log scale. The value
|
||
𝐹𝑠 = 10−9 is based on the permitted failure probability of 10−9 for ASIL
|
||
D, the highest safety certification level in ISO 26262. The additional
|
||
case of 𝐹𝑠 = 0 is the special case of deterministic schedulability only for
|
||
Fig. 3. Varying each HI task’s Threshold WCET index 𝑖𝑛𝑑(𝐶𝑖𝑡ℎ𝑟 ) and max{𝐿𝑂
|
||
𝐿𝑂
|
||
(𝛤 )}.
|
||
hard real-time systems. Fig. 2 shows the results, where each data point
|
||
represents the average outcome obtained from a variable number of
|
||
task sets selected from 500 synthetic tasksets generated for each value
|
||
of max{𝐿𝑂 𝐿𝑂 (𝛤 )}, using different seeds for the pseudo-random number • The schedulability ratio is negatively correlated with max
|
||
𝐿𝑂 (𝛤 )}, as expected.
|
||
{𝐿𝑂
|
||
generator.
|
||
• The schedulability ratio is negatively correlated with 𝐶𝑖𝑡ℎ𝑟 . With
|
||
We make the following observations from Fig. 2:
|
||
increasing 𝐶𝑖𝑡ℎ𝑟 , HI tasks have larger WCETs (both expected
|
||
and maximum) in LO mode according to the trimming opera-
|
||
• The schedulability ratio is positively correlated with 𝐹𝑠 , con- tion for pWCET defined in Eq. (2), causing max{ 𝐿 (𝑡)} and
|
||
firming the significant advantages of considering probabilistic max{ 𝐻 (𝑡)} to increase, which reduces system schedulability.
|
||
schedulability compared to considering deterministic schedulabil- • The average normalized energy consumption 𝑁 𝐸(𝛤 ) is positively
|
||
ity only, even at very small values of 𝐹𝑠 for high levels of safety correlated with max{𝐿𝑂 𝐿𝑂 (𝛤 )}. From Eq. (22), 𝑁 𝐸(𝛤 ) is depen-
|
||
certification. dent on each task’s expected pWCET 𝑥𝑖 and the energy-efficient
|
||
• The schedulability ratio is negatively correlated with max processor speed in LO mode 𝑆𝐿 . With increasing max{𝐿𝑂 𝐿𝑂 (𝛤 )},
|
||
{𝐿𝑂 𝐿𝑂 (𝛤 )}, since both max{ (𝑡)} and max{ (𝑡)} increase
|
||
𝐿 𝐻 both 𝑥𝑖 and 𝑆𝐿 increase, causing 𝑁 𝐸(𝛤 ) to increase.
|
||
with increasing max{𝐿𝑂 𝐿𝑂 (𝛤 )}, which reduces system schedulabil-
|
||
• 𝑁 𝐸(𝛤 ) is positively correlated with 𝐶𝑖𝑡ℎ𝑟 . With increasing 𝐶𝑖𝑡ℎ𝑟 , HI
|
||
ity. task 𝜏𝑖 has a larger expected pWCET in LO mode, causing both 𝑥𝑖
|
||
and 𝑆𝐿 to increase, which in turn causes 𝑁 𝐸(𝛤 ) to increase.
|
||
In the second experiment, we fix the permitted system failure prob-
|
||
ability to be 𝐹𝑠 = 10−7 (based on the requirement for ASIL A in ISO Averaged over all cases, our approach achieves an average reduction
|
||
26262). We vary each HI task’s 𝐶𝑖𝑡ℎ𝑟 through varying its index 𝑖𝑛𝑑(𝐶𝑖𝑡ℎ𝑟 ) of 33.49% for the average normalized energy consumption compared
|
||
from 0 to 𝐾 − 1 with step size 1, i.e., the sequence {0, 1, 2, 3} (The to EDF without DVFS.
|
||
case of 𝑖𝑛𝑑(𝐶𝑖𝑡ℎ𝑟 ) = 3 is the special case where each HI task 𝜏𝑖 has the
|
||
7. Practical considerations
|
||
same WCET in both modes.). Each LO task’s 𝐶𝑖𝑑 𝑒𝑔 is fixed to be the
|
||
default value of 𝑖𝑛𝑑(𝐶𝑖𝑑 𝑒𝑔 ) = 1. The results are shown in Fig. 3, including
|
||
In this section, we address some practical considerations in trans-
|
||
both the schedulability ratio, and the normalized energy consumption
|
||
posing our proposal into to industry practice.
|
||
(𝑁 𝐸(𝛤 ) defined in Eq. (22)). Each data point represents the average
|
||
Timing analysis for pWCET. Task 𝜏𝑖 ’s pWCET 𝑖 , as specified
|
||
outcome obtained from a variable number of task sets selected from 500
|
||
𝐿𝑂 (𝛤 )}, depending by its PMF, may be obtained via static, dynamic or measurement-
|
||
synthetic tasksets generated for each value of max{𝐿𝑂
|
||
𝑡ℎ𝑟 based, or hybrid timing analysis methods, as discussed in the survey
|
||
on the value of 𝑖𝑛𝑑(𝐶𝑖 ).
|
||
paper [49]. Static Probabilistic Timing Analysis (SPTA) is based on
|
||
We make the following observations from Fig. 3: the analysis of the program code, along with an abstract model of the
|
||
|
||
8
|
||
Y.-W. Zhang and J.-L. Zhang Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
|
||
hardware behavior. Measurement-Based Probabilistic Timing Analysis CRediT authorship contribution statement
|
||
(MBPTA) typically applies Extreme Value Theory (EVT) to make a
|
||
statistical estimate of the pWCET distribution of a program. Hybrid Yi-Wen Zhang: Writing – review & editing, Writing – original draft,
|
||
Probabilistic Timing Analysis (HyPTA) combines both statistical and Methodology, Funding acquisition, Formal analysis, Conceptualization.
|
||
analytical approaches, e.g., by taking measurements at the level of basic Jin-Long Zhang: Writing – original draft, Visualization, Software, Data
|
||
blocks or sub-paths, and then composing the results using structural curation.
|
||
information obtained from static analysis of the code.
|
||
Number of discrete value (𝐾) of pWCET 𝑖 . The value of 𝐾 Declaration of competing interest
|
||
determines the granularity of modeling the pWCET’s PMF: larger 𝐾
|
||
implies finer granularity modeling, but may not be well-supported by
|
||
The authors declare that they have no known competing finan-
|
||
timing analysis techniques, and also leads to higher computational costs
|
||
cial interests or personal relationships that could have appeared to
|
||
in schedulability analysis. The typical value of 𝐾 is 2-8 [5], although
|
||
influence the work reported in this paper.
|
||
there is no hard lower or upper bound on its value. Our experiments
|
||
with 𝐾 varying from 4 to 8 indicate that its value does not affect
|
||
system schedulability and power consumption significantly, indicating Acknowledgments
|
||
that 𝐾 = 4 already provides sufficiently fine granularity modeling
|
||
under our experimental setup. This work has been supported by the Natural Science Foundation
|
||
PMF of pWCET 𝑖 . In the absence of real industry tasksets, we of Fujian Province of China under Grant 2023J01139 and the Funda-
|
||
need to generate each task’s pWCET 𝑖 synthetically, as defined by mental Research Funds for the Central Universities, China under Grant
|
||
the PMF. There is no clear consensus on the generation method in the ZQN-1009.
|
||
literature on probabilistic schedulability analysis. An early work Edgar
|
||
and Burns [50] used the trimmed and scaled Gumbel distribution to Data availability
|
||
model likely WCET values; Draskovic [36] used the Weibull distribution
|
||
with an upper bound, which was used for modeling the distribution No data was used for the research described in the article.
|
||
of long but unlikely execution times based on EVT [51] (the Log of a
|
||
Weibull distribution is a Gumbel distribution); Wang et al. [46] and
|
||
Markovic et al. [47] adopted the uniform random distribution; Bozhko References
|
||
et al. [52] assumed two execution modes for each task in an MCS: a
|
||
typical mode and a rare exceptional mode. Its pWCET is equal to 𝑐 [1] Alan Burns, Robert Ian Davis, Mixed criticality systems-a review:(february 2022),
|
||
with probability .95 (the typical mode), and 4𝑐 with probability .05 2022, pp. 1–97, https://eprints.whiterose.ac.uk/183619/.
|
||
[2] Steve Vestal, Preemptive scheduling of multi-criticality systems with varying
|
||
(the exceptional mode), where 𝑐 was scaled to match the expected task
|
||
degrees of execution time assurance, in: 28th IEEE International Real-Time
|
||
utilization. In this paper, we adopt the simple approach of the uniform Systems Symposium, RTSS 2007, IEEE, 2007, pp. 239–243.
|
||
random distribution similar to [46,47]. [3] Yi-Wen Zhang, Jin-Peng Ma, Hui Zheng, Zonghua Gu, Criticality-aware EDF
|
||
Runtime overhead of DVFS. The overhead of varying the pro- scheduling for constrained-deadline imprecise mixed-criticality systems, IEEE
|
||
cessor speed with DVFS is assumed to be zero. This is a common Trans. Comput.-Aided Des. Integr. Circuits Syst. 43 (2) (2024) 480–491.
|
||
[4] Yi-Wen Zhang, Hui Zheng, Slack time management for imprecise mixed-criticality
|
||
assumption adopted in the DVFS literature [7]. We can determine
|
||
systems with reliability constraints, IEEE Trans. Comput. (2025).
|
||
through offline measurement an upper bound on the processor speed [5] Robert I. Davis, Liliana Cucu-Grosjean, A survey of probabilistic schedulability
|
||
transition overhead, which is typically relatively small compared to the analysis techniques for real-time systems, Leibniz Trans. Embed. Syst. 6 (1)
|
||
WCET of the task, hence it can be added to each task’s execution time (2019) 04:1–04:53.
|
||
without a significant impact on the solution. [6] Yi-Wen Zhang, Rong-Kun Chen, A survey of energy-aware scheduling in
|
||
Multiprocessor platforms. Our work can be easily extended to mixed-criticality systems, J. Syst. Archit. 127 (2022) 102524.
|
||
[7] Ashikahmed Bhuiyan, Federico Reghenzani, William Fornaciari, Zhishan Guo,
|
||
multi-processor platforms by a partitioned scheduling approach [31,32,
|
||
Optimizing energy in non-preemptive mixed-criticality scheduling by exploiting
|
||
53]. In partitioned scheduling, tasks are statically assigned to proces- probabilistic information, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.
|
||
sors, with each processor managed by a local scheduler. We can use 39 (11) (2020) 3906–3917.
|
||
simple allocation methods, e.g., Criticality-unaware worst-fit decreas- [8] Yi-Wen Zhang, Chen Ouyang, Semi-clairvoyant scheduling in non-preemptive
|
||
ing (CU-WFD), and criticality-aware first-fit decreasing (CA-FFD), to fixed-priority mixed-criticality systems, J. Syst. Archit. 159 (2025) 103332.
|
||
[9] Qingling Zhao, Mengfei Qu, Zonghua Gu, Haibo Zeng, Minimizing stack memory
|
||
allocate tasks to each processor while using an Energy-Efficient Task
|
||
for partitioned mixed-criticality scheduling on multiprocessor platforms, ACM
|
||
Execution Model to schedule tasks in each processor. Trans. Embed. Comput. Syst. (TECS) 21 (2) (2022) 1–30.
|
||
[10] Benny Akesson, Mitra Nasri, Geoffrey Nelissen, Sebastian Altmeyer, Robert I
|
||
8. Conclusions and future work Davis, A comprehensive survey of industry practice in real-time systems,
|
||
Real-Time Syst. (2021) 1–41.
|
||
The classic MCS task model has several restrictive assumptions, [11] Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen,
|
||
Katharina Morik, Björn B Brandenburg, Efficiently approximating the worst-
|
||
including hard real-time constraints, dropping LO tasks in HI mode,
|
||
case deadline failure probability under EDF, in: 2021 IEEE Real-Time Systems
|
||
and lack of consideration of power/energy consumption issues. In Symposium, RTSS, IEEE, 2021, pp. 214–226.
|
||
this paper, we relax these assumptions to make the MCS task model [12] Alexandre Esper, Geoffrey Nelissen, Vincent Nélis, Eduardo Tovar, An industrial
|
||
more practically applicable. We consider an IMC taskset scheduled view on the common academic understanding of mixed-criticality systems,
|
||
with the EDF algorithm on a uniprocessor platform, and propose an Real-Time Syst. 54 (3) (2018) 745–795.
|
||
[13] Sanjoy Baruah, Alan Burns, Implementing mixed criticality systems in ADA, in:
|
||
Energy-Efficient Task Execution Model that guarantees (deterministic
|
||
International Conference on Reliable Software Technologies, Springer, 2011, pp.
|
||
or probabilistic) schedulability, allows degraded QoS to LO tasks in HI 174–188.
|
||
mode, and applies DVFS to save energy. [14] Sanjoy K. Baruah, Alan Burns, Robert I. Davis, Response-time analysis for mixed
|
||
In this paper, we have considered EDF-based uniprocessor schedul- criticality systems, in: 2011 IEEE 32nd Real-Time Systems Symposium, IEEE
|
||
ing, dual-criticality MCS, and task execution time as probabilistic vari- Computer Society, 2011, pp. 34–43.
|
||
ables. As part of future work, these assumptions can be further relaxed [15] François Santy, Gurulingesh Raravi, Geoffrey Nelissen, Vincent Nelis, Pratyush
|
||
Kumar, Joël Goossens, Eduardo Tovar, Two protocols to reduce the critical-
|
||
to fixed-priority scheduling, multi-processor platforms, multiple crit- ity level of multiprocessor mixed-criticality systems, in: Proceedings of the
|
||
icality levels, and the multiple task parameters (e.g., task period) 21st International Conference on Real-Time Networks and Systems, 2013, pp.
|
||
represented by random variables. 183–192.
|
||
|
||
|
||
9
|
||
Y.-W. Zhang and J.-L. Zhang Journal of Systems Architecture 160 (2025) 103361
|
||
|
||
|
||
[16] Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo DAngelo, Haohan Li, Alberto [39] Yifeng Guo, Dakai Zhu, Hakan Aydin, Jian-Jun Han, Laurence T Yang, Exploit-
|
||
Marchetti-Spaccamela, Suzanne Van Der Ster, Leen Stougie, The preemptive ing primary/backup mechanism for energy efficiency in dependable real-time
|
||
uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task sys- systems, J. Syst. Archit. 78 (2017) 68–80.
|
||
tems, in: 2012 24th Euromicro Conference on Real-Time Systems, IEEE, 2012, [40] Yi-Wen Zhang, System level fixed priority energy management algorithm for
|
||
pp. 145–154. embedded real time application, Microprocess. Microsyst. 64 (2019) 170–177.
|
||
[17] Di Liu, Nan Guan, Jelena Spasic, Gang Chen, Songran Liu, Todor Stefanov, Wang [41] Yi-Wen Zhang, Chu-Gui Xu, Low power fixed priority scheduling sporadic task
|
||
Yi, Scheduling analysis of imprecise mixed-criticality real-time tasks, IEEE Trans. with shared resources in hard real time systems, Microprocess. Microsyst. 45
|
||
Comput. 67 (7) (2018) 975–991. (2016) 164–175.
|
||
[18] Hang Su, Nan Guan, Dakai Zhu, Service guarantee exploration for mixed- [42] Wei Jiang, Xiong Pan, Ke Jiang, Liang Wen, Qi Dong, Energy-aware design of
|
||
criticality systems, in: 2014 IEEE 20th International Conference on Embedded stochastic applications with statistical deadline and reliability guarantees, IEEE
|
||
and Real-Time Computing Systems and Applications, IEEE, 2014, pp. 1–10. Trans. Comput.-Aided Des. Integr. Circuits Syst. 38 (8) (2019) 1413–1426.
|
||
[19] Robert I. Davis, Alan Burns, Iain Bate, Compensating adaptive mixed criticality [43] Yi-Wen Zhang, Hui Zheng, Energy-aware fault-tolerant scheduling for imprecise
|
||
scheduling, in: Proceedings of the 30th International Conference on Real-Time mixed-criticality systems with semi-clairvoyance, J. Syst. Archit. 151 (2024)
|
||
Networks and Systems, Association for Computing Machinery, 2022, pp. 81–93. 103141.
|
||
[20] Zhe Jiang, Xiaotian Dai, Alan Burns, Neil Audsley, Zonghua Gu, Ian Gray, A [44] Yi-Wen Zhang, Hui Zheng, Energy-aware reliability guarantee scheduling with
|
||
high-resilience imprecise computing architecture for mixed-criticality systems, semi-clairvoyant in mixed-criticality systems, J. Syst. Archit. 156 (2024) 103269.
|
||
IEEE Trans. Comput. (2022). [45] Baoxian Zhao, Hakan Aydin, Dakai Zhu, Energy management under general
|
||
[21] Yi-Wen Zhang, Rui-Feng Guo, Low-power scheduling algorithms for sporadic task-level reliability constraints, in: 2012 IEEE 18th Real Time and Embedded
|
||
task with shared resources in hard real-time systems, Comput. J. 58 (7) (2015) Technology and Applications Symposium, IEEE, 2012, pp. 285–294.
|
||
1585–1597. [46] Tianyi Wang, Soamar Homsi, Linwei Niu, Shaolei Ren, Ou Bai, Gang Quan,
|
||
[22] Pengcheng Huang, Pratyush Kumar, Georgia Giannopoulou, Lothar Thiele, En- Meikang Qiu, Harmonicity-aware task partitioning for fixed priority scheduling
|
||
ergy efficient dvfs scheduling for mixed-criticality systems, in: 2014 International of probabilistic real-time tasks on multi-core platforms, ACM Trans. Embed.
|
||
Conference on Embedded Software, EMSOFT, IEEE, 2014, pp. 1–10. Comput. Syst. (TECS) 16 (4) (2017) 1–21.
|
||
[23] Yi-Wen Zhang, Energy-aware mixed-criticality sporadic task scheduling algo- [47] Filip Markovic, Thomas Nolte, Alessandro Vittorio Papadopoulos, Analytical
|
||
rithm, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 40 (1) (2021) approximations in probabilistic analysis of real-time systems, in: Proceedings of
|
||
78–86. the 43rd IEEE Real-Time Systems Symposium, RTSS, IEEE, 2022.
|
||
[24] Yi-Wen Zhang, Rong-Kun Chen, Energy aware fixed priority scheduling in [48] Jonah Caplan, Zaid Al-Bayati, Haibo Zeng, Brett H. Meyer, Mapping and
|
||
mixed-criticality systems, Comput. Stand. Interfaces 83 (2023) 103671. scheduling mixed-criticality systems with on-demand redundancy, IEEE Trans.
|
||
[25] Yi-Wen Zhang, Energy efficient non-preemptive scheduling of imprecise Comput. 67 (4) (2017) 582–588.
|
||
mixed-criticality real-time tasks, Sustain. Comput.: Inform. Syst. 37 (2023) [49] Robert I. Davis, Liliana Cucu-Grosjean, A survey of probabilistic timing analysis
|
||
100840. techniques for real-time systems, LITES: Leibniz Trans. Embed. Syst. (2019) 1–60.
|
||
[26] Yi-Wen Zhang, Ning Cai, Energy efficient EDF-VD-based mixed-criticality [50] Stewart Edgar, Alan Burns, Statistical analysis of WCET for scheduling, in:
|
||
scheduling with shared resources, J. Syst. Archit. 119 (2021) 102246. Proceedings 22nd IEEE Real-Time Systems Symposium (RTSS 2001)(Cat. No.
|
||
[27] Y.-W. Zhang, Energy aware algorithm based on actual utilization for periodic 01PR1420), IEEE, 2001, pp. 215–224.
|
||
tasks in mixed-criticality real-time systems, Comput. Stand. Interfaces 79 (2022) [51] Liliana Cucu-Grosjean, Luca Santinelli, Michael Houston, Code Lo, Tullio Var-
|
||
103563. danega, Leonidas Kosmidis, Jaume Abella, Enrico Mezzetti, Eduardo Quinones,
|
||
[28] Yi-Wen Zhang, DVFS-based energy-aware scheduling of imprecise mixed- Francisco J Cazorla, Measurement-based probabilistic timing analysis for multi-
|
||
criticality real-time tasks, J. Syst. Archit. 137 (2023) 102849. path programs, in: 2012 24th Euromicro Conference on Real-Time Systems, IEEE,
|
||
[29] Sujay Narayana, Pengcheng Huang, Georgia Giannopoulou, Lothar Thiele, 2012, pp. 91–101.
|
||
R Venkatesha Prasad, Exploring energy saving for mixed-criticality systems [52] Sergey Bozhko, Georg von der Brüggen, Björn Brandenburg, Monte carlo
|
||
on multi-cores, in: 2016 IEEE Real-Time and Embedded Technology and response-time analysis, in: IEEE 42nd Real-Time Systems Symposium, IEEE, 2021,
|
||
Applications Symposium, RTAS, IEEE, 2016, pp. 1–12. pp. 342–355.
|
||
[30] Behnaz Ranjbar, Tuan D.A. Nguyen, Alireza Ejlali, Akash Kumar, Power-aware [53] Yi-Wen Zhang, Rong-Kun Chen, Energy-efficient scheduling of imprecise mixed-
|
||
runtime scheduler for mixed-criticality systems on multicore platform, IEEE criticality real-time tasks based on genetic algorithm, J. Syst. Archit. 143 (2023)
|
||
Trans. Comput.-Aided Des. Integr. Circuits Syst. 40 (10) (2021) 2009–2023. 102980.
|
||
[31] Yi-Wen Zhang, Rong-Kun Chen, Zonghua Gu, Energy-aware partitioned schedul-
|
||
ing of imprecise mixed-criticality systems, IEEE Trans. Comput.-Aided Des. Integr.
|
||
Circuits Syst. 42 (11) (2023) 3733–3742. Yi-Wen Zhang (Senior Member, IEEE) received his Ph.D
|
||
[32] Yi-Wen Zhang, Jin-Peng Ma, Zonghua Gu, Partitioned scheduling with shared in Computer Application Technology from University of Chi-
|
||
resources on imprecise mixed-criticality multiprocessor systems, IEEE Trans. nese Academy of Sciences in 2016. He was a Post-doctoral
|
||
Comput.-Aided Des. Integr. Circuits Syst. 44 (1) (2025) 65–76. Fellow with Shenyang Institute of Computing Technology,
|
||
[33] Luca Santinelli, Laurent George, Probabilities and mixed-criticalities: the Chinese Academy of Sciences from 2017 to 2019.
|
||
probabilistic c-space, in: Proceedings of WMC, 2015. He has been an associate professor since 2020. He is
|
||
[34] Dorin Maxim, Robert I Davis, Liliana Cucu-Grosjean, Arvind Easwaran, Prob- named in the world’s top 2% of Scientists List 2023 and
|
||
abilistic analysis for mixed criticality systems using fixed priority preemptive 2024 by Stanford University. His current research interests
|
||
scheduling, in: Proceedings of the 25th International Conference on Real-Time include real-time systems and low-power design.
|
||
Networks and Systems, 2017, pp. 237–246.
|
||
[35] Jasdeep Singh, Luca Santinelli, Federico Reghenzani, Konstantinos Bletsas,
|
||
Zhishan Guo, Non-preemptive scheduling of periodic mixed-criticality real-time Jin-Long Zhang received the B.E. degree in Software En-
|
||
systems, in: Proceedings of the 10th European Congress on Embedded Real-Time gineering from Jiangxi Agricultural University in 2023. He
|
||
Systems, ERTS 2020, IEEE, 2020. is currently pursuing the MS degree in Huaqiao University.
|
||
[36] Stefan Draskovic, Rehan Ahmed, Pengcheng Huang, Lothar Thiele, Schedulability His current research interests include real-time systems and
|
||
of probabilistic mixed-criticality systems, Real-Time Syst. 57 (4) (2021) 397–442. low power design.
|
||
[37] Zhishan Guo, Sudharsan Vaidhun, Luca Satinelli, Samsil Arefin, Jun Wang,
|
||
Kecheng Yang, Mixed-criticality scheduling upon permitted failure probability
|
||
and dynamic priority, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 41
|
||
(1) (2021) 62–75.
|
||
[38] Kuan-Hsun Chen, Mario Günzel, Georg von der Brüggen, Jian-Jia Chen, Critical
|
||
instant for probabilistic timing guarantees: Refuted and revisited, in: 2022 IEEE
|
||
Real-Time Systems Symposium, RTSS, IEEE, 2022, pp. 145–157.
|
||
|
||
|
||
|
||
|
||
10
|
||
|