=Paper=
{{Paper
|id=Vol-1697/EWiLi16_3
|storemode=property
|title=Optimal Priority and Threshold Assignment for Fixed-priority Preemption Threshold Scheduling
|pdfUrl=https://ceur-ws.org/Vol-1697/EWiLi16_3.pdf
|volume=Vol-1697
|authors=Leo Hatvani,Sara Afshar,Reinder J. Bril
|dblpUrl=https://dblp.org/rec/conf/ewili/HatvaniAB16
}}
==Optimal Priority and Threshold Assignment for Fixed-priority Preemption Threshold Scheduling==
https://ceur-ws.org/Vol-1697/EWiLi16_3.pdf
Optimal Priority and Threshold Assignment for
Fixed-priority Preemption Threshold Scheduling∗
Leo Hatvani Sara Afshar Reinder J. Bril
Technische Universiteit Mälardalen University (MDH) Technische Universiteit
Eindhoven (TU/e) Västerås, Sweden Eindhoven (TU/e)
The Netherlands sara.afshar@mdh.se The Netherlands
l.hatvani@tue.nl Mälardalen University (MDH)
Västerås, Sweden
r.j.bril@tue.nl
ABSTRACT the flexibility of dynamic-priority algorithms, fixed-priority
Fixed-priority preemption-threshold scheduling (FPTS) is a scheduling algorithms are a de facto standard in industry
generalization of fixed-priority preemptive scheduling (FPPS) due to their lower implementation and execution overhead
and fixed-priority non-preemptive scheduling (FPNS). Since compared to dynamic-priority algorithms.
FPPS and FPNS are incomparable in terms of potential Another way of classifying scheduling algorithms is whether
schedulability, FPTS has the advantage that it can schedule they allow a task that is currently executing to be preempted
any task set schedulable by FPPS or FPNS and some that or not, these are preemptive and non-preemptive schedul-
are not schedulable by either. FPTS is based on the idea that ing algorithms. Recently, new scheduling approaches have
each task is assigned a priority and a preemption threshold. been proposed as an alternative to the extremes of fully pre-
While tasks are admitted into the system according to their emptive and non-preemptive scheduling. One such scheduling
priorities, they can only be preempted by tasks that have approach is called fixed-priority preemption threshold schedul-
priority higher than the preemption threshold. ing (FPTS) [12, 11] where each task τi is annotated by a
This paper presents a new optimal priority and preemption preemption threshold θi besides its priority πi . Preemption
threshold assignment (OPTA) algorithm for FPTS which in threshold for a task specifies which tasks can preempt it and
general outperforms the existing algorithms in terms of the is always greater than or equal to the priority of that task.
size of the explored state-space and the total number of worst If a task’s priority is higher than the preemption threshold
case response time calculations performed. The algorithm is of the currently executing task, it is allowed to preempt the
executing task. This means that as soon as the task starts
based on back-tracking, i.e. it traverses the space of potential
priorities and preemption thresholds, while pruning infeasible executing, its effective priority is increased to its preemption
paths, and returns the first assignment deemed schedulable. threshold.
We present the evaluation results where we compare the There are two special cases of the FPTS scheduling algo-
complexity of the new algorithm with the existing one. We rithm. First, when the preemption threshold of every task is
show that the new algorithm significantly reduces the time equal to the task’s priority, FPTS becomes equivalent to the
needed to find a solution. Through a comparative evaluation, FPPS scheduling algorithm. Second, when all preemption
we show the improvements that can be achieved in terms of thresholds are equal to the highest priority in the system,
schedulability ratio by our OPTA compared to a deadline FPTS becomes equivalent to FPNS, as no task can preempt
monotonic priority assignment. any other task.
FPTS improves the schedulability compared to both ap-
proaches by leveraging the preemption of higher priority tasks
CCS Concepts under FPPS and the blocking incurred by non-preemptive
•Computer systems organization → Embedded soft- execution of lower priority tasks under FPNS. An optimal pri-
ware; •Software and its engineering → Real-time schedu- ority and threshold assignment (OPTA) algorithm for FPTS
lability; is any algorithm that for a given set of tasks determines
if it can be scheduled by means of FPTS and when it can
be scheduled provides task priorities and thresholds. The
1. INTRODUCTION original OPTA for FPTS has been introduced by Wang and
Scheduling theory has been widely studied over the years Saksena [12]. However, the high computation time required
to provide effective scheduling solutions for real-time em- to find a feasible solution using this algorithm, if such exists,
bedded systems. Scheduling algorithms can be divided into warrants research into more efficient approaches [6]. In this
fixed-priority and dynamic-priority, where the priorities of paper, we introduce a new OPTA algorithm for FPTS which
tasks stay the same throughout the execution of the system effectively can decrease the computation time of finding a
for the former ones and change depending on some parameter feasible solution. Our algorithm is based on (i) backtracking,
for the latter ones. Even though it can be said that they lack (ii) pruning to reduce the search space, and (iii) a heuristic
∗This work is supported by the ARTEMIS Joint Undertaking to traverse the search space.
project EMC2 (grant agreement 621429). Contributions: In this paper we propose an algorithm for
EWiLi’16, October 6th, 2016, Pittsburgh, USA. optimal priority and threshold assignment. Moreover, we
Copyright retained by the authors.
show by means of experimental results that the computation The preemption of a higher priority task is postponed until
time for finding a priority and threshold assignment for a set the next preemption point of a running task. This approach
of tasks that can make them schedulable, if such a combina- is also referred to as cooperative scheduling.
tion exists, is growing considerably slower compared to the Worst-case response time analysis for FPTS as well as
existing solution when the number of tasks increases. Fur- an optimal priority and preemption threshold assignment
ther, we present the schedulability results of comparing our algorithm was first presented in [12]. Later, in [10], it has
proposed algorithm with FPPS and FPTS under a deadline been shown that the analysis in [12] was optimistic, and a
monotonic assignment. Finally, we present a comparative revised analysis was presented.
evaluation of FPTS with a deadline monotonic priority as- Worst-case response time analysis of periodic real-time
signment and optimal preemption thresholds and our OPTA, tasks under fixed-priority scheduling with deferred preemption
which clearly illustrates the advantage of our OPTA. (FPDS)has been studied in [4, 5, 8]. In [3], Bril et. al have
shown that the analysis presented in [4, 5] is both pessimistic
2. MOTIVATION EXAMPLE and optimistic where they have revised the analysis.
In this section we show by means of an example that the
deadline monotonic priority assignment is not optimal for 4. SYSTEM MODEL
FPTS.
4.1 Task Specification
Table 1: Specifications of TI task set. The system consist of a single processor including a set
of n independent sporadic tasks. Each task τi is denoted
task Ci Ti = Di πiDM πi θi Ri
by < Ci , Di , Ti >, where Ci ∈ R+ denotes the worst-case
τ1 1 7 1 1 1 1 execution time, Di ∈ R+ denotes the relative deadline and
τ2 8 23 2 2 2 21 Ti ∈ R+ is the minimum inter-arrival time. We assume a
τ3 10 25 3 4 2 25 constrained-deadline task model, i.e., Di ≤ Ti (even though
τ4 3 33 4 3 2 25 we use a generalized analysis).
Let us consider a task set TI which consists of 4 tasks as 4.2 FPTS Scheduling
presented in Table 1. The tasks are characterized by their Tasks are further annotated by unique priorities πi ∈ N
worst-case computation time Ci , minimum inter-arrival time and preemption thresholds θi ∈ N. For both, smaller values
Ti , deadline Di , preemption thresholds θi , and priority πi . denote higher priorities. Whenever we compare priorities or
The smaller numbers denote higher priorities. All tasks have thresholds, we compare their numerical values, i.e. πi < πj
implicit deadlines, i.e. Ti = Di , and the priorities πiDM are means that task πi has a higher priority than πj . Preemption
assigned based on deadline monotonic priority assignment, thresholds are always greater than or equal to the correspond-
i.e. the task with the smallest deadline has the highest ing priorities θi ≤ πi .
priority. At utilization U TI ≈ 0.982, TI is not schedulable Given these priorities and thresholds, the tasks are sched-
under FPTS. If the priorities of τ3 and τ4 are exchanged (as uled as follows. If there are no running tasks, the task τi
in πi ) TI becomes schedulable under FPTS with preemption with the highest priority among the simultaneously released
thresholds θi and worst-case response times Ri . tasks starts executing. As soon as it starts executing it can
be preempted only by tasks τj that have priority greater
3. RELATED WORK than its preemption threshold πj < θi . In the situation when
the executing task has a higher priority than the preempted
Preemption Threshold Scheduling (PTS) has been pro-
task τi and waiting task τj where θi ≤ πj , τi will always
posed by Wang and Saksena in [12]. Under this approach,
start executing before τj .
besides a regular priority, each task is assigned a preemption
threshold up to where it can prevent preemptions. The pre-
emption is allowed only when the priority of a ready task is 5. RESPONSE TIME ANALYSIS
higher than the threshold of the running task.
Deferred Preemptions Scheduling (DPS) has first been in- 5.1 Analysis
troduced by Baruah [1] under Earliest Deadline First (EDF). While worst-case response time analysis for FPTS policy
Under this approach, for each task the longest interval that has been published several times [12, 10], in this paper we
can be executed non-preemptively is specified. Two types employ the exact analysis presented by Keskin et al. [7] with
of implementation exist for this approach based on how the the added assumption that there is no jitter.
non-preemptive regions are implemented: Floating model A task τi releases an infinite series of jobs τik . Each of
and Activation-triggered model implementation. Under the these jobs faces two kinds of delays to its execution: blocking
former model, non-preemptive regions are specified in the and interference. Blocking (1) comes from the lower priority
code by inserting specific primitives that disable and enable tasks that have a preemption threshold equal to or higher
preemption. Under the later model, non-preemptive regions than the priority of the current task.
are specified by setting a timer at the arrival of a higher
priority task which lasts for the specified non-preemptive Bi = max(0, max Cj ) (1)
∀j:θj ≤πi <πj
interval.
Fixed Preemption Points (FPP) has been proposed by Since the sequence of jobs released by the task τi is infinite,
Burns [4]. Under FPP, preemption is allowed only at prede- we need to determine how many jobs should be analyzed to
fined points during a task’s execution. As a results, a task is determine whether the entire task is schedulable or not. This
divided into a number of non-preemptive execution chunks. calculation is based on the worst-case level-i active period
[3] and is given as the smallest positive Li that satisfies (2). we can inspect that while blocking value Bi in (4) influences
Li only the start time of the task, if the same computation
Li = B i + Cj (2) time is allocated to a higher priority, it is introduced into
Tj the computation of starting time (4) and optionally finishing
∀j:πj ≤πi
time (5) as Cj .
The maximum number li of jobs of τi that can be executed
in this level-i active period is given by (3). Lemma 1. Let τi be a task and T be a set of schedulable
Li tasks with assigned priorities and thresholds. If task τi is
li = (3) not schedulable in the context of T with the lowest priority
Ti
∀πj ∈ T : πi > πj and any preemption threshold, it will not
Given the knowledge of how many jobs need to be analyzed, be schedulable if additional tasks are added to T .
we can compute their worst-case start time Sik for 0 ≤ k < li
as the smallest positive value Sik that satisfies (4). From the worst case response time equations, it is trivial
⎧ to deduce that adding more interference will never reduce
⎪ Sik
⎨ Bi + kCi + ∀j:πj <πi Tj Cj
⎪ if Bi > 0 the response time.
Sik =
⎪
⎪
⎩ kCi + 1 + Sik
Cj if Bi = 0
∀j:πj <πi Tj 6. OPTIMAL PRIORITY AND THRESHOLD
(4) ASSIGNMENT
Likewise, other tasks may preempt the observed job, thus
causing interference. This quantity is encompassed by calcu- In this section, we present an OPTA algorithm for FPTS.
lating each job’s worst-case finalization time Fik . It can be The algorithm is optimal in the sense that it will find a
found as the smallest positive Fik that satisfies (5). feasible priority and thresholds assignment that makes a
⎧ task set schedulable if such solution exists. Similar to the
⎪
⎪ Sik + Ci + OPTA in the work by Wang and Saksena [12] (including the
⎪
⎪
⎪
⎪ correction discussed in Section 7), the algorithm proposed in
⎨ Fik
− STik Cj if Bi > 0
∀j:πj <θi Tj this paper is based on (i) backtracking, (ii) pruning the search
Fik = j
⎪
⎪ Sik + Ci + space, and (iii) a heuristic for traversing the search space.
⎪
⎪
⎪
⎪ However, unlike the Wang-Saksena OPTA, our algorithm (1)
⎩ Fik
− 1 + Sik Cj if Bi = 0 assigns priorities in a descending order, i.e. from the highest
∀j:πj <θi Tj Tj
(5) to the lowest priority, rather than in ascending order, (2)
Finally, according to (6), we compute the worst-case re- determines preemption thresholds of tasks while the priority
sponse time as the maximum of response times of all jobs ordering is determined, rather than determining preemption
within the worst-case level-i active period. thresholds after the priority ordering is completed and (3)
uses the notion of blocking tolerance rather than lateness in
Ri = max (Fik − kTi ) (6) the heuristic.
∀k:0≤k βi ,
of the task τi (βj ≥ Ci ). Then there is only one sequence of
task τi will be rendered unschedulable if task τj blocks it
priorities under which these tasks can be made schedulable:
(πj > πi ∧ θj ≤ πi ) or is assigned a priority greater than
τi at a higher priority than τj . Therefore, it is safe to remove
πi .
the task τj from the current priority (lines 12–19).
Based on Definition 1, the first part of Lemma 1 is imme-
diately true. To observe that the second part is also true, 6.2 State-space Traversal Heuristic
Algorithm 1 FPTS-OPT priority should be processed is passed to the algorithm, which
Input: is initially the highest available priority in the system.
H=∅ The algorithm finds a solution if no task remains in L (lines
A set of tasks L, and {Ci , Ti , Di } ∀τi ∈ L. 2–4 in the algorithm). In each iteration of the algorithm, first
Prio = 1 The highest priority. the blocking tolerance and preemption thresholds of all tasks
Output: in L are calculated (line 5 in the algorithm). The preemption
The schedulability of the task set, πi , and θi ∀τi ∈ T . threshold θi is the highest one with which all tasks in H can
1: function Search(H, L, Prio) be scheduled if the task were added to the set at the priority
2: if L = ∅ then Prio. This preemption threshold is subsequently used to
3: return schedulable calculate blocking tolerance βi of the same task.
4: end if There are two pruning conditions to determine if the task
5: ∀τi ∈ L : βi , θi ← CalculateBT(H, τi ); set is unschedulable: In a given priority level, if (i) the
6: if (∃τi ∈ L : βi < 0) then blocking tolerance of any task is a negative value (lines 6–
7: return unschedulable 8 in the algorithm), and (ii) there exist two tasks where
8: end if blocking tolerance of each is lower than the execution time
9: if (∃τi , τj ∈ L : i = j ∧ βi < Cj ∧ βj < Ci ) then of the other, i.e., (∃τi , τj ∈ L : i = j ∧ βi < Cj ∧ βj < Ci )
10: return unschedulable (lines 9–11 in the algorithm).
11: end if Another condition for pruning the tasks from a specific
L is a list of tasks that can be assigned priority Prio. priority level is that, the execution time of those tasks cannot
12: L ← L satisfy the blocking tolerance of some tasks at that priority
13: for (τi ∈ L) do level, i.e., (∃τi , τj ∈ L : i = j ∧βi < Cj ∧βj ≥ Ci ) (lines 12–19
14: for (τj ∈ L \ {τi }) do in the algorithm) which means that τi is not schedulable
15: if (βi < Cj ∧ βj ≥ Ci ) then at a lower priority level, thus τj is pruned from the current
16: L ← L \ {τj } priority level. The tasks that should be explored at the
17: end if current priority level are added to list L . Tasks in L are
18: end for then sorted in ascending order of their blocking tolerances
19: end for by SortβInc function (line 20 in the algorithm).
20: L ← SortβInc(L , β) The task τi at the head of L , i.e., the task with minimum
21: for (τi ∈ L ) do blocking tolerance, is selected to be assigned to the current
22: H ← H ∪ {τi } priority level, removed from L, and added to H (lines 22 to
23: L ← L \ {τi } 25 in the algorithm).
24: πi ← Prio The algorithm subsequently goes one step deeper in the
25: θi ← θi recursion for the next (lower) priority level (line 26 in the
26: if (Search(H, L, P rio + 1)) then algorithm). If the recursion returns a schedulable value,
27: return schedulable the value is returned, otherwise the algorithm proceeds to
28: end if try to schedule the next task from the list L .
29: H ← H \ {τi }
30: L ← L ∪ {τi } 7. FIXING WANG-SAKSENA ALGORITHM
31: end for A prerequisite for a comparative evaluation of our algo-
32: return unschedulable rithm and the algorithm presented by Wang and Saksena [12]
33: end function was to implement both algorithms. During the implementa-
tion of the algorithm of Wang and Saksena, we noticed that
it does not explore the entire state-space.
The idea behind assigning priorities in a descending order After inspecting the pseudo-code in Figure 3 of [12], we
is that, if a task is at a lower priority, it will experience a have determined that the most probable original intention for
higher amount of interference which in turn leads to a smaller the algorithm was to continue the state space exploration if
tolerance for blocking. an unschedulable configuration was found. A simple removal
On the other hand, smaller blocking tolerance reduces the of line 4 from the pseudo-code results in an algorithm that
opportunity for lower priority tasks (which are not schedu- completely explores the state-space of the potential priority
lable by their current priority level) to increase their pre- orderings. Further, this closely reflects the approach use in
emption threshold for a try to become schedulable. To exploit the same algorithm on lines 22–24.
these properties, we employ a heuristic for traversal of the
potential priority assignment state-space. We first allocate
those tasks to the highest priorities that have the lowest
8. EVALUATION
blocking tolerance. In this section we present the results of our experiments.
As the first set of experiments, we have measured the com-
6.3 FPTS-OPT Algorithm plexity of our proposed algorithm compared to Wang and
Saksena’s algorithm1 [12]. Since both algorithms execute in
The algorithm divides the task set into two groups: (i) a
exponential time, we chose two different measures to compare
set of higher priority tasks H which have their priorities and
them, the number of recursive calls to the main function,
thresholds assigned (ii), and a set of lower priority tasks L
and the number of worst-case response time (WCRT) com-
with unassigned priorities and thresholds.
putation calls. While Wang-Saksena algorithm uses WCRT
The algorithm starts with an empty set H, and all tasks
1
to be processed in L. Additionally, a parameter of which After applying the corrections outlined in Section 7.
computation, our algorithm is based on blocking tolerance
computation. To achieve a common ground between the
algorithms, we have implemented blocking tolerance and
maximum preemption threshold computation using WCRT
calls.
As a second set of experiments, we compared the schedula-
bility ratios of task sets under FPTS with deadline monotonic
priority assignments and optimal preemption thresholds and
under FPTS with our OPTA.
8.1 Experimental Setup
For both sets of experiments, 5000 task sets are randomly
generated using UUnifast algorithm [2] for every x-axis point.
Task’s inter-arrival times were randomly chosen from the
range [10, 1000]. Task’s deadlines were uniformly selected
from the range [Ci + α(Ti − Ci ), Ti ], where α is the deadline Figure 1: Number of recursions versus task set car-
scaling factor. At α = 1, the deadlines are equal to periods, dinality.
and at α = 0, the deadlines are equal to computation times.
In all the experiments the following system parameters were
used as defaults (except in the experiment that the specified
parameter is varying): α = 1, the task set utilization is fixed
to 0.9, and the task set cardinality is set to 8.
In the first set of experiments, the recursion depth and
number of calls to WCRT function were measured when the
task set cardinality is varied from 3 to 8. In the second set
of experiments, the schedulability ratio is calculated when
(i) the task set cardinality was varied from 3 to 9, (ii) the
task set utilization was varied in the range [0.6, 0.95] with
granularity of 0.05 and (iii) α is varied in the range [0.1, 1]
with granularity of 0.1.
8.2 Results
The results in the first set of experiments are shown by
means of box plots (a.k.a. box and whisker diagram) in
Figures 1 and 2. Each graph represents the data using five Figure 2: Number of WCRT calls versus task set
values: (1) minimum value which is the lower point in the cardinality.
graph, (2) first quartile value which is the lower edge of the
square, (3) median value which is the line in the middle of
proposed algorithm can improve the schedulability up to 15%.
the rectangle, (4) third quartile value which is the upper
It can be observed from Figures 3 and 4 that system
edge of the rectangle, and (5) maximum value which is the
schedulability decreases by both increasing the number of
top line.
the tasks in the task set as well as increasing the task set
As it can be observed from Figures 1 and 2, the number
utilization. Moreover, Figure 5 shows that increasing α, i.e.,
of WCRT calls as well as recursion depths are lower under
larger deadlines, the system schedulability is increased, which
our optimal algorithm compared to Wang-Saksena algorithm.
are not surprising results.
This implies that the time needed to find a solution is in
general lower under our algorithm. Further, it can be seen
that the growth of the measured values in the graphs is 9. CONCLUSION
steeper under Wang-Saksena algorithm compared to FPTS- In this paper we proposed a new optimal priority and
OPT algorithm. It is interesting to observe that, in general, preemption threshold assignment algorithm for FPTS.
the maximum number of WCRT calls and recursion depths The algorithm is based on backtracking, pruning the search
under the FPTS-OPT algorithm are smaller than the 25% of space and a heuristic for traversing the search space. By
the WCRT calls and recursion depths under Wang-Saksena generating a large number of synthetic task sets, we have
algorithm. However, the results show that the FPTS-OPT compared our algorithm with the original algorithm by Wang
algorithm does not completely outperform the Wang-Saksena and Saksena. The results show that our algorithm clearly
algorithm. In those cases, Wang-Saksena algorithm can find outperforms the Wang-Saksena algorithm in general in terms
the solution faster, e.g., for 5 and 7 tasks in Figures 1 and 2. of number of recursive calls and number of worst-case re-
sponse time calculations, although special cases exist for
8.3 Schedulability Ratio which Wang-Saksena performs better than our algorithm.
In the second set of experiments we compared schedula- Further, we have used our algorithm to evaluate the rele-
bility of different priority and threshold assignments while vance of using a complex algorithm to determine the priority
varying experiment parameters. The results in Figures 3, 4 assignment compared to simple deadline monotonic assign-
and 5 show that FPTS-OPT clearly outperforms both FPPS ment. With up to 15% observed increase in schedulability,
and FPTS with deadline monotonic priority assignment. Our we can conclude that it is worth having the option of opti-
Figure 3: Task set schedulability ratio in comparison Figure 5: Task set schedulability ratio compared to
with task set cardinality. different values of α.
[5] A. Burns and A. J. Wellings. Restricted tasking models.
In Proc. 8th International Workshop on Real-Time Ada,
IRTAW, pages 27–32, New York, NY, USA, 1997.
ACM.
[6] R. I. Davis, L. Cucu-Grosjean, M. Bertogna, and
A. Burns. A review of priority assignment in real-time
systems. Journal of Systems Architecture, 65:64 – 82,
2016.
[7] U. Keskin, R. J. Bril, and J. J. Lukkien. Exact
response-time analysis for fixed-priority
preemption-threshold scheduling. In 15th IEEE Conf.
on Emerging Technologies and Factory Automation
(ETFA), pages 1–4, Sept. 2010.
[8] S. Lee, C.-G. Lee, M. Lee, S. Min, and C. Kim. Limited
preemptible scheduling to embrace cache memory in
Figure 4: Task set schedulability ratio in comparison real-time systems. In F. Mueller and A. Bestavros,
with task set utilization. editors, Languages, Compilers, and Tools for Embedded
Systems, volume 1474 of Lecture Notes in Computer
mal priority assignment for cases that cannot be scheduled Science, pages 51–64. Springer Berlin Heidelberg, 1998.
by means of deadline monotonic priorities and optimal pre- [9] V. Lortz and K. Shin. Semaphore queue priority
emption thresholds. However, since the algorithm still func- assignment for real-time multiprocessor
tions in exponential time, it may be impractical to execute synchronization. IEEE Transactions on Software
it on very large task sets. Engineering, 21(10):834–844, Oct. 1995.
The problem itself of whether it is possible to construct [10] J. Regehr. Scheduling tasks with mixed preemption
an efficient algorithm for FPTS OPTA still remains open. relations for robustness to timing faults. In 23rd IEEE
Real-Time Systems Symposium (RTSS), pages 315–326,
10. REFERENCES 2002.
[11] M. Saksena and Y. Wang. Scalable real-time system
[1] S. Baruah. The limited-preemption uniprocessor
design using preemption thresholds. In 21st IEEE
scheduling of sporadic task systems. In 17th Euromicro
Real-Time Systems Symposium (RTSS), pages 25–34,
Conference on Real-Time Systems (ECRTS), pages
2000.
137–144, July 2005.
[12] Y. Wang and M. Saksena. Scheduling fixed-priority
[2] E. Bini and G. Buttazzo. Measuring the performance of
tasks with preemption threshold. In 6th International
schedulability tests. Real-Time Systems,
Conference on Real-Time Computing Systems and
30(1-2):129–154, 2005.
Applications (RTCSA), pages 328–335, 1999.
[3] R. Bril, J. Lukkien, and W. Verhaegh. Worst-case
[13] G. Yao, G. Buttazzo, and M. Bertogna. Bounding the
response time analysis of real-time tasks under
maximum length of non-preemptive regions under fixed
fixed-priority scheduling with deferred preemption
priority scheduling. In 15th IEEE International
revisited. In 19th Euromicro Conference on Real-Time
Conference on Embedded and Real-Time Computing
Systems (ECRTS), pages 269–279, July 2007.
Systems and Applications, pages 351–360, Aug 2009.
[4] A. Burns. Preemptive priority-based scheduling: An
appropriate engineering approach. In Advances in
Real-Time Systems, chapter 10, pages 225–248.
Prentice Hall, 1994.