Computing (2017) 99:1257–1270 DOI 10.1007/s00607-017-0562-9
Real-time uniprocessor scheduling with fewer preemptions
Jinkyu Lee1
Received: 12 September 2016 / Accepted: 10 June 2017 / Published online: 28 June 2017 © Springer-Verlag GmbH Austria 2017
Abstract In this paper, we propose a simple, but effective scheduling framework for EDF and RM, which reduces the number of preemptions by simply introducing a dummy task. We first observe useful preemption behavior under EDF and RM, leading to an interesting finding: an effective way to reduce the number of preemptions is to prevent jobs of a task with the smallest task period from preempting other jobs upon their release. To achieve this, we add a dummy task that invokes its job only when a newly-released job of the task with the smallest task period has a higher priority than the currently-executing job. Then, the currently-executing job can continue its execution without getting preempted by inheriting the priority of the dummy job. Since adding the dummy task can make a schedulable task set unschedulable, we propose how to set the dummy task’s parameters without compromising schedulability. In addition to the negligible overhead of this framework due to its simplicity, it holds an important property that does not increase the number of preemptions of any task set, compared to the original scheduling algorithm, which has not been achieved by existing studies. We also demonstrate via simulation that the proposed framework effectively reduces the number of preemptions under EDF and RM.
Keywords Fewer preemptions · EDF (Earliest Deadline First) · RM (Rate Monotonic) · Real-time scheduling · Uniprocessor systems
Mathematics Subject Classification 68M20
B Jinkyu Lee jinkyu.lee@skku.edu
1
Suwon, Republic of Korea
Department of Computer Science and Engineering, Sungkyunkwan University (SKKU),
123
1258 J. Lee
1 Introduction
To satisfy the timing requirements of critical tasks, the subject of real-time scheduling has been studied extensively [1,2]. As a result, EDF (Earliest Deadline First) [3] and RM (Rate Monotonic) [3] have been proved as optimal dynamic and static scheduling algorithms for uniprocessor platforms, respectively, if a higher-priority job is always allowed to preempt a lower-priority one. However, a preemption incurs additional delay and power consumption for a context switch. For a uniprocessor system equipped with a cache, this overhead becomes greater because the preemption may cause loss of the cached contents.
There have been numerous efforts to reduce the number of preemptions on a unipro- cessor platform [4], which can be classified into three categories. First, some studies have controlled preemptions in order to support various preemption requirements or improve schedulability. Starting from [5] that enforces a dual prioritization mechanism for job selection in the wait queue and job preemption (later extended in [6–8]), the studies in [9–13] accommodated non-preemptive regions. Since techniques in these studies have been originally designed to accommodate various preemption require- ments or improve schedulability, there is no guarantee that the number of preemptions with the techniques is always smaller than that without the techniques for any task set (albeit the former is smaller, on average). Second, there have been some proposals for reducing preemptions. The proposal in [14] exchanges the order of execution based on the original schedule, but it requires knowledge of future job release patterns offline and complex run-time mechanisms for safe execution exchanges without missing any deadline. Third, several studies rely on dynamic voltage/frequency scaling [15–18], all of which require hardware support. Most studies in the third category incorporate non-zero preemption delays into schedulability analyses [19–21], which focus on a system model different from the one in this paper.
To overcome the limitations of the existing studies, the goal of this paper is to develop a scheduling framework that reduces the number of preemptions with the following salient features.
(i) Simplicity: it incurs little run-time/system overhead;
(ii) Wide applicability—it can be applied to not only existing algorithms including
EDF and RM, but also existing schedulability analyses;
(iii) Independence from hardware/information: it does not rely on hardware support
of dynamic voltages/frequency scaling and information of future job release
patterns; and
(iv) Satisfaction of the important property: for every task set, the number of preemp-
tions with our approach is smaller than (or at least equal to) that with the original scheduling.
To this end, we propose a new scheduling framework based on a dummy task, which provides the above four features. To achieve this, we first observe that under EDF and RM, (a) all preemptions take place when a job is released, and (b) a task with the smallest task period is a dominant source of preemption. Based on this preemption behavior, we artificially add a dummy task, which invokes its job only when a newly- released job of the task with the smallest task period has a higher priority than the
123
Real-time uniprocessor scheduling with fewer preemptions 1259
currently-executing job. Then, the currently-executing job can continue execution without getting preempted by inheriting the priority of the dummy job. Since adding the dummy task may cause regular task deadline misses, we also present how to set the dummy task parameters without compromising the schedulability of a given task set.
Our proposed scheduling framework then provides the features (i)–(iv). Adding a dummy task makes the framework not only simple, but also applicable to most (if not all) scheduling algorithms as well as their schedulability analyses.1 Also, the framework does not require any hardware support, nor any information on future job releases. More importantly, Sect. 3.3 proves that the framework meets the important property in (iv), which has not been achieved by existing studies. In addition to the four salient features, we demonstrate via simulation that EDF and RM associated with the framework based on the dummy task reduce the number of preemptions significantly, compared to vanilla EDF and RM.
The rest of the paper is organized as follows. Section 2 introduces the system model, assumptions and notations. Section 3 identifies preemption behavior under EDF and RM, proposes the dummy task based scheduling framework, and inves- tigates its property. Section 4 describes how to set the dummy task parameters to preserve schedulability. Section 5 demonstrates the effectiveness of the framework using simulation. Finally, Sect. 6 concludes the paper.
2 System model, assumptions and notations
In this paper, we focus on a sporadic task model in [3], in which a task τi in a task set τ is specified by (Ti , Ci ) where Ti is the the minimum separation between successive invocations (or the task period), and Ci is the worst-case execution time. Without loss of generality, we sort tasks in τ such that a task with a smaller Ti has a smaller task index, i.e., T1 ≤ T2 ≤ …T|τ|, where |τ| is the number of tasks in the set τ. A task τi invokes a series of jobs; each job is separated from the predecessor/successor job by at least Ti time units, and supposed to finish its execution within Ti time units. We assume that a job can be preempted at any time.
We consider a uniprocessor system, on which at most one job can be executed in each time slot. We focus on two popular scheduling algorithms, EDF and RM [3]. In each time slot, while EDF executes a job with the earliest deadline, RM executes a job with the smallest task period (Ti ).
3 Scheduling framework based on a dummy task for fewer preemptions
We now present a dummy-task-based scheduling framework to reduce preemptions. To achieve this, we first identify some preemption behavior under EDF and RM. Based on this observed behavior, we develop a dummy-task-based scheduling framework, which can significantly reduce the number of preemptions under EDF and RM. Finally, we derive an important property of the framework.
1 Wewouldliketostressthattheframeworkcanutilizeanyexistingschedulabilityanalysisinthatitsimply adds the dummy task to the original task set.
123
1260
J. Lee
Table 1 Percentage of preemptions caused by a specific task under EDF and RM; 4500 task sets, each consisting of five tasks with Tmax = 1000, are tested, and how to generate task sets is detailed in Sect. 5
Task # of preemptions incurred by a specific task (%)
3.1 Preemption behavior under EDF and RM
Under EDF (%)
τ1 83.5 τ2 12.4 τ3 3.4 τ4 0.8 τ5 0.0
Under RM (%)
80.5 13.3 4.6 1.5 0.0
While preemption depends on the underlying scheduling algorithms, we will show that under EDF and RM, the task with the shortest period is a dominant source of preemption. Specifically, we will present an analytic property and an empirical result of the dominant preemption source.
The following observation states the preemption behavior under EDF and RM.
Observation 1 Under EDF and RM, a job Jx can preempt another job Jy , only upon release of Jx . Moreover, a preemption occurs only if the period of Jx is no larger than that of Jy.
Proof Since the priority of jobs does not vary with time under EDF and RM, a job can preempt another job only when it is released. What remains is thus to prove the task period condition for preemptions.
Under EDF, if τi has a longer period than τ j (i.e., Ti > T j ), a newly-released job of τi cannot have an earlier deadline than a currently-executing job of τ j . Under RM, if Ti > Tj, all jobs of τi have lower priorities than all jobs of τj, meaning that no job of τi can preempt any job of τ j . Thus, the lemma follows. ⊓⊔
By Observation 1, we know that a job of τi can preempt another job of τ j only if i < j (recall that tasks are indexed in ascending order according to their periods). Then, a task with a smaller index has more likely to cause preemptions. Thus, while τ1 (i.e., the task with the smallest period) can preempt jobs of all other tasks, regardless of their deadlines under RM, and depending on their deadlines under EDF, τ|τ| (i.e., the task with the largest period) cannot preempt any job in any case under EDF and RM. To obtain the statistical results of this property, we simulate 4500 task sets of five tasks each, and measure the number of preemptions during the first 100,000 time units for each task set. As shown in Table 1, most preemptions are caused by τ1: 83.5% under EDF, and 80.5% under RM. Note that τ5 cannot cause any preemption by Observation 1.
Using Observation 1 and the simulation result, we will develop next a new schedul- ing framework that can reduce preemptions.
3.2 Dummy-task-based scheduling framework
Observation 1 and the simulation result in Table 1 indicate “which task” and “when” we should control. That is, to effectively reduce the number of preemptions under
123
Real-time uniprocessor scheduling with fewer preemptions 1261
Algorithm 1 Dummy-task-based scheduling framework
Timer Set: If a newly-released job of τ1 has a higher priority than the currently-executing job at t, and the release time of the dummy task’s previous job is no later than the current time − Tx ,
1: Release a job of the dummy task τx with the execution time Cx .
2: Setthetimertot+Cx.
3: Let the currently-executing job inherit the priority of the job of the dummy task, i.e., keep the currently-
executing job executing.
4: Put the newly-released job of τ1 into the wait queue.
Timer expiration: If the timer expires at t and the currently-executing job is the one that inherits the priority of a job of the dummy task,
1: Let the currently-executing job stop inheriting the priority of the dummy task’s job, i.e., let the currently- executing job stop execution.
2: Put the currently-executing job in the wait queue. 3: Start execution of the τ1’s job in the wait queue.
EDF or RM, we should control preemptions incurred by the task with the smallest task period (i.e., τ1 ∈ τ), when it releases jobs. With this information, our goal is to reduce the number of preemptions without compromising task set schedulability. In other words, controlling preemptions should not make any schedulable task set unschedulable.
To achieve this goal, we add a dummy task τx (Tx , Cx ) which invokes its jobs as follows:
(i) τx invokes a job only when a newly-released job of τ1 has a higher priority than the currently-executing job.
(ii) The minimum separation between successive jobs (or the task period) of τx is T1, i.e., Tx = T1.
Since Tx = T1, two jobs of τx and τ1 always have the same priority under RM, and two jobs of τx and τ1 released at the same time have the same priority under EDF. For the same-priority jobs, we enforce a tie-breaking rule; we give a higher priority to the dummy task’s job if the priorities of multiple jobs are the same under EDF or RM. Then, between the two jobs of τ1 and τx , released at the same time, the job of τx is always a given priority over that of τ1. Therefore,
(iii) a job of τx has the highest priority when it is released, and this holds until its execution is completed. So, the job of τx executes for Cx time units without any preemption.
Under RM, a job of τx always has the highest priority. Recalling (i), under EDF, a job of τx has the highest priority when it is released. Since τx has the smallest period (Tx ), no job released after τx releases a job, has a shorter deadline than the job of τx .
Using the property (iii), we can prevent a job of τ1 from preempting the currently- executing job, by letting the currently-executing job inherit the priority of the job of τx . Then, by (iii), the currently-executing job can continue its execution without any preemption until the (virtual) execution of the dummy task’s job is completed. Algorithm 1 details this dummy-task-based scheduling framework using (i), (ii) and (iii). It is important to note that the currently-executing job can have the highest priority during Cx time units because the virtual execution time of the job of the dummy task is Cx , and this is implemented using a timer in the algorithm.
123
1262 J. Lee
As one can see in Algorithm 1, the dummy-task-based scheduling framework does not change the prioritization policy of the original scheduling algorithms. Instead, it adds jobs of the dummy task, and gives the currently-executing job chance to continue execution. Therefore, it need not (a) know job release patterns offline and (b) enforce complicated online mechanisms, which are required by some existing approaches. The only additional overhead is setting and expiration of a timer set for dummy jobs. Also, one more advantage of the framework in Algorithm 1 is its wider applicability to different scheduling algorithms. The framework can be applied not only to both EDF and RM, but also potentially to other existing algorithms; we can also re-use existing schedulability analyses by simply adding a dummy task when the task set is tested.
In the rest of the paper, let EDF-d (likewise RM-d) denote EDF (likewise RM) associated with Algorithm 1.
One may regard the proposed framework as a different expression of an existing technique called the limited preemption [9]. Under the limited preemption technique, a job always keeps its execution without any preemption during X time units, where X is the invoking task’s length of non-preemptive region. Since the technique always disallows preemptions of a job of a task during X time units, it is impossible to selectively prevent a currently-executing job from being preempted by a job of τ1. Therefore, the limited preemption technique with any parameter cannot yield the schedule generated by the proposed framework.
3.3 Property and example
Since Algorithm 1 is developed for fewer preemptions, it is important to determine whether the algorithm guarantees the reduction of the number of preemptions of any task set under a certain condition, compared to the corresponding original scheduling, which has not been done with any existing study. That is, we want to find the property that the number of preemptions of any task set under EDF-d is smaller than that under EDF. The following lemma addresses the property.
Lemma 1 As long as there is no deadline miss, the number of preemptions of a task set under EDF-d (likewise RM-d) is no greater than that under EDF (likewise RM).
Proof Let nEDF(t) and nEDF-d(t) denote the number of preemptions of a task set in [0,t) under EDF and EDF-d, respectively. Suppose that there exists t such that nEDF-d(t) > nEDF(t). We focus on the earliest t, called t0. Then, at t0, a preemption occurs under EDF-d, but not under EDF. We consider two cases: the job which incurs a preemption at t0 belongs to (i) τ1, and (ii) other task than τ1.
Case (i). Since a job of the dummy task is released whenever a job of τ1 is released, the job of τ1 causes a preemption only when the timer is expired at t0 (which was set to t0 − Cx ). Then, at t0 − Cx (when the timer is set), a preemption occurs under EDF, but not under EDF-d. Therefore, nEDF-d(t0 − Cx ) ≤ nEDF(t0 − Cx ) − 1 holds; otherwise, nEDF-d(t0 − Cx − ε) > nEDF(t0 − Cx − ε) holds for a small ε > 0, which contradicts the definition of t0. Using the inequality of nEDF-d(t0 − Cx ) ≤ nEDF(t0 − Cx ) − 1 and the fact that there is no preemption under EDF-d in (t0 − Cx , t0), we derive that nEDF-d(t0) ≤ nEDF(t0), which contradicts the supposition.
123
Real-time uniprocessor scheduling with fewer preemptions 1263
Fig. 1 Schedules with preemption behavior of τ = {τ1(T1 = 4, C1 = 1), τ2(12, 4), τ3(20, 3)} under EDF or RM, and EDF-d or RM-d
Case (ii). A job J of a task other than τ1 can incur a preemption only when it is released and the currently-executing job has a lower priority than J. If we compare the schedule under EDF-d with that under EDF, the currently-executing job with the former has an equal- or higher-priority than that with the latter (since the former allows a job to inherit a dummy job’ priority, which is the highest). Therefore, the supposition cannot hold.
By Cases (i) and (ii), the lemma holds for EDF-d; the proof for RM-d is the same as that for EDF-d. ⊓⊔
We would like to emphasize that such a guarantee on preemption reduction has not been achieved by existing studies (which can reduce the number of preemptions on average). While Lemma 1 guarantees fewer preemptions, we present an illustrative example, showing how Algorithm 1 actually reduces preemptions.
Example 1 Consider a task set τ with three tasks {τ1(T1 = 4, C1 = 1), τ2(12, 4), τ3(20, 3)}, and suppose that jobs of the tasks are periodically released starting from t = 0. Then, the execution order in [0, 10) under EDF or RM is shown in the upper figure of Fig. 1. Here, the total number of preemptions of τ in [0, 10) under EDF orRMis2;thesecondjobofτ1 preemptsthefirstjobofτ2 att = 4,andthe third job of τ1 does the first job of τ3 at t = 8. However, if we apply Algorithm 1 with a dummy task τx (Tx = 4, Cx = 1), the execution order in [0, 10) under EDF- d or RM-d is shown in the lower figure of Fig. 1, where no preemption occurs. That is, the currently-executing job of τ2 at t = 4 (likewise τ3 at t = 8) inher- its the priority of a job of the dummy task, and finishes its execution without any preemption.
As shown in Lemma 1 and Example 1, we can effectively reduce preemptions by Algorithm 1, which delays the execution of τ1’s jobs through the virtual exe- cution of dummy jobs. However, such a delay may make a schedulable task set unschedulable. In the next section, we will discuss how to set Cx (the virtual execu- tion time of the dummy task) without compromising the schedulability of a given task set.
123
1264 J. Lee
4 Dummy task parameter setting
This section describes how to set the execution time of the dummy task for EDF-d and RM-d, without compromising the schedulability of a given task set.
4.1 Generation of a dummy task for EDF-d
To guarantee the schedulability under EDF, we use the following existing exact schedu- lability condition.
Lemma2 (Theorem7in[3])UnderEDFwithanyarbitrarytie-breakingrule,atask set τ is schedulable if and only if the following conditions holds:
Ci ≤1. (1) τi∈τ Ti
Using Lemma 2, we determine the execution time of the dummy task as follows. Theorem1 SupposethatLemma2guaranteesatasksetτtobeschedulablebyEDF.
Then, τ is also schedulable by EDF-d, if the dummy task τx is set as follows: C
Cx Ci
T + T ≤
+
Ci/Ti =1. (3)
Cx≤1− i·Tx. (2) τi∈τ Ti
Proof If we focus on τ ∪ {τx }, the following conditions holds.
1 −
Ci τi∈τ Ti
T x
· Tx
τi∈τ
x τi∈τ i
Therefore, by Lemma 2, τ ∪ {τx } is schedulable by EDF.
If we compare the schedule of τ under EDF-d, with that of τ ∪ {τx } under EDF, the finishing time of any job in the former is equal to, or earlier than that of the same job in the latter. Therefore, since τ ∪ {τx } is schedulable under EDF, τ is schedulable under EDF-d. Thus, the theorem follows. ⊓⊔
In Sect. 5, we will demonstrate the effectiveness of EDF-d in terms of the number of preemptions, by setting Cx to the RHS of Eq. (2), i.e., the largest possible Cx .
4.2 Generation of a dummy task for RM-d
For RM, we use the following existing exact schedulability condition.
Lemma 3 (Fig. 3 in [22]) Under RM, a task set τ is schedulable if and only if every
task τk satisfies Rs∗ ≤ Tk such that Rs∗+1 ≤ Rs∗ for some s∗, starting from R0 = Ck: kkkk
s + 1 R ks
Rk ←Ck + T ·Ci, (4)
τi ∈HP(τk ,τ ) i
123
Real-time uniprocessor scheduling with fewer preemptions 1265
where HP(τk,τ) denotes a set of tasks in τ whose priority is higher than τk, i.e., HP(τk,τ) {τi ∈ τ|Ti ≤ Tk}.
Following Lemma 3, we set the execution time of the dummy task as follows.
Theorem 2 Suppose that Lemma 3 guarantees a task set τ to be schedulable by RM.
Then, τ is also schedulable by RM-d, if the dummy task τx is set as follows: every task
τk ∈ τ satisfies Rs∗ ≤ Tk such that Rs∗+1 ≤ Rs∗ for some s∗, starting from R0 = Ck: kkkk
Rs Rs+1 ←Ck + k
·Cx +
Rs
k ·Ci. (5)
τi∈HP(τk,τ) Ti
k Tx
Proof TheproofissimilartothatofTheorem1.Ifwecomparethescheduleofτunder RM-d, with that of τ ∪ {τx } under RM, the finishing time of any job in the former is equal to or earlier than that of the same job in the latter. Therefore, if τ ∪ {τx } is schedulable under RM, τ is schedulable under RM-d. By Lemma 3, the condition in Theorem 2 is the exact schedulability condition of a task set τ ∪ {τx } under RM. This proves the theorem. ⊓⊔
In Sect. 5, we will demonstrate the reduction of the number of preemptions by RM-d using the largest possible Cx , which is calculated by applying the binary search to Theorem 2.
5 Evaluation and discussion
This section compares the number of preemptions under EDF-d and RM-d, with that under EDF and RM.
Task set generation We generate task sets based on a widely used technique [23,24]. To make a variety of task sets, we consider two task parameters: task utilization (Ci /Ti ) and the maximum task period (Tmax ). First, we consider 10 individual task utilization (Ci / Ti ) distributions: bimodal with parameters 0.1, 0.3, 0.5, 0.7 and 0.9, and exponential with parameters 0.1, 0.3, 0.5, 0.7 and 0.9. For a given bimodal parameter p, a value for Ci/Ti is uniformly distributed in [0,0.5) with probability p, and in [0.5, 1] with probability 1 − p. For a given exponential parameter 1/λ, a value for Ci/Ti is chosen according to an exponential distribution whose probability density function is λ · exp(−λ · x ). Second, we consider two different maximum task periods: Tmax = 10 and Tmax = 1000. Then, for each task, Ti is uniformly chosen in [1, Tmax ], and Ci is chosen based on the given bimodal or exponential parameter. Note that we set Ti and Ci to the closest positive integer values.
For a given bimodal or exponential parameter and a given Tmax, we repeat the following procedure and generate 10,000 task sets, yielding 200,000 task sets in total.
1. Wegenerateasetoftwotaskssinceatasksetconsistingofasingletaskistrivially schedulable.
Ci/Ti ≤1[3].
2. In order to exclude unschedulable task sets, we check the generated task set τ can
passtheexactfeasibilitycondition,i.e.,
τi ∈τ
123
1266 J. Lee
3. If it fails to pass the feasibility test, we discard the generated task set and return to Step 1. Otherwise, we include this set for evaluation. Then, this set serves as a basis for the next new set; we create a new set by adding a new task into an already created and tested set, and return to Step 2.
Average performance comparison To compare the number of preemptions under EDF with EDF-d, and RM with RM-d, we simulate each task set with periodic job releases from t = 0 and on. Then, we measure the number of preemptions under each schedul- ing algorithm until 2520 time units when Tmax = 10, which is a common multiple of task periods in any task set with Tmax = 10. Then, the preemption behavior (as well as schedules) of each task set with Tmax = 10 for the first 2520 time units is repeated forever.FortasksetswithTmax =1000,itisintractabletosimulateeachtasksetupto the least common multiple of its task periods, and therefore, we measure the number of preemptions until 100,000 time units for task sets with Tmax = 1000.
Ci / Ti . Note that the smallest possible contribution of a task to task set utilization is 0.1 for Tmax = 10 (when Ci = 1 and Ti = 10). Since the number of tasks in each task set is at least two, the number of generated task sets whose task set utilization is in [0, 0.5] is small for Tm a x = 10. Therefore,weonlyshowapartialrangeoftasksetutilizationinthex-axisforTmax = 10, i.e., [0.5, 1.0], while we present the entire range for Tmax = 1000, i.e., [0.0, 1.0]. Figure 2a, c show the ratio of the number of preemptions of EDF-d to that of EDF. As shown in the figures, when task set utilization is low, EDF-d significantly reduces the number of preemptions in terms of the ratio. This is because EDF-d can accommodate the dummy task with a large Cx , and then in most cases, a job of τ1 does not resume its execution before the completion of the job that inherits the priority of the dummy job. As the task utilization gets higher, we have a smaller Cx, resulting in higher chance for a job of τ1 to preempt the currently-executing job when the job of τ1 resumes its execution. In the extreme case of task set utilization equal to 1.0, we cannot accommodate any positive value of Cx , and therefore, the number of
preemptions under EDF-d is the same as that under EDF.
Figure 2b, d show the quantitative difference of the number of preemptions under
EDF-d and EDF. For low task set utilization, EDF-d cannot reduce a larger number of preemptions, because the number of preemptions under EDF itself is not substantial in this environment. Therefore, although the ratio of the number of preemptions of EDF-d to EDF is increasing, the absolute value for EDF-d to reduce the number of preemptions is increasing up to a certain point; in the figures, the maximum point is around 0.8 when Tmax = 1000 and 0.65 when Tmax = 10. Beyond this point, it is difficult to reduce the number of preemptions due to a small (or even zero) Cx .
For the comparison of RM-d and RM, we only focus on RM-schedulable task sets by Lemma 3, resulting in 88,483 task sets out of 100,000 task sets with Tmax = 1000 and94,476tasksetsoutof100,000setswithTmax =10.Then,thedifferencebetween the preemption behavior of RM-d and RM is similar to that between the preemption behavior of EDF-d and EDF. As shown in Fig. 3a, c, the ratio of the number of preemptions of RM-d to RM is increasing as the task utilization gets larger; if task set
Then, Fig. 2 compares the number of preemptions of EDF-d with that of EDF, and RM-d with RM, in terms of their ratio and difference. In each figure, the x-
axis represents task set utilization, i.e.,
τi ∈τ
123
Real-time uniprocessor scheduling with fewer preemptions
1267
Fig. 2 Comparison of the number of preemptions under EDF-d with EDF. a Ratio of the number of preemptions between EDF-d and EDF when
Tmax = 1000. b Difference of the number of preemptions between EDF and EDF-d when Tmax = 1000. c Ratio of the number of preemptions between EDF-d and EDF when
Tmax = 10. d Difference of the number of preemptions between EDF and EDF-d when
Tmax = 10
(a)
(b)
(c)
(d)
123
1268 J. Lee
Fig. 3 Comparison of the number of preemptions under RM-d and RM. a Ratio of the number of preemptions between RM-d and RM when
Tmax = 1000. b Difference of the number of preemptions between RM and RM-d when Tmax = 1000. c Ratio of the number of preemptions between RM-d and RM when
Tmax = 10. d Difference of the number of preemptions between RM and RM-d when Tmax = 10
(a)
(b)
(c)
123
(d)
Real-time uniprocessor scheduling with fewer preemptions 1269
utilization equals to 1.0, the number of preemptions under RM-d is the same as that under RM. In Fig. 3b, d, the number of preemptions reduced by RM-d is maximized when task set utilization is around 0.7 when Tmax = 1000 and 0.65 when Tmax = 10.
In summary, EDF-d and RM-d effectively reduce the number of preemptions, com- pared to the corresponding scheduling algorithms EDF and RM. Also, we observe that the resource saved by EDF-d and RM-d is maximized with a certain task utilization, which varies with scheduling and task set specification. Then, the saved resource by reducing the number of preemptions can be utilized to enhance system performance, e.g., accommodation of more non-real-time tasks, and/or quick response of non-real- time tasks.
6 Conclusion
We proposed a simple but effective scheduling framework that incurs fewer preemp- tions, and applied the framework to two popular scheduling algorithms, EDF and RM, yielding EDF-d and RM-d. We not only proved that the framework does not increase the number of preemptions for any task set, but also demonstrated via simulation that EDF-d and RM-d effectively reduces the number of preemptions, compared to EDF and RM.
While the framework targets uniprocessor platforms, the dummy-task-based scheduling concept can be extended to multiprocessor platforms. It would be interest- ing to generalize the framework for multiprocessor platforms and global scheduling algorithms that are specialized for the platforms, e.g., EDZL [25], SPDF [26].
Acknowledgements This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2016R1D1A1B03930580) and the Ministry of Science, ICT & Future Planning (NRF-2017R1A2B2002458, NRF-2014R1A1A103- 5827).
References
1. BaskiyarS,HuangC-C,TamT-Y(2016)Minimumenergyconsumptionforratemonotonicscheduled tasks. Computing 98(6):661–684
2. Kim SC, Lee S (2015) Decentralized task scheduling for a fixed priority multicore embedded rtos. Computing 97(6):543–555
3. LiuC,LaylandJ(1973)Schedulingalgorithmsformulti-programminginahard-real-timeenvironment. J ACM 20(1):46–61
4. ButtazzoG,BertognaM,YaoG(2013)Limitedpreemptiveschedulingforreal-timesystems:asurvey. IEEE Trans Ind Inf 9(1):3–13
5. WangY,SaksenaM(1999)Schedulingfixed-prioritytaskswithpreemptionthreshold,In:Proceedings of IEEE international conference on embedded and real-time computing systems and applications (RTCSA), pp 318–335
6. Kim S, Hong S, Kim T-H (2002) Integrating real-time synchronization schemes into preemption threshold scheduling, In: Proceedings of the 5th IEEE international symposium on object-oriented real-time distributed computing, pp 145–152
7. KimS,HongS,KimT-H(2002)Perfectingpreemptionthresholdschedulingforobject-orientedreal- time systems design: from the perspective of real-time synchronization, In: Proceedings of languages, compilers, and tools for embedded systems, pp 223–232
123
1270 J. Lee
8. Bril RJ, van den Heuvel MM, Keskin U, Lukkien JJ (2012) Generalized fixed-priority scheduling with limited preemptions, In: Proceedings of Euromicro conference on real-time systems (ECRTS), pp 209–220
9. Baruah S (2005) The limited-preemption uniprocessor scheduling of sporadic task systems, In: Pro- ceedings of Euromicro conference on real-time systems (ECRTS), pp 137–144
10. BrilRJ,LukkienJJ,VerhaeghWFJ(2007)Worst-caseresponsetimeanalysisofreal-timetasksunder fixed-priority scheduling with deferred preemption revisited. In: Proceedings of the 19th Euromicro conference on real-time systems, pp 269–279
11. Yao G, Buttazzo G, Bertogna M (2009) Bounding the maximum length of non-preemptive regions under fixed priority scheduling, In: Proceedings of IEEE international conference on embedded and real-time computing systems and applications (RTCSA), pp 351–360
12. Bertogna M, Baruah S (2010) Limited preemption EDF scheduling of sporadic task systems. IEEE Trans Ind Inf 6(4):579–591
13. Davis RI, Bertogna M (2012) Optimal fixed priority scheduling with deferred pre-emption, In: Pro- ceedings of IEEE real-time systems symposium (RTSS), pp 39–50
14. Dobrin R, Fohler G (2004) Reducing the number of preemptions in fixed priority scheduling. In: Proceedings of the 16th Euromicro conference on real-time systems, pp 144–152
15. KimW,KimJ,MinSL(2004)Preemption-awaredynamicvoltagescalinginhardreal-timesystems. In: Proceedings of the 2004 international symposium on low power electronics and design, pp 393–398
16. Yang C-Y, Chen J-J, Kuo T-W (2007) Preemption control for energy-efficient task scheduling in systems with a dvs processor and non-dvs devices. In: Proceedings of the 13th IEEE international conference
on embedded and real-time computing systems and applications, pp 293–300
17. Yang L, Lin M, Yang LT (2009) Integrating preemption threshold to fixed priority dvs scheduling algorithms. In: Proceedings of the 15th IEEE international conference on embedded and real-time
computing systems and applications, pp 165–171
18. Thekkilakattil A, Pillai AS, Dobrin R, Punnekkat S (2010) Reducing the number of preemptions
in real-time systems scheduling by cpu frequency scaling. In: Proceedings of the 18th international
conference on real-time and network systems, pp 144–152
19. BertognaM,ButtazzoG,MarinoniM,CaccamoM(2010)Preemptionpointsplacementforsporadic
task sets. In: Proceedings of Euromicro conference on real-time systems (ECRTS), pp 251–260
20. Bertogna M, Xhani O, Marinoni M, Esposito F, Buttazzo G (2011) Optimal selection of preemption points to minimize preemption overhead. In: Proceedings of Euromicro conference on real-time systems
(ECRTS), pp 217–227
21. LeeJ,ShinKG(2014)PreemptajobornotinEDFschedulingofuniprocessorsystems.IEEETrans
Comput 63(5):1197–1206
22. Audsley N, Burns A, Richardson M, Wellings A (1991) Hard real-time scheduling: the deadline-
monotonic approach. In: Proceedings of the IEEE workshop on real-time operating systems and
software, pp 133–137
23. Baker TP (2005) Comparison of empirical success rates of global vs. paritioned fixed-priority and
EDF scheduling for hard real time. Tech. Rep. TR-050601, Dept. of Computer Science, Florida State
University, Tallahasee
24. LeeJ,EaswaranA,ShinI(2011)Maximizingcontention-freeexecutionsinmultiprocessorscheduling.
In: Proceedings of IEEE real-time technology and applications symposium (RTAS), pp 235–244
25. LeeSK(1994)On-linemultiprocessorschedulingalgorithmsforreal-timetasks.In:IEEERegion10’s
ninth annual international conference, pp 607–611
26. ChwaHS,BackH,ChenS,LeeJ,EaswaranA,ShinI,LeeI(2012)Extendingtask-leveltojob-level
fixed priority assignment and schedulability analysis using pseudo-deadlines. In: Proceedings of IEEE real-time systems symposium (RTSS), pp 51–62
123