Semi-Clairvoyant Scheduling for Jobs with Multiple Criticalities

Agrawal, Kunal; Thai, Tung Duc; Zhao, Jinhao

doi:10.4230/LIPIcs.ECRTS.2026.21

Semi-Clairvoyant Scheduling for Jobs with Multiple Criticalities

Kunal Agrawal

Washington University in St. Louis, MO, USA Tung Duc Thai Washington University in St. Louis, MO, USA Jinhao Zhao

Washington University in St. Louis, MO, USA

Abstract

This paper considers scheduling jobs semi-clairvoyantly in mixed-criticality systems. In the semi-clairvoyant model, unlike the non-clairvoyant model, we know the WCET mode of the job at job arrival. Prior work has only considered this model for dual criticality jobs. We consider this problem for an arbitrary number of criticalities. We prove that there exist semi-clairvoyant schedulers that guarantee schedulability with speedup $\frac{2^{m}-1}{2^{m-1}}$ for systems with $m$ criticality levels. In addition, we prove that this bound is tight by providing a job set construction that requires this speed for any semi-clairvoyant scheduler. Finally we provide a linear programming formulation that optimally schedules the semi-clairvoyant system of jobs. The number of variables and constraints is polynomial in the number of jobs, but exponential in the number of criticalities.

Keywords and phrases:

mixed-criticality, semi-clairvoyance, schedulers, linear programming

Funding:

Kunal Agrawal: NSF CCF-2106699, CCF-2107280, PPoSS-2216971.

Copyright and License:

2012 ACM Subject Classification:

Computer systems organization

\rightarrow

Real-time systems ; Software and its engineering

\rightarrow

Real-time schedulability ; Computer systems organization

\rightarrow

Embedded and cyber-physical systems ; Mathematics of computing

\rightarrow

Linear programming ; Theory of computation

\rightarrow

Scheduling algorithms

DOI:

10.4230/LIPIcs.ECRTS.2026.21

Event:

38th European Conference on Real-Time Systems (ECRTS 2026)

Editor:

Angeliki Kritikakou

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The idea of mixed-criticality(MC) scheduling was introduced several years ago [23] to improve the performance and utilization of systems in the presence of timing unpredictability. While real-time schedulers rely on worst case execution time (WCET) estimates to achieve safety and predictability, these estimates are often extremely pessimistic. Mixed-criticality models allow the specification of multiple WCET parameters, one for each criticality level, which allows a finer granularity of information to be provided to the scheduler.

In this model, each job is assigned a static criticality level, which indicates the importance of the job. In particular, each job $J_{q}$ has a static criticality level $\chi(J_{q})$ between $1$ and $m$ as well as $\chi(J_{q})$ WCETs $e^{1}(J_{q}),e^{2}(J_{q}),\ldots,e^{\chi(J_{q})}(J_{q})$ such that $e^{x+1}(J_{q})\geq e^{x}(J_{q})$ . If any job $J_{q}$ ’s actual work exceeds its $(x-1)$ th WCET estimate $e^{x-1}(J_{q})$ , but does not exceed its $x$ th criticality WCET estimate $e^{x}(J_{q})$ , then we say that the job’s runtime mode is $\rho(J_{q})=x$ . If the highest runtime mode of any job is $x$ , then the system criticality $\Phi$ is said to be $x$ . In this case, jobs with static criticality smaller than $x$ need not execute, but all deadlines for jobs with static criticality $x$ or greater must meet their deadlines.

In the standard mixed-criticality model, the actual execution time of the job is revealed when the job finishes executing – the only way to know if a job will exceed $x$ -th criticality WCET $e^{x}(J_{q})$ is to execute it until it has exceeded this quantity or completed; in other words, the job’s execution criticality is revealed as the job executes. More recently, researchers have considered a slightly different model, called semi-clairvoyant mixed-criticality model [2] . In this model, the job’s runtime mode $\rho(J_{q})$ is revealed on arrival. This definition makes sense if the execution time depends on input parameters which may be known at arrival or if the job has several possible implementations one of which is chosen at arrival.

Agrawal et al [2] introduced this model and primarily considered it for 2 criticality levels. They showed a tight speedup bound of $3/2$ . They also provided a linear programming based algorithm to check for semi-clairvoyant schedulability and show that this algorithm is optimal – if any semi-clairvoyant scheduler guarantees schedulability to a system of jobs, then so can this scheduler. Semi-clairvoyance and its variants have since been considered extensively [10] in the literature. However, theoretical work on semi-clairvoyance seems restricted to 2 criticality levels. In this paper, we completely generalize these results to more than two criticality levels.

1.

In Section 3, we show that given jobs with $m$ distinct criticalities, no semi-clairvoyant scheduler can guarantee a speedup of less than $(2^{m}-1)/2^{m-1}$ – this reduces to $3/2$ for two criticality levels.
2.

In Section 4, we show that there exist semi-clairvoyant schedulers which can achieve this speedup bound – in other words, the speedup bound of $(2^{m}-1)/2^{m-1}$ is tight.
3.

In Section 5, we provide linear programming formulation which allows us to check the schedulability of semi-clairvoyant job systems exactly. It is important to note that this LP-based scheduling algorithm is an optimal semi-clairvoyant algorithm (not just speedup optimal). In other words, given system of jobs, if any semi-clairvoyant scheduler can schedule this system, then this LP-based algorithm can also schedule it. If it does not find a solution, then we know that the system is not schedulable.

These results starkly indicate the advantage of semi-clairvoyance in mixed-criticality scheduling over the traditional model of non-clairvoyance. There are no tight speedup bounds known for non-clairvoyant systems; and all known bounds scale approximately linearly or slightly sublinearly with the number of criticality levels. On the other hand, semi-clairvoyant systems can be optimally scheduled and require speedup of less than $2$ for arbitrary criticality levels.

2 Preliminaries

Mixed-Criticality Jobs.

A problem instance $\Delta$ consists of $n$ jobs where every $J_{q}\in\Delta$ has the following parameters: (1) $\chi(J_{q})\in\{1,2\ldots,m\}$ denotes the static criticality or importance of the job. (2) $a(J_{q})$ denotes the arrival time of the job. (3) $d(J_{q})$ denotes the deadline of the job. (4) $[e^{1}(J_{q}),e^{2}(J_{q}),\ldots,e^{\chi(J_{q})}(J_{q})]$ denotes the worst case execution times (WCETs) of the job for the different modes.¹¹1We use $\chi(J_{q})$ and $\chi_{q}$ interchangeably as appropriate – similarly for other parameters. Each job $J_{q}$ in $\Delta$ is released at time $a(J_{q})$ , has deadline $d(J_{q})$ and executes for some duration $\gamma(J_{q})$ . If the $e^{x-1}(J_{q})<\gamma(J_{q})\leq e^{x}(J_{q})$ , then the runtime mode of $J_{q}$ is $\rho(J_{q})=x$ . We say the system criticality is the highest runtime mode of any job.

Correctness criteria.

A scheduling algorithm is said to schedule $\Delta$ correctly iff the following condition is true. All jobs with static criticality at or above the highest system criticality ever reached must meet their deadlines. In particular, if the system criticality $\Phi$ is $x$ at some time, but is never $x+1$ , then all jobs with static criticality $\chi_{q}\geq x$ must meet their deadlines. For instance, if no jobs exceed their $e^{1}(J_{q})$ , then all jobs must meet their deadlines. If some job $J_{q}$ exceeds $e^{x-1}(J_{q})<\gamma(J_{q})\leq e^{x}(J_{q})$ and no job has $\gamma(J_{q})>e^{x}(J_{q})$ , then all jobs with (static) criticality $x$ or above must meet their deadlines, but no guarantees are needed for jobs with static criticality smaller than $x$ .

Clairvoyant Schedulability.

Clairvoyant Scheduler is an idealization in MC system that it can know all the exact execution time $\gamma$ before the arrival of any jobs. A clairvoyant scheduler can ignore all jobs with static criticality lower than $j$ (where $j$ is the highest execution criticality of any job) and run all other jobs using EDF. As a well-known result in EDF, a job set is schedulable iff for all intervals $[t_{i},t_{j}]$ , the total work of jobs with arrival time $\geq t_{i}$ and deadline $\leq t_{j}$ is at most $t_{j}-t_{i}$ . For mixed criticality systems, this means that for all criticality levels $x$ and all intervals $[t_{i},t_{j}]$ , the following holds: Say $X$ is the set of jobs with criticality level at least $x$ with arrival time $\geq t_{i}$ and deadline $\leq t_{j}$ . The sum of $e^{x}(J_{q})$ for all $J_{q}\in X$ is at most $t_{j}-t_{i}$ .

Clairvoyant schedulers are generally used to characterize the performance of other schedulers. In particular, speedup factor is the typical metric that is used to compare different MC scheduling algorithms. Formally, an algorithm A has speedup factor $f$ , if, given any instance that is schedulable on a unit-speed processor by optimal clairvoyant algorithm, A can schedule the same instance on a speed- $f$ processor.

Non-clairvoyant Schedulability.

Most work for scheduling MC systems is done under the non-clairvoyance assumption where $\gamma$ values for jobs becomes known as the jobs execute. That is, we do not know the exact runtime mode for a job until the job finishes executing. Non-clairvoyant schedulability is known to be NP-complete for both jobs and tasks even for dual criticality systems [1].

Semi-clairvoyant schedulability.

In this paper, we study semi-clairvoyant scheduling for MC systems. A semi-clairvoyant scheduler knows the job’s static parameters (its release time, deadline, static criticality, and worst case execution time for all criticality modes) in advance. However, unlike the clairvoyant scheduler, it does not know the job’s actual execution time and therefore, the job’s or the system’s runtime mode in advance. When a job $J_{q}$ arrives at time $a_{q}$ , its runtime mode is revealed to the scheduler, but the scheduler still does not know its exact execution time $\gamma$ . Formally, it knows a mode $x$ such that $e^{x-1}(J_{q})<\gamma(J_{q})\leq e^{x}(J_{q})$ .

Therefore, if a job $J_{q}$ arrives with runtime mode $\rho(J_{q})=x$ at time $a_{q}$ and the system criticality $\Phi$ is smaller than $x$ at this time , then a semi-clairvoyant scheduler can immediately increase the system criticality $\Phi$ to $x$ . An instant at which an online MC system changes (increases) it system mode $\Phi$ is called a mode switch time. At this time, the MC scheduler immediately stop executing all jobs $J_{p}$ with static criticality $\chi(J_{p})<x$ since the correctness condition no longer requires that it finish these jobs. We denote the time instance for a mode switch to runtime mode $\alpha$ as $k_{\alpha}$ . We know that $0=k_{1}\leq k_{2}\leq\ldots\leq k_{\Phi}$ .

Difference between semi-clairvoyance and non-clairvoyance.

For non-clairvoyant schedulers, a mode switch occurs and the system criticality $\Phi$ increases to $x$ when some job $J_{q}$ executes for more than $e^{x-1}(J_{q})$ time since this is the time when the scheduler discovers that runtime mode of this job. Therefore, the mode switch can happen at any time during the schedule. In contrast, mode switches always occur at arrival times for semi-clairvoyant schedulers since the runtime mode of a job is known at arrival. This difference shows up in complexity results. For dual-criticality jobs, semi-clairvoyant schedulability can be checked in polynomial time by using a linear program while non-clairvoyant schedulability is NP-Hard. In addition, the speedup bounds are also different; for dual-criticality jobs, semi-clairvoyant jobs need a speedup of $3/2$ relative to clairvoyant schedulability while non-clairvoyant systems require a speedup of about $1.62$ .

3 Lower Bound

In this section, we will show that given a feasible set of semi-clairvoyant jobs with $m$ criticality levels, no online algorithm can guarantee schedulability with speedup smaller than $s=(2^{m}-1)/2^{m-1}$ . We will argue this by creating a set of jobs which are schedulable by a clairvoyant scheduler, but needs speed $s$ to schedule online by any semi-clairvoyant scheduler.

The set of $2m-1$ jobs are shown in Table 1. We can divide these jobs into two groups. The first $m$ jobs $J_{1},J_{2},\ldots,J_{m}$ are called initial jobs – they all arrive at time $0$ . Here are the characteristics of these initial jobs: job $J_{q}$ has deadline $2^{q-1}$ , static criticality $q$ , and work (at all criticality levels) $2^{q-2}$ (Except the first job whose work at criticality level 1 is just 1). The second set of $m-1$ jobs, namely $J_{m+1}\ldots,J_{2m-1}$ , are the later jobs. These are more interesting. Job $J_{m+q}$ has arrival time $2^{q-1}$ , deadline $2^{q}$ and static criticality $q+1$ . Each of these jobs has work $0$ at all criticality levels except at its highest criticality level – that is job $J_{m+q}$ has $e_{1},\ldots,e_{q}=0$ and $e_{q+1}=2^{q-1}$ .

Table 1: The set of jobs that shows that any semi-clairvoyant scheduler needs a speedup of

2-1/2^{m-1}

in order to schedules jobs with

m

different criticalities.

Jobs	$\chi_{p}$	$a_{p}$	$e^{1}_{p}$	$e^{2}_{p}$	$e^{3}_{p}$	$\ldots$	$e^{m-2}_{p}$	$e^{m-1}_{p}$	$e^{m}_{p}$	$d$
$J_{1}$	$1$	$0$	$1$	-	-	$\ldots$	-	-	-	$1$
$J_{2}$	$2$	$0$	$1$	$1$	-	$\ldots$	-	-	-	$2$
$J_{3}$	$3$	$0$	$2$	$2$	$2$	$\ldots$	-	-	-	$2^{2}$
$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$
$J_{m-1}$	$m-1$	0	$2^{m-3}$	$2^{m-3}$	$2^{m-3}$	$\ldots$	$2^{m-3}$	$2^{m-3}$	-	$2^{m-2}$
$J_{m}$	$m$	$0$	$2^{m-2}$	$2^{m-2}$	$2^{m-2}$	$\ldots$	$2^{m-2}$	$2^{m-2}$	$2^{m-2}$	$2^{m-1}$
$J_{m+1}$	$2$	$1$	$0$	$1$	-	$\ldots$	-	-	-	$2$
$J_{m+2}$	$3$	$2$	$0$	$0$	$2$	$\ldots$	-	-	-	$2^{2}$
$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$
$J_{2m-2}$	$m-1$	$2^{m-3}$	$0$	$0$	$0$	$\ldots$	$0$	$2^{m-3}$	-	$2^{m-2}$
$J_{2m-1}$	$m$	$2^{m-2}$	$0$	$0$	$0$	$\ldots$	$0$	$0$	$2^{m-2}$	$2^{m-1}$

