Elastic real-time scheduling models provide a framework to reduce the utilizations of individual tasks in response to system overload. The original model proposed by Buttazzo et al. [1], [2] considers uniprocessor scheduling of implicitdeadline tasks. Using a physical analogy, it represents each task's utilization as a spring; the task's "elasticity" reflects its ability to adapt its utilization to a lower quality of service. The total length of the springs, placed end-to-end, represents system utilization. If this exceeds the schedulable bound, a compressive force is applied to the system. Each spring (and corresponding utilization) is compressed proportionally to its elasticity until the total utilization no longer exceeds the bound or until the task reaches its minimum serviceable utilization; task periods are adjusted accordingly.
Chantem et al. [3], [4] demonstrated the equivalence of elastic scheduling to the problem of minimizing a weighted sum of squared deviations of each task's compressed utilization from its nominal value, constrained by each task's minimum utilization and the total utilization bound of the system. The model was extended to constrained-deadline tasks, for which utilization compression extends periods while holding the relative deadlines constant. The constraint on total utilization was replaced by a tractable approximation of the processordemand analysis (PDA) [5] test for earliest-deadline first (EDF) schedulability. Recently, Baruah [6] demonstrated that these approximations result in a high degree of pessimism for certain task sets. An alternative was presented in [6] that uses an iterative approach, increasing the total compression according to a tunable step size until the system is schedulable according to PDA. The algorithm is tuned by selecting the amount to increase compression at each step; a smaller step increases the running time of the algorithm but allows for a more precise result.
In this work, we extend this approach to deadline-monotonic (DM) uniprocessor scheduling of systems of constraineddeadline elastic tasks. We first present an iterative algorithm that similarly increases compression until schedulability is achieved according to the response time analysis (RTA) test [7]. We then present two refinements to this algorithm, both leveraging the observation that once a task has been compressed to schedulability according to RTA, it remains schedulable when more compression is applied to the system. The first refinement iterates over tasks in order of decreasing priority, increasing total compression until that task is schedulable under RTA before considering the next task. The second performs binary search over the range of allowed compression, skipping RTA for tasks that are already known to be schedulable at lower levels of compression.
Next, we formulate the problem of finding the optimal amount of compression to guarantee schedulability for a single task as a mixed integer quadratic program (MIQP). This allows us to present an alternative algorithm that considers each task in turn; if a task is not RTA schedulable for the current level of system compression, the MIQP is solved to find the exact amount of compression necessary to schedule the task. By iterating over each task, we can determine the minimum sufficient compression that must be applied to the task system.
We implement the latter three approaches, using SCIP [8] to solve the MIQP. By evaluating each algorithm for randomlygenerated synthetic task sets, we demonstrate that the approximate procedures are both highly efficient and typically give a result close enough to optimal to be useful for online scheduling decisions in low-powered embedded devices. We also show that, when an optimal solution is desired, the MIQP may be solved feasibly offline to compress task periods.
The remainder of this paper is organized as follows:
Section II, we provide the necessary background on system models used in this paper. Section III presents a basic iterative algorithm to compress tasks until RTA guarantees schedulability. Sections I V and V refine the algorithm to a more efficient iterative approach and a binary search, respectively. Section V I formulates an MIQP representation of the problem of finding the optimal amount of compression to schedule a single task, then applies this to a complete task system. In Section VII, we show results of our evaluation of those approaches. Finally, Section VIII concludes the paper and discusses the contexts under which each approach may be relevant.
The elastic model for recurrent, implicit-deadline tasks on a uniprocessor [1], [2] characterizes each task τi =(Ci , U mi n , U max , Ui , Ei ) by five non-negative parameters:
• Ci : The task's worst-case execution time.
• U max : The task's maximum utilization, i.e., its nominal value when executing at the desired service level in an uncompressed state.
• U min : Its minimum utilization, i.e., a bound on the amount its service can degrade.
• Ui: The task's assigned utilization, constrained to U min ≤ Ui ≤ U max (the value of this parameter needs to be assigned prior to run-time).
• E i : An elastic constant, representing "the flexibility of the task to vary its utilization" [1].
A task system Γ = {τ1, . . . , τn} has a total uncompressed utilization U max expressed as
and a desired utilization U D representing the utilization bound given by the scheduling algorithm in use. In the event of system overload, i.e., if U max > UD , the elastic model assigns a utilization Ui to each task τi according to these conditions:
• U n = UD , i.e., total utilization is set to the schedulable bound.
• Any task for which E i = 0 is considered inelastic; we consider this equivalent to the case that U min = U max .
• For all other tasks τi and τj , if Ui > U min and Uj > U min , then Ui and Uj must satisfy the relationship U max -Ui U max -Uj E i E j Put simply, the model compresses each task's utilization such that it is reduced from its desired maximum proportionally to the task's elasticity parameter, subject to the constraint that it remains no less than the specified minimum. 1 Compression is then realized by adjusting each task's period Ti according to its new utilization, i.e., Ti = Ci /Ui . The original algorithm presented in [1], [2] for assigning utilizations under this model executed in time quadratic in the number of elastic tasks. A recent improvement [9] yielded a more efficient algorithm that runs in quasilinear time (or linear time for admission of a new task).
In [3], [4], Chantem et al. showed that utilizations selected by the elastic model also solve the following quadratic programming problem:
This allowed for an extension of the model to constraineddeadline tasks. A task τi = (Ci , Di , U min , U max , Ui , Ei ) is now characterized with an additional parameter, D i , representing a relative deadline that remains fixed even if the task's period is extended in response to reduced utilization. Under the constrained deadline model, only tasks for which D i ≤ Ti (i.e., D i ≤ Ci /U ma x ) are considered. The schedulability constraint (Eqn. 2b) is replaced by a representation of the PDA [5] schedulability test. PDA is an optimal technique for schedulability analysis of constraineddeadline sporadic task systems under preemptive EDF scheduling on a uniprocessor. It considers the demand bound function D B F i (t) for each task τi, which denotes the maximum possible cumulative execution required by jobs of the task that arrive and have their deadlines within any contiguous interval of duration t ≥ 0. This can be computed as:
i For t ≥ 0 and D i ≤ Ti, this can be expressed more simply as:
A constrained-deadline task system Γ = {τ1, . . . , τn} is schedulable under preemptive EDF on a uniprocessor if and only if for all t > 0,
In [5], it was shown that it is sufficient to check this condition for values of t within the first hyperperiod that take the form ( k T i + D i ) for non-negative integers k. This set of values constitute the PDA testing set. For elastic scheduling, Chantem et al. [3], [4] add a constraint in the form of Eqn. 5 for each element of the testing set to the optimization problem represented by Eqn. 2.
However, the resulting problem may not be tractable. The size of the testing set may be exponential in general, and
pseudo-polynomial for bounded-utilization tasks, and may result in an optimization problem with too many constraints to be efficiently solvable. Also, due to its use of the floor function, D B F i (t) is not a linear expression, and so the optimization problem does not remain a quadratic program. Chantem et al. [3], [4] over-approximate the demand-bound function by removing the floor. Nonetheless, because the test set itself depends on the task periods, the times defining the RHS of the constraints formed by Eqn. 5 are variables in the optimization problem, and the problem remains non-linear. Chantem et al. [3], [4] introduced an approximate form of the problem, and a heuristic approach to solving it, that were proved correct in the sense that the resulting compressed system would be guaranteed schedulable.
In recent work [6], Baruah showed that these approximations are highly conservative and may result in significant overcompression for certain task sets. Two alternative approaches were presented; in this paper, we extend these to fixed-priority DM scheduling. Baruah introduces a term λ representing the degree by which compression is applied to the task system. Recall that in the original model [1], [2], each task τi is compressed proportionally to its elasticity E i , but not beyond its minimum utilization U min . This allows us to express the utilization Ui of each task as:
Since Ti = Ci /Ui , we define T min = C i /U m a x and T max = Ci /U min . Then for λ < Ci /(Ei T m i n ):
In an uncompressed state, λ = 0 and for each task, Ui = U max (equivalently, Ti = T min ). The values U min also imply a value λ max beyond which the utilization of task τi cannot be compressed further:
Baruah also defines a value λmax beyond which the system cannot be further compressed [6]; we express it as:
which implies an alternative expression for Ti as follows:
Baruah [6] also introduces the notation Γ(λ), representing the task system obtained from Γ by applying compression λ, i.e., with each task τi having a period Ti according to Eqn. 7. An optimal algorithm, then, for elastic scheduling of constrained-deadline task systems under EDF finds the value λ representing the minimum value λ for which Γ ( λ ) is schedulable. In [6], Baruah presents two algorithms that, while not optimal, are nonetheless tunable by a parameter ϵ; both algorithms are guaranteed to find a value λ < λ + ϵ for which Γ ( λ ) is schedulable. We summarize both:
1) E L A S T I C : This algorithm iterates over values of λ [0, λmax] with granularity ϵ. For each value of λ tested, it performs PDA over the task set Γ(λ). Once PDA indicates schedulability, the search stops, and compression is applied. For efficiency, binary search is proposed as an alternative. For a considered value of λ, if PDA indicates schedulability, a smaller value of λ is subsequently tested; if not, a larger value is checked. The binary search limits the number of times PDA is performed to log λ m a x ; PDA is itself pseudopolynomial for bounded-utilization task systems.
2) E L A S T I C -E FFI C I E N T : A more efficient algorithm is supported by two observations in [6], repeated here: Observation 1. If a given sporadic task system Γ satisfies Expression 5 for a given value of t (say, to), then any task system Γ ′ obtained from Γ by increasing the period parameters of one or more tasks also satisfies Expression 5 for to. Observation 2. Let Γ denote some constrained-deadline elastic sporadic task system, and λ, ϵ, and ts denote positive numbers. If all elements in the testing set of Γ ( λ ) that are ≤ ts satisfy Condition 5, then all elements in the testing set of Γ ( λ + ϵ) that are ≤ ts also satisfy Condition 5
The algorithm proceeds by iterating over values of λ, beginning with λ = 0. It considers elements of the PDA testing set in increasing order. Baruah observes that the testing set need not be enumerated in its entirety a priori [6]; instead, the current element being tested, to, can be updated to the smallest value from amongst the next deadlines of each task. When an element is reached for which PDA fails at the current test set element to, λ is incremented by ϵ. Observation 2 implies that once PDA succeeds at to, only larger values need to be tested. Once the test set is exhausted, the current value λ is returned. However, if λ reaches λmax, the algorithm terminates, as the task system remains unschedulable even under compression.
Because the algorithm essentially performs a single PDA (the testing set is only traversed once), while additionally recomputing the periods of each task τi in Γ ( λ ) for each value of λ, the worst-case running time of the algorithm is:
where n denotes the number of tasks in Γ. For constant ϵ, this is dominated by the running time of PDA.
In this section, we present a simple extension of Baruah's algorithm E L A S T I C [6] (summarized in Section II-B2) to fixed-priority deadline-monotonic (DM) scheduling, which maintains the priority order of tasks as their periods are extended. The procedure is outlined in Algorithm 1. Given a system Γ of elastic constrained-deadline tasks (characterized as described in Section II), it seeks to determine the smallest value of λ for which Γ ( λ ) is schedulable. Like the E L A S T I C algorithm, its precision is tunable by a parameter ϵ; the value λ found is guaranteed to be less than λ +ϵ. The algorithm initializes λ, the amount of compression to be applied, to 0. It then increases λ in steps of size ϵ, performing RTA for the complete task set Γ ( λ ) for each value of λ. Once λ is found for which schedulability is achieved, the algorithm terminates and the value is returned. However, if λ exceeds λmax, the utilization constraints on each task prevent the system from being scheduled under the elastic model. Running Time: Since at most λ max /ϵ calls are made to RTA by the algorithm E L A S T I C -F P , its worst-case running time is λ m a x × the worst-case running time of RTA (which is pseudo-polynomial in the representation of the task system).
In this section, we present the first of two refinements to Algorithm 1 (E L A S T I C -F P). We begin with a brief summary of Audsley et al.'s response time analysis (RTA) [7], which will provide a key observation leveraged by both refinements.
A task set Γ is schedulable if and only if the response time of each task does not exceed its deadline. Under fixed-priority preemptive scheduling, the response time R i of a task τi is characterized as the sum of its execution time C i and the interference I i of the higher priority tasks; the interference is, itself, a function of the response time. Assuming without loss of generality that tasks are indexed by decreasing priority, the following expression describes the response time:
Audsley et al. [7] describe a recursive process by which to determine the response time; the system is schedulable if and only if R i does not exceed the deadline D i for each task τi. If used in the context of RTA, our algorithm requires up to λ max /ϵ calls to RTA in the worst case. However, the following observation provides a slight improvement to execution time: Observation 3. If the condition R i ≤ D i holds for a task τi in Γ(λ), then the condition also holds for the same task τi in Γ ( λ + δ) for any δ > 0.
Proof. Since the period Ti only appears in the denominator in the expression for computing response time (Eqn. 11), and the period does not decrease as λ increases (from Eqn. 10), it follows that R i does not increase when increasing λ. Therefore, if R i ≤ D i for some λ, the inequality still holds as λ increases.
This observation implies that Algorithm 1 can be improved by considering only a single task at a time. RTA requires checking every task in a task system, but once a task is shown to be schedulable for a given value of λ, it need not be rechecked for larger values. The resulting improvement is outlined in Algorithm 2.
Algorithm 2: Elastic-FP-Efficient(Γ)
1 Input: Elastic constrained-deadline task system Γ 2 Output: Smallest λ such that Γ ( λ ) is DM-schedulable 3 λ ← 0 4 λmax computed according to Eqn. 9 As in Algorithm 1 (E L A S T I C -F P), E L A S T I C -F P -E FFI C I E N T begins by initializing λ to 0. It considers tasks in turn, beginning with τ1, the highest-priority task. The algorithm introduces the notation τ i (λ) to refer to task τi Γ(λ), i.e., task τi having a period Ti according to Eqn. 10 for the given value of λ. When RTA determines that the current task under consideration, τi, is unschedulable for the current value of λ, the algorithm increases λ in steps of ϵ until the task is schedulable. At this point, it considers the next task in the system. If there are no tasks remaining to be checked (line 9), the algorithm terminates and returns the current value of λ. However, if the value of λ exceeds λ max , the algorithm fails.
Running Time: As before, at most λ max /ϵ values of λ are checked by the algorithm E L A S T I C -F P -E FFI C I E N T . However, RTA is only performed for a single task at a time. For a single value of λ, no more than a single failing check can be made. Additionally, each task need only have a single successful Observation 3 implies that, when testing using RTA to test Γ ( λ ) for schedulability, any tasks already known to be schedulable for smaller values of λ do not need to be rechecked. The complete procedure is outlined in Algorithm 3. The algorithm first performs RTA for Γ(λma x ); if it is not schedulable, the algorithm fails. Otherwise, it performs binary search over values of λ in the range [0, λmax]: λhi (initialized to λmax) tracks the smallest value of λ tested for which Γ ( λ ) is schedulable, while λlo (initialized to 0) tracks the largest tested value for which Γ ( λ ) is not schedulable. A variable S tracks the indices of tasks in Γ(λlo ) that are schedulable. 2 At each step, the algorithm performs RTA for those tasks τi Γ ( λ ) that are not in S . If all tasks are schedulable, λhi is decreased to the tested value of λ; otherwise, λlo is increased to the tested value of λ and S is updated to include those tasks for which RTA nonetheless succeeded. The algorithm terminates when the difference between λhi and λlo does not exceed ϵ, at which point it is guaranteed that λhi < λ + ϵ for optimal λ , since λ > λlo.
Running Time: Since algorithm E L A S T I C -F P -B S requires RTA to be performed for all tasks in Γ(λmax ) prior to the binary search, in the worst case log (λmax /ϵ) + 1 total calls are made to RTA. The use of the variable S to track tasks already known to be schedulable for smaller values of λ may improve the execution time for some task sets; indeed, if λ > λmax -ϵ, and if RTA determines schedulability for all but one task at λ = λmax /2, then binary search will only proceed upward, and RTA will only need to be performed for a single task at each checked value of λ thereafter. In this case, RTA for a single task is performed only
times. This is more efficient than Algorithm 2 (E L A S T I C -F P -
For ϵ chosen such that λmax /ϵ = 1000, this is more efficient for systems of fewer than 990 tasks. On the other hand, if λ < ϵ, binary search will only proceed downward, so S remains empty, and so RTA must be performed for all tasks in Γ for each tested value of λ. In this case, RTA must be performed (i.e., RTA will succeed for each value of λ checked), in which case the analysis must be performed for each elastic task τi Γ . In this case, RTA for a single task is performed log 2 max + 1 × n times. This is more efficient than Algorithm 2 (E L A S T I C -F P -
For ϵ chosen such that λmax /ϵ = 1000, this is more efficient only if the system has fewer than 100 tasks. In Section VII, we evaluate both algorithms to compare their performance in the context of randomly-generated synthetic task sets.
V I . A N MIQP R E P R E S E N TAT I O N In this section we describe how the problem of finding the value λ representing the minimum amount of compression to apply to a fixed-priority, preemptive task system Γ to guarantee
schedulability of a single task τi can be formulated as a mixed integer quadratic program (MIQP). We then use this result to present an algorithm that finds the optimal compression value λ for the complete task system.
A. Formulating the MIQP We build upon the mixed integer linear programming representation of RTA given in [10]. In [11], it is shown that for a fixed-priority, preemptive task system Γ to be schedulable, it is necessary and sufficient that for each τi Γ , there exists some value of t ≤ D i for which:
The minimum value of t satisfying this condition for τi is the response time of the task. However, unlike in [10], we do not seek to find the minimum value of t for each task. Instead, for a single task τi, we seek to find the minimum value of λ i for which there exists a t < D i satisfying Eqn. 15 for Γ(λ). In other words, it must satisfy:
for Tj (λ i ) as defined in Eqn. 10. The MIQP problem is formulated as follows:
1) For task τi, we define a real-valued variable ti representing some value of t for which Eqn. 15 holds. Unlike in [10], where the corresponding R i is non-negative, we restrict ti to be positive: if ti = 0 satisfies Eqn. 15, then C i = 0, in which case the task can be ignored. This becomes an important distinction in a later step.
2) We specify the constraint:
3) As in [10], for each j {1, . . . , i -i}, we define a nonnegative integer variable Z i j that represents the term ti /Tj (λi ) . 4) As in [10], to enforce this intended interpretation on the Z i j variables, we must add constraints of the form Z i j ≥ ti /Tj (λi ) for each j {1, . . . , i -i}. Since Z i j is specified to be an integer variable, this will respect the ceiling operator that appears in Eqn. 15.
From the formulation of Tj (λi ) in Eqn. 10, we can express the term ti /Tj (λ i ) as:
This requires two linear constraints for each Z i j : j {1, . . . , i -1}, Z i j ≥ T max (18) 3 Without loss of generality, we again assume tasks are indexed in decreasing order of priority. j {1, . . . , i -1}, Z i j ≥
Because ti is itself a variable, and λ i is the value we want to minimize ultimately, we rewrite this expression: ! 0 ≤ Z i j -
This is a quadratic constraint, as it contains the term ti λi . 5) As in [10], we add a final constraint for Eqn. 16:
6) To find the minimum value of λ i for which the problem can be satisfied, we add the following objective function:
Recall that in Step 1 of the MIQP, t i is restricted to the positive reals; this implies that if a solution exists, λ i is welldefined for any value of ti.
By solving an MIQP, we can find the exact value of λ i by which to compress a task system Γ to guarantee schedulability for an individual task according to RTA. We now present an algorithm that extends this approach to finding the optimal value, λ , representing the minimum amount of compression to guarantee schedulability of all tasks. The procedure is outlined in Algorithm 4. The algorithm initializes λ to 0. Each task in the system is checked for schedulability under the current compression level using RTA. Once a task τi is found that cannot be scheduled, the MIQP described in Section VI-A is constructed and solved for that task. If no solution is found, the minimum utilization constraints of its constituent tasks prevent the system from compressing to schedulability. Otherwise, λ is updated to λ , and the remaining tasks are checked in the same manner.
Running Time: For a task system Γ of n tasks, algorithm E L A S T I C -F P -M I Q P must perform RTA for each task (the equivalent of performing RTA once over the complete task system). It must also solve, in the worst-case, n instances of the MIQP problem. Even the decision version of the problem (showing the existence of a λ that satisfies schedulability) is N P -complete. Nonetheless, as we demonstrate in Section VII, this procedure can often efficiently find the optimal amount of compression using off-the-shelf solvers.
To evaluate the effectiveness and efficiency of the E L A S T I C -F P -E FFI C I E N T (Alg. 2), E L A S T I C -F P -B S (Alg. 3), and E L A S T I C -F P -M I Q P (Alg. 4) procedures, we run them over a large collection of randomly-generated constrained-deadline task sets. We track their execution, both in time and calls to RTA. We also analyze the overhead incurred by using these algorithms for online admission control in an embedded system running an ARM Cortex-A53 processor. Finally, we compare the compression values λ produced by each algorithm.
To evaluate elastic scheduling for constrained-deadline tasks, we consider tasks that begin with a relative deadline D i equal to their period Ti. Tasks individually have a utilization not exceeding 1, but the task systems as a whole are not schedulable due to their joint utilizations exceeding the utilization bound of the system. To accommodate such a task system, each task has its period extended while its deadline remains the same. We generate task sets of size in steps of 10. For each size, we consider total utilizations in the range [1.0-2.0] in steps of 0.1. For each combination of size/utilization we generate 100 sets of tasks (for a total of 11 000) according to the following methodology:
1) Uncompressed task periods T min are generated using a loguniform distribution (per [12]) in .
2) Task deadlines D i are set equal to T min .
3) Tasks are sorted according to increasing deadline (decreasing priority under DM scheduling). 4) The total utilization of the task system is partitioned among tasks using the UUniSort technique (a more elegant version of UUniFast) [13], such that each task is assigned a utilization U max .
5) Execution time is assigned according to Ci =U m a x ×T m i n . 6) A minimum utilization U min is assigned to each task so that the total utilization cannot exceed 0.69, the Liu and Layland schedulability bound of a rate-monotonic implicitdeadline task system [14]. To do so, we define a constant s = 0.69/USUM, where USUM is the total utilization of the task set. We then obtain U min by multiplying each task's U max by a random value uniformly selected from the range [0-s]. On average, the total minimum utilization is expected to be 0.345, with a narrower distribution for larger task sets. This is illustrated in Fig. 1. 7) The maximum period is derived as T max = U min /Ci . 8) Elasticity E i is uniformly selected in [0-1].
We implement the recursive RTA of Audsley et al. [7] and the three algorithms we consider in C++, into which we link version 8 [15] of the SCIP constraint integer program solver [8] to execute the MIQP. Offline Elastic Scheduling: Elastic scheduling can be leveraged in situations where a task set is compressed online for scheduling on an overutilized target system. To consider this case, we evaluate the execution of our algorithms on a server with two Intel Xeon Gold 6130 (Skylake) processors running at 2.1 GHz, and with 32GB of memory.
We begin by executing both E L A S T I C -F P -E FFI C I E N T and E L A S T I C -F P -B S sequentially in a single-threaded environment over all 11 000 task sets. For each task set, we consider values of ϵ that divide the compression limit λ max respectively 100, 1000, and 10 000 times. Mean execution times are illustrated in Fig. 2. Both algorithms are quite efficient, with mean execution times not exceeding 4 milliseconds for the task sets tested. For larger values of ϵ, iteration is more efficient on average than binary search; but as ϵ gets smaller, E L A S T I C -F P -B S becomes faster. Worst observed execution times (WOET) and maximum total calls to RTA 4 are listed in Table I. As expected, algorithm running times are closely related to the number of calls to RTA. We then run E L A S T I C -F P -M I Q P over a subset of our generated task systems, limited to those with no more than 50 4 Performing response time analysis for a single task counts 1 call to RTA. tasks. The solver is configured to execute in a single thread, which allows us to run separate instances of the algorithm sequentially on each of the unused logical cores on our server, splitting up the work of compressing the 5500 considered task systems. Execution time distributions are illustrated in Fig. 3. For task sets with 20 or fewer tasks, the algorithm consistently completes in under 10 seconds. Even with up to 40 tasks, the algorithm finds an optimal value of λ in under 3 minutes (and often under 10 seconds). However, for systems of 50 tasks, the solver may be slow to produce the optimal solution. For 95% of task sets with 50 tasks, an optimal solution is returned in under 80 seconds. However, three of the task sets take over 2 hours to complete, with the longest taking 5.1 hours.
Online Elastic Scheduling: Elastic scheduling can also be used for online adaption of task rates, e.g., when admitting new tasks on a fully-utilized system, or when task execution times change in response to dynamic exogenous factors. Despite its precision, the uncertain execution time to solve the MIQP make the E L A S T I C -F P -M I Q P algorithm unsuitable for online scheduling decisions in real-time systems. We consider instead the worst observed execution times of the E L A S T I C -F P -E FF I C I E N T and E L A S T I C -F P -B S algorithms when running on an embedded system. We apply both algorithms to each of the 11 000 randomly-generated task sets, again using values of λ max /ϵ in {100, 1000, 10 000}. We measure their execution times on a single core of a Raspberry Pi 3 Model B+, which has a Broadcom BCM2837B0 system-on-chip with an ARM Cortex-A53 running at 1.4GHz. For each combination of size/utilization, we take the maximum execution time among the 100 task sets tested; these are plotted in Fig. time and accuracy. We first compare the relative compression achieved by the three algorithms to illustrate when approximation may be sufficient. We define the metric λ -λ λ max representing the difference between the compression value λ returned by an approximate algorithm and the optimal λ returned by E L A S T I C -F P -M IQ P, normalized by λ max . We compare values of δ between E L A S T I C -F P -E F F I C I E N T and E L A S T I C -F P -B S for each of the three values of ϵ/λ max considered. The relative distributions are plotted in Fig. 5. To achieve the same range of values in the horizontal axes of each plot, we multiply by ϵ/λ max , with values closer to 0 representing better agreement with λ . We observe that, while similar, E L A S T I C -F P -B S tends to do better than E L A S T I C -F P -E FFI C I E N T . Since it is also more efficient for finer granularity of ϵ, this likely makes it the preferred choice among the two approximate algorithms.
To quantify the effect of using an approximate algorithm to enact period compression over an elastic task set, we next compare the relative periods achieved by each algorithm. We define the metric θi = T i (λ)/Ti (λ ) representing the ratio of a task's period when compressed by an approximate algorithm to the period under optimal compression. We compare values of θi between E L A S T I C -F P -E FFI C I E N T and E L A S T I C -F P -B S for each of the three values of ϵ/λ max considered. Results for the 162 420 total tasks for which compression was achieved are summarized in Table II. In this work, we have extended uniprocessor elastic scheduling to fixed-priority, constrained-deadline tasks. We have presented three algorithms: E L A S T I C -F P -E FFI C I E N T , which applies compression iteratively using step sizes of a tunable value ϵ; E L A S T I C -F P -B S, which performs a binary search over the range of possible compression values, also using a precision of ϵ; and E L A S T I C -F P -M I QP, which formulates the problem of finding the exact amount of compression to apply as a mixed integer quadratic program.
We have demonstrated that both approximate algorithms are highly efficient. Even for systems of 100 tasks and small values of ϵ, E L A S T I C -F P -B S enables compression on the order of tens of milliseconds on a Raspberry Pi 3 Model B+. We also observed that, when compared to the optimal compression achieved by the MIQP approach, the approximate algorithms overcompress periods by less than 10% for 99.5% of tasks tested. However, in very rare corner cases ( < 0.006% of tested tasks), the iterative algorithms overcompress periods by more than 10× the optimal compression. Therefore, for offline scheduling decisions, E L A S T I C -F P -M I Q P may still remain a better choice. Even for task sets of size 50, the on Real Time Programm ng, Atlanta, GA, USA, 15-17 May 1991. algorithm completed in under 1.5 minutes 95% of the time, though we did observe 3 task sets for which the MIQP took over 2 hours to finish.
As future work, we intend to extend constrained-deadline elastic scheduling (including the PDA-based approach in [6] for EDF scheduling) to consider multiprocessor and distributed systems and computationally elastic tasks for which workloads, instead of periods, are compressed. We also plan to investigate whether an MIQP can be formulated to find optimal compression for dynamic-priority algorithms (e.g., EDF). Extensions to the MIQP may prove useful for handling additional constraints imposed under different system models.
This statement holds true for inelastic tasks, as E = 0 implies U m i n = U m a x , and therefore the utilization is not reduced.
S can be implemented as a bitmask or an array, allowing O ( 1) checking and insertion for a given task index.