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