First, we argue that this set of jobs is schedulable by a clairvoyant scheduler.

Lemma 1.

The set of jobs shown in Table 1 can be scheduled by a clairvoyant scheduler.

Proof.

The clairvoyant scheduler knows the criticality level of the system. Therefore, we just have to argue that the total work that the optimal scheduler has to do before every deadline is feasible. Note that the system criticality is determined by the execution time of the later jobs since we can assume that the initial jobs always arrive at criticality level $1$ . Intuitively, the system of jobs is designed so that at any system criticality , only one of the later jobs takes up any execution time and its work is equal to the work of the lower criticality jobs that need not execute. More concretely, the clairvoyant scheduler works as follows:

1.

If the system remains at criticality level $1$ – that is, $\gamma(J_{m+1})=\gamma(J_{m+2})=\ldots=\gamma(J_{2m-1})=0$ – then the scheduler has to execute only the initial jobs. Now consider any set of jobs $J_{1},\ldots,J_{q}$ – the deadlines of these jobs are all before $2^{q-1}$ and the collective work of these jobs is also $2^{q-1}$ . Therefore, the clairvoyant scheduler can complete this work in time using EDF. Concretely, the system executes job $J_{q}$ in the interval $[2^{q-1},2^{q}]$ .
2.

if the system remains at criticality level $2$ , it can drop the first job. In addition, $\gamma(J_{m+1})=1$ , but $\gamma(J_{m+2})=\ldots=\gamma(J_{2m-1})=0$ . Therefore, it can execute $J_{2}$ and $J_{m+1}$ by time $2$ and then follow the same schedule outlined above, scheduling $J_{q}$ in the interval $[2^{q-1},2^{q}]$ .
3.

More generally, if the system is at criticality level $j$ , for $j>1$ , then it need never execute jobs $J_{1},\ldots,J_{j-1}$ as well as jobs $J_{m+1},\ldots,J_{m+j-2}$ . In this case $\gamma(J_{m+j-1})=2^{j-2}$ , but $\gamma(J_{m+j})=\ldots=\gamma(J_{2m-1})=0$ . Therefore, the clairvoyant scheduler can execute job $J_{j}$ by time $2^{j-2}$ . At this time job $J_{m+j-1}$ arrives and can be executed by time $2^{j-1}$ . The remaining schedule remains the same as above.

$\hfill\blacktriangleleft$

Lemma 2.

No semi-clairvoyant scheduler with speed less than $s<(2^{m}-1)/2^{m-1}$ can schedule this system of jobs under all arrival conditions.

Proof.

Say this set of jobs is executed by a semi-clairvoyant scheduler on a processor of speed $s$ . The initial criticality of the system is 1. Now we consider each interval $[0,1)$ and $[2^{q},2^{q+1})$ for every $q$ from 0 to $m-1$ :

$\blacksquare$

Over the interval $[0,1)$ , the first $m$ jobs arrive. $J_{1}$ must receive 1 unit of execution (otherwise it will miss its deadline). The remaining $s-1$ unit of execution could be used to execute any other initial jobs.
$\blacksquare$

Over the interval $[1,2)$ , $J_{m+1}$ arrives. $J_{m+1}$ with static criticality $\chi_{m+1}=2$ (and work $\gamma(J_{m+1})=1)$ increasing the criticality level of the system to $2$ . Both $J_{2}$ and $J_{m+1}$ both have a deadline of $2$ ; therefore, the semi-clairvoyant scheduler must complete $3$ units of work (belonging to $J_{1},J_{2},J_{m+1}$ ) by time $2$ .
$\blacksquare$

At time $2$ , job $J_{m+2}$ arrives with static criticality $\chi_{m+2}=3$ and work $\gamma(J_{m+2})=2$ . Again, the system criticality rises to $3$ at this time, but both criticality $3$ jobs must be completed by time $4$ since that is their deadline. Therefore, the semi-clairvoyant scheduler must complete at least $7$ units of work by time $4$ .
$\blacksquare$

More generally, at time $2^{j-1}$ , the system criticality increases to $j$ due to the arrival of job $J_{m+j-1}$ with its runtime mode at the level $j$ . But by this time, all the jobs with lower criticality have already finished executing since they all have earlier deadlines.

Therefore, over the entire interval, up to time $2^{m-1}$ , the total work that is executed is the sum of the work of all initial jobs as well as the maximum work of the later jobs. The total work of the initial jobs is $1+\sum_{q=0}^{m-2}2^{q}=2^{m-1}$ . In addition, the later jobs always arrive at their highest criticality level; therefore, the total work due to the later jobs is $\sum_{q=0}^{m-2}2^{q}=2^{m-1}-1$ . Therefore, the semi-clairvoyant scheduler must do the total work of $2^{m}-1$ in time $2^{m-1}$ . This means the speedup required is at least $(2^{m}-1)/2^{m-1}$ . $\hfill\blacktriangleleft$

4 Upper Bound

We will now show that there exist semi-clairvoyant schedulers which provide the speedup bound of $s=(2^{m}-1)/2^{m-1}$ . For the purposes of this proof, we assume that we have a job set $\Delta$ which is schedulable by a clairvoyant algorithm OPT on a processor of speed $1$ . We will define a theoretical semi-clairvoyant scheduler and prove that it can schedule any such job set on a processor of speed $s$ . Since we already showed that there exist instances for which no semi-clairvoyant scheduler can provide a better speedup bound, we can conclude that this bound is tight.

While the scheduler we use in this section does not work when the speedup is $<s$ , in the next section, we will provide a linear programming based semi-clairvoyant algorithm which is an optimal semi-clairvoyant scheduler for any instance and therefore also provides the stated speedup bound.

Proof Intuition

Let us first understand the high-level intuition and overview of how this proof will proceed. The details are in subsequent subsections.

1.

We will first define a scheduling algorithm called EDF-Zeno – nominally, this algorithm pretends that a processor of speed $s=(2^{m}-1)/2^{m-1}$ is split into $m$ processors (called lanes) with where the first lane has speed $1$ , the second $1/2$ , and so on; therefore, collectively, these lanes have speed $s$ . Each of these processors run EDF, but (potentially) on different subsets of jobs. This scheduler also uses “flow control” in order to ensure that low criticality jobs do not get too much processing at the cost of higher criticality jobs.
2.

We also apply a transformation called zipping on the job set. In particular, given a set of jobs $\Delta$ , we transform them into a different set of jobs, say $\Delta_{\text{zip}}$ , and prove that proving the speedup bound on this transformed set of jobs will prove it for the original set of jobs.
3.

We now get into the nitty-gritty of the proof. We assume for contradiction that EDF-Zeno cannot correctly schedule some instance and identify the first deadline miss, say for job $J_{\text{miss}}$ and assume that this happens when the system is in some system criticality $\Phi$ .
4.

We identify the busy period preceding this deadline miss for all individual lanes. The definition of the busy period is somewhat complicated due to two reasons (1) each lane schedules different subsets of jobs; and (2) the scheduler on each lane is not quite pure-EDF due to flow control.
5.

We then identify a subset of “bottleneck” jobs – these are the jobs that can potentially prevent our job $J_{\text{miss}}$ from completing by its deadline. We then prove that if this set of bottleneck jobs is schedulable, then the original set of jobs is also schedulable. Therefore, we can restrict our attention to just this set of jobs.
6.

This allows us to bound the interference that our job $J_{\text{miss}}$ can experience during the busy period. However, this interference calculation is also complicated due to several factors: (1) some jobs may interfere in some lanes but not others; (2) the flow control mechanism allows us to bound some of the interference; and (3) lower criticality jobs sometimes stop interfering after mode switches.
7.

After considering all these factors, we are able to bound the interference on the job and show that the interference is strictly smaller than the total execution capacity of the busy period. This gives us a contradiction due to the definition of the busy period.

Definition of EDF-Zeno

For this proof, we will use a relatively unnatural scheduling algorithm which is designed purely to make the proof tractable. We will assume that this scheduler always runs (semi-clairvoyantly) on a machine with speed $s=(2^{m}-1)/2^{m-1}$ . EDF-Zeno has two aspects: division into lanes and flow control. We will define both here.

Definition 3 (EDF-Zeno’s Lane Policy).

For a machine with $s=(2^{m}-1)/2^{m-1}$ speedup, EDF-Zeno divides it into $m$ lanes, where lane $L_{i}$ has speed $s_{i}=1/2^{i-1}$ – lane $L_{1}$ has speed $1$ and subsequent speeds decrease geometrically by a factor of $1/2$ .²²2In a sense, these lanes are time-sharing the processor and dividing up the speed of the processor among themselves.

A job with criticality $\beta$ is only eligible to run on lanes $L_{1}$ through $L_{\beta}$ . In other words, all jobs are eligible to run on $L_{1}$ , but only jobs with criticality level $2$ and above can run on $L_{2}$ , and so on. Within each lane EDF-Zeno uses EDF to run jobs that are eligible to run on this lane.³³3If a job is simultaneously running on multiple lanes, then it is equivalent to running the job at the speed that is the sum of those lanes’ speed.

Here’s the intuition for this policy: Recall that if we only had a 2-criticality system, then the speed of $1.5$ is enough. Therefore, EDF-Zeno allows the jobs of the lowest two criticalities to essentially only use a machine with speed $1.5$ . In general, if we collectively consider the jobs of the lowest $\beta$ criticalities, they are only using a machine of speed $(2^{\beta}-1)/2^{\beta-1}$ .

EDF-Zeno has another policy to restrict the execution of “current” criticality jobs. In particular, after the mode switch to criticality level $\beta$ , jobs of criticality level $\beta$ become the lowest criticality jobs. However, they are still allowed to use the first $\beta$ lanes. Therefore, if a lot of criticality $\beta$ work arrives after this mode switch, it can overuse the machine and prevent higher criticality jobs from running. Therefore, we restrict the execution provided to these jobs using the a flow control policy.

Definition 4 (EDF-Zeno flow control).

Say that the mode switch to criticality level $\beta$ happens at time $k_{\beta}$ . Consider the set of all jobs $X$ which have static criticality level $\beta$ and they arrived after time $k_{\beta}$ . At any time $t>k_{\beta}$ , the total work done by EDF-Zeno on jobs in set $X$ is at most $t-k_{\beta}$ .

We make a quick observation about the impact of flow control on various lanes:

Observation 5.

Say, at time $t$ , a set of jobs $X$ of criticality level $\beta$ are being flow-controlled. At time $t$ , these jobs can run at speed at most 1. Therefore, if one of these jobs is the earliest deadline job, it can still run on lane 1. Therefore, lane 1 still follows EDF on jobs which are still in the system. However, flow-controlled jobs cannot run on any other lane.

Zipping the Job Set

In order to simplify the proof, we will apply a transformation to the job set – this transformation guarantees that each job has at most two “interesting” criticality levels.

Definition 6 (Zipped problem set).

Given a set of jobs $\Delta$ , consider each job $J_{q}\in\Delta$ with static criticality $\chi(J_{q})=\beta$ and work estimates $e^{1}(J_{q}),e^{2}(J_{q}),\ldots,e^{\beta}(J_{q})$ . In $\Delta_{\text{zip}}$ , $\beta-1$ jobs, $J_{q}^{2},J_{q}^{3},\ldots,J_{q}^{\beta}$ (with the same release time and deadline as $J_{q}$ ), are created as follows: For $i=2,3,\ldots,\beta-1$ , if $e^{i}(J_{q})-e^{1}(J_{q})>0$ , job $J_{q}^{i}$ has (static) criticality level $i$ and $e^{1}(J_{q}^{i})=e^{2}(J_{q}^{i})=\ldots=e^{i-1}(J_{q}^{i})=0$ , and $e^{i}(J_{q}^{i})=e^{i}(J_{q})-e^{1}(J_{q})$ ; if $e^{i}(J_{q})-e^{1}(J_{q})=0$ , $J_{q}^{i}$ is skipped. Finally, $J_{q}^{\beta}$ has (static) criticality level $\beta$ and $e^{1}(J_{q}^{\beta})=e^{2}(J_{q}^{\beta})=\ldots=e^{\beta-1}(J_{q}^{\beta})=e^% {1}(J_{q})$ , and $e^{\beta}(J_{q}^{\beta})=e^{\beta}(J_{q})$ .

Essentially, we create jobs such that their execution times for most of the criticality levels are $0$ . For example, if we are given a job $J_{q}$ with static criticality $\beta=4$ such that its execution times at levels $1,\ldots,4$ was $a, b, c, d$ , then we would have $3$ jobs: (1) $J_{q}^{2}$ with static criticality $2$ and work estimate at criticality levels $1$ and $2$ as $0$ and $b-a$ respectively; (2) $J_{q}^{3}$ with static criticality 3 and estimate $0,0,c-a$ respectively; and (3) $J_{q}^{4}$ static criticality $4$ with estimates $a, a, a, d$ respectively. This transformation simplifies the reasoning in the proof. We will now prove that this transformation is valid.

Lemma 7.

If $\Delta$ is feasible, then $\Delta_{\text{zip}}$ is also feasible (on the processor of the same speed).

Proof.

As a stronger conclusion, we prove the equivalence in feasibility. That is, OPT can either schedule both job sets or neither. Consider any single criticality level $\beta$ . The total work of $J_{q}$ if it arrives in criticality level $\beta$ is equal to the work of $J_{q}^{i}$ ’s collectively in criticality level $\beta$ by construction. Since they all share release times and deadlines, the total load within any interval remains the same for every criticality level. Since the feasibility of clairvoyant schedulers depends only on the workload within each time interval and at every criticality level, feasibility of the two systems is equivalent. $\hfill\blacktriangleleft$

We now consider semi-clairvoyant schedulability. This is less straightforward since semi-clairvoyant schedulability depends on the actual scheduler.

Lemma 8.

