Sanjoy Baruah
email: baruah@cs.unc.edu.

Alberto Marchetti-Spaccamela

Gran G D'angelo

S Van Der Ster

L Stougie

Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems

Keywords: Algorithms Mixed criticality, sporadic task system, preemptive scheduling

Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification; the rest of the functionality is non-safety-critical and does not need to be certified, or is certified to lower levels of assurance. The certification-cognizant runtime scheduling of such mixedcriticality systems is considered. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is presented: this algorithm can schedule systems for which any number of criticality levels are defined. Efficient implementations of EDF-VD, as well as associated schedulability tests for determining whether a task system can be correctly scheduled using EDF-VD, are presented. For up to 13 criticality levels, analyses of EDF-VD, based on metrics such as processor speedup factor and utilization bounds, are derived, and conditions under which EDF-VD is optimal with respect to these metrics are identified. Finally, two extensions of EDF-VD are discussed that enhance its applicability. The extensions are aimed at scheduling a wider range of task sets, while preserving the favorable worst-case resource usage guarantees of the basic algorithm.

INTRODUCTION

In implementing safety-critical embedded systems, there is an increasing trend towards integrated computing environments, in which multiple functionalities are implemented on a shared computing platform; this trend is evident in industry-driven initiatives such as Integrated Modular Avionics (IMA) [START_REF] Prisaznuk | Integrated modular avionics[END_REF]] in aerospace and AUTOSAR (AUTomotive Open System ARchitecture -see www.autosar.org) in the automotive industry. It is often the case that not all functionalities implemented in this manner upon a shared platform are equally important (or critical) to the overall system; such systems are called mixed-criticality (MC) systems.

In some application domains, critical functionalities are subject to mandatory certification by statutory certification authorities (CAs). In conjunction with the increasing trend towards computerized control of functionalities, including non-safety-critical ones such as entertainment and comfort features, the trend towards integration of multiple functionalities upon a shared platform means that even in highly safety-critical systems, typically only a relatively small fraction of the overall system is actually of highly critical functionality and subject to certification; the rest of the system does not need to be certified, or is certified to lower levels of assurance. For instance, the RTCA DO-178B software standard specifies several different criticality levels, with the system designer expected to assign one of these criticality levels to each task -Figure 1 lists the criticality levels, and intended interpretations, that are specified in this standard.

In order to certify a system as being correct, the CA must make certain assumptions about the worst-case behavior of the system during run time. CAs tend to be very conservative and require that the safety-critical functionalities be shown to be correct at a very high level of assurance; the remaining (non-safety-critical) functionalities are usually validated correct by the system designer/ integrator at lower levels of assurance.

Worst-Case Execution Time. The worst-case execution time (WCET) abstraction plays a central role in the analysis of real-time systems. For a specific piece of code and a particular platform upon which this code is to execute, the WCET of the code denotes the maximum duration of time the code would take to execute upon the platform. Determining the exact WCET of an arbitrary piece of code is clearly a provably undecidable problem. However, even when severe restrictions are placed upon the structure of the code (e.g., loops bounds must be known at compile time), sophisticated features that are found upon the powerful processors used in embedded systems today (such as multi-level cache, deep pipelining, speculative out-of-order execution, etc.) are hard to analyze and make it extremely difficult to determine WCETs precisely. Devising analytical techniques for obtaining tight upper bounds on WCETs is currently a very active and thriving area of research, and sophisticated tools incorporating the latest results of such research have been developed (see [START_REF] Wilhelm | The worst-case execution-time problem -overview of methods and survey of tools[END_REF] for an excellent, if slightly dated, survey).

One consequence of the different levels of assurance of correctness sought by the CA and the system designer is that the same piece of code may be characterized by different WCET parameters for the purposes of certification, and for design validation. This is because different tools for determining WCET bounds may be more or less conservative than one another: a more conservative tool determines an upper bound on the actual WCET of a piece of code at a higher level of assurance than a less conservative tool. The upper bound determined by the more conservative tool is larger -sometimes by several Fig. 1. DO-178B is a software development process standard, Software Considerations in Airborne Systems and Equipment Certification, published by RTCA, Incorporated. The United States Federal Aviation Authority (FAA) accepts the use of DO-178B as a means of certifying software in avionics applications. RTCA DO-178B assigns criticality levels to tasks, categorized by effects on commercial aircraft. orders of magnitude -than the one determined by the less conservative tool. Although it may be necessary (i.e., mandated by a statutory Certification Authority) to use a very conservative tool for validating the correctness of safety-critical functionalities, less conservative tools should suffice for validating the correctness of less critical functionalities. Based on this observation, [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF] proposed that multiple different WCET values be specified, with the different values being determined at different levels of assurance. These different values are obtained by using different execution-time analysis tools; we expect that the tool used by the CA is more conservative than the one used by the system engineer, and hence the CA's WCET estimates are larger than the estimates used during the design process.

Multiple Criticality Levels. We have considered two criticality levels -needing certification, and not needing certification -in the previous discussion. However, in many safety-critical application domains, more than two criticality levels are specified; for instance, the DO-178B standard that is widely used in the avionics domain specifies five different criticality levels (A:-catastrophic/ B:-hazardous/ C:-major/ D:-minor/ E:-no effect -the adjectives denote the potential consequences of failure at the corresponding level) and mandates that each functionality be assigned one of these levels. Functionalities at higher criticality levels (A is the highest level, and E the lowest) are then subject to more rigorous validation requirements.

Context and Related Work. In traditional (e.g., not mixed-criticality) real-time systems, a sporadic task [START_REF] Mok | Fundamental design problems of distributed systems for the hard real-time environment[END_REF][START_REF] Leung | On the complexity of fixed-priority scheduling of periodic, real-time tasks[END_REF] τ i is characterized by a WCET c i , a relative deadline d i , and a period p i ; such a task generates an unbounded sequence of jobs, with successive jobs arriving at least p i time units apart, and each job needing up to c i units of execution by a deadline that occurs d i time units after the job's arrival. As already mentioned, [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF] proposed generalizing the model to mixed-criticality systems by allowing for several WCETs to be specified for each task, and studied the fixed-priority scheduling of such mixed-criticality sporadic task systems on a preemptive uniprocessor.