If some semi-clairvoyant scheduler can schedule $\Delta_{\text{zip}}$ , then an optimal semi-clairvoyant scheduler can also schedule $\Delta$ (on the processor of the same speed). Therefore, if EDF-Zeno can schedule $\Delta_{\text{zip}}$ , then the optimal semi-clairvoyant scheduler can schedule $\Delta$ .

Proof.

Say that some semi-clairvoyant schedule, $A(\Delta)$ , can correctly schedule $\Delta$ . We can now simulate the execution of $\Delta_{\text{zip}}$ – call this scheduler $B(\Delta_{\text{zip}})$ . Say job $J_{q}$ is released in runtime mode $k$ when executing $\Delta$ and therefore, has execution requirement $e^{k}(J_{q})$ . Therefore, in $\Delta_{\text{zip}}$ all $J_{q}^{i}$ s will also be released on mode $k$ which indicates the following: (1) if $k=1$ or $k=\chi(J_{q})=\beta$ , then in $\Delta_{\text{zip}}$ , $J_{q}^{\beta}$ has work $e^{k}(J_{q})$ and other $J_{q}^{i}$ don’t have any work; (2) otherwise, $J_{q}^{\beta}$ has work $e^{1}(J_{q})$ and $J_{q}^{k}$ has work $e^{k}(J_{q})-e^{1}(J_{q})$ . Therefore, the total work is the same. Therefore, any time the scheduler $A(\Delta)$ runs $J_{q}$ , $B(\Delta_{\text{zip}})$ runs one of the corresponding jobs. Therefore, both schedulers do exactly the same amount of work on $J_{q}$ for all $q$ . Therefore if $A(\Delta)$ meets all the relevant deadlines, then so does $B(\Delta_{\text{zip}})$ . $\hfill\blacktriangleleft$

Note that the above lemma doesn’t say anything about EDF-Zeno; in particular, we have not argued that if EDF-Zeno can schedule $\Delta_{\text{zip}}$ then it can also schedule $\Delta$ . As we will argue later, this is sufficient for us to prove the speedup bound we need.⁴⁴4Alternatively, we can also transform arbitrary $\Delta$ into $\Delta_{\text{zip}}$ and just run EDF-Zenoon the corresponding $\Delta_{\text{zip}}$ . As we will prove that EDF-Zenocan schedule $\Delta_{\text{zip}}$ , this transformation means that $\Delta$ is schedulable. The zipped problem set has the following property which will be helpful for our purposes.

Observation 9.

In $\Delta_{zip}$ , a job with static criticality $i$ is released in runtime mode either $1$ or $i$ .

For the rest of this section, we will treat $\Delta_{\text{zip}}$ as $\Delta$ , our job set under consideration.

Busy Period

We are now ready to define some terms to prove the following theorem:

Theorem 10.

A feasible zipped problem $\Delta_{\text{zip}}$ with $m$ criticality levels is schedulable by EDF-Zeno with $m$ lanes.

Note that the behavior of a semi-clairvoyant scheduler depends on the timing of mode switches – that is, as jobs arrive in different criticality levels, the scheduler responds accordingly. Assume for contradiction that there is some runtime behavior $R$ for which EDF-Zeno misses a deadline – and say $J_{\text{miss}}$ is the first job in this runtime behavior which misses its deadline. Let the arrival time of $J_{\text{miss}}$ be $a$ , the deadline of $J_{\text{miss}}$ be $d$ , and the static criticality of $J_{\text{miss}}$ is $\alpha$ . Also, assume the system is at system criticality $\Phi$ at time $d$ . We know that $\Phi\leq\alpha$ .

We can now ignore the behavior of the system after the time $d$ .

Therefore, the system has gone through a series of mode switches at times $0=k_{1}\leq k_{2}\leq\ldots\leq k_{\Phi}$ . We can ignore all mode switches after $\Phi$ .

We now define the interesting period of execution, namely the busy period before $d$ . Intuitively, the busy period contains jobs which interfered with the execution of job $J_{\text{miss}}$ – this sort of busy period analysis is common in real-time systems. However, in this proof, this definition is somewhat involved since (1) the busy period can be different for each lane since different subsets of jobs are eligible to run in each lane; and (2) flow control causes scheduling anomalies which make the definition complicated.

Definition 11 (Busy period).

Say $J_{\text{early}}$ is the set of jobs with deadline $\leq d$ and $J_{\text{late}}$ are the remaining jobs. For each lane $\beta>1$ , we look backward from $d$ , and find the latest time instance that is not running $J_{\text{early}}$ (i.e., running $J_{\text{late}}$ or idle). Let this time instance be $b_{\beta}$ . The busy period for lane $\beta>1$ is the interval $[b_{\beta},d]$ . For lane $1$ , the definition is a bit more complicated. We go backwards from $d$ and find the latest instance when either lane $1$ is not running $J_{\text{early}}$ , or some $J_{\text{late}}$ was scheduled on some other lane $\beta\geq 2$ while $J_{\text{early}}$ were eligible for lane 1 (this only happens when job running on lane 1 is subject to flow control on other lanes) (see Observation 5).

Note that $b_{1},b_{2},\ldots,b_{m}$ must exist, because time $0$ always fits the conditions. We can now observe some structural properties of these busy periods.

Observation 12.

Only jobs with deadline $\leq d$ are executed on a lane within its busy period.

Moreover, the starting points of each busy period are nicely ordered:

Lemma 13.

$b_{1}\leq b_{2}\leq\ldots\leq b_{m}$ .

Proof.

We only need to prove for any $\beta$ , $b_{\beta}\leq b_{\beta+1}$ . Assume for contradiction that $b_{\beta}>b_{\beta+1}$ . At any time in interval $[b_{\beta+1},b_{\beta}]$ , lane $\beta+1$ is working on some job in $J_{\text{early}}$ (Definition 11). But this job is also eligible to run on lane $\beta$ (Definition 3), and it is not subject to flow control (since it is running on lane $\beta+1$ ); therefore, lane $\beta$ cannot be idle or working on $J_{\text{late}}$ since it uses EDF. Hence a contradiction. $\hfill\blacktriangleleft$

Now we are ready to reduce the set of jobs that we must consider – nominally, these are jobs that execute within the busy period and therefore interfere with $J_{\text{miss}}$ . However, again, the definition is somewhat complex due to the various lanes and due to flow control.

Definition 14 (Bottleneck Jobs).

We will define bottleneck jobs $B_{\beta}$ for each criticality level $1\leq\beta\leq m$ . A job belongs to $B_{\beta}$ if (1) its static criticality level $\geq\beta$ ; and (2) it has a deadline $\leq d$ ; and (3) it has not completed by time $b_{\beta}$ . In addition, we will truncate both the interval and the work of some of these jobs. If a bottleneck job $J_{q}$ arrived before $b_{1}$ (the start of the busy period of lane 1), then its release time is modified to $b_{1}$ . In addition, if this job completed some execution say $w$ before $b_{1}$ , then its execution requirement is reduced by this quantity $w$ . Call the (sub)set of bottleneck jobs that were truncated $T$ . After truncation, we have the property that all bottleneck jobs have arrival time $\geq b_{1}$ and deadlines $\leq d$ .

A quick observation is that $B_{m}\subseteq\ldots\subseteq B_{2}\subseteq B_{1}$ . Precisely, $B_{\beta}$ are the jobs that possibly interfere with $J_{\text{miss}}$ on lane $\beta$ . When we refer to bottleneck jobs without $\beta$ , we mean $B_{1}$ . We now show that the truncated jobs are a limited set of jobs.

Lemma 15.

A bottleneck job $J_{q}$ with criticality $\beta$ is truncated if all three conditions hold: (1) $k_{\beta}\leq b_{1}\leq k_{\beta+1}$ – i.e., the busy period for lane 1 starts during system’s criticality $\beta$ ; (2) jobs of lane $\beta$ were subject to flow control immediately before $b_{1}$ ; and (3) $b_{1}=b_{2}=$ $\ldots=b_{\beta}$ .

Proof.

Say $t$ is the moment right before $b_{1}$ . At time $t$ , $J_{q}$ has arrived, but not completed. Since lane 1 does pure EDF, it is neither idle nor executing a job in $J_{\text{late}}$ . Therefore, $b_{1}$ was defined due to the second condition of Definition 11 – that some lane was subject to flow control. Say this lane was $\gamma$ ; which implies that $k_{\gamma}\leq b_{1}\leq k_{\gamma+1}$ . Since $J_{q}$ is executing, $\beta\geq\gamma$ . Therefore, $J_{q}$ is eligible to execute on lane $\gamma$ ; but it doesn’t. Therefore, $J_{q}$ must be subject to flow control and $\gamma=\beta$ . Finally, since the system is already in criticality level $\beta$ at time $t$ , lanes $1$ through $\beta$ have the same set of jobs that are eligible to run on them after this time. In addition, this is the last instant in time where $b_{1}$ is defined due to flow control. Therefore, due to Definition 11 and Lemma 13, we have $b_{1}=b_{2}=\ldots=b_{\beta}$ . $\hfill\blacktriangleleft$

We are now ready to prove that we can safely restrict our attention to bottleneck jobs only for the purposes of analysis.

Lemma 16.

If the original set of jobs was feasible, then (constructed) bottleneck jobs $B_{1}$ are also feasible. That is, if OPT could schedule the original set, it can schedule the bottleneck set $B_{1}$ . In addition, EDF-Zeno still misses the deadline $J_{miss}$ if only the jobs in $B_{1}$ are released.

Proof.

Say $O$ is OPT’s schedule on the original set of jobs and $O^{\prime}$ is OPT’s schedule on the bottleneck jobs. Removal of jobs obviously doesn’t impact feasibility. Now consider the truncated jobs. From Lemma 15, we know that jobs are only truncated when subject to flow control and all truncated jobs belong to the same criticality, say $\gamma$ . Therefore, these jobs have done (collectively) $b_{1}-k_{\gamma}$ work at time $b_{1}$ (that’s why they were flow controlled). Since they were all released after time $k_{\gamma}$ , $O$ cannot do more than $b_{1}-k_{\gamma}$ work on these jobs by time $b_{1}$ . $O$ has at least as much work to do on these jobs as $O^{\prime}$ ; therefore, if $O$ can schedule them, then so can $O^{\prime}$ .

We now show that if EDF-Zeno misses the deadline for $J_{\text{miss}}$ in the original set of jobs, then it also misses it for the bottleneck jobs. Say $S$ is the original schedule and $S^{\prime}$ is the schedule for bottleneck jobs. First we note that we can safely ignore jobs in $J_{\text{late}}$ since they do not interfere with jobs in $B_{1}$ on any of the lanes.

Now, if we just look at $J_{\text{early}}$ , all jobs that are not completed before time $b_{1}$ are included in the bottleneck jobs $B_{1}$ (either fully or in a truncated form). Therefore, within interval $[b_{1},d]$ $S$ and $S^{\prime}$ are responsible for the same set of jobs. Also note that jobs are truncated according to their execution in $S$ ; therefore, truncated jobs have exactly the same remaining work and the same deadline in $S$ and $S^{\prime}$ . Therefore, the schedules for $S$ and $S^{\prime}$ are identical. $\hfill\blacktriangleleft$

From now, we will implicitly assume that we are just running EDF-Zeno on bottleneck jobs. We first prove a structural property that relates the mode switches with the busy period.

Lemma 17.

For any $2\leq\beta\leq\Phi$ , if $b_{1}\leq k_{\beta}$ , we have $b_{\beta}\leq k_{\beta}$ .

Proof.

Proof by contradiction. If $b_{\beta}>k_{\beta}$ , consider the time instance just before $b_{\beta}$ – we know that no job in $J_{\text{early}}$ with criticality level at least $\beta$ is available; otherwise lane $\beta$ would run it. However, since $b_{1}\leq k_{\beta}$ , there must be a job in $J_{\text{early}}$ running on lane 1 at time $t$ and this job has criticality at least $\beta$ (because the system is in criticality $\beta$ , the lower jobs are dropped). It is either eligible for lane $\beta$ (an immediate contradiction), or it triggers the flow control so that it cannot run on lane $\beta$ . In the second case, since lane $\beta$ is not running $J_{\text{early}}$ , $b_{\beta}$ also matches the condition of Definition 14, which means $b_{1}=b_{\beta}>k_{\beta}$ , which also leads to a contradiction. $\hfill\blacktriangleleft$

We now observe another structural property which relates the mode switch times and the busy period. In particular, we need only focus on the worst case for the purposes of our bound and the following lemma implies that $b_{1}\leq k_{2}$ is the worst case. That is, the busy period for lane $1$ starts before the mode switch to criticality level $2$ . Intuitively, this is easy to see – if $b_{1}>k_{2}$ , we functionally only have $m-1$ criticalities since no (static) criticality level 1 job is part of $B_{1}$ . Therefore, the problem becomes easier.

Lemma 18.

We can assume that $b_{1}\leq k_{2}$ without loss of generality.

Proof.

Say, for contradiction, that $b_{1}>k_{2}$ . Let $k_{\beta}<b_{1}\leq k_{\beta+1}$ . Now $B_{1}$ does not have a job with criticality $<\beta$ since all those jobs were already dropped at time $k_{\beta}$ . Create a new problem instance $N B$ , which is basically $B_{1}$ , but transforms everyone’s criticality levels so that criticality $\beta-1+i$ in $B_{1}$ acts as criticality $i$ in $N B$ . OPT can still schedule $N B$ ; however for EDF-Zeno, each job in $N B$ can use fewer lanes than it could when this job was in $B_{1}$ . Hence, no job $N B$ finishes before the corresponding job in $B_{1}$ . Therefore, if $N B$ is at least as hard as $B_{1}$ ; more precisely, if $N B$ is schedulable, then so is $B_{1}$ . $N B$ has the property that $b_{1}<k_{2}$ . $\hfill\blacktriangleleft$

Defining Interference

We now are able to specifically measure the interference experienced by $J_{\text{miss}}$ on each processing lane in terms of these job sets $B_{1},\ldots,B_{m}$ . We will define several such parameters. In our proof, these are called utilities since they measure partial work of jobs actually completed by EDF-Zeno on specific lanes during the busy period instead of the entire work of the job.

Definition 19 (Utilities $U_{x}^{y}$ ).

Consider a schedule of EDF-Zeno on a set of bottleneck jobs $B_{1}$ . Consider any $\gamma$ for $1\leq\gamma\leq m$ . We first define the partial utility $U_{x}^{y}(\gamma)$ as the total work done by EDF-Zeno within the busy period on some job $J\in B_{\gamma}\setminus B_{\gamma+1}$ (formally, $B_{m+1}=\varnothing$ ) with static criticality $x$ and runtime criticality (mode) $y$ . The utility $U_{x}^{y}$ is defined as $U_{x}^{1}=\sum_{\beta=x}^{\alpha}U_{\beta}^{1}(x)$ , and $U_{x}^{x}=\sum_{\beta=x}^{\alpha}U_{x}^{x}(\beta)$ .

Note that for all $1<y<x$ , we have $U_{x}^{y}=0$ since we are only considering $\Delta_{\text{zip}}$ (Observation 9). Consider a job in $B_{x}-B_{x+1}$ but with static criticality $\beta>x$ . This job must have arrived and completed within the interval $[b_{x},b_{x+1}]$ (Definition 14). Therefore, we treat it (functionally) as a criticality $x$ job for the purposes of utilities. We can make the following observation:

Observation 20.

When collecting partial utilities $U_{\beta}^{1}(x)$ , each partial utility is counted exactly once to $U_{\min\{\beta,x\}}^{1}$ . Meanwhile for $\beta\geq 2$ , all $U_{\beta}^{\beta}(x)$ trivially count to $U_{\beta}^{\beta}$ (and $\beta<x$ results in $U_{\beta}^{\beta}(x)=0$ because before $k_{\beta}$ there are no jobs with runtime mode $\beta$ ). Therefore, all the partial utilities are counted exactly once.

Another important note: One might think that the sum of all the utilities is equal to the sum of the work of all the bottleneck jobs during our execution $R$ . However, it turns out that the sum of utilities might be smaller due to three factors:

$\blacksquare$

Some jobs may remain incomplete due to a mode switches – therefore, the total work done by EDF-Zeno is smaller than the work of the job.
$\blacksquare$

More importantly, some jobs may be in $B_{1}\setminus B_{2}$ (or more generally, some jobs are in $B_{1},..,B_{i}$ , but not in subsequent lanes) even though its static criticality is greater than $1$ . This means that this job arrived after time $b_{1}$ but completed before $b_{2}$ , and lane 2 subsequently experienced an idle instant (or worked on $J_{\text{late}}$ ). Therefore, some of this job’s work is included in the busy period of lane $1$ and therefore appears in the utilities $U_{1}^{1}$ , but any work done by lane 2 doesn’t is not included in any of the utilities.
$\blacksquare$

Finally, recall that $J_{\text{miss}}$ belongs to $J_{\text{early}}$ , so the completed part of $J_{\text{miss}}$ shows up in the utilities. But, since we assume (for contradiction) that $J_{\text{miss}}$ misses its deadline, therefore, it has some remaining work when we get to time $d$ . Lets call this uncompleted work $\delta$ .

Bounding the utilities

We will now provide bounds on these utilities which will allow us to reach a contradiction. The following two lemma generates $2\alpha-1$ inequalities due to the different values of $\beta$ .

Lemma 21.

For $1\leq\beta\leq\alpha$ ,

\underbrace{\sum_{\gamma=\beta}^{m}U_{\gamma}^{1}}_{\text{Part 1}}+\underbrace% {\mathbb{I}(\beta\neq 1)U_{\beta}^{\beta}+\mathbb{I}(\beta=\alpha\vee\rho(J_{% miss})=1)\delta}_{\text{Part 2}}\leq d-b_{\beta}.

Proof.

Suppose the system is in criticality $\beta$ at time $d$ . We know that the clairvoyant algorithm which runs in system criticality $\beta$ can finish all relevant jobs in $B_{\beta}$ . Lets call this algorithm $OPT^{\beta}$ . Since $OPT^{\beta}$ never runs any jobs with criticality level $<\beta$ , these jobs have arrival time $\geq b_{\beta}$ and deadline $\leq d$ (Definition 14 and Lemma 13). Therefore, the total work of these jobs must be at most $d-b_{\beta}$ to make $OPT^{\beta}$ feasible – this is the RHS of the statement.

Now, lets count up the total work of these jobs. First, consider a job with static criticality $\gamma>\beta$ . This job never switched to $\beta+1$ mode. Since it is a zipped job, it arrived in mode $1$ . Therefore, the total work of these jobs collectively is at least $U_{\gamma}^{1}$ since EDF-Zeno did this much work on these jobs. This is Part 1 on the LHS, excluding the first term where $\gamma=\beta$ . Now, consider jobs with criticality level $\beta$ . Some of these jobs may arrived in mode $1$ (if they arrived before $k_{\beta}$ ) and some in mode $\beta$ . Therefore, the work of these jobs is at least $U_{\beta}^{1}+U^{\beta}_{\beta}$ . In addition, if $\beta=\alpha$ or $J_{miss}$ releases in runtime mode 1, then the total work of these all these jobs also includes $\delta$ since $J_{\text{miss}}$ is part of this set and it has $\delta$ work undone at the deadline. This is Part 2 of the LHS (the second term has an If, since we over count when $\beta=1$ ). Summing them all up in the LHS gives us a lower bound on the total work of jobs that must be scheduled by OPT in criticality level $\beta$ . Since RHS is an upper bound, we get the inequality. $\hfill\blacktriangleleft$

Lemma 22.

For $1\leq\beta<\alpha$ ,

\underbrace{\sum_{\gamma=1}^{\beta}U_{\gamma}^{1}}_{\text{Part 1}}+\underbrace% {\sum_{\gamma=2}^{\beta}U_{\gamma}^{\gamma}+\frac{2^{\beta}-1}{2^{\beta-1}}% \sum_{\gamma=\beta+1}^{\alpha}U_{\gamma}^{\gamma}}_{\text{Part 2}}\leq\frac{2^% {\beta}-1}{2^{\beta-1}}d-\sum_{\gamma=1}^{\beta}\frac{1}{2^{\gamma-1}}b_{% \gamma}.

Proof.

Consider EDF-Zeno for jobs with criticality $\gamma\leq\beta$ in the various sets $B_{1},B_{2},\ldots$ . Each of these jobs arrives either in runtime criticality 1 or $\gamma$ . Therefore, the total utility (execution given to these jobs collectively by EDF-Zeno) is $\sum_{\gamma=1}^{\beta}U_{\gamma}^{1}+\sum_{\gamma=2}^{\beta}U_{\gamma}^{\gamma}$ . All these jobs will be dropped at $k_{\beta+1}$ . Therefore, the total work EDF-Zeno does on these jobs is no more than the possible execution time on the various lanes. The total available execution time is: $(k_{\beta+1}-b_{1})$ on lane 1; $0.5\times(k_{\beta+1}-b_{2})$ on lane 2, and so on. (Note that due to Lemmas 17, 18, we can assume that $b_{\beta}\leq k_{\beta+1}$ , so these intervals always exist). This means $\sum_{\gamma=1}^{\beta}U_{\gamma}^{1}+\sum_{\gamma=2}^{\beta}U_{\gamma}^{% \gamma}\leq\sum_{\gamma=1}^{\beta}\frac{1}{2^{\gamma-1}}(k_{\beta+1}-b_{\gamma})$ .

On the other hand, recall that the system is in criticality $\Phi$ at time $d$ . For $\beta<\gamma<\Phi$ , consider $U_{\gamma}^{\gamma}$ . This is the work done by EDF-Zeno on jobs released with static criticality $\gamma$ and runtime mode $\gamma$ . Therefore, these jobs must be in set $B_{\gamma}$ and must be released after $k_{\gamma}$ .

Due to the flow control policy of EDF-Zeno (Definition 4), we know that $U_{\gamma}^{\gamma}\leq k_{\gamma+1}-k_{\gamma}$ for $\beta<\gamma<\Phi$ , and $U_{\Phi}^{\Phi}\leq d-k_{\Phi}$ . Also, for $\Phi<\gamma\leq\alpha$ , $U_{\gamma}^{\gamma}=0$ .

Multiplying the second inequality by $\frac{2^{\beta}-1}{2^{\beta-1}}$ , and adding them to the first inequality gives us the lemma. $\hfill\blacktriangleleft$

Finally, using Lemmas 21 and 22, we can complete the proof for Theorem 10.

Proof.

We first define some weights that we will multiply to these inequalities in order to get appropriate coefficients. In particular, we define $A_{\alpha}=\frac{1}{2^{\alpha-1}}$ and for all $1\leq\beta<\alpha$ , $A_{\beta}=\frac{2^{\beta}-1}{2^{\beta-1}}A_{\beta+1}$ . As an illustration, if $J_{\text{miss}}$ ’s static criticality is $4$ , then $A_{4}=1/8$ , $A_{3}=7/32$ , $A_{2}=21/64$ , and $A_{1}=21/64$ .

Considering Lemmas 21 and 22, we have a total of $\alpha+(\alpha-1)=2\alpha-1$ inequalities. For clarity, we put these in Table 2 where the first $\alpha$ rows are for Lemma 21 and the subsequent $\alpha-1$ rows are for Lemma 22. We also divide the LHS into two parts as marked in the corresponding lemmas: Part 1 corresponds to the work included in $U_{x}^{1}$ and Part 2 corresponds to the work included in $U_{x}^{x}$ . We multiply each row by weights as shown in the table and add them together.

Table 2: The coefficients of each inequality when adding them up.

Weight	LHS(Part 1)	LHS(Part 2)	RHS
$A_{1}$	$U_{1}^{1}+U_{2}^{1}+\ldots+U_{m}^{1}$		$d-b_{1}$
$A_{2}$	$U_{2}^{1}+\ldots+U_{m}^{1}$	$U_{2}^{2}$	$d-b_{2}$
$\ldots$	$\ldots$	$\ldots$	$\ldots$
$A_{\alpha-1}$	$U_{\alpha-1}^{1}+U_{\alpha}^{1}+\ldots+U_{m}^{1}$	$U_{\alpha-1}^{\alpha-1}$	$d-b_{\alpha-1}$
$A_{\alpha}$	$U_{\alpha}^{1}+\ldots+U_{m}^{1}$	$U_{\alpha}^{\alpha}$	$d-b_{\alpha}$
$A_{2}$	$U_{1}^{1}$	$U_{2}^{2}+U_{3}^{3}+U_{4}^{4}\ldots+U_{\alpha}^{\alpha}$	$d-b_{1}$
$A_{3}$	$U_{1}^{1}+U_{2}^{1}$	$U_{2}^{2}+\frac{3}{2}(U_{3}^{3}+U_{4}^{4}+\ldots+U_{\alpha}^{\alpha})$	$d-b_{1}-\frac{1}{2}b_{2}$
$A_{4}$	$U_{1}^{1}+U_{2}^{1}+U_{3}^{1}$	$U_{2}^{2}+U_{3}^{3}+\frac{7}{4}(U_{4}^{4}+\ldots+U_{\alpha}^{\alpha})$	$d-\sum_{\beta=1}^{3}\frac{1}{2^{\beta-1}}b_{\beta}$
$\ldots$	$\ldots$	$\ldots$	$\ldots$
$A_{\alpha}$	$U_{1}^{1}+U_{2}^{1}+\ldots+U_{\alpha-1}^{1}$	$U_{2}^{2}+\ldots+U_{\alpha-1}^{\alpha-1}+\frac{2^{\alpha-1}-1}{2^{\alpha-2}}U_% {\alpha}^{\alpha}$	$d-\sum_{\beta=1}^{\alpha}\frac{1}{2^{\beta-1}}b_{\beta}$

These coefficients have the following properties (which can be proved through induction):

\sum_{\gamma=1}^{\beta}A_{\gamma}=2^{\beta-1}A_{\beta},\quad A_{\beta}+\frac{1% }{2^{\beta-1}}A_{\beta+1}=\frac{1}{2^{\beta-1}}

Using these properties, we first show that the coefficients of each term that appears on the LHS is $1$ once add up all the inequalities. For Part 1, check $U_{\beta}^{1}$ for $1\leq\beta\leq\alpha$ : it appears in the first $\beta$ rows and last $\alpha-\beta$ rows. (For instance, $U_{1}^{1}$ appears in the first row and the last $\alpha-1$ rows. Therefore, the coefficients of each $U_{\beta}^{1}$ is $\sum_{\beta=1}^{\alpha}A_{\beta}=2^{\alpha-1}A_{\alpha}=1$ . For $\beta>\alpha$ , these $U_{\beta}^{1}$ s have the same coefficient as $U_{\alpha}^{1}$ , so the total is still 1.

Part 2 is a bit more involved. We use induction to show that after adding all the rows, the coefficient of each term is $1$ . The base case is $\beta=2$ (the coefficient of $U_{2}^{2}$ is $A_{2}+\sum_{\beta=2}^{\alpha}A_{\beta}=1$ ). We now show that the difference between the coefficients of $U_{\beta}^{\beta}$ and $U_{\beta+1}^{\beta+1}$ is $0$ .

1.

Row $\beta$ only has $U_{\beta}^{\beta}$ , with weight $A_{\beta}$ ;
2.

Row $\beta+1$ only has $U_{\beta+1}^{\beta+1}$ , with weight $A_{\beta+1}$ ;
3.

Row $\alpha+\beta$ has $U_{\beta}^{\beta}+\frac{2^{\beta}-1}{2^{\beta-1}}U_{\beta+1}^{\beta+1}$ , with weight $A_{\beta+1}$ .
4.

In other rows, the coefficient of $U_{\beta}^{\beta}$ and $U_{\beta+1}^{\beta+1}$ are the same.

Therefore, the difference between the coefficient of $U_{\beta}^{\beta}$ and $U_{\beta+1}^{\beta+1}$ is:

A_{\beta}-A_{\beta+1}+A_{\beta+1}(1-\frac{2^{\beta}-1}{2^{\beta-1}})=A_{\beta}% -\frac{2^{\beta}-1}{2^{\beta-1}}A_{\beta+1}=0.

Now consider $\delta$ (which was not included in the table). If $\alpha>\Phi$ , then job $J_{\text{miss}}$ appears in runtime mode $1$ ; therefore, its coefficient is $1$ ; otherwise, it is released in runtime mode $\Phi$ and its coefficient is $1/2^{\alpha-1}$ . Therefore, in the worst case, it has a coefficient of $1/2^{\alpha-1}$ .

For RHS, check $b_{\beta}$ for $1\leq\beta\leq\alpha$ . $b_{\beta}$ appears at the $\beta$ -th row and the last $\beta-1$ rows (with coefficient $\frac{1}{2^{\beta-1}}$ ). The total coefficient is:

-A_{\beta}-\frac{1}{2^{\beta-1}}\sum_{\gamma=\beta+1}^{\alpha}A_{\gamma}=-A_{% \beta}-\frac{1}{2^{\beta-1}}(1-2^{\beta-1}A_{\beta})=-\frac{1}{2^{\beta-1}}.

Finally, check $d$ , the coefficient is

\sum_{\beta=1}^{\alpha}A_{\beta}+\sum_{\beta=2}^{\alpha}A_{\beta}=2-A_{1}=% \frac{2^{\alpha}-1}{2^{\alpha-1}}

Collecting them altogether, the sum of these inequalities results in:

\sum_{\beta=1}^{\alpha}U_{\beta}^{1}+\sum_{\beta=2}^{\alpha}U_{\beta}^{\beta}+% \frac{1}{2^{\alpha-1}}\delta\leq\frac{2^{\alpha}-1}{2^{\alpha-1}}d-\sum_{\beta% =1}^{\alpha}\frac{1}{2^{\beta-1}}b_{\beta}.

Since $J_{\text{miss}}$ misses its deadline, $\delta>0$ , so we have

\sum_{\beta=1}^{\alpha}U_{\beta}^{1}+\sum_{\beta=2}^{\alpha}U_{\beta}^{\beta}<% \frac{2^{\alpha}-1}{2^{\alpha-1}}d-\sum_{\beta=1}^{\alpha}\frac{1}{2^{\beta-1}% }b_{\beta}.

The LHS is all the work of $B_{1}$ that was done by EDF-Zeno within the busy period and the RHS is the total execution capacity of the busy period. Therefore, by definition of the busy period, the work done cannot be smaller than the capacity of the processor. Hence a contradiction. $\hfill\blacktriangleleft$

We have now shown that EDF-Zeno provides the optimal speedup bound. However, it is important to note that it is not an optimal scheduler for individual instances. For instance, even if a particular set of jobs is semi-clairvoyantly schedulable on speed 1.1 processors, EDF-Zeno will still (potentially) need speed $s=(2^{m}-1)/2^{m-1}$ speed processor to schedule it. Alternatively, one can say that, on a speed 1 processor, EDF-Zeno only guarantees schedulability to job sets which are feasible on speed $1/s$ processor. In the next section, we provide a scheduler which is instance optimal.

5 Scheduling Multi-Criticality Semi-Clairvoyant Jobs Optimally

This section provides a linear programming formulation for checking the schedulability for a system of $n$ semi-clairvoyant jobs with $m$ criticality levels. Solving the linear program also provides a scheduling algorithm that can then be implemented at runtime as the jobs arrive. This scheduler provides a quantitatively different guarantee relative to EDF-Zeno. Given a particular set of jobs, if the linear program fails to provide a schedule, then no semi-clairvoyant scheduler can schedule this set of jobs under all possible runtime conditions (sequence of mode switches).

5.1 Semi-Clairvoyant Scheduling using LP

Basic Ideas and Notation

We will use a linear program to check if the system of such jobs is schedulable. Since we have $n$ jobs, we have $2n$ key instances on the timeline which represent the arrival times and deadlines of these jobs⁵⁵5For simplicity in exposition and without loss of generality, we assume that all these instances are unique., dividing the timeline into $2n-1$ intervals. We will sort these key instances and represent them as $t_{i}$ . For each of these intervals, we will compute how much execution should be done by jobs with each static criticality given the history of criticality switches so far. In particular, the linear program uses the following notation:

$\blacksquare$

The variables for the linear program are $c_{k_{\alpha},j}^{x}({k_{1},\ldots k_{\alpha}})$ : Amount of $x$ criticality work done from $k_{\alpha}$ to $t_{j}$ . $k_{y}$ is the time instant system criticality increased to $y$ (Note that $k_{1}=0$ ). The parameters $k_{1},k_{2},\ldots,k_{\alpha}$ can be a set of any size between $1$ and $m$ and must all take values smaller than $t_{j}$ since a mode switch after time $t_{j}$ cannot impact the execution time given to any criticality level up to time $t_{j}$ .⁶⁶6For example, $c_{1,j}^{3}({0})$ denotes the execution time allocated to the jobs with static criticality $3$ up to time $t_{j}$ . As another example, $c_{4,10}^{9}({0,t_{4},t_{4}})$ denotes the amount of time spent on jobs with static criticality $9$ between time $t_{4}$ and $t_{10}$ assuming the system criticality increased to $3$ (and implicitly to $2$ ) at time $t_{4}$ . These are the quantities the linear program will compute.
$\blacksquare$

Key instances $t_{i}$ : obtained by sorting the release time and deadline of all the jobs. Assume that $t_{0}=0$ .
$\blacksquare$

$S_{i,j}^{x}$ : the set of jobs with static criticality $x$ with arrival time $\geq t_{i}$ and deadline $\leq t_{j}$ . These are the jobs with static criticality $x$ that must be executed between time $t_{i}$ and $t_{j}$
$\blacksquare$

$\sum_{J\in S_{i,j}^{x}}{e^{y}(J)}$ : sum of $y$ criticality work over $S_{i,j}^{x}$ .

Note that the variables $c_{k_{\alpha},j}^{x}({k_{1},\ldots k_{\alpha}})$ compute the entire schedule for semi-clairvoyant scheduler under all possible mode-switch conditions and prefixes. There are approximately $mn^{m+2}$ of these variables since $i,j,k_{d}$ can take $n$ values each and $x$ takes $m$ values. One can store these in a lookup table to be used for runtime scheduling.

LP Constraints

The basic idea behind the linear program is simple. We will consider all pairs $i, j$ such that $0\leq i<j$ and consider the interval between $t_{i}$ and $t_{j}$ . For all possible mode switch conditions, we want to ensure that we can allocate enough time to work for jobs of each static criticality level. In other words, we want to ensure that for all jobs that arrive at or after time $t_{i}$ and have a deadline at or before $t_{j}$ can get “sufficient execution time” to satisfy the correctness condition. Note that not all of these jobs may meet their deadlines since the scheduler may abandon some of these jobs due to mode switches. These variables $c$ represent the reserved time for each static criticality level within each interval.

Consider an instant $k_{\alpha}$ when some job with static criticality $\alpha$ might arrive. We will consider two cases.

Case 1.

We first consider the simple case where $t_{i}\geq k_{\alpha}$ . In this case, Inequality 1 represents the fact that all jobs must be able to meet their deadlines – it simply checks that we reserve enough time for each criticality level to complete the work that must be done within that interval. Inequality 2 represents the fact that we cannot execute more work than has arrived so far for any static criticality level. Finally, Inequality 3 represents the fact that the total execution within any interval cannot exceed the total time in that interval.

for $x\in\{\alpha,\ldots,m\}$ :

c_{k_{\alpha},j}^{x}({k_{1},\ldots k_{\alpha}})-c_{k_{\alpha},i}^{x}({k_{1},% \ldots k_{\alpha}})\geq\sum_{J\in S_{i,j}^{x}}{e^{\alpha}(J)}

(1)

\begin{split}c_{k_{\alpha},j}^{x}({k_{1},\ldots k_{\alpha}})+&\sum_{y=1}^{% \alpha-1}c_{k_{y},k_{y+1}}^{x}({k_{1},\ldots,k_{y}})\leq\sum_{J\in S_{k_{% \alpha},2n-1}^{x}}{e^{\alpha}(J)}-\sum_{J\in S_{j,2n-1}^{x}}{e^{\alpha}(J)}\\ &+\sum_{y=1}^{\alpha-1}(\sum_{J\in S_{k_{y},2n-1}^{x}}{e^{y}(J)}-\sum_{J\in S_% {k_{y+1},2n-1}^{x}}{e^{y}(J)})\end{split}

(2)

\sum_{y=\alpha}^{m}(c_{k_{\alpha},j}^{y}({k_{1},\ldots k_{\alpha}})-c_{k_{% \alpha},i}^{y}({k_{1},\ldots k_{\alpha}}))\leq t_{j}-t_{i}

(3)

Case 2.

Now consider the case where $t_{i}<k_{\alpha}$ . This is the crucial inequality since this is the only one that is worried about changes in the system criticalities. Say $t_{i}$ is between 2 transition time $k_{\beta-1}$ and $k_{\beta}$ . Now, we must ensure that all deadlines between $k_{\alpha}$ and $t_{j}$ are met. Inequality 4 checks this. The first term on the LHS represents the amount of time allocated to the jobs with static criticality $x$ between time $k_{\alpha}$ and $t_{j}$ given the history of criticality switches up to $k_{\alpha}$ . The term $c_{k_{\beta-1},k_{\beta}}^{x}({k_{1},\ldots,k_{\beta-1}})-c_{k_{\beta-1},i}^{x% }({k_{1},\ldots,k_{\beta-1}})$ represents the amount of time allocated to the jobs with static criticality $x$ between $t_{i}$ and $k_{\beta}$ and the last term $\sum_{y=\beta+1}^{\alpha}c_{k_{y-1},k_{y}}^{x}({k_{1},\ldots,k_{y-1}})$ represents the amount of time allocated to the jobs with static criticality $x$ between $k_{\beta}$ and $k_{\alpha}$ . Therefore, collectively, the LHS represents the amount of time allocated to the jobs with static criticality $x$ between $t_{i}$ and $t_{j}$ . The RHS represents the total amount of work that must be done for these jobs. The first term, $\sum_{J\in S_{k_{\alpha},j}^{x}}{e^{\alpha}(J)}$ represents the jobs that arrive between time $k_{\alpha}$ and $t_{j}$ – these jobs arrive with $\rho=\alpha$ ; so we consider $e^{\alpha}(J)$ for these jobs. The second term, $(\sum_{J\in S_{i,j}^{x}}{e^{\beta-1}(J)}-\sum_{J\in S_{k_{\beta},j}^{x}}{e^{% \beta-1}(J)})$ represents the jobs that arrived between time $t_{i}$ and $k_{\beta}$ – these jobs arrive at $\rho=\beta-1$ . The last term $\sum_{y=\beta+1}^{\alpha}(\sum_{J\in S_{k_{y-1},j}^{x}}{e^{y-1}(J)}-\sum_{J\in S% _{k_{y},j}^{x}}{e^{y-1}(J)})$ represents the jobs that arrive between time $k_{\beta}$ and $k_{\alpha}$ .

\displaystyle\begin{split}&c_{k_{\alpha},j}^{x}({k_{1},\ldots k_{\alpha}})+c_{% k_{\beta-1},k_{\beta}}^{x}({k_{1},\ldots,k_{\beta-1}})-c_{k_{\beta-1},i}^{x}({% k_{1},\ldots,k_{\beta-1}})\\ &+\sum_{y=\beta+1}^{\alpha}c_{k_{y-1},k_{y}}^{x}({k_{1},\ldots,k_{y-1}})\geq% \sum_{J\in S_{k_{\alpha},j}^{x}}{e^{\alpha}(J)}+(\sum_{J\in S_{i,j}^{x}}{e^{% \beta-1}(J)}-\sum_{J\in S_{k_{\beta},j}^{x}}{e^{\beta-1}(J)})\\ &+\sum_{y=\beta+1}^{\alpha}(\sum_{J\in S_{k_{y-1},j}^{x}}{e^{y-1}(J)}-\sum_{J% \in S_{k_{y},j}^{x}}{e^{y-1}(J)})\text{ for $x$ in $\alpha,\ldots,m$}\end{split}

(4)

The final inequality just checks that these variable values are well-formed since we cannot do more work until time $t_{j}$ than we do until time $t_{j+1}$ .

c_{k_{\alpha},j}^{y}({k_{1},\ldots k_{\alpha}})\leq c_{k_{\alpha},j+1}^{y}({k_% {1},\ldots k_{\alpha}}).

(5)

Without worrying about the actual asymptotic, it should be clear that the number of constraints is polynomial in $n$ and exponential in $m$ .

Runtime scheduling

Let $\widehat{c}_{k_{1},i}^{x_{1}}({k_{1}}),\widehat{c}_{k_{2},i}^{x_{2}}({k_{1},k_% {2}}),\ldots,\widehat{c}_{k_{d},i}^{x_{d}}({k_{1},\ldots,k_{d}})$ be the solution of our LP. In particular, the set of solution looks like this: $\{\widehat{c}_{k_{1},i}^{1}({k_{1}}),\widehat{c}_{k_{1},i}^{2}({k_{1}}),\ldots% ,\widehat{c}_{k_{1},i}^{d}({k_{1}}),\widehat{c}_{k_{2},i}^{2}({k_{1},k_{2}}),% \ldots\widehat{c}_{k_{2},i}^{d}({k_{1},k_{2}}),\ldots,$ $\widehat{c}_{k_{d-1},i}^{d-1}({k_{1},\ldots,k_{d-1}}),\widehat{c}_{k_{d-1,i}}^% {d}({k_{1},\ldots,k_{d-1}}),\widehat{c}_{k_{d},i}^{d}({k_{1},\ldots,k_{d}})\}$ .

Consider an arbitrary criticality $x$ . During runtime, let say that the system at time $t_{i}$ is currently in $\alpha$ criticality mode. Then the mode switch time $k_{1},k_{2},\ldots,k_{\alpha}$ is known. We reserve $\widehat{c}_{k_{\alpha},i+1}^{x}({k_{1},\ldots,k_{\alpha}})-\widehat{c}_{k_{% \alpha},i}^{x}({k_{1},\ldots,k_{\alpha}})$ time for $x$ criticality work in the interval $[i,i+1)$ (Jobs with the same criticality level are scheduled by EDF).

5.2 Proof of Correctness

We now prove that this linear program is correct. That is, a system of jobs is semi-clairvoyantly schedulable iff the the linear program is feasible.

Direction 1: LP solution can be used to schedule jobs

We first consider the case when the linear program has a solution and computes the $c$ values. We must argue that the computed values of $c$ are enough to schedule all jobs correctly under any sequence of mode switches.

We first make an observation – without loss of generality, we will assume that the actual execution time $\gamma$ of the job is always maximum for a given criticality level since that is the worst case for any semi-clairvoyant scheduler. We can formally state this as follows:

Observation 23.

When a job $J$ arrives with runtime $\rho$ , then it always have requires $\gamma(J)$ execution time. We assume this since this is the worst case for semi-clairvoyant schedulers.

We now show that if linear program has a solution, then every reserved interval is busy.

Lemma 24.

Say the linear program computes a solution and that some mode switches have occurred at times $k_{1},k_{2},\ldots,k_{\alpha}$ . Now consider any time $t_{j}$ . $c_{k_{\alpha},j+1}^{x}({k_{1},\ldots k_{\alpha}})-c_{k_{\alpha},j}^{x}({k_{1},% \ldots k_{\alpha}})$ is exactly the amount of $x$ criticality work done in $[t_{j},t_{j+1})$ assuming Observation 23 holds.

Proof.

Consider an arbitrary criticality level $x$ and any combination of mode switch $k_{1},k_{2},$ $\ldots,k_{\alpha}$ that occur at or before time $t_{j}$ .

We want to use induction to show that $c_{k_{\alpha},j+1}^{x}({k_{1},\ldots k_{\alpha}})-c_{k_{\alpha},j}^{x}({k_{1},% \ldots,k_{\alpha}})$ is exactly the amount of $x$ criticality work done in $[j,j+1)$ .

Base case.

$j=0$ , this is true since both reserved time and work available are 0.

Induction step.

Consider any $j^{\prime}<j$ and say $k_{\beta}$ is the time of the last mode switch at or before time $t_{j^{\prime}}$ . We assume that, $c_{k_{\beta},j^{\prime}+1}^{x}({k_{1},\ldots k_{\beta}})$ - $c_{k_{\alpha},j^{\prime}}^{x}({k_{1},\ldots,k_{\alpha}})$ is the amount of $x$ work executed in $[t_{j^{\prime}},t_{j^{\prime}+1})$ . We want to show that $c_{k_{\alpha},j+1}^{x}({k_{1},\ldots,k_{\alpha}})-c_{k_{\alpha},j}^{x}({k_{1},% \ldots,k_{\alpha}})$ is exactly the amount of $x$ criticality work done in $[t_{j},t_{j+1})$ .

Since the maximum amount of work arrives in every interval (Observation 23), the right hand side of (2) represents the total work $x$ criticality work that must be done before time $t_{j+1}$ under these mode switches. Subtracting $c_{k_{\alpha},j}^{x}({k_{1},\ldots,k_{\alpha}})-\sum_{y=1}^{\alpha-1}c_{k_{y},% k_{y+1}}^{x}({k_{1},\ldots,k_{y}})$ on both sides of (2), we get:

\displaystyle\begin{split}c_{k_{\alpha},j+1}^{x}({k_{1},\ldots,k_{\alpha}})-c_% {k_{\alpha},j}^{x}({k_{1},\ldots,k_{\alpha}})\leq\sum_{J\in S_{k_{\alpha},2n-1% }^{x}}{e^{\alpha}(J)}-\sum_{J\in S_{j+1,2n-1}^{x}}{e^{\alpha}(J)}+\\ \sum_{y=1}^{\alpha-1}(\sum_{J\in S_{k_{y},2n-1}^{x}}{e^{y}(J)}-\sum_{J\in S_{k% _{y+1},2n-1}^{x}}{e^{y}(J)})-c_{k_{\alpha},j}^{x}({k_{1},\ldots,k_{\alpha}})-% \sum_{y=1}^{\alpha-1}c_{k_{y},k_{y+1}}^{x}({k_{1},\ldots,k_{y}})\end{split}

(6)

By induction hypothesis on every small interval between $[0,k_{\alpha})$ , we know that: $\sum_{y=1}^{\alpha-1}c_{k_{y},k_{y+1}}^{x}({k_{1},\ldots,k_{y}})$ is exactly the amount of $x$ work completed in $[0,k_{\alpha})$ . Similarly, by induction hypothesis, if we consider any interval between $[k_{\alpha},t_{j})$ , $c_{k_{\alpha},j}^{x}({k_{1},\ldots,k_{\alpha}})$ is the amount of work with static criticality $x$ completed in $[k_{\alpha},j)$ .

Therefore, the right hand side of (6) represents the total leftover work with static criticality $x$ that is must be done within the interval $[t_{j},t_{j+1})$ under these mode switch conditions. So $c_{k_{\alpha},j+1}^{x}({k_{1},\ldots,k_{\alpha}})-c_{k_{\alpha},j}^{x}({k_{1},% \ldots,k_{\alpha}})$ must be the exact amount of $x$ criticality work done within this interval. $\hfill\blacktriangleleft$

Corollary 25.

The system is never idle – some work is executed during any reserved time.

We can now show that the LP schedule guarantees that all deadlines are met.

Lemma 26.

If the LP has a solution, then the semi-clairvoyant scheduler correctly schedules jobs under all mode switch conditions.

Proof.

As in Section 4, we assume, for contradiction, that job $J_{\text{miss}}$ with static criticality level $\chi(J_{\text{miss}})=x$ arrived at $t_{a}$ and misses its deadline at $t_{d}$ . In other word, we did not reserve enough time for $x$ criticality work. Now, consider only jobs with criticality $x$ . Let $[t_{b},t_{d})$ be the busy period for criticality $x$ , i.e., $t_{b}$ is the latest time instant before $t_{a}$ ( $t_{b}\leq t_{a}$ ) such that in the interval $[t_{b},t_{d})$ , only jobs that arrive after $t_{b}$ and have deadline before $t_{d}$ are executed within the time reserved for $x$ -criticality work.

From (4) or (1) (if there is at least 1 mode switch between $t_{b}$ and $t_{d}$ then use (4), else use (1)), substitute $i=b$ and $j=d$ .

In both cases, the LHS denotes the $x$ criticality work that was executed in the interval $[t_{b},t_{d})$ . However, the RHS is exactly the jobs with criticality $x$ , arrival time $\geq t_{b}$ and deadline $\leq t_{d}$ . In addition, note that if the maximum amount of work arrives in every interval, from Corollary 25, none of the reserved time is wasted on idleness. Therefore, this entire interval was used. However we still missed $J_{\text{miss}}$ deadline at $t_{d}$ , which is a contradiction. $\hfill\blacktriangleleft$

Direction 2: If LP fails, then the system of jobs is not semi-clairvoyantly schedulable

Now we argue that the linear program is optimal. In other words, if the linear program does not find a feasible solution, then no online semi-clairvoyant scheduler can schedule this system of jobs under all mode change conditions.

Now consider an optimal online scheduler $OPT^{\alpha}$ for scheduling a set of jobs. We will now construct $S=\{\widehat{c}_{k_{\alpha},i}^{x}({k_{1},k_{2},\ldots,k_{\alpha}})\}$ for all $i$ and possible mode switch times $k_{1},k_{2},\ldots,k_{\alpha}$ before time $t_{i}$ such that $\widehat{c}_{k_{\alpha},i}^{x}({k_{1},k_{2},\ldots,k_{\alpha}})$ represents the amount of time $OPT^{\alpha}$ spends on $x$ -criticality work $OPT^{\alpha}$ schedules between time $k_{\alpha}$ and $t_{i}$ .

Claim 27.

With $OPT^{\alpha}$ , we can construct this set $S$ .

Proof.

Since the optimal scheduler $OPT^{\alpha}$ exists, we can construct $S$ by simulating it under all mode switch conditions. Consider an arbitrary criticality $x$ . If no mode switch happens (system always stay at $1$ criticality), we can get $\widehat{c}_{k_{1},i}^{x}({k_{1}})$ for any $i$ by calculating the amount of $x$ criticality work executed in the interval $[0,i)$ . If instead, the system switch to $2$ criticality at some time $k_{2}=i^{\prime}$ , we can still get $\widehat{c}_{k_{1},i}^{x}({k_{1}})$ is still the same for any $i\leq i^{\prime}$ since $OPT^{\alpha}$ is an online scheduler and cannot look into the future to know that the mode switch will occur at time $t_{i^{\prime}}$ . Also, we can get $\widehat{c}_{k_{2},i}^{x}({k_{1},k_{2}})$ for any $t_{i}\geq k_{2}$ by calculating the amount of $x$ criticality work executed in the interval $[k_{2},i)$ . In this manner, we can run the scheduler for all mode switch possibilities and calculate a consistent $S$ . $\hfill\vartriangleleft$

It is straightforward to see that the set $S$ could be used to in our runtime schedule. Therefore, we get the following claim.

Claim 28.

If there is no solution to the linear program, then set $S$ from $OPT^{\alpha}$ must also not satisfy the LP.

We can now argue that this is impossible if $OPT^{\alpha}$ is a valid scheduler.

Lemma 29.

If set $S$ does not satisfy the linear program, then $OPT^{\alpha}$ is not a valid semi-clairvoyant scheduler.

Proof.

We can look at each constraint and check what happens if $S$ does not satisfy the constraint. If $S$ does not satisfies an inequality in (4), then there exists $j^{\prime},l^{\prime},\alpha^{\prime},x^{\prime}$ such that:

\begin{split}&\widehat{c}_{k_{\alpha^{\prime}},{j^{\prime}}}^{{x^{\prime}}}({k% _{1},\ldots,k_{\alpha^{\prime}}})+\widehat{c}_{k_{\beta-1},k_{\beta}}^{{x^{% \prime}}}({k_{1},\ldots,k_{\beta-1}})-\widehat{c}_{k_{\beta-1},{l^{\prime}}}^{% {x^{\prime}}}({k_{1},\ldots,k_{\beta-1}})\\ +&\sum_{y=\beta+1}^{{\alpha^{\prime}}}\widehat{c}_{k_{y-1},k_{y}}^{{x^{\prime}% }}({k_{1},\ldots,k_{y-1}})<\sum_{J\in S_{k_{\alpha^{\prime}},{j^{\prime}}}^{x^% {\prime}}}{e^{\alpha^{\prime}}(J)}\\ +&\sum_{y=\beta+1}^{{\alpha^{\prime}}}(\sum_{J\in S_{k_{y-1},{j^{\prime}}}^{x^% {\prime}}}{e^{y-1}(J)}-\sum_{J\in S_{k_{y},{j^{\prime}}}^{x^{\prime}}}{e^{y-1}% (J)})+\sum_{J\in S_{{l^{\prime}},{j^{\prime}}}^{x^{\prime}}}{e^{\beta-1}(J)}-% \sum_{J\in S_{k_{\beta},{j^{\prime}}}^{x^{\prime}}}{e^{\beta-1}(J)}\end{split}

On the LHS, $\widehat{c}_{k_{\beta-1},k_{\beta}}^{{x^{\prime}}}({k_{1},\ldots,k_{\beta-1}})% -\widehat{c}_{k_{\beta-1},{l^{\prime}}}^{{x^{\prime}}}({k_{1},\ldots,k_{\beta-% 1}})$ is the amount of $x^{\prime}$ work done by $OPT^{\alpha}$ in $[l^{\prime},k_{\beta})$ , $\sum_{y=\beta+1}^{{\alpha^{\prime}}}\widehat{c}_{k_{y-1},k_{y}}^{{x^{\prime}}}% ({k_{1},\ldots,k_{y-1}})$ is the amount of $x^{\prime}$ work done by $OPT^{\alpha}$ in $[k_{\beta},k_{\alpha^{\prime}})$ and $\widehat{c}_{k_{\alpha^{\prime}},t_{j^{\prime}}}^{{x^{\prime}}}({k_{1},\ldots,% k_{\alpha^{\prime}}})$ is the amount of $x^{\prime}$ work done by $OPT^{\alpha}$ in $[k_{\alpha^{\prime}},j^{\prime})$ . So, the LHS is the amount of $x^{\prime}$ work done by $OPT^{\alpha}$ in $[t_{l^{\prime}},t_{j^{\prime}})$ . On the RHS, we have: $\sum_{J\in S_{{l^{\prime}},{j^{\prime}}}^{x^{\prime}}}{e^{\beta-1}(J)}-\sum_{J% \in S_{k_{\beta},{j^{\prime}}}^{x^{\prime}}}{e^{\beta-1}(J)}$ is the amount of $x^{\prime}$ work arrives in $[t_{l^{\prime}},k_{\beta})$ that has deadline $t_{j^{\prime}}$ , $\sum_{y=\beta+1}^{{\alpha^{\prime}}}(\sum_{J\in S_{y-1,{j^{\prime}}}^{x^{% \prime}}}{e^{y-1}(J)}-\sum_{J\in S_{y,{j^{\prime}}}^{x^{\prime}}}{e^{y-1}(J)})$ is the amount of $x^{\prime}$ work arrives in $[k_{\beta},k_{\alpha^{\prime}})$ that has deadline $t_{j^{\prime}}$ , and $\sum_{J\in S_{k_{\alpha^{\prime}},{j^{\prime}}}^{x^{\prime}}}{e^{\alpha^{% \prime}}(J)}$ is the amount of $x^{\prime}$ work arrives in $[k_{\alpha^{\prime}},t_{j^{\prime}})$ that has deadline $t_{j^{\prime}}$ . So the RHS is the amount of $x^{\prime}$ work arrives after $t_{l^{\prime}}$ and has deadline $t_{j^{\prime}}$ . If $LHS<RHS$ , then $OPT^{\alpha}$ must miss the deadline of some $x^{\prime}$ criticality job that has deadline $t_{j^{\prime}}$ . Since $OPT^{\alpha}$ can schedule the system, $OPT^{\alpha}$ must satisfies (4).

If $S$ does not satisfy an inequality in (1), then there exists $j^{\prime},l^{\prime},\alpha^{\prime},x^{\prime}$ such that:

\displaystyle\widehat{c}_{k_{\alpha^{\prime}},{j^{\prime}}}^{{x^{\prime}}}({k_% {1},\ldots,k_{\alpha^{\prime}}})-\widehat{c}_{k_{\alpha^{\prime}},{l^{\prime}}% }^{{x^{\prime}}}({k_{1},\ldots,k_{\alpha^{\prime}}})<\sum_{J\in S_{{l^{\prime}% },{j^{\prime}}}^{x^{\prime}}}{e^{\alpha^{\prime}}(J)}

$\widehat{c}_{k_{\alpha^{\prime}},{j^{\prime}}}^{{x^{\prime}}}({k_{1},\ldots,k_% {\alpha^{\prime}}})-\widehat{c}_{k_{\alpha^{\prime}},{l^{\prime}}}^{{x^{\prime% }}}({k_{1},\ldots,k_{\alpha^{\prime}}})$ is the amount of $x^{\prime}$ work done by $OPT^{\alpha}$ in $[l^{\prime},j^{\prime})$ while $\sum_{J\in S_{{l^{\prime}},{j^{\prime}}}^{x^{\prime}}}{e^{\alpha^{\prime}}(J)}$ is the amount of $x^{\prime}$ work arrives after $t_{l^{\prime}}$ and has deadline $t_{j^{\prime}}$ . If $LHS<RHS$ , then $OPT^{\alpha}$ must misses the deadline of some $x^{\prime}$ criticality job that has deadline $t_{j^{\prime}}$ . Since $OPT^{\alpha}$ can schedule the system, $OPT^{\alpha}$ must satisfies (1).

If $S$ does not satisfies an inequality in (2), then there exists $j^{\prime},\alpha^{\prime},x^{\prime}$ such that:

\begin{split}\widehat{c}_{k_{\alpha^{\prime}},{j^{\prime}}}^{{x^{\prime}}}({k_% {1},\ldots,k_{\alpha^{\prime}}})+\sum_{y=1}^{{\alpha^{\prime}}-1}\widehat{c}_{% k_{y},k_{y+1}}^{{x^{\prime}}}({k_{1},\ldots,k_{y}})>\sum_{J\in S_{k_{\alpha^{% \prime}},2n-1}^{x^{\prime}}}{e^{\alpha^{\prime}}(J)}-\sum_{J\in S_{{j^{\prime}% },2n-1}^{x^{\prime}}}{e^{\alpha^{\prime}}(J)}\\ +\sum_{y=1}^{{\alpha^{\prime}}-1}(\sum_{J\in S_{k_{y},2n-1}^{x^{\prime}}}{e^{y% }(J)}-\sum_{J\in S_{k_{y+1},2n-1}^{x^{\prime}}}{e^{y}(J)})\end{split}

On the LHS, $\sum_{y=1}^{{\alpha^{\prime}}-1}\widehat{c}_{k_{y},k_{y+1}}^{{x^{\prime}}}({k_% {1},\ldots,k_{y}})$ is the amount of $x^{\prime}$ work done by $OPT^{\alpha}$ in $[0,k_{\alpha^{\prime}})$ and $\widehat{c}_{k_{\alpha^{\prime}},{j^{\prime}}}^{{x^{\prime}}}({k_{1},\ldots,k_% {\alpha^{\prime}}})$ is the amount of $x^{\prime}$ work done by $OPT^{\alpha}$ in $[k_{\alpha^{\prime}},j^{\prime})$ . So, the LHS is the amount of $x^{\prime}$ work done by $OPT^{\alpha}$ in $[0,j^{\prime})$ . On the RHS, $\sum_{y=1}^{{\alpha^{\prime}}-1}(\sum_{J\in S_{k_{y},2n-1}^{x^{\prime}}}{e^{y}% (J)}-\sum_{J\in S_{k_{y+1},2n-1}^{x^{\prime}}}{e^{y}(J)})$ is the amount of $x^{\prime}$ work arrives in $[0,k_{\alpha^{\prime}})$ and $\sum_{J\in S_{k_{\alpha^{\prime}},2n-1}^{x^{\prime}}}{e^{\alpha^{\prime}}(J)}-% \sum_{J\in S_{{j^{\prime}},2n-1}^{x^{\prime}}}{e^{\alpha^{\prime}}(J)}$ is the amount of $x^{\prime}$ work arrives in $[k_{\alpha^{\prime}},j^{\prime})$ . So, the RHS is the amount of $x^{\prime}$ work arrives before $t_{j^{\prime}}$ . By definition, LHS cannot be larger than RHS. Thus, $OPT^{\alpha}$ must satisfies (2).

If $S$ does not satisfies an inequality in (3), then there exists $i^{\prime},j^{\prime},\alpha^{\prime}$ such that:

\displaystyle\sum_{y={\alpha^{\prime}}}^{d}(\widehat{c}_{k_{\alpha^{\prime}},{% j^{\prime}}}^{y}({k_{1},\ldots,k_{\alpha^{\prime}}})-\widehat{c}_{k_{\alpha^{% \prime}},{i^{\prime}}}^{y}({k_{1},\ldots,k_{\alpha^{\prime}}}))>t_{{j^{\prime}% }}-t_{{i^{\prime}}}

LHS is the total amount of work done by $OPT^{\alpha}$ in $[t_{i^{\prime}},t_{j^{\prime}})$ while $t_{{j^{\prime}}}-t_{{i^{\prime}}}$ is the amount of time available between $t_{i^{\prime}}$ and $t_{j^{\prime}}$ . Since $OPT^{\alpha}$ can schedule this system, LHS cannot greater than RHS. Thus, $OPT^{\alpha}$ must satisfies (3).

Therefore, $OPT^{\alpha}$ must satisfies all constrains of LP, which is a contradiction. Thus, if there is no solution to the LP, the system is unschedulable. $\hfill\blacktriangleleft$

6 Related Work

Since it was first considered, mixed criticality model has been studied extensively [12, 20, 21, 13, 24, 19, 18, 9, 14, 15, 17] (see [10] for a survey). While most of this work is on recurrent tasks, there has also been significant work on jobs.

Most prior work considers the non-clairvoyant model where the system discovers the runtime mode of a job as it executes. Baruah et al. [6] developed Own Criticality Based Priority (OCBP) which provides the optimal speedup bound for jobs in the non-clairvoyant setting. Several runtime mechanisms have also been explored empirically. Baruah and Burns [3] demonstrated that it is practical to implement a MCS with run-time monitoring, which led to the formal introduction of a theoretical framework [4]. Static Mixed Criticality (SMC) and Adaptive Mixed Criticality (AMC) [4] are the continuation of OCBP by allowing run-time monitoring. Most work on mixed criticality systems considers the case where the system mode monotonically increases – as jobs arrive with higher runtime mode, the system criticality increases and lower criticality jobs are discarded, but some systems [22, 7, 8] allow systems to switch back to lower criticality mode.

In 2019, Agrawal et al. [2] introduced the notion of semi-clairvoyance that is used in this paper. Burns and Davis [11] provided an analysis of AMC algorithm in dual-criticality system with semi-clairvoyant behavior. Zhao et al [25] examine the integration of AMC, Preemption Threshold Scheduling(PTS) and semi-clairvoyance. Baruah and Ekberg [5] study graceful degradation (ensure less criticality jobs can be dropped safely during mode switch) for semi-clairvoyant systems. Jiang et al. [16] proposed the notion of quarter-clairvoyance, where execution time is revealed not when a job is released but when it is executed for a certain amount of time.

7 Conclusions

In this paper, we provide tight upper and lower bounds of $(2^{m}-1)/2^{m-1}$ on the speedup required to schedule feasible mixed criticality jobs in the semi-clairvoyant model. In addition, we provide a linear program which can (instance)-optimally schedule a system of semi-clairvoyant jobs with arbitrary criticality levels. While the running time of the LP is exponential in the number of criticalities, this seems unavoidable and is also potentially not too onerous given that the number of criticalities is typically small. We also provide EDF-Zeno, which (while not instance optimal) provides the optimal speedup bound for semi-clairvoyant jobs. While we use it as an analysis tool, it can also be used as a scheduling algorithm if one does not want to solve the linear program.

This work demonstrates the significant advantage of semi-clairvoyance over non-clairvoyance since there are functionally no nontrivial speedup bounds for non-clairvoyant schedulers for more than 2 criticality levels and solving the scheduling problem is NP-complete even for two criticality levels. This indicates that getting the information about mode switches early and at a predictable time is a significant benefit and any systems which can implement semi-clairvoyance or variants thereof should attempt to do so since it can lead to significant advantages in schedulability. In particular, there is a small marginal cost for adding additional criticality levels, which would allow system designers more flexibility in their design.

There are several open questions. First, could one either design an exact algorithm for semi-clairvoyance which runs in polynomial time in the number of jobs and criticalities or prove that it is impossible. In addition, speedup bounds for semi-clairvoyant tasks (especially non-implicit deadline tasks) has not been studied at all, to the best of our knowledge. Finally, how much can we relax semi-clairvoyance and still get optimal algorithms and good speedup bounds relative to full non-clairvoyance?

References

[1] Kunal Agrawal and Sanjoy K. Baruah. Intractability issues in mixed-criticality scheduling. In Sebastian Altmeyer, editor, 30th Euromicro Conference on Real-Time Systems, ECRTS 2018, Barcelona, Spain, July 3-6, 2018, volume 106 of LIPIcs, pages 11:1–11:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ECRTS.2018.11.
[2] Kunal Agrawal, Sanjoy K. Baruah, and Alan Burns. Semi-clairvoyance in mixed-criticality scheduling. In IEEE Real-Time Systems Symposium, RTSS 2019, Hong Kong, SAR, China, December 3-6, 2019, pages 458–468. IEEE, IEEE, 2019. doi:10.1109/RTSS46320.2019.00047.
[3] Sanjoy K. Baruah and Alan Burns. Implementing mixed criticality systems in ada. In Alexander B. Romanovsky and Tullio Vardanega, editors, Reliable Software Technologies - Ada-Europe 2011 - 16th Ada-Europe International Conference on Reliable Software Technologies, Edinburgh, UK, June 20-24, 2011. Proceedings, volume 6652 of Lecture Notes in Computer Science, pages 174–188. Springer, Springer, 2011. doi:10.1007/978-3-642-21338-0_13.
[4] Sanjoy K. Baruah, Alan Burns, and Robert I. Davis. Response-time analysis for mixed criticality systems. In Proceedings of the 32nd IEEE Real-Time Systems Symposium, RTSS 2011, Vienna, Austria, November 29 - December 2, 2011, pages 34–43. IEEE, IEEE Computer Society, 2011. doi:10.1109/RTSS.2011.12.
[5] Sanjoy K. Baruah and Pontus Ekberg. Graceful degradation in semi-clairvoyant scheduling. In Björn B. Brandenburg, editor, 33rd Euromicro Conference on Real-Time Systems, ECRTS 2021, Virtual Conference, July 5-9, 2021, volume 196 of LIPIcs, pages 9:1–9:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ECRTS.2021.9.
[6] Sanjoy K. Baruah, Haohan Li, and Leen Stougie. Mixed-criticality scheduling: Improved resource-augmentation results. In Thomas Philips, editor, Proceedings of the ISCA 25th International Conference on Computers and Their Applications, CATA 2010, March 24-26, 2010, Sheraton Waikiki Hotel, Honolulu, Hawaii, USA, pages 217–223. ISCA, 2010.
[7] Iain Bate, Alan Burns, and Robert I. Davis. A bailout protocol for mixed criticality systems. In 27th Euromicro Conference on Real-Time Systems, ECRTS 2015, Lund, Sweden, July 8-10, 2015, pages 259–268. IEEE, IEEE Computer Society, 2015. doi:10.1109/ECRTS.2015.30.
[8] Iain Bate, Alan Burns, and Robert I. Davis. An enhanced bailout protocol for mixed criticality embedded software. IEEE Trans. Software Eng., 43(4):298–320, 2017. doi:10.1109/TSE.2016.2592907.
[9] Alan Burns and Robert Davis. Mixed Criticality Systems - A Review : (13th Edition, February 2022). White Rose Research Online, February 2022.
[10] Alan Burns and Robert I. Davis. A survey of research into mixed criticality systems. ACM Comput. Surv., 50(6):82:1–82:37, 2018. doi:10.1145/3131347.
[11] Alan Burns and Robert I. Davis. Schedulability analysis for adaptive mixed criticality systems with arbitrary deadlines and semi-clairvoyance. In 41st IEEE Real-Time Systems Symposium, RTSS 2020, Houston, TX, USA, December 1-4, 2020, pages 12–24. IEEE, IEEE, 2020. doi:10.1109/RTSS49844.2020.00013.
[12] Lia Cagnizi, Federico Reghenzani, and William Fornaciari. Poster abstract: Run-time dynamic WCET estimation. In Proceedings of the 8th ACM/IEEE Conference on Internet of Things Design and Implementation, IoTDI 2023, San Antonio, TX, USA, May 9-12, 2023, IoTDI ’23, pages 458–460, New York, NY, USA, 2023. ACM. doi:10.1145/3576842.3589168.
[13] Akanksha Chaudhari and Sanjoy K. Baruah. Efficient schedulability analysis of semi-clairvoyant sporadic task systems with graceful degradation. In Yasmina Abdeddaïm, Liliana Cucu-Grosjean, Geoffrey Nelissen, and Laurent Pautet, editors, RTNS 2022: The 30th International Conference on Real-Time Networks and Systems, Paris, France, June 7 - 8, 2022, RTNS ’22, pages 116–126, New York, NY, USA, 2022. ACM. doi:10.1145/3534879.3534881.
[14] Pontus Ekberg and Wang Yi. Bounding and shaping the demand of generalized mixed-criticality sporadic task systems. Real Time Syst., 50(1):48–86, January 2014. doi:10.1007/s11241-013-9187-z.
[15] Zhishan Guo, Luca Santinelli, and Kecheng Yang. EDF schedulability analysis on mixed-criticality systems with permitted failure probability. In 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2015, Hong Kong, China, August 19-21, 2015, pages 187–196. IEEE Computer Society, 2015. doi:10.1109/RTCSA.2015.8.
[16] Zhe Jiang, Kecheng Yang, Nathan Fisher, Neil C. Audsley, and Zheng Dong. Pythia-mcs: Enabling quarter-clairvoyance in i/o-driven mixed-criticality systems. In 41st IEEE Real-Time Systems Symposium, RTSS 2020, Houston, TX, USA, December 1-4, 2020, pages 38–50. IEEE, IEEE, 2020. doi:10.1109/RTSS49844.2020.00015.
[17] Jaewoo Lee, Kieu-My Phan, Xiaozhe Gu, Jiyeon Lee, Arvind Easwaran, Insik Shin, and Insup Lee. Mc-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors. In Proceedings of the IEEE 35th IEEE Real-Time Systems Symposium, RTSS 2014, Rome, Italy, December 2-5, 2014, pages 41–52. IEEE Computer Society, 2014. doi:10.1109/RTSS.2014.32.
[18] Ruixiao Li, Fahao Chen, and Peng Li. Semi-clairvoyant scheduling of speculative decoding requests to minimize LLM inference latency. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, IJCAI ’25, pages 8554–8562. ijcai.org, 2025. doi:10.24963/ijcai.2025/951.
[19] Behnaz Ranjbar, Tuan D. A. Nguyen, Alireza Ejlali, and Akash Kumar. Power-aware runtime scheduler for mixed-criticality systems on multicore platform. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 40(10):2009–2023, 2021. doi:10.1109/TCAD.2020.3033374.
[20] Federico Reghenzani, Zhishan Guo, Luca Santinelli, and William Fornaciari. A mixed-criticality approach to fault tolerance: Integrating schedulability and failure requirements. In 28th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2022, Milano, Italy, May 4-6, 2022, pages 27–39. IEEE, 2022. doi:10.1109/RTAS54340.2022.00011.
[21] Amir Hassan Safizadeh, Sepideh Safari, Shayan Shokri, and Shaahin Hessabi. Energy-aware fault-tolerant mapping of mixed-criticality tasks on heterogeneous multicores. IEEE Trans. Sustain. Comput., 10(4):756–767, 2025. doi:10.1109/TSUSC.2025.3532766.
[22] François Santy, Gurulingesh Raravi, Geoffrey Nelissen, Vincent Nélis, Pratyush Kumar, Joël Goossens, and Eduardo Tovar. Two protocols to reduce the criticality level of multiprocessor mixed-criticality systems. In Michel Auguin, Robert de Simone, Robert I. Davis, and Emmanuel Grolleau, editors, 21st International Conference on Real-Time Networks and Systems, RTNS 2013, Sophia Antipolis, France, October 17-18, 2013, pages 183–192. ACM, 2013. doi:10.1145/2516821.2516834.
[23] Steve Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS 2007), 3-6 December 2007, Tucson, Arizona, USA, pages 239–243. IEEE, IEEE Computer Society, 2007. doi:10.1109/RTSS.2007.47.
[24] Yiwen Zhang and Hui Zheng. Energy-aware reliability guarantee scheduling with semi-clairvoyant in mixed-criticality systems. J. Syst. Archit., 156(C):103269, November 2024. doi:10.1016/j.sysarc.2024.103269.
[25] Qingling Zhao, Mengfei Qu, Bo Huang, Zhe Jiang, and Haibo Zeng. Schedulability analysis and stack size minimization for adaptive mixed criticality scheduling with semi-clairvoyance and preemption thresholds. J. Syst. Archit., 124:102383, 2022. doi:10.1016/j.sysarc.2021.102383.

[bib.bib1] [1] Kunal Agrawal and Sanjoy K. Baruah. Intractability issues in mixed-criticality scheduling. In Sebastian Altmeyer, editor, 30th Euromicro Conference on Real-Time Systems, ECRTS 2018, Barcelona, Spain, July 3-6, 2018, volume 106 of LIPIcs, pages 11:1–11:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ECRTS.2018.11.

[bib.bib2] [2] Kunal Agrawal, Sanjoy K. Baruah, and Alan Burns. Semi-clairvoyance in mixed-criticality scheduling. In IEEE Real-Time Systems Symposium, RTSS 2019, Hong Kong, SAR, China, December 3-6, 2019, pages 458–468. IEEE, IEEE, 2019. doi:10.1109/RTSS46320.2019.00047.

[bib.bib3] [3] Sanjoy K. Baruah and Alan Burns. Implementing mixed criticality systems in ada. In Alexander B. Romanovsky and Tullio Vardanega, editors, Reliable Software Technologies - Ada-Europe 2011 - 16th Ada-Europe International Conference on Reliable Software Technologies, Edinburgh, UK, June 20-24, 2011. Proceedings, volume 6652 of Lecture Notes in Computer Science, pages 174–188. Springer, Springer, 2011. doi:10.1007/978-3-642-21338-0_13.