The preemptive uniprocessor scheduling of collections of mixed-criticality independent jobs was studied in Baruah et al. [2010aBaruah et al. [ , 2010b[START_REF] Baruah | Scheduling real-time mixed-criticality jobs[END_REF]]. An efficient scheduling algorithm and associated polynomial-time schedulability test was proposed that makes the following guarantee: any 2-level mixed-criticality system that can be scheduled by a clairvoyant exact algorithm on a given processor can be scheduled by this algorithm on a processor that is (1 + √ 5)/2 ≈ 1.618 times as fast. In [START_REF] Li | An algorithm for scheduling certifiable mixed-criticality sporadic task systems[END_REF], this result was extended to mixed-criticality sporadic task systems: a scheduling algorithm and associated pseudopolynomial-time schedulability test was proposed that gives the same guarantee. [START_REF] Guan | Effective and efficient scheduling of certifiable mixedcriticality sporadic task systems[END_REF] subsequently proposed an algorithm called PLRS that only has quadratic runtime complexity, able to schedule a wider range of instances.

Earlier work of the authors introduced the scheduling algorithm EDF-VD, that will be presented in Section 3. The idea is that higher-criticality tasks have their deadlines reduced as long as the system is in lower criticality levels, to ensure schedulability across a criticality change. Roughly, if there are two criticality levels, then high-criticality tasks have two deadlines. One deadline is defining the real deadline of the task, the other is a virtual earlier deadline that is used to increase the likelihood that EDF schedules high-criticality tasks before low-criticality ones.

Subsequently, virtual deadlines have been studied by other authors. Ekberg andYi [2012, 2014] also scale relative deadlines, but their approach is somewhat different. They extend the concept of demand bound function to the mixed-criticality setting and provide a schedulability test. Namely, in the case of two levels, they consider to what extent the deadline of each high-criticality task can be lowered without violating the schedulability condition. Since there are exponentially many possibilities, a pseudopolynomial-time heuristic is proposed that is essentially greedy. The approach has then been extended [START_REF] Ekberg | Bounding and shaping the demand of generalized mixed-criticality sporadic task systems[END_REF] assuming that criticality levels are represented by a directed acyclic graph. [START_REF] Easwaran | Demand-based scheduling of mixed-criticality sporadic tasks on one processor[END_REF] introduces a different technique for determining the virtual deadlines, which also tries to decrease the deadlines of the high-criticality tasks separately. This technique, combined with the new schedulability test, seems to be able to schedule a larger fraction of randomly generated instances than the algorithm of [START_REF] Ekberg | Bounding and shaping the demand of generalized mixed-criticality sporadic task systems[END_REF]. As observed by [START_REF] Burns | Mixed criticality systems -A Review[END_REF], it is unclear whether the approach of [START_REF] Easwaran | Demand-based scheduling of mixed-criticality sporadic tasks on one processor[END_REF] scales to more than two criticality levels. The downside of [START_REF] Easwaran | Demand-based scheduling of mixed-criticality sporadic tasks on one processor[END_REF] and Ekberg andYi [2012, 2014] is that the proposed preprocessing algorithms are not polynomial-time, no speedup bounds are provided and the authors' claim that their tests outperform EDF-VD is only supported by results on synthetic task sets. [START_REF] Su | An elastic mixed-criticality task model and its scheduling algorithm[END_REF] consider two criticality levels and a model in which low-criticality tasks can be released early. In this model they propose to exploit elastic scheduling, in which the period of a task can change. They propose a minimum service requirement for low-criticality tasks, expressed by a maximum period. The system is schedulable if the high-criticality tasks have a high-criticality execution time and for the low-criticality tasks the maximum period is considered. The intuition is to exploit the slack left by high-criticality tasks to execute the low-criticality tasks more frequently. Simulation results again show that (for certain parameters settings) an improvement over EDF-VD can be obtained. The downside of the model is that it relaxes the model of [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF] by assuming early release. We also observe that the proposal has higher overhead and it is unclear whether the approach can be effectively extended to more criticality levels.

We refer to [START_REF] Burns | Mixed criticality systems -A Review[END_REF] for an extensive survey of the research that has been conducted within the real-time scheduling community on mixed-criticality scheduling problems.

This Research. We study the scheduling of mixed-criticality sporadic task systems upon a single preemptive processor. An important special case of sporadic task systems are task systems in which each task τ i satisfies the property that d i = p i -such systems are called implicit-deadline or Liu & Layland task systems, to distinguish them from general, arbitrary-deadline task systems. We derive results for both implicitdeadline and arbitrary-deadline mixed-criticality sporadic task systems. Specifically, we propose a scheduling algorithm called EDF-VD, and establish the following.

(1) We show that any 2-level (respectively, 3-level) implicit-deadline task system that can be scheduled by a clairvoyant exact algorithm on a given processor, can be scheduled by EDF-VD on a processor that is 4/3 (respectively, 2) times as fast.

(2) We show that any K-level implicit-deadline task system that can be scheduled by a clairvoyant exact algorithm on a given processor can be scheduled by EDF-VD on a processor that is f K times as fast, where f K is the solution of a nonlinear optimization problem. Using a global nonlinear continuous optimization solver, we compute the speedup bound f K for up to 13 criticality levels.

(3) We also show that no non-clairvoyant algorithm can guarantee to always meet all deadlines on a processor that is less than 4/3 times as fast as the processor available to the clairvoyant exact algorithm, thereby proving that EDF-VD is an optimal non-clairvoyant algorithm for 2-level implicit-deadline systems from the perspective of the processor speedup metric. ( 4) For 2-level arbitrary-deadline task systems, we prove a speedup bound of 1+ √ 3/2 ≈ 1.866. That is, we show that any 2-level arbitrary-deadline task system that can be scheduled by a clairvoyant exact algorithm on a given processor can be scheduled by EDF-VD on a processor that is 1 + √ 3/2 times as fast. (5) We provide a schedulability test for EDF-VD having polynomial-time complexity, and also show that the time complexity per scheduling decision is logarithmic in the number of tasks. Based on these runtime properties, it is evident that EDF-VD, in contrast to the algorithms in Li and Baruah [2010] and [START_REF] Guan | Effective and efficient scheduling of certifiable mixedcriticality sporadic task systems[END_REF], can be considered suitable for implementation in actual systems. (6) Algorithm EDF-VD sets virtual deadlines in a uniform way for all tasks. In the case of a 2-level task system with implicit deadlines, the results in ( 1) and ( 3) show that EDF-VD has speedup 4/3 and that in the worst case a speedup of 4/3 is necessary for any algorithm. Despite this optimality result, it is of interest to investigate whether defining virtual deadlines nonuniformly might allow to schedule task sets that are not deemed schedulable by EDF-VD. We show that this is the case and present an algorithm, EDF-NUVD, that also allows scaling the deadlines nonuniformly by considering a different schedulability condition than the one used in (1). We show that, by optimizing the scaling parameters in EDF-NUVD, the resulting schedulability test recognizes a superset of the task sets schedulable by EDF-VD.

Organization. The remainder of this article is organized as follows. In Section 2, we formally describe the mixed-criticality model that we will be using in the remainder of this article. In Section 3, we consider implicit-deadline tasks; we provide a high-level description of EDF-VD (Section 3.1) and a formal analysis of its properties and behavior for implicit-deadline task sets (Sections 3.2-3.4). Then, in Section 4, we move on to analyze EDF-VD for arbitrary-deadline tasks. The efficient implementation of the runtime dispatching procedure is discussed in Section 5, while Section 6 discusses more optimistic runtime dispatching rules and analyzes how to extend EDF-VD to consider nonuniform scaling factors. We summarize our findings and conclude in Section 7.

MODEL AND DEFINITIONS

MC Task Systems. Let K ≥ 1 be an integer. A K-level MC sporadic task system τ consists of a finite collection (τ 1 , . . . , τ n ) of MC sporadic tasks. In the following, let

[n] def = {1, 2, . . . , n}. MC Tasks. An MC sporadic task τ i of a K-level system is characterized by a criticality level χ i ∈ [K] and a triple (c i ,

d i , p i ) ∈ Q χ i + × Q + × Q + , where -c i = (c i (1), c i (2), . . . , c i (χ i )
) is a vector of worst-case execution times (WCET), one for each criticality level less than or equal to χ i . We assume that c i (1)

≤ c i (2) ≤ • • • ≤ c i (χ i ).
It will be convenient to extend the definition of c i to a K-dimensional vector, by letting c i (k) = c i (χ i ) when χ i < k ≤ K; -d i is the relative deadline of the jobs of τ i ; -p i is the minimum interarrival time (or period) between two jobs of task τ i . MC Jobs. Task τ i generates a sequence of jobs (J i1 , J i2 , . . .). An MC job J ij of task τ i is characterized by two parameters:

J ij = (a ij , γ ij ), where -a ij ∈ R + is the arrival time of the job; -γ ij ∈ (0, c i (χ i )] is the execution requirement of the job; -the (absolute) deadline of job J ij is d ij def = a ij + d i .
It is important to notice that neither the arrival times nor the execution requirements are known in advance. A collection I = (a ij , γ ij ) i∈[n], j≥1 of arrival times and execution requirements is called a scenario for the task system.

The notation is summarized in Table I.

Semantics. The MC task model has the following semantics. Task τ i generates an unbounded sequence of jobs (J i1 , J i2 , . . .), with successive jobs being released at least p i time units apart. Job J ij arrives at time a ij , has a deadline at time d ij , and needs to execute for some amount of time γ ij . The value γ ij is not known in advance; it is discovered by executing the job until it signals that it has completed execution.

The values of γ ij for a given scenario of the system define the kind of behavior exhibited by the system under that scenario. The criticality level (or simply level) of a scenario is defined as the smallest integer k (1 ≤ k ≤ K) such that γ ij ≤ c i (k) for all jobs J ij . Note that such an integer always exists, since γ ij is assumed to be at most c i (χ i ).

The level of a scenario is always between 1 and K. In a scenario of level k, only the jobs from tasks of criticality at least k are required to be completed before their deadlines; all other jobs can be ignored and discarded.

In this article, we assume that there is only one processor to execute the jobs. We assume the processor to be preemptive: executing jobs may have their execution interrupted at any instant in time and resumed later, at no additional cost. Definition 2.1. A schedule for a scenario of level k is feasible if every job J ij with χ i ≥ k receives execution time γ ij during its time window [a ij , d ij ). A task system τ is (clairvoyantly) feasible if for every scenario of τ there exists a feasible schedule.

An online (or non-clairvoyant) scheduling policy for an MC task system τ discovers the criticality level of the scenario only by executing jobs. At each time instant, scheduling decisions can be based only on the partial information revealed thus far. Definition 2.2. An online scheduling policy A is correct for a feasible task system τ if for any scenario of τ the policy generates a feasible schedule. A task system τ is A-schedulable if A is a correct online scheduling policy for τ .

Notice that it is always safe to ignore jobs whose criticality is less than k whenever the scenario has already exhibited a level of at least k. The level exhibited by a scenario can only increase, or remain constant, over time.

IMPLICIT-DEADLINE TASKS

In this section, we deal with implicit-deadline task systems. This means that the period of each task equals its relative deadline: p i = d i for all i ∈ [n]. We define the utilization

c i (l) lth level WCET of τ i d i relative deadline of τ i p i period of τ i J ij jth job of τ i a ij arrival time of J ij d ij absolute deadline of J ij γ ij execution requirement of J ij of task τ i at level k as u i (k) def = c i (k) p i i = 1, . . . , n, k = 1, . . . , χ i .
Then, the total utilization at level k of tasks that are of criticality level l is

U l (k) def = i∈[n]: χ i =l u i (k) l = 1, . . . , K, k = 1, . . . , l.
For implicit-deadline systems, it is well known that, in the case of a single criticality level (i.e., K = 1), a task system is feasible on a speed-σ uniprocessor if and only if U 1 (1) ≤ σ [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. This yields the following necessary condition for feasibility in mixed-criticality systems. PROPOSITION 3.1. If τ is feasible on a unit-speed processor, then

max k=1,...,K K l=k U l (k) ≤ 1.
(1) PROOF. For each k = 1, . . . , K, consider a scenario where each task τ i with χ i ≥ k releases jobs with execution requirement c i (k).

In the sequel, we call a job active if it has been released but not yet completed. In the case of a single criticality level and a single processor, it is well known that the Earliest Deadline First (EDF) algorithm, which schedules the active job with earliest (absolute) deadline, is optimal [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF][START_REF] Dertouzos | Control robotics: The procedural control of physical processes[END_REF]]. PROPOSITION 3.2. If K = 1, then the Earliest Deadline First algorithm is a correct scheduling policy for a processor of speed σ if and only if U 1 (1) ≤ σ .

In the presence of multiple criticality levels, EDF does not necessarily produce a feasible schedule, even if the total utilization at each level is less than 1. Consider the following example.

Example 3.3. Consider a task system τ = (τ 1 , τ 2 ) with the following parameters.

τ i χ i c i (1) c i (2) p i τ 1 1 2 2 4 τ 2 2 1 5 6
Note that the total utilization at level 1 is U 1 (1) + U 2 (1) = 2/3, while at level 2 it is U 2 (2) = 5/6. However, EDF may fail to meet deadlines, as follows: Assume jobs are released as early as possible. At time 0, EDF schedules the first job of τ 1 . At time 2, the job finishes and EDF starts running the first job of τ 2 . However, if it turns out that this job exhibits level-2 behavior, it will execute for five time units and miss its deadline at time 6. If we had started the other way around, either the first job of τ 2 would have finished after one time unit and there would have been enough time to schedule the job from τ 1 , or the scenario would have exhibited level-2 behavior and we could have discarded the job from τ 1 .

The scheduling algorithm that we propose is called EDF with Virtual Deadlines (EDF-VD) and is an adaptation of EDF that handles the problem sketched previously, while maintaining some of the desirable properties of EDF. In the remainder of this section, we first introduce the algorithm EDF-VD and give a corresponding schedulability condition for a system of K criticality levels. Then, we assess the quality of the algorithm using the notion of speedup factor.

Overview of EDF-VD for Implicit-Deadline Tasks

Let τ denote the MC implicit-deadline sporadic task system that is to be scheduled on a unit-speed preemptive processor. Algorithm EDF-VD consists of an offline preprocessing phase and a runtime scheduling phase. The first phase is performed prior to runtime and executes a schedulability test to determine whether τ can be successfully scheduled by EDF-VD or not. If τ is deemed schedulable, this phase also provides two output values that will serve as input for the runtime scheduling algorithm: an integer parameter k (with 1 ≤ k ≤ K); and, for each task τ i of τ , a parameter di , called virtual deadline, which is never larger than d i . The second phase performs the actual runtime scheduling and consists of K variants, called EDF-VD(1), EDF-VD(2), . . . , EDF-VD(K). Each of these is related to a different value of the parameter k that was provided by the first phase; that is, at runtime, the variant EDF-VD(k) is applied. Intuitively, if the scenario is exhibiting a level smaller than or equal to k, then jobs are scheduled according to EDF with respect to the virtual deadlines ( di ) n i=1 . As soon as the scenario exhibits a level greater than k, jobs are scheduled according to EDF with respect to the original deadlines (d i ) n i=1 . In the following, we give more details on the two phases.

Offline Preprocessing Phase. The algorithm for the first phase is given in pseudocode form in Algorithm 1. If K l=1 U l (l) ≤ 1, then all jobs can be scheduled for their worstcase execution times at their own criticality level. Therefore, in this case, the virtual deadlines of all the tasks are set to be equal to the original deadlines (see lines 1-5). Otherwise, at line 7, we test whether there exists a 1 ≤ k ≤ K satisfying condition (3), which is given in Section 3.2 along with its correctness proof. If no such k exists, then τ is deemed unschedulable (line 9). If there exists a k satisfying condition (3), then the virtual deadlines of all tasks having criticality level 1, . . . , k are set to be equal to the original deadlines (line 14), while those of tasks having criticality level k + 1, . . . , K are scaled by a factor x (line 16). The value of x is specified at line 11 and will be explained later in Section 3.2. Note that if condition (3) is satisfied, then x is well defined. Moreover, since K l=1 U l (l) > 1, then x < 1.

ALGORITHM 1: EDF with Virtual Deadlines (EDF-VD) -Offline preprocessing phase (for implicit-deadline task systems) Input: task system τ = (τ 1 , . . . , τ n ) to be scheduled on a unit-speed preemptive processor

1: if K l=1 U l (l) ≤ 1 then 2: k ← K 3: for i = 1, 2, . . . , n do 4: di ← d i 5:
end for 6: else

7: Let k (1 ≤ k < K) be such that (3) holds 8: if no such k exists then 9: return unschedulable 10: else 11: Let x ∈ K l=k+1 U l (k) 1-k l=1 U l (l) , 1-K l=k+1 U l (l) k l=1 U l (l)
12:

for i = 1, 2, . . . ,
end if 20: end if 21: return (schedulable, k, ( di ) n i=1 )
Runtime Scheduling Phase. A pseudocode describing the runtime phase is given in Algorithm 2. The function current_level() returns the level exhibited by the scenario so far, that is,

current_level() = min{l ∈ [K] : γij ≤ c i (l) for all jobs J ij (partially) executed so far},
where γij is the part of γ ij that has been observed thus far. (When current_level() = l, we also say that the system is in level l.)

Algorithm 2 takes as input the integer k and the virtual (relative) deadlines di computed during the preprocessing phase. As long as the system is in level 1, 2, . . . , k, the tasks having level greater than or equal to current_level() are scheduled according to EDF with respect to these virtual deadlines, while tasks of level smaller than current_level() are discarded (lines 1-5). When the system is observed to reach a level greater than k, all jobs from tasks of criticality k or below are discarded and the original deadlines of the tasks of criticality k + 1 and higher are restored. The priority ordering of the jobs that are active at the time when the system turns to a level greater than k is computed according to the original deadlines at lines 6-7 and the jobs are scheduled accordingly. From this moment onwards, EDF is applied to all the tasks having level greater than or equal to current_level() (lines 9-14). Note that if k = K, then Algorithm 2 is simply EDF, as no scaling of the deadlines occurs in Algorithm 1.

The efficient implementation of Algorithm 2 is discussed in Section 5. Note that once the parameter k is fixed, when applying EDF-VD(k), the criticality levels are divided into two sets, where the levels in the same set are treated homogeneously, as if there were only two levels. The parameter k determines the boundary between these two sets.

ALGORITHM 2: EDF with Virtual Deadlines (EDF-VD) -Runtime scheduling schedule the active job, among the tasks τ i such that χ i ≥ current level(), having earliest absolute deadline (ties broken arbitrarily) 14: end loop

Input: task system τ = (τ 1 , . . . , τ n ), integer k (1 ≤ k ≤ K), virtual deadlines ( di )

Schedulability Conditions

THEOREM 3.4. Given an implicit-deadline task system τ , if either

K l=1 U l (l) ≤ 1 ( 2 )
or, for some k (1 ≤ k < K), the following condition holds:

1 - k l=1 U l (l) > 0 and K l=k+1 U l (k) 1 -k l=1 U l (l) ≤ 1 -K l=k+1 U l (l) k l=1 U l (l) , ( 3
)
then τ can be correctly scheduled by EDF-VD.

PROOF. If condition (2) holds, then all jobs can be scheduled for their worst-case execution times at their own criticality level. Hence, EDF-VD(K), that is, EDF without deadline scaling, will yield a correct schedule. Therefore, from here on, the proof focuses on the case that (2) does not hold and (3) holds for some k < K.

The proof consists of two steps. In the first step, we show that if there is an x ≤ 1 such that the following two inequalities hold:

k l=1 U l (l) + K l=k+1 U l (k) x ≤ 1 ( 4 ) x k l=1 U l (l) + K l=k+1 U l (l) ≤ 1, (5)
then EDF-VD(k) is a correct scheduling policy for τ .

In the second step, we show that if (3) holds for some k < K, then there exists x ≤ 1 such that (4) and ( 5) hold. We discuss later in this section how the scaling parameter x is determined . For the first step , we determine an upper bound on the "virtual utilization"; the utilization of the system as long as the virtual deadlines are applied, if EDF-VD(k) is the scheduling algorithm we apply. We will slightly abuse notation and write pi for the "virtual period" that equals the virtual deadline di for all tasks τ i , in order to define the "virtual utilization." Assume for all tasks τ i with χ i at most k, that all jobs are executed at their own-criticality execution requirement. For all tasks τ i with χ i > k, the jobs are executed at criticality level k. This clearly gives an upper bound on the utilization for as long as the system is in criticality levels 1, 2, . . . , k. Also note that by this assumption, no complications can occur at criticality changes before level k + 1 is reached. The "virtual utilization" of this task system in levels 1, 2, . . . , k is at most

Û (k) := i∈[n] c i (k) pi = i∈[n] c i (k) di = i∈[n]: χ i ≤k c i (χ i ) d i + i∈[n]: χ i >k c i (k) xd i = i∈[n]: χ i ≤k c i (χ i ) p i + i∈[n]: χ i >k c i (k) xp i = k l=1 U l (l) + K l=k+1 U l (k) x .
Note that a sufficient condition for correctness in levels 1, 2, . . . , k is that Û (k) ≤ 1. Hence, we find that (4) ensures correctness in levels 1, 2, . . . , k.

For any level l > k, assume by contradiction that a deadline miss occurs in some scenario. We bound the execution requirement of all tasks until the time of the first deadline miss, which is denoted by t f . Let I denote a minimal collection of jobs released by τ on which a deadline is missed (by minimal, we mean that EDF-VD(k) would meet all deadlines if scheduling any proper subset of I). We assume that (4) and (5) hold and, without loss of generality, that the first job arrival is at time zero. Hence, the job that misses a deadline is of level l > k, because at time t f the system is at least in level k + 1. Let t * denote the time where behavior of level k + 1 is first exhibited. CLAIM 3.5. All jobs receiving execution in [t * , t f ) have deadlines at most t f . PROOF. Suppose there is a job that has deadline larger than t f and receives some execution between t * and t f , say in the interval [t 1 , t 2 ). This means that during [t 1 , t 2 ) there are no jobs pending with deadline at most t f . Then, the set of jobs obtained by considering only jobs with arrival time at least t 2 will also miss a deadline at t f , which contradicts the assumed minimality of I.

We define the quantity η i (t) as the cumulative execution requirement of jobs of task τ i until time t and derive upper bounds for it, for all tasks. Among all jobs executing in [t * , t f ), let J 0 be the job with the earliest arrival time. Denote by a 0 its arrival time and by d 0 its absolute deadline. CLAIM 3.6. For any task τ i having χ i ≤ k, it holds that

η i (t f ) ≤ (a 0 + x(t f -a 0 ))u i (χ i ).
PROOF. Note that no job of τ i will receive execution after t * . If such a job executes after a 0 , it must have a deadline no larger than the virtual deadline of J 0 , which is a 0 + x(d 0 -a 0 ). Since t f ≥ d 0 by Claim 3.5, this means that no job of task τ i with deadline greater than a 0 + x(t fa 0 ) will execute after a 0 .

Suppose now that a job with χ i ≤ k and deadline larger than a 0 + x(t fa 0 ) was executed for some time before a0. Let tl denote the latest instant at which any such job executes. This means that at this instant, there were no jobs with absolute deadline at most a 0 + x(t fa 0 ) awaiting execution. Hence, the set of jobs obtained by considering only those jobs in I that have arrival time at least t l also misses a deadline. This contradicts the assumed minimality of I.

This implies that there are at most (a 0 + x(t fa 0 ))/ p i jobs of τ i until time t f ; each of them requires an execution time of at most c i (χ i ). Therefore, the total execution requirement of τ i is bounded by (a 0 + x(t fa 0 ))u i (χ i ).

CLAIM 3.7. Any task τ i with χ i > k has

η i (t f ) ≤ a 0 x u i (k) + (t f -a 0 )u i (χ i ).
PROOF. We distinguish two cases. Case 1. Task τ i Does not Release a Job at or after a 0 . Each job of τ i has a virtual deadline of at most a 0 + x(t fa 0 ). Otherwise, consider a job with a larger virtual deadline and let t l denote the latest time instant at which this job executes. The job sequence consisting of only those jobs with an arrival time larger than t l also misses a deadline and this is in contradiction with the assumed minimality of I. Hence, each job of τ i has an actual deadline of at most a 0 /x + t fa 0 and there are at most

a 0 /x+t f -a 0 p i
of them. Since these jobs do not execute in [t * , t f ) (else, J 0 would not be the one with earliest release), the execution requirement per job is at most c i (k). Combining these observations, we bound the execution requirement of jobs from task τ i by

a 0 x + t f -a 0 c i (k) p i = a 0 x u i (k) + (t f -a 0 )u i (k) ≤ a 0 x u i (k) + (t f -a 0 )u i (χ i ).
Case 2. Task τ i Releases One or More Jobs at or after a 0 . Let a i denote the first release of a job from τ i greater than or equal to a 0 . The previously released job of τ i did not execute in [t * , t f ), by definition of a i and a 0 . Therefore, it is safe to assume that until a i the execution requirement per job from τ i was bounded by c i (k) and after that it is bounded by c i (χ i ). Hence, the cumulative requirement of all jobs from τ i is bounded by

a i u i (k) + (t f -a i )u i (χ i ) ≤ a 0 u i (k) + (t f -a 0 )u i (χ i ) ≤ a 0 x u i (k) + (t f -a 0 )u i (χ i ),
where the first inequality comes from the facts that a 0 ≤ a i and u i (k) ≤ u i (χ i ) and the second one from x ≤ 1.

Summing the cumulative requirements over all tasks gives

i:χ i ≤k η i (t f ) + i:χ i >k η i (t f ) ≤ i:χ i ≤k (a 0 + x(t f -a 0 ))u i (χ i ) + i:χ i >k a 0 x u i (k) + (t f -a 0 )u i (χ i ) = a 0 k l=1 U l (l) + K l=k+1 U l (k) x + (t f -a 0 ) x k l=1 U l (l) + K l=k+1 U l (l) ≤ a 0 + (t f -a 0 ) x k l=1 U l (l) + K l=k+1 U l (l) ,
where the last inequality comes from the assumption that (4) holds. The assumed deadline miss implies

a 0 + (t f -a 0 ) x k l=1 U l (l) + K l=k+1 U l (l) > t f ⇔ (t f -a 0 ) x k l=1 U l (l) + K l=k+1 U l (l) > t f -a 0 ⇔ x k l=1 U l (l) + K l=k+1 U l (l) > 1.
But this directly contradicts (5). Now that we have shown that ( 4) and ( 5) are sufficient for the correctness of EDF-VD(k), it remains to show that if (3) holds, then (4) and ( 5) also hold. Rewriting (4) gives

k l=1 U l (l) + K l=k+1 U l (k) x ≤ 1 ⇔ x k l=1 U l (l) + K l=k+1 U l (k) ≤ x ⇔ K l=k+1 U l (k) ≤ x 1 - k l=1 U l (l) ⇔ K l=k+1 U l (k) 1 -k l=1 U l (l) ≤ x, ( 6
)
where in the last step we used that 1 -k l=1 U l (l) > 0. Rewriting (5) gives

x k l=1 U l (l) + K l=k+1 U l (l) ≤ 1 ⇔ x k l=1 U l (l) ≤ 1 - K l=k+1 U l (l) ⇔ x ≤ 1 -K l=k+1 U l (l) k l=1 U l (l) . ( 7
)
Hence, if (3) holds, there must exist an x that satisfies both ( 6) and ( 7). This concludes the proof of Theorem 3.4. Note that any x satisfying ( 6) and ( 7) suffices as a scaling parameter.

Speedup Bounds

Between the sufficient condition for schedulability given by (3) and the necessary condition (1), there is a gap. To analyze this gap, we consider a task system satisfying the necessary condition given in (1) and determine how much faster the processor should be to correctly schedule the task set by EDF-VD.

The speedup factor of a scheduling algorithm A is the smallest real number f such that any task system τ that is feasible on a unit-speed processor (in the sense of Definition 2.1) is correctly scheduled by A on a speed-f processor. The speedup factor is a convenient metric for comparing the worst-case behavior of different algorithms for solving the same problem: the smaller the speedup factor, the closer the behavior of the algorithm to that of a clairvoyant exact algorithm.

We show how to derive tight speedup bounds for EDF-VD for any number K of criticality levels. When K equals 2 or 3, we analytically derive closed-form expressions for the speedup bounds. When K > 3, the computation of the speedup bound is an analytically challenging problem; we solve it numerically for all K ≤ 13.

3.3.1. Two Levels THEOREM 3.8. If a 2-level task system τ satisfies max{U 1 (1) + U 2 (1), U 2 (2)} ≤ 1,
then EDF-VD correctly schedules τ on a processor of speed 4/3. In particular, if τ is schedulable on a unit-speed processor, then it is EDF-VD-schedulable on a processor of speed 4/3. PROOF. For a 2-level system, the schedulability condition (3) is

U 2 (1) 1 -U 1 (1) ≤ 1 -U 2 (2) U 1 (1) , ( 8
)
and 1 -U 1 (1) > 0. To prove the claim, we find the largest q such that, if

U 1 (1) + U 2 (1) ≤ q (9) U 2 (2) ≤ q,
then the sufficient condition (8) still holds. The required speedup then equals 1/q. Note that since U 2 (2) only appears with a negative sign on the right-hand side of (8) and U 2 (1) only appears on the left-hand side, the worst case in terms of tightness of the condition is that U 2 (2) = q and U 2 (1) = q -U 1 (1). Henceforth, this assumption is made. Further, we define y def = 1q. Then, sufficient condition (8) becomes

1 -y -U 1 (1) 1 -U 1 (1) ≤ y U 1 (1) . ( 10
)
This condition is satisfied if and only if U 1 (1) 2 -U 1 (1) + y ≥ 0 (here we used 1 -U 1 (1) > 0). This inequality holds for all U 1 (1) ∈ [0, 1) if and only if y ≥ 1/4. Hence, the largest q such that (9) implies ( 8) is q * = 3/4, and the required speedup is 1/q * = 4/3. The second part of the statement follows from the first and Proposition 3.1.

Three Levels

THEOREM 3.9. If a 3-level task system τ satisfies

max k=1,2,3 K l=k U l (k) ≤ 1, ( 11
)
then EDF-VD correctly schedules τ on a processor of speed 2. In particular, if τ is feasible on a unit-speed processor, then it is EDF-VD-schedulable on a processor of speed 2.

PROOF. We recall the schedulability conditions for a 3-level system from (3) for i = 1, 2:

U 2 (1) + U 3 (1) 1 -U 1 (1) ≤ 1 -U 2 (2) -U 3 (3) U 1 (1) (12) U 3 (2) 1 -U 1 (1) -U 2 (2) ≤ 1 -U 3 (3) U 1 (1) + U 2 (2) , ( 13
)
where for (12) we also assume that 1 -U 1 (1) > 0 and for (13) that 1 -U 1 (1) -U 2 (2) > 0.

We find the speedup in a similar way as in Section 3.3.1. That is, we search for the largest q, such that if

U 1 (1) + U 2 (1) + U 3 (1) ≤ q U 2 (2) + U 3 (2) ≤ q U 3 (3) ≤ q
hold, then at least one of the inequalities in ( 12) and ( 13) holds. Note that the worstcase speedup is obtained when the previous inequalities hold with equality. To see this, we reason as follows.

The term U 3 (3) only appears in the right-hand side of ( 12) and ( 13) and the expressions are monotonically decreasing in U 3 (3). Hence, the worst case (lowest right-hand side value) is when

U 3 (3) is largest, that is, U 3 (3) = q.
Since U 3 (2) appears only in the left-hand side of ( 13) and this side is monotonically increasing in U 3 (2), the worst-case is if

U 3 (2) = q -U 2 (2).
Since U 2 (1) and U 3 (1) appear only in the left-hand side of ( 12) and this side is monotonically increasing in U 2 (1) +U 3 (1), the worst-case is if U 2 (1) +U 3 (1) = q -U 1 (1). Now we substitute these expressions in the inequalities ( 12) and ( 13) to obtain the following two conditions

q -U 1 (1) 1 -U 1 (1) ≤ 1 -q -U 2 (2) U 1 (1) q -U 2 (2) 1 -U 1 (1) -U 2 (2) ≤ 1 -q U 1 (1) + U 2 (2)
.

In these two equations, we substitute y def = 1q, and after rewriting we find

(1 -U 1 (1))(U 1 (1) + U 2 (2)) ≤ y (1 -U 2 (2))(U 1 (1) + U 2 (2)) ≤ y.
It is easily verified that the minimum of these two left-hand sides attains its maximum value when U 1 (1) = U 2 (2). After substituting, we obtain

2U 1 (1) 2 -2U 1 (1) + y ≥ 0.
This inequality holds for all U 1 (1) ∈ [0, 1) if and only if y ≥ 1/2, which gives q * = 1/2; the resulting speedup bound is therefore 2. Again, the second part of the claim follows from the first and Proposition 3.1.

Arbitrary Number of Levels.

The problem of determining the minimum speedup factor f K such that any K-level task system that is feasible on an unit-speed processor is correctly scheduled by EDF-VD on a f K -speed processor can be formulated as follows: Find the largest q (q ≤ 1) such that the following implication holds for all U l (k),

k = 1, 2, . . . , K, l = k, k + 1, . . . , K: K l=k U l (k) ≤ q ∀k = 1, 2, . . . , K ⇒ either K l=1 U l (l) ≤ 1 or ∃k ∈ {1, 2, . . . , K -1} s.t. ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 - k l=1 U l (l) > 0 and K l=k+1 U l (k) 1-k l=1 U l (l) ≤ 1-K l=k+1 U l (l) k l=1 U l (l) .
If the largest such value of q is q * , the speedup factor is then f K = 1/q * . Equivalently, we want to find the smallest q such that this implication does not hold, that is, the premise is true but the conclusion is false; in other words, the largest value of the speedup for which one can still construct a counterexample. This leads to the following formulation:

min q (NLP) s.t. K l=k U l (k) ≤ q ∀k = 1, 2, . . . , K; K l=1 U l (l) > 1 ¬ 1 - k l=1 U l (l) > 0 ∧ K l=k+1 U l (k) 1 -k l=1 U l (l) ≤ 1 -K l=k+1 U l (l) k l=1 U l (l) ∀k = 1, 2, . . . , K -1.
Formulation (NLP) involves disjunctions (the negated conjunctions in the last set of constraints), which are typically disallowed by numerical solvers. We prove that solving (NLP) is equivalent to finding q * def = min j=1,2,...,K-1 q * j , where each q * j is the solution to the following nonlinear program:

q * j = min q j (NLP j ) s.t. K l=k U l (k) ≤ q j ∀k = 1, 2, . . . , K; K l=1 U l (l) > 1 K l=k+1 U l (k) 1 -k l=1 U l (l) > 1 -K l=k+1 U l (l) k l=1 U l (l) ∀k = 1, 2, . . . , j; 1 - j l=1 U l (l) > 0 1 - j+1 l=1 U l (l) ≤ 0.
We denote the constraints of these nonlinear programs as follows:

C def = K l=k U l (k) ≤ q ∀k = 1, 2, . . . , K ∧ K l=1 U l (l) > 1 , A k def = K l=k+1 U l (k) 1 -k l=1 U l (l) ≤ 1 -K l=k+1 U l (l) k l=1 U l (l) , B k def = 1 - k l=1 U l (l) > 0 ,
for each k = 1, 2, . . . , K -1. Then, the constraints of program (NLP) can be written as

C ∧ K-1 k=1 ¬ (Ak ∧ B k) ,
while those of program (NLP j ) can be written as

C ∧ j k=1 ¬A k ∧ B j ∧ ¬B j+1 .
The equivalence is shown in the next lemma.

LEMMA 3.10. For any K-level feasible task system, the set of values U l (k

), k = 1, 2, . . . , K, l = k, k + 1, . . . , K satisfies C ∧ K-1 k=1 ¬ ( A k ∧ B k) ( 14
)
if and only if it satisfies

K-1 j=1 C ∧ j k=1 ¬A k ∧ B j ∧ ¬B j+1 . ( 15
)
PROOF. First, observe that condition B j implies condition B j for any j < j and that condition C implies condition ¬B K . Moreover, condition B 1 holds since the task system is assumed feasible. Therefore, for K = 2, conditions ( 14) and ( 15) are both equivalent to C ∧ ¬A 1 .

By induction, let us assume that conditions ( 14) and ( 15) are equivalent for task systems of K -1 levels. We rewrite conditions ( 14) and ( 15) for K-level systems as follows, respectively:

¬ (AK-1 ∧ B K-1) ∧ C ∧ K-2 k=1 ¬ (Ak ∧ B k) (14')
and

C ∧ K-1 k=1 ¬A k ∧ B K-1 ∧ ¬B K ∨ K-2 j=1 C ∧ j k=1 ¬A k ∧ B j ∧ ¬B j+1 = C ∧ K-1 k=1 ¬A k ∧ B K-1 ∨ K-2 j=1 C ∧ j k=1 ¬A k ∧ B j ∧ ¬B j+1 . ( 15

')

We distinguish the cases that B K-1 does and does not hold. If B K-1 holds, then B j holds for each j = 1, 2, . . . , K -1. It follows that (14') and (15') are equivalent to If B K-1 does not hold, the two conditions are equivalent to

C ∧ K-1 k=1 ¬A k .
C ∧ K-2 k=1 ¬ (Ak ∧ B k) and K-2 j=1 C ∧ j k=1 ¬A k ∧ B j ∧ ¬B j+1 ,
respectively, and the lemma holds by the inductive hypothesis.

We solve program (NLP j ), for each j = 1, 2, . . . , K -1, to find the minimum speedup factor f K = 1/q * , where q * = min j=1,2,...,K-1 q * j . After clearing the denominators in program (NLP j ), we obtain a system of multivariate polynomial inequalities in the variables U l (k) and q j . As such, it can be solved by a (numerical) global nonlinear continuous optimization solver. In this case, we used COUENNE [START_REF] Belotti | Branching and bounds tightening techniques for non-convex MINLP[END_REF]. COUENNE was able to find the optimum for any K ≤ 13. The resulting speedup factors are reported in Table II. THEOREM 3.11. Let τ be a K-level task system with 2 ≤ K ≤ 13. If τ is feasible on a unit-speed processor, then it is EDF-VD-schedulable on a processor of speed f K , where f K (±10 -4 ) is as in Table II.

Optimality of EDF-VD for Two Levels

We now show that -at least in the case of 2-level implicit-deadline systems -EDF-VD is an optimal algorithm in terms of the speedup factor metric. THEOREM 3.12. No non-clairvoyant algorithm for scheduling 2-level implicitdeadline sporadic task systems can have a speedup bound better than 4/3. PROOF. Consider the example task system τ = (τ 1 , τ 2 ), with the following parameters, where is an arbitrary small positive number.

τ i χ i c i (1) c i (2) p i τ 1 1 1+ 1 + 2 τ 2 2 1+ 3
This system is feasible according to Definition 2.1: EDF would meet all deadlines in scenarios of level 1 (since U 1 (1) + U 2 (1) ≤ 1), while only jobs of τ 2 would get to execute in scenarios of level 2 (and U 2 (2) ≤ 1).

To see that τ cannot be scheduled correctly on a unit-speed processor by any online scheduler, suppose both tasks were to generate jobs simultaneously. It need not be revealed prior to one of the jobs receiving (1 + ) units of execution, whether the level of the scenario is 1 or 2. We consider two cases.

(1) τ 1 's job receives (1 + ) units of execution before τ 2 's job does. In this case, the scenario is revealed to be of level 2. But now there is not enough time remaining for τ 2 's job to complete by its deadline at time instant 4. (2) τ 2 's job receives (1 + ) units of execution before τ 1 's job does. In this case, the scenario is revealed to be of level 1, in that τ 2 's job signals that it has completed execution. But then, there is not enough time remaining for τ 1 's job to complete by its deadline at time 2.

We have thus shown that no non-clairvoyant algorithm can correctly schedule τ . The theorem follows, based on the observation that max(U 1 (1) + U 2 (1), U 2 (2)) exceeds 3/4 by an arbitrarily small amount.

The optimality of EDF-VD for 2-level implicit-deadline task systems follows by combining the analysis in this example with Theorem 3.8. A speedup bound of 4/3 holds for EDF-VD and, by the previous argument, a lower speedup is not possible for any non-clairvoyant algorithm.

ARBITRARY-DEADLINE TASKS

We now study the case in which deadlines do not necessarily equal periods of the corresponding tasks (arbitrary deadlines). In this section, we only consider task systems that consist of two criticality levels.

Overview of EDF-VD for Arbitrary-Deadline Tasks

In the case that deadlines are independent of the periods, the notion of utilization is insufficient to characterize schedulability. In conventional real-time scheduling theory, the notion of load takes this role. The load of a collection of jobs denotes the maximum, over all time intervals, of the cumulative execution requirement by jobs of the scenario due in the interval, divided by the interval length. Informally speaking, the load of a scenario represents the minimum speed of any processor that can meet all deadlines in that scenario.

Recall that a sporadic task system τ can generate infinitely many different scenarios. Each scenario I can be seen as a collection of independent jobs, where the arrival time of job J ij of task τ i is a ij and its absolute deadline is d ij = a ij + d i . Then, for a scenario I of a mixed-criticality system, we can define three notions of load, analogous to the aforementioned concept.

Definition 4.1. The load λ(I), the level-1 load λ 1 (I) and the level-2 load λ 2 (I) of a mixed-criticality scenario I with two criticality levels are defined according to the following three formulas:

λ(I) def = max 0≤t 1 <t 2 J ij ∈I: t 1 ≤a ij ∧ d ij ≤t 2 c i (χ i ) t 2 -t 1 λ 1 (I) def = max 0≤t 1 <t 2 J ij ∈I: t 1 ≤a ij ∧ d ij ≤t 2 c i (1) t 2 -t 1 λ 2 (I) def = max 0≤t 1 <t 2 J ij ∈I: χ i =2 ∧ t 1 ≤a ij ∧ d ij ≤t 2 c i (2) t 2 -t 1 .
Informally, λ(I) bounds the load of the scenario in the absence of any prior information; λ 1 (I) bounds the load when the level of the scenario is a priori known to be 1 (i.e., no job exceeds its level 1 WCET); and λ 2 (I) bounds the load when the level of the scenario is a priori known to be 2. In particular, λ 2 (I) disregards the tasks with χ i = 1.

The load λ(τ ) of a task system τ is defined to be the largest value that λ(I) can have, over any scenario I generated by τ . We define λ 1 (τ ) and λ 2 (τ ) similarly. For any task system τ , the values λ(τ ), λ 1 (τ ) and λ 2 (τ ) can be computed by determining the loads of "regular" (i.e., non-MC) sporadic task systems. Namely, λ(τ ), λ 1 (τ ) and λ 2 (τ ) are, respectively, the loads of regular sporadic task systems

{(c i (χ i ), d i , p i )|τ i ∈ τ }, {(c i (1), d i , p i )|τ i ∈ τ } and {(c i (2), d i , p i )|τ i ∈ τ ∧ χ i = 2}.
The values λ(τ ), λ 1 (τ ), λ 2 (τ ) can either be computed exactly, or they can be efficiently approximated with arbitrarily small error, using well-known techniques (see, e.g., [START_REF] Baruah | Feasibility problems for recurring tasks on one processor[END_REF] and [START_REF] Albers | An event stream driven approximation for the analysis of real-time systems[END_REF]). In the sequel, it will be convenient to abbreviate λ(τ ), λ 1 (τ ) and λ 2 (τ ) to λ, λ 1 and λ 2 , respectively.

The synchronous arrival sequence of τ is the job sequence in which each task τ i generates its jth job at time a ij = ( j -1) p i . It is well known [START_REF] Baruah | Feasibility problems for recurring tasks on one processor[END_REF]] that, on a preemptive uniprocessor, the largest demand of a non-MC sporadic task set over any time interval is achieved by the synchronous arrival sequence; this is one of the key facts used when computing the load.

The following immediate observation gives a necessary condition for any scheduling algorithm to be correct for a 2-level task system. PROPOSITION 4.2. Let τ be a 2-level task system. If λ 1 > 1 or λ 2 > 1, then τ is not feasible.

A relationship between the three loads is given in the next observation, which follows immediately from the definitions. PROPOSITION 4.3. Let τ be a 2-level task system. Then λ ≤ λ 1 + λ 2 .

We consider the EDF-VD algorithm for scheduling a sporadic MC system with arbitrary deadlines. As in the case of implicit-deadline task systems, EDF-VD consists of two phases: an offline preprocessing phase and a runtime scheduling phase. The runtime scheduling is exactly as in Algorithm 2 (with K = 2). The offline preprocessing phase test is, however, somewhat modified as it is based on a different schedulability test.

We give here an overview of the preprocessing phase, which is described exactly in Algorithm 3, whereas details and justifications are given in Section 4.2. We start by computing λ, λ 1 , λ 2 at line 1 -either exactly, as in [START_REF] Baruah | Feasibility problems for recurring tasks on one processor[END_REF], or more efficiently but approximately using, for example, the approach in [START_REF] Albers | An event stream driven approximation for the analysis of real-time systems[END_REF]. To facilitate the exposition, we work with the exact values of λ, λ 1 and λ 2 , keeping in mind that we may have only approximate values for them -we revisit this issue in Section 4.4.

Since there are only two criticality levels, there are only two different cases. If λ ≤ 1, then the deadlines are not scaled and the runtime algorithm will coincide with EDF (lines 2-6). Otherwise, a certain condition involving λ 1 and λ 2 is checked at line 8; if the condition does not hold, the schedulability test reports a failure (line 9). If the condition holds, modified deadlines are computed based on an appropriately chosen ALGORITHM 3: EDF with Virtual Deadlines (EDF-VD) -Offline preprocessing phase (for arbitrary-deadline task systems) Input: task system τ = (τ 1 , . . . , τ n ) to be scheduled on a unit-speed preemptive processor

1: Compute λ, λ 1 , λ 2 2: if λ ≤ 1 then 3: k ← 2 4: for i = 1, 2, . . . , n do 5: di ← d i 6:
end for 7: else scaling parameter x (lines 10-20) and used as before for assigning virtual deadlines to jobs, as long as the scenario exhibits level 1. As before, once the scenario exhibits level 2, the original deadlines are restored.

8: if λ 1 + λ 2 /2 > 1 or λ 1 + λ 2 -λ 1 λ 2 /4 >

Schedulability Conditions

We now prove the correctness of Algorithm 3. At a high level, the proof is very much in line with the proof of Theorem 3.4, but details are more complicated and the results are therefore presented as three separate lemmata.

LEMMA 4.4. If a 2-level task system τ satisfies λ ≤ 1, then τ is schedulable by EDF-VD.

PROOF. Notice that it is always possible to regard τ as an ordinary, non-MC task system where the WCET of task τ i is c i (χ i ) (this is the "worst-case reservations" approach). The load λ then coincides with the standard notion of load for ordinary task systems. Since (for ordinary task systems) EDF is an optimal scheduling strategy on a preemptive uniprocessor, the task system is EDF-schedulable if λ ≤ 1. LEMMA 4.5. If a 2-level task system τ satisfies λ 1 ≤ 1, then a scaling parameter x such that λ 1 ≤ x ≤ 1 guarantees that no deadline is missed in a level-1 scenario. PROOF. To prove that there is no deadline miss, we assume the opposite, which is that a job J misses its deadline in a level-1 scenario. Let I denote a minimal collection of jobs released by τ on which a deadline is missed. The deadline of job J is denoted by d . Now, due to the minimality of I, criticality-1 jobs have deadlines no greater than d , and criticality-2 jobs have virtual deadlines no greater than d (otherwise, the removal of such a job would yield a smaller collection I on which a deadline is missed). Notice that all virtual deadlines of criticality-2 jobs can be represented as dij = a ij + xd i ≥ x(a ij + d i ) = xd ij . This together with dij ≤ d implies that all criticality-2 jobs have actual absolute deadline no later than d /x. Therefore, the cumulative execution requirement of the system until time d is at most λ 1 • d /x in a level-1 scenario. Because J misses its deadline d , it must hold that

d x λ 1 > d ⇔ λ 1 > x. ( 16
)
Since we assumed that job J misses its deadline in a level-1 scenario, the contrapositive of ( 16),

x ≥ λ 1 , ( 17
)
yields a sufficient condition for schedulability of level-1 scenarios.

LEMMA 4.6. If a 2-level task system τ satisfies λ 1 + λ 2 /2 ≤ 1 and λ 1 + λ 2 -λ 1 λ 2 /4 ≤ 1, then setting x = 1 -λ 2 /2 as the scaling parameter in EDF-VD guarantees that no deadline is missed in a level-2 scenario. PROOF. To prove that there is no deadline miss, we argue by contradiction and assume that a job J misses its deadline at time t f . Let I denote a minimal collection of jobs for which a deadline miss occurs. Therefore, by Lemma 4.5, job J must be of criticality level 2, since the condition λ 1 + λ 2 /2 ≤ 1 (checked in Algorithm 3) ensures that x = 1-λ 2 /2 ≥ λ 1 , so no deadline miss can occur while the scenario exhibits level-1 behavior. Denote by time t * the time instant at which the scenario first exhibits level-2 behavior. The following claim is equivalent to Claim 3.5 and so is its proof. CLAIM 4.7. All jobs receiving execution in [t * , t f ) have deadlines at most t f . We see from Claim 4.7 that all jobs that receive execution after t * have priority higher than or equal to the priority of J after t * . Let S * be the set of jobs which receive execution after t * . Then J ∈ S * and all jobs in S * are of criticality level 2.

Let J 0 be the job in S * that is released earliest. Let a 0 and d 0 be its arrival time and absolute deadline, respectively. Thus, d0 = a 0 + x(d 0a 0 ) is the virtual deadline of J 0 . CLAIM 4.8. Any job J ij that is in the minimal job sequence I and only receives execution before t * must have an absolute deadline

d ij ≤ a 0 + x(t f -a 0 ) if it is a level-1 job, and absolute virtual deadline dij ≤ a 0 + x(t f -a 0 ) if it is a level-2 job.
PROOF. Note that no criticality-1 job J ij with d ij > d0 will execute at or after a 0 ; since J ij will only receive execution time before t * , this would imply that J 0 should be finished before t * (contradicting the definition of J 0 ).

Suppose there is a criticality-1 job J ij with d ij > d0 that executes somewhere before a 0 . Denote by t l the latest moment in time where it executes. At this point there are no available jobs with deadline at most d0 and the job sequence obtained by only considering jobs released after t l also misses a deadline. That contradicts the assumed minimality of I.

So, any criticality-1 job J ij in I must have a deadline

d ij ≤ d0 = a 0 + x(d 0 -a 0 ) ≤ a 0 + x(t f -a 0 ), using Claim 4.7 saying that d 0 ≤ t f .
If a level-2 job J ij ∈ I does not receive execution after t * , we have the following possible cases.

(1) a ij ≥ a 0 . Then dij ≤ d0 , since otherwise J ij would not receive any execution after a 0 , implying that it does not receive any execution before t * , which combined with J ij not receiving any execution after t * , would make that the instance I without J ij would also see a deadline miss of J at t f , contradicting the minimality of I.

(2) a ij < a 0 . If d ij ≤ t f , then dij = a ij + x(d ij -a ij ) ≤ a 0 + x(t f -a 0 ). Otherwise, if d ij > t f ,
then again dij ≤ d0 must hold, since otherwise we can remove J ij from I without affecting the deadline miss of J, thus contradicting the minimality of I.

The proof is completed by noting that dij ≤ d0 = a 0 + x(d 0a 0 ) ≤ a 0 + x(t fa 0 ).

Following Claim 4.8, we define S 1 to be the set of criticality-1 jobs of I, and S 2 to be the set of criticality-2 jobs of I that only receive execution before t * . Therefore, the collection of jobs I is the disjoint union of S 1 , S 2 and S * .

Let C 1 be the sum of execution requirements of jobs in S 1 ; C 2 the sum of execution requirements of jobs in S 2 ; and C * the sum of execution requirements of jobs in S * . Let δ def = t fa 0 , the length of the time interval in which there are pending jobs from S * . Then, Claim 4.8 yields the following two inequalities:

C 1 ≤ λ 1 (a 0 + xδ) C 1 + C 2 ≤ λ 1 (a 0 /x + δ). ( 18
)
The second inequality holds because a ij +xd i = dij ≤ a 0 +xδ implies that d ij ≤ (a 0 +xδ)/x, similar to the conclusion we had in the proof of Lemma 4.5. By definition of λ 2 , we also obtain another set of inequalities

C * ≤ λ 2 δ C * + C 2 ≤ λ 2 (a 0 /x + δ). ( 19
)
Since J misses its deadline t f = a 0 + δ, as we assumed, we have

C 1 + C 2 + C * > t f , which is equivalent to C 1 + C 2 + C * -a 0 > δ.
Without loss of generality, we assume that δ is constant (since all other values can be scaled proportionally). Then, the maximum value of C 1 + C 2 + C *a 0 over all possible a 0 will be greater than δ.

In order to find this maximum value, we replace a 0 by t and study the function 18) and ( 19), we get

o(t) def = C 1 + C 2 + C * -t. From inequalities (
o(t) ≤ f (t) def = λ 1 (t + xδ) + λ 2 (t/x + δ) -t o(t) ≤ g(t) def = λ 1 (t/x + δ) + λ 2 δ -t. ( 20
)
Note that since λ 1 + λ 2 > 1 (otherwise, it must be the case that λ ≤ λ 1 + λ 2 ≤ 1, according to Proposition 4.3) and λ 1 /x ≤ 1 (because of Lemma 4.5), we obtain the following bounds on the derivatives of f and g

∂ f (t) ∂t = λ 1 + λ 2 /x -1 ≥ λ 1 + λ 2 -1 > 0 ∂g(t) ∂t = λ 1 /x -1 ≤ 1 -1 = 0.
Hence, when t increases, f (t) increases and g(t) does not increase, for t ∈ (0, +∞). Thus, max t o(t) cannot exceed the value of f and g at the point where they cross. We denote this point by γ , that is,

f (γ ) = g(γ ). Straightforward calculations yield γ = λ 1 (1 -x)xδ λ 2 -λ 1 (1 -x) , (21)
and therefore

max t o(t) ≤ f (γ ) = g(γ ) = λ 2 2 + λ 1 λ 2 x -λ 1 x + λ 1 x 2 λ 2 -λ 1 + λ 1 x δ. (22)
Hence, if J misses its deadline as we assumed, we must have o(γ ) > δ, that is,

λ 1 x 2 + (λ1λ2 -2λ 1) x + λ 1 -λ 2 + λ 2 2 > 0. ( 23
) Inserting our choice of x = 1 -λ 2 /2 = -(λ1λ2 -2λ 1) /2λ 1 in (23) leads to -(λ1λ2 -2λ 1) 2 + 4λ 1 λ 1 -λ 2 + λ 2 2 > 0, which simplifies to λ 1 + λ 2 - λ 1 λ 2 4 -1 > 0, (24)
contradicting the assumption of the theorem.

COROLLARY 4.9. If for a 2-level task system τ ,

λ 1 + λ 2 /2 ≤ 1 and λ 1 + λ 2 -λ 1 λ 2 /4 ≤ 1, then τ is correctly scheduled by EDF-VD with scaling parameter x = 1 -λ 2 /2.
PROOF. By Lemma 4.6, we can select x = 1 -λ 2 /2 to guarantee no deadline miss while the system is in level 2. Since x = 1 -λ 2 /2 ≥ λ 1 , Lemma 4.5 guarantees that there is no deadline miss while the system is in level 1.

Speedup Bound

THEOREM 4.10. If a 2-level task system τ is feasible on a unit-speed processor, then it is schedulable by EDF-VD on a processor of speed 1 + √ 3/2 ≈ 1.866.

PROOF. If a 2-level task system τ is feasible on a unit-speed processor, by Proposition 4.2, λ 1 (τ ) and λ 2 (τ ) are both no greater than 1. Thus, on a (1 + √ 3/2)speed processor, the load-to-speed ratios λ 1 /(1 + √ 3/2) and λ 2 /(1 + √ 3/2) are no greater than 1/(1 + √ 3/2) = 4 -2 √ 3. We complete the proof by showing that any task set is schedulable by EDF-VD on a unit-speed processor whenever max(λ 1 , λ

2 ) ≤ 4 -2 √ 3. Define L(λ 1 , λ 2 ) = λ 1 + λ 2 -λ 1 λ 2 /4 -1. Basic arithmetic shows that choosing λ 1 = λ 2 = 4 -2 √ 3 yields L(λ 1 , λ 2 ) = 0 and also λ 1 + λ 2 /2 ≤ 4 -2 √ 3 + 2 - √ 3 = 6 -3 √ 3 ≤ 1.
Thus, Corollary 4.9 asserts that such a system is EDF-VD schedulable, with scaling parameter x = 1 -λ 2 /2. For values of λ 1 and λ 2 satisfying λ 1 + λ 2 ≥ 1, λ 1 ≥ 0 and λ 2 ≥ 0, we have

∂ L(λ 1 , λ 2 ) ∂λ 1 = 1 - λ 2 4 > 0 ∂ L(λ 1 , λ 2 ) ∂λ 2 = 1 - λ 1 4 > 0,
which implies the schedulability of any system with max(λ 1 , λ 2 ) ≤ 4 -2 √ 3.

This analysis of EDF-VD is tight for arbitrary-deadline systems, as shown by the following. THEOREM 4.11. Let > 0. There exists a 2-level task system τ with λ 1 = λ 2 = 4 -2 √ 3 + that cannot be scheduled by EDF-VD on a unit-speed processor.

PROOF. We define α def = 4 -2 √ 3, and let T , N and M be large integers with T M N; for concreteness, say T = M 2 = N 4 . Then, we choose N large enough, such that N( √ α-α) ≥ 2 and ( √ α-α)/N = ν < . We define a task system τ = (τ 1 , τ 2 , τ 3,1 , . . . , τ 3,M ) as follows.

τ i χ i c i (1) c i (2) d i p i τ 1 1 α α α / (α + ) T τ 2 2 0 α + 1 T τ 3,1 2 ( √ α -α)/N ( √ α -α)/N 1 + (1/ √ α -1)/N T τ 3,2 2 ( √ α -α)/N ( √ α -α)/N 1 + 2(1/ √ α -1)/N T . . . . . . . . . τ 3,i 2 ( √ α -α)/N ( √ α -α)/N 1 + i(1/ √ α -1)/N T . . . . . . . . . τ 3,N 2 ( √ α -α)/N ( √ α -α)/N 1/ √ α T . . . . . . . . . τ 3,i 2 ( √ α -α)/N ( √ α -α)/N 1 + M(1/ √ α -1)/N T
In the sequel, we will frequently use that √ α -α = α(1/ √ α -1). We verify that λ 1 and λ 2 of τ are both α + , by considering the synchronous arrival sequences of τ for level 1 and level 2 separately. Let λ 1 (t) and λ 2 (t) be the load at level 1 and 2, respectively, over the interval [0, t):

λ 1 (t) def = 1 t τ i t p i c i (1), λ 2 (t) def = 1 t τ i :χ i =2 t p i c i (2).
As argued before, λ 1 and λ 2 are determined by max t λ 1 (t) and max t λ 2 (t). Clearly, λ 1 (α/(α + )) = α + and λ 2 (1) = α + . Since T is very large, we only need to further consider λ 1 (1 + i(1/ √ α -1)/N), for i = 1, . . . , M:

λ 1 (1 + i(1/ √ α -1)/N) = α + i( √ α -α)/N 1 + i(1/ √ α -1)/N = α ≤ α + .
Similarly, λ 2 (1 + i(1/ √ α -1)/N) ≤ α + . Hence, λ 1 and λ 2 are both equal to α + . Now let us assume that a scaling factor x has been selected. We would like to show that the system is not schedulable by EDF-VD with this (arbitrary) x.

Given x, assume that τ 2 releases its first job at time 1x, and all other tasks release their first job at time 0. Then, the actual deadline of the first job of τ 2 (denoted as J 2 ) is d 2 = 1x + 1 = 2x, and the virtual deadline will be d2 = (1x) + x × 1 = 1. Because the virtual deadline is greater than the deadline of the first job of τ 1 (denoted as J 1 ), which is d 1 = 1 -, J 2 will wait until J 1 finishes.

If x is so small that x(1+M(1/ √ α-1)/N) < 1, then all first jobs from τ 3,1 , . . . , τ 3,M have priority over J 2 . Their total execution requirement is M( √ α -α)/N = N( √ α -α) ≥ 2, by the choice of M and N.

Otherwise, there exists a largest number i such that x(1 + i(1/ √ α -1)/N) ≤ 1. Let this number be i x . Then all first jobs of τ 3,1 , . . . , τ 3,i x have priority over J 2 . Their total worst-case execution time is

i x ( √ α -α)/N = (i x + 1)( √ α -α)/N -( √ α -α)/N = (i x + 1)α(1/ √ α -1)/N -ν ≥ α 1 x -1 -ν.
This, together with the WCET of J 1 and the level-2 WCET of J 2 itself, yields a total execution requirement of

α + α + + α x -α -ν = α + α x + -ν.
Now, by the choice of N we have def = -ν > 0 and

α + α/x + -(2 -x) = α + α/x + x -2 + ≥ α + 2 √ α -2 = 4 -2 √ 3 + 2( √ 3 -1) -2 + = > 0.
Hence, for this arbitrarily given x, we can always find a scenario in which J 2 misses its deadline, implying that it is impossible to schedule τ using EDF-VD.

Effect of the Approximation Error when Computing the Loads

Theorem 4.10 presumes that the load λ, the level-1 load λ 1 , and the level-2 load λ 2 are computed exactly in Algorithm 3 (line 1). However, for improved efficiency -for example, if a polynomial-time schedulability test is desired -it may be necessary to resort to approximations of such loads. The approach of [START_REF] Albers | An event stream driven approximation for the analysis of real-time systems[END_REF], for example, guarantees that one can find, in polynomial time for any fixed > 0, values λ1 , λ2 such that

λ 1 ≤ λ1 (1 + )λ 1 , λ 2 ≤ λ2 ≤ (1 + )λ 2 . ( 25
)
We observe that if one defines further

λ def = λ1 + λ2 (26)
and uses λ, λ1 , λ2 in place of λ, λ 1 , λ 2 , respectively, then all the claims in Sections 4.1 and 4.2 continue to hold. This is due to the fact that such approximate loads never underestimate the correct load values. For example, Lemma 4.4 used the hypothesis λ ≤ 1, but since λ ≥ λ 1 + λ 2 ≥ λ (Proposition 4.3), the hypothesis λ ≤ 1 implies λ ≤ 1.

Similarly, the hypotheses of Lemma 4.5 and Lemma 4.6 are stronger when expressed in terms of the approximated loads. Proposition 4.2, on the other hand, is easily adapted using the fact that λ k ≥ λk /(1 + ), for k ∈ {1, 2}.

PROPOSITION 4.12. Let τ be a 2-level task system and > 0. If λ1 > 1 + or λ2 > 1 + , then τ is not feasible.

We conclude that one needs simply generalize the statement of Theorem 4.10 by increasing the stated speedup from 1 + √ 3/2 to (1

+ )(1 + √ 3/2).
THEOREM 4.13. Let > 0. If a 2-level task system τ is feasible on a unit-speed processor, then it is schedulable by EDF-VD on a processor of speed (1 + )(1 + √ 3/2) whenever the loads λ, λ 1 , λ 2 are approximated as in (25)-( 26).

PROOF. Let σ

def = (1 + )(1 + √ 3/2).
Reasoning as in the proof of Theorem 4.10 yields that the normalized estimated loads λ1 /σ and λ2 /σ are both not larger than 4 -2 √ 3, and the proof of Theorem 4.10 already establishes that a task set is schedulable by EDF-VD on a unit-speed processor whenever the largest of its (normalized) estimated loads does not exceed 4 -2 √ 3.

EFFICIENT IMPLEMENTATION OF THE RUNTIME DISPATCHING

For traditional (non-MC) sporadic task systems consisting of n tasks, uniprocessor EDF can be implemented efficiently to have a runtime complexity of O(log n) per event, where an event is either the arrival of a job, or the completion of the execution of a job (see, e.g., [START_REF] Mok | Task management techniques for enforcing ED scheduling on periodic task set[END_REF]). A direct application of such implementations can be used to obtain an implementation of the runtime dispatching of EDF-VD that has a runtime of O(log n) per job-arrival and job-completion event. However, EDF-VD potentially needs to deal with an additional runtime event: the change in the criticality level of the behavior from at most k to more than k (this is the event that is triggered at the instant that current level() > k). Since this event requires that each subsequent scheduling be done according to each task's original deadline, explicitly recomputing priorities according to these original deadlines would take time linear in the number of tasks of criticality more than k -in the worst case, O(n) time. We now describe an implementation of EDF-VD's runtime system that has a worst-case runtime of O(log n) per event for all three kinds of events: job arrival, job completion, and change in the criticality level of the behavior from LO (i.e., at most k) to HI (more than k).

Recall that a priority queue supports the operations of inserting (insert) and deleting the smallest item (deleteMin) in logarithmic time, and the operation of finding the smallest item (min) in constant time. In addition, the standard priority queue data structure can be enhanced to support the deletion of a specified item (the delete operation), also in logarithmic time (see, e.g., Cormen et al. [2009, Sect. 6.5]). We maintain two such enhanced priority queues, Q LO and Q HI . We also use a timer that is used to indicate whether the currently executing job has executed for more than its kth level WCET (thereby triggering the event current level() > k).

Initially, current level() = 1 and there are three kinds of events to be dealt with: (1) the arrival of a job; (2) the completion of a job; and (3) current level() reaching a value larger than k. We consider each separately. Suppose that the event occurs at time-instant t c , and let J c denote the currently executing job.

(1) A job of task τ i arrives at time t c .

(a) Insert the newly arrived job into Q LO , prioritized according to its virtual scheduling deadline. (b) If χ i > k, then also insert it into Q HI , prioritized according to its unmodified (i.e., actual) scheduling deadline. (c) If J c is no longer the minimum job in Q LO , it must be the case that the newly arrived job has an earlier virtual deadline than J c 's virtual deadline. In that case, the newly inserted job becomes J c , and a timer for it is switched on and set to go off after it has clocked c i (k). The timer of the interrupted job is stopped (and resumed as soon as the job will get executed again).

(2) The currently executing job J c completes execution at time t c .

(a) Delete this job from Q LO , using the deleteMin operation supported by priority queue implementations. (b) If it was a job of criticality larger than k, also delete it from Q HI -this would be accomplished by a delete operation. (c) Set the current-job indicator J c to denote the new minimum (virtual) deadline job -the "minimum" job in Q LO ; and set the timer to go off at t c + this job's remaining level-k WCET (when the job would exceed its level-k WCET if allowed to execute without interruption).

(3) The timer goes off, indicating that the currently executing job has executed beyond its level-k WCET without signaling completion. We switch to scheduling according to Q HI . Henceforth, all runtime dispatch decisions are taken as indicated by this priority queue.

After the event current level() > k, no jobs of criticality at most k need execution, and jobs of criticality larger than k are executed according to EDF with respect to their original (unmodified) deadlines. Hence, subsequent runtime dispatching is done as for traditional EDF scheduling (as described in, e.g., [START_REF] Mok | Task management techniques for enforcing ED scheduling on periodic task set[END_REF]), with Q HI being the priority queue used for this purpose.

EXTENSIONS

The basic algorithm EDF-VD can be extended in a number of ways that enhance its applicability. In this section, we consider two such extensions.

Best-Effort Runtime Dispatching and Return to Low-Level Dispatching Mode

The basic algorithm EDF-VD was designed for best performance under worst-case scenarios; in particular, it may sometimes be overly pessimistic by completely discarding low-criticality tasks after observing a high-criticality behavior, and by never returning to the low-level mode of runtime dispatching (lines 1-8 of Algorithm 2) after a high-level behavior has been observed. We briefly discuss how to modify the algorithm in order to correctly schedule a larger number of jobs whenever possible, while maintaining the same worst-case guarantee in terms of speedup bounds.

The first modification is straightforward: instead of completely discarding lowcriticality tasks after entering the higher-level behavior, they can simply be scheduled with a priority lower than that of all high-criticality tasks. This, clearly, will meet the deadlines of at least all the jobs that meet their deadlines under the basic EDF-VD schedule; in particular, it preserves the correct scheduling of the high-criticality tasks. On the other hand, this more optimistic schedule may meet the deadlines of many otherwise ignored tasks, especially when the high-level behavior is exhibited marginally and by only a few tasks.

Regarding the return to the low-level mode of runtime dispatching, the modification is perhaps less straightforward. Let us limit the discussion to task systems with two criticality levels, 1 (LO) and 2 (HI). We note that we can preserve the schedulability guarantees with the following modification: on top of its criticality level, the runtime dispatcher classifies at all times each job as either standard or best-effort. All standard jobs have priority over best-effort jobs; standard jobs are scheduled as before by Algorithm 2, while the relative priorities of best-effort jobs can be arbitrary. Initially, the best-effort queue is empty and newly released jobs are always classified as standard.

Whenever the criticality-level counter current level() is 2, but the set of active jobs having criticality level HI is empty, the algorithm (i) resets the criticality-level counter current level() to 1 -and consequently, returns the runtime dispatcher to its LO mode of execution; (ii) at the same time, it demotes all active LO-criticality job to best-effort priority. This may violate the deadline of some active LO-criticality job; in particular, of a job demoted to the best-effort queue. However, we observe that such jobs need not be guaranteed anyway, since current level() reaches the value 2 at some point and so the criticality level of the scenario is HI according to the definition (Section 2). The advantage of returning to the low-level dispatching mode is that subsequently released jobs of LO-criticality will be correctly scheduled, at least until a HI-level behavior is exhibited again. Note that tasks having criticality level HI are always guaranteed, since, by construction, best-effort jobs never interfere with standard jobs (and HIcriticality jobs are never moved to the best-effort queue).

Nonuniform Virtual Deadlines

In our basic approach, there was a single scaling factor x and the virtual deadlines for the high-criticality tasks were defined uniformly, via the rule di def = x • d i . However, in many situations, it may be beneficial to define nonuniform scaling factors x i -one for every high-criticality task. For concreteness, we limit this discussion to the case of two criticality levels and implicit-deadline task systems.

Although, in light of Theorem 3.12, this will not help to achieve a better worst-case speedup bound than 4/3, setting the virtual deadlines nonuniformly may potentially schedule task sets that are not deemed schedulable by EDF-VD. We proceed to show that this is indeed sometimes the case and discuss how the schedulability condition is affected and how to set the deadline-scaling factors.

Consider the following variant of EDF-VD, called EDF with Non-Uniform Virtual Deadlines (EDF-NUVD). Given a task system τ , we first check whether τ satisfies the hypothesis of Theorem 3.4; if it does, we can simply apply EDF-VD. If the hypothesis of Theorem 3.4 is not satisfied, then instead of defining di def = x • d i for every highcriticality task τ i , we set di def = x i • d i , where x i ∈ (0, 1) is a task-dependent scaling parameter; we will see shortly how to set the scaling parameters and how to complete the schedulability test. Apart from the revised definition of the virtual deadlines, the runtime dispatching algorithm is otherwise unaffected.

As starting point of the analysis, we use the following alternative schedulability condition. For a task set τ , let L 2 def = {i ∈ [n] : χ i = 2} be its set of high-criticality tasks. LEMMA 6.1. Let τ be a 2-level task system and let 0 < x i < 1, for each i ∈ L 2 . If U 1 (1) + i∈L 2 u i (1)/x i ≤ 1

i∈L 2 u i (2)/(1 -x i ) ≤ 1, ( 27
)
then τ is schedulable by EDF-NUVD.

PROOF. First observe that the condition U 1 (1) + i∈L 2 u i (1)/x i ≤ 1 ensures that no deadline (virtual or otherwise) is missed by EDF-NUVD while the system exhibits level-1 behavior. Let t * denote the time at which the scenario first exhibits level-2 behavior. Consider a job J ij of a high-criticality task τ i that is active at t * . Let a ij denote its arrival time. The absolute deadline of this job is d ij = a ij + d i and before t * , J ij is EDF-scheduled by EDF-NUVD assuming a deadline dij = a ij + x i d i . Since all jobs would meet their virtual deadlines in any level-1 scenario, we know that t * ≤ dij ; otherwise, the job would no longer be active at t * . Note that

d ij -t * ≥ d ij -dij = d i -x i d i = (1 -x i )d i .
In the worst case, we can therefore regard the system after time t * as a single-criticality task system in which task τ i has period (1x i )d i and utilization u i (2)/(1x i ). Then, condition i∈L 2 u i (2)/(1x i ) ≤ 1 ensures that this system is itself EDF-schedulable.

It remains to show how to choose the scaling parameter x i for each high-criticality task τ i . We show that, when using (27) as the sufficient schedulability condition, a best possible choice of the x i is given by

x i def = 1 + λ u i (2)/u i (1) -1
for all i ∈ L 2 (28)

for some positive parameter λ. The particular form (28) is not arbitrary; its choice is justified by the following result. THEOREM 6.2. For a 2-level task system τ , let

S 12 def = i∈L 2 u i (1)u i (2).
If τ satisfies U 1 (1) + U 2 (1) + λ S 12 ≤ 1,

U 2 (2) + λ -1 S 12 ≤ 1, ( 29
)
for some λ > 0, then τ is schedulable by EDF-NUVD when the x i are as in (28). Moreover, whenever (27) holds for some choice of the x i , then (29) holds for some λ > 0.

PROOF. For the first part of the theorem, by Lemma 6.1, we just need to check if (27) holds for the given choice of the x i , which are determined up to the constant λ. We substitute the value of λ from (28) and the definition of S 12 into (29) to obtain the condition

U 1 (1) + U 2 (1) + i∈L 2 (1/x i -1) u i (1)/u i (2) • u i (1)u i (2) ≤ 1 U 2 (2) + i∈L 2 (x i /(1 -x i )) u i (2)/u i (1) • u i (1)u i (2)
≤ 1, which is easily seen to be equivalent to (27), proving the first part of the theorem.

To prove the second part, we form the Lagrange dual function of ( 27) [Boyd and Vandenberghe 2009, Sect. 5.8.1]. Since (27) has two constraints, the dual function g involves two arguments μ 1 , μ 2 (μ 1 , μ 2 ≥ 0):

g(μ 1 , μ 2 ) = inf 0<x i <1 : i∈L 2 (μ 1 f 1 (x) + μ 2 f 2 (x)), (30)
where

f 1 (x) = U 1 (1) + i∈L 2 u i (1) x i -1, f 2 (x) = i∈L 2 u i (2) 1 -x i -1.
Since the set {0 < x i < 1, i ∈ L 2 } is open, the infimum with respect to x in (30) must be achieved for values x such that ∂ ∂ x i μ 1 f 1 (x) + μ 2 f 2 (x) = 0 for all i ∈ L 2 , yielding the condition

μ 1 - u i (1) x 2 i + μ 2 u i (2) (1 -x i ) 2 = 0.
Solving for x i yields

x i = ⎛ ⎝ 1 + μ 2 μ 1 u i (2) u i (1) ⎞ ⎠ -1
for all i ∈ L 2 , which is equivalent to (28) after defining λ = √ μ 2 /μ 1 . The weak alternative form of Lagrange duality implies that if the inequality system ( 27) is feasible, the inequality μ 1 f 1 (x) + μ 2 f 2 (x) > 0 must be infeasible for any choice of μ 1 , μ 2 ≥ 0. This in turn implies that f 1 (x), f 2 (x) ≤ 0, which for the particular choice of x given by ( 28) implies (29).

Similarly as in Section 3, we can rewrite the system of inequalities (29) as a single condition:

S 12 1 -U 2 (2) ≤ 1 -U 1 (1) -U 2 (1) S 12 . ( 31
)
If (31) holds, then λ can be chosen as any value in the interval

S 12 1 -U 2 (2) , 1 -U 1 (1) -U 2 (1) S 12 ,
and the values of the x i can be chosen accordingly. In summary, whenever either the assumptions of Theorem 3.4 hold, or Condition (31) holds, then τ is schedulable by EDF-NUVD.

Example 6.3. Consider the following task set τ = (τ 1 , τ 2 , τ 3 ), where = 1/1000.

τ i χ i u i (1) u i (2) τ 1 1 3/4 - 3/4 - τ 2 2
1/8 1/8 τ 3 2 5/8

We observe that U 1 (1) = 3/4 -, U 2 (1) = 1/8 + , U 2 (2) = 3/4. Conditions (2) and (3) are both violated (for = 1/1000), so that the system is deemed unschedulable by EDF-VD. On the other hand, Condition (31) is satisfied since S 12 = i∈L 2 u i (1)u i (2) = 3/20. Therefore, we can choose any λ ∈ [3/5, 5/6] and conclude that τ is schedulable by EDF-NUVD.

SUMMARY AND CONCLUSIONS

Devising more cost-efficient techniques for obtaining certification for safety-critical embedded systems has been identified as a prime research challenge [START_REF] Barhorst | A research agenda for mixed-criticality systems[END_REF]]. We believe that in mixed-criticality systems, these certification considerations give rise to fundamental new resource allocation and scheduling challenges that are not adequately addressed by conventional real-time scheduling theory. In this article, we consider the scheduling, upon preemptive uniprocessors, of mixed-criticality systems that can be modeled using a mixed-criticality generalization of the sporadic task model.

We propose an algorithm called EDF-VD for scheduling such systems. We have proved that EDF-VD is speedup-optimal by showing that (i) it has a processor speedup factor equal to 4/3 for 2-level implicit-deadline systems (Theorem 3.8); and (ii) no nonclairvoyant algorithm can have a smaller speedup factor (Theorem 3.12). We have also proved bounds on the speedup factor of EDF-VD for implicit-deadline systems with up to 13 criticality levels (Theorem 3.11), and a bound of 1 + √ 3/2 on the speedup factor of EDF-VD for 2-level arbitrary-deadline systems (Theorem 4.10).

We have shown how EDF-VD admits efficient schedulability tests and how it can be implemented to have a runtime complexity per scheduling decision that is logarithmic in the number of tasks for any K-level implicit-deadline task system, and thus demonstrated the practical applicability of the algorithm. Finally, we discussed extensions of EDF-VD by analyzing the possibility of using nonuniform scaling parameters and more optimistic runtime dispatching rules.

For further research, we observe that the mixed-criticality model proposed by [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF] can be extended to take into account other aspects that arise in the design of safety-critical systems. A detailed discussion of the extensions is not the focus of this article. We observe, however, that a very interesting contribution of [START_REF] Ekberg | Bounding and shaping the demand of generalized mixed-criticality sporadic task systems[END_REF] concerns the generalization of the mixed-criticality task model to models where not only the execution times change after a critical event, but all task parameters are allowed to change.

  a job of task τ i arrives at time t, assign it a virtual absolute deadline equal to t + di the active job, among the tasks τ i such that χ i ≥ current level(), having earliest virtual absolute deadline (ties broken arbitrarily); the active job, among the tasks τ i such that χ i > k, having earliest absolute deadline (ties broken arbitrarily); then break from the loop 8: end loop

		n
		i=1
	1: loop
	2:	on job arrival:
	3:
	4:	on job arrival/completion:
	5:
	6:	on current level() > k:
	7:
	9: loop
	10:	on job arrival:

if schedule schedule 11: if a job of task τ i arrives at time t, assign it an absolute deadline equal to t + d i 12: on job arrival/completion: 13:

Table II .

 II Minimum Speedup Factor for K ≤ 13 Levels

	Number of levels K	Speedup factor f K
	2	1.3333
	3	2.0000
	4	2.6180
	5	3.0811
	6	3.7321
	7	4.2361
	8	4.7913
	9	5.3723
	10	5.8551
	11	6.4641
	12	6.9487
	13	7.5311

  1 then

	9:	return unschedulable
	10:	else
	11:	k ← 1
	12:	x ← 1 -λ 2 /2
	13:	for i = 1, 2, . . . , n do
	14: 15:	if χ i ≤ k then di ← d i
	16: 17:	else di ← x d i
	18:	end if
	19:	end for
	20:	end if
	21: end if 22: return (schedulable, k, ( di ) n i=1 )

ACKNOWLEDGMENTS

We thank the anonymous referees for their observations and criticisms that helped improve the presentation and quality of this work.

's research was supported in part by NSF grants CNS 1016954, CNS 1115284, CNS 1218693, and CNS 1409175; and ARO grant W911NF-09-1-0535.