[bib.bib4] [4] Sanjoy K. Baruah, Alan Burns, and Robert I. Davis. Response-time analysis for mixed criticality systems. In Proceedings of the 32nd IEEE Real-Time Systems Symposium, RTSS 2011, Vienna, Austria, November 29 - December 2, 2011, pages 34–43. IEEE, IEEE Computer Society, 2011. doi:10.1109/RTSS.2011.12.

[bib.bib5] [5] Sanjoy K. Baruah and Pontus Ekberg. Graceful degradation in semi-clairvoyant scheduling. In Björn B. Brandenburg, editor, 33rd Euromicro Conference on Real-Time Systems, ECRTS 2021, Virtual Conference, July 5-9, 2021, volume 196 of LIPIcs, pages 9:1–9:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ECRTS.2021.9.

[bib.bib6] [6] Sanjoy K. Baruah, Haohan Li, and Leen Stougie. Mixed-criticality scheduling: Improved resource-augmentation results. In Thomas Philips, editor, Proceedings of the ISCA 25th International Conference on Computers and Their Applications, CATA 2010, March 24-26, 2010, Sheraton Waikiki Hotel, Honolulu, Hawaii, USA, pages 217–223. ISCA, 2010.

[bib.bib7] [7] Iain Bate, Alan Burns, and Robert I. Davis. A bailout protocol for mixed criticality systems. In 27th Euromicro Conference on Real-Time Systems, ECRTS 2015, Lund, Sweden, July 8-10, 2015, pages 259–268. IEEE, IEEE Computer Society, 2015. doi:10.1109/ECRTS.2015.30.

[bib.bib8] [8] Iain Bate, Alan Burns, and Robert I. Davis. An enhanced bailout protocol for mixed criticality embedded software. IEEE Trans. Software Eng., 43(4):298–320, 2017. doi:10.1109/TSE.2016.2592907.

[bib.bib9] [9] Alan Burns and Robert Davis. Mixed Criticality Systems - A Review : (13th Edition, February 2022). White Rose Research Online, February 2022.

[bib.bib10] [10] Alan Burns and Robert I. Davis. A survey of research into mixed criticality systems. ACM Comput. Surv., 50(6):82:1–82:37, 2018. doi:10.1145/3131347.

[bib.bib11] [11] Alan Burns and Robert I. Davis. Schedulability analysis for adaptive mixed criticality systems with arbitrary deadlines and semi-clairvoyance. In 41st IEEE Real-Time Systems Symposium, RTSS 2020, Houston, TX, USA, December 1-4, 2020, pages 12–24. IEEE, IEEE, 2020. doi:10.1109/RTSS49844.2020.00013.

[bib.bib12] [12] Lia Cagnizi, Federico Reghenzani, and William Fornaciari. Poster abstract: Run-time dynamic WCET estimation. In Proceedings of the 8th ACM/IEEE Conference on Internet of Things Design and Implementation, IoTDI 2023, San Antonio, TX, USA, May 9-12, 2023, IoTDI ’23, pages 458–460, New York, NY, USA, 2023. ACM. doi:10.1145/3576842.3589168.

[bib.bib13] [13] Akanksha Chaudhari and Sanjoy K. Baruah. Efficient schedulability analysis of semi-clairvoyant sporadic task systems with graceful degradation. In Yasmina Abdeddaïm, Liliana Cucu-Grosjean, Geoffrey Nelissen, and Laurent Pautet, editors, RTNS 2022: The 30th International Conference on Real-Time Networks and Systems, Paris, France, June 7 - 8, 2022, RTNS ’22, pages 116–126, New York, NY, USA, 2022. ACM. doi:10.1145/3534879.3534881.

[bib.bib14] [14] Pontus Ekberg and Wang Yi. Bounding and shaping the demand of generalized mixed-criticality sporadic task systems. Real Time Syst., 50(1):48–86, January 2014. doi:10.1007/s11241-013-9187-z.

[bib.bib15] [15] Zhishan Guo, Luca Santinelli, and Kecheng Yang. EDF schedulability analysis on mixed-criticality systems with permitted failure probability. In 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2015, Hong Kong, China, August 19-21, 2015, pages 187–196. IEEE Computer Society, 2015. doi:10.1109/RTCSA.2015.8.

[bib.bib16] [16] Zhe Jiang, Kecheng Yang, Nathan Fisher, Neil C. Audsley, and Zheng Dong. Pythia-mcs: Enabling quarter-clairvoyance in i/o-driven mixed-criticality systems. In 41st IEEE Real-Time Systems Symposium, RTSS 2020, Houston, TX, USA, December 1-4, 2020, pages 38–50. IEEE, IEEE, 2020. doi:10.1109/RTSS49844.2020.00015.

[bib.bib17] [17] Jaewoo Lee, Kieu-My Phan, Xiaozhe Gu, Jiyeon Lee, Arvind Easwaran, Insik Shin, and Insup Lee. Mc-fluid: Fluid model-based mixed-criticality scheduling on multiprocessors. In Proceedings of the IEEE 35th IEEE Real-Time Systems Symposium, RTSS 2014, Rome, Italy, December 2-5, 2014, pages 41–52. IEEE Computer Society, 2014. doi:10.1109/RTSS.2014.32.

[bib.bib18] [18] Ruixiao Li, Fahao Chen, and Peng Li. Semi-clairvoyant scheduling of speculative decoding requests to minimize LLM inference latency. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, IJCAI ’25, pages 8554–8562. ijcai.org, 2025. doi:10.24963/ijcai.2025/951.

[bib.bib19] [19] Behnaz Ranjbar, Tuan D. A. Nguyen, Alireza Ejlali, and Akash Kumar. Power-aware runtime scheduler for mixed-criticality systems on multicore platform. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 40(10):2009–2023, 2021. doi:10.1109/TCAD.2020.3033374.

[bib.bib20] [20] Federico Reghenzani, Zhishan Guo, Luca Santinelli, and William Fornaciari. A mixed-criticality approach to fault tolerance: Integrating schedulability and failure requirements. In 28th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2022, Milano, Italy, May 4-6, 2022, pages 27–39. IEEE, 2022. doi:10.1109/RTAS54340.2022.00011.

[bib.bib21] [21] Amir Hassan Safizadeh, Sepideh Safari, Shayan Shokri, and Shaahin Hessabi. Energy-aware fault-tolerant mapping of mixed-criticality tasks on heterogeneous multicores. IEEE Trans. Sustain. Comput., 10(4):756–767, 2025. doi:10.1109/TSUSC.2025.3532766.

[bib.bib22] [22] François Santy, Gurulingesh Raravi, Geoffrey Nelissen, Vincent Nélis, Pratyush Kumar, Joël Goossens, and Eduardo Tovar. Two protocols to reduce the criticality level of multiprocessor mixed-criticality systems. In Michel Auguin, Robert de Simone, Robert I. Davis, and Emmanuel Grolleau, editors, 21st International Conference on Real-Time Networks and Systems, RTNS 2013, Sophia Antipolis, France, October 17-18, 2013, pages 183–192. ACM, 2013. doi:10.1145/2516821.2516834.

[bib.bib23] [23] Steve Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS 2007), 3-6 December 2007, Tucson, Arizona, USA, pages 239–243. IEEE, IEEE Computer Society, 2007. doi:10.1109/RTSS.2007.47.

[bib.bib24] [24] Yiwen Zhang and Hui Zheng. Energy-aware reliability guarantee scheduling with semi-clairvoyant in mixed-criticality systems. J. Syst. Archit., 156(C):103269, November 2024. doi:10.1016/j.sysarc.2024.103269.

[bib.bib25] [25] Qingling Zhao, Mengfei Qu, Bo Huang, Zhe Jiang, and Haibo Zeng. Schedulability analysis and stack size minimization for adaptive mixed criticality scheduling with semi-clairvoyance and preemption thresholds. J. Syst. Archit., 124:102383, 2022. doi:10.1016/j.sysarc.2021.102383.

Semi-Clairvoyant Scheduling for Jobs with Multiple Criticalities

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

2 Preliminaries

Mixed-Criticality Jobs.

Correctness criteria.

Clairvoyant Schedulability.

Non-clairvoyant Schedulability.

Semi-clairvoyant schedulability.

Difference between semi-clairvoyance and non-clairvoyance.

3 Lower Bound

Lemma 1.

Proof.

Lemma 2.

Proof.

4 Upper Bound

Proof Intuition

Definition of EDF-Zeno

Definition 3 (EDF-Zeno’s Lane Policy).

Definition 4 (EDF-Zeno flow control).

Observation 5.

Zipping the Job Set

Definition 6 (Zipped problem set).

Lemma 7.

Proof.

Lemma 8.

Proof.

Observation 9.

Busy Period

Theorem 10.

Definition 11 (Busy period).

Observation 12.

Lemma 13.

Proof.

Definition 14 (Bottleneck Jobs).

Lemma 15.

Proof.

Lemma 16.

Proof.

Lemma 17.

Proof.

Lemma 18.

Proof.

Defining Interference

Definition 19 (Utilities Uxy).

Observation 20.

Bounding the utilities

Lemma 21.

Proof.

Lemma 22.

Proof.

Proof.

5 Scheduling Multi-Criticality Semi-Clairvoyant Jobs Optimally

5.1 Semi-Clairvoyant Scheduling using LP

Basic Ideas and Notation

LP Constraints

Case 1.

Case 2.

Runtime scheduling

5.2 Proof of Correctness

Direction 1: LP solution can be used to schedule jobs

Observation 23.

Lemma 24.

Proof.

Base case.

Induction step.

Corollary 25.

Lemma 26.

Proof.

Direction 2: If LP fails, then the system of jobs is not semi-clairvoyantly schedulable

Claim 27.

Proof.

Definition 19 (Utilities $U_{x}^{y}$ ).