# Assigning Priorities for Fixed Priority Preemption Threshold Scheduling

Authors: Saehwa Kim
Journal: The Scientific World Journal
 (2015)

---

## Abstract

Preemption threshold scheduling (PTS) enhances real-time schedulability by controlling preemptiveness of tasks. This benefit of PTS highly depends on a proper algorithm that assigns each task feasible scheduling attributes, which are priority and preemption threshold. Due to the existence of an efficient optimal preemption threshold assignment algorithm that works with fully assigned priority orderings, we need an optimal priority assignment algorithm for PTS. This paper analyzes the inefficiency or nonoptimality of the previously proposed optimal priority assignment algorithms for PTS. We develop theorems for exhaustively but safely pruning infeasible priority orderings while assigning priorities to tasks for PTS. Based on the developed theorems, we correct the previously proposed optimal priority assignment algorithm for PTS. We also propose a performance improved optimal priority assignment algorithm for PTS proving its optimality. The empirical evaluation results clearly show the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

Preemption threshold scheduling (PTS) is an extension of preemptive fixed priority scheduling where each task has an extra scheduling attribute, called a preemption threshold, in addition to a priority. The preemption threshold of a task is its run-time priority, which is maintained after the task is dispatched and until it terminates its execution, so it regulates the degree of “preemptiveness” in fixed priority scheduling [1]. If the threshold of each task is the same as its original priority, then PTS is equivalent to fully preemptive fixed priority scheduling (FPS), and if each task has the highest threshold value in a system, it is equivalent to nonpreemptive scheduling (NPS). The use of PTS is very effective in system tuning processes since it enhances real-time schedulability, eliminates unnecessary preemptions, reduces memory stack usage [2] via the notion of nonpreemption groups [3], and allows for scalable real-time system design [4–6]. Preemption thresholds and nonpreemption groups are also parts of OSEK [7] and AUTOSAR [8] standards of automotive operating systems. As remarked in [9], PTS represents an example of a great success of transferring academic research results to industrial applications [10–12].The benefit of enhanced real-time schedulability of PTS highly depends on a proper algorithm that assigns each task feasible scheduling attributes, which are priority and preemption threshold. The work of this paper has been highly motivated by our previous work of SISAtime [13], which adopts PTS to schedule active (concurrent) objects of real-time object-oriented models [14–19]. While SISAtime contains an optimal scheduling attributes assignment algorithm for PTS, it is not so much efficient. A scheduling attributes assignment algorithm isoptimal if it is guaranteed to output a feasible (schedulable) scheduling attributes assignment if one exists [1, 20–22].There are two previously proposed optimal scheduling attributes assignment algorithms for PTS: TRAVERSE of SISAtime [13] and SEARCH of [1], which is the first academic article that presented PTS. Both algorithms work in two stages. At the first stage, priorities are assigned to all tasks. At the second stage, preemption thresholds are assigned using the optimal preemption threshold assignment algorithm, OPT-ASSIGN-THRESHOLD of [1], which has the complexity of O
(
n
2
). Recently, [23] extends OPT-ASSIGN-THRESHOLD by considering the cache-related preemption delay (CRPD), and it also assigns optimal preemption thresholds for tasks with preassigned priorities. Since preemption thresholds are wholly assigned at the second stage, both algorithms focus on how to assign priorities to tasks. With this, we call these optimal “scheduling attributes” assignment algorithms for PTS as optimal “priority” assignment algorithms for PTS.In this paper, we analytically show that TRAVERSE is inefficient and SEARCH is not optimal. We develop theorems for exhaustively pruning infeasible priority orderings without harming the optimality of priority assignment algorithms for PTS. Specifically, we develop following lemmas and theorems under PTS:(i)
Under PTS, if the priority of a task is fixed, its worst-case response time does not decrease when its preemption threshold is lowered (Lemma3).
(ii)
Under PTS, if the preemption threshold of a task is fixed, its worst-case response time does not decrease when its priority is lowered (Theorem6).
(iii)
Under PTS, if a task with the highest preemption threshold in a priority ordering is infeasible, the task set with the priority ordering is also infeasible (Theorem4).
(iv)
Under PTS, if a task with the highest preemption threshold in a priority ordering is infeasible, the task set with another priority ordering that assigns the task the lowered priority is also infeasible (Theorem7).By applying these theorems, we correct SEARCH and propose CORRECTED-SEARCH which is more efficient than TRAVERSE. We also propose PRUNED-TRAVERSE that improves the performance of CORRECTED-SEARCH and proves its optimality.We also empirically evaluate the performances of the discussed optimal priority assignment algorithms. We first empirically show the usefulness of the proposed optimal priority assignment algorithm by showing that they always achieve the better schedulability than any other existing nonoptimal priority assignment algorithms. We also compare the actual runtimes for executing each optimal priority assignment algorithm as well as PA-DMMPT by [24], which is the most effective heuristic priority assignment algorithm for PTS if it is combined with the policy of deadline monotonic priority ordering (DMPO). The empirical results clearly show that the actual runtimes of TRAVERSE are reduced by CORRECTED-SEARCH, whose actual runtimes are also more reduced by PRUNED-TRAVERSE while such performance improvements become drastically large as the number of tasks increases. It is also shown that the actual runtimes of PRUNED-TRAVERSE are even smaller than those of PA-DMMPT.The remainder of the paper is composed as follows. Section2 gives the task model with notations and presents a walk-through example that motivates our work. Section 3 analyzes previously proposed optimal priority assignment algorithms for PTS. Section 4 corrects previously proposed SEARCH algorithm making it an optimal priority assignment algorithm for PTS. Section 5 describes our proposed optimal priority assignment algorithm for PTS and proves its optimality. Section 6 considers the complexity of the discussed optimal priority assignment algorithms. Section 7 shows our empirical evaluation results. Finally, Section 8 concludes the paper.


## 2. Task Model

We use the same task model as the one used in the traditional preemption threshold scheduling [1, 3, 25, 26]. Specifically, a system has a fixed set of tasks Γ
=
τ
1
,
τ
2
,
…
,
τ
Γ. Each task τ
i has a fixed period T
i, a fixed relative deadline D
i, and a known worst-case execution time C
i. There is no restriction such that each task’s deadline should be shorter than its period. We also adopt the “integer time model” of [9], where all timing parameters are assumed to be nonnegative integer values.Each taskτ
i also has a fixed priority p
i and a preemption threshold p
t
i where p
i is assigned by a specific priority assignment algorithm and p
t
i is assigned by OPT-ASSIGN-THRESHOLD of [1]. Each task has a distinct priority value: every task has a different priority value. Each task set Γ has Γ
! distinct priority orderings for its tasks. Accordingly, the set of distinct priority orderings has cardinality Γ
!, which we denote P
O
Γ
=
P
O
1
,
P
O
2
,
…
,
P
O
Γ
!. We denote the resultant priority ordering generated by a specific priority assignment algorithm ALGORITHM as P
O
A. With this, a specific priority ordering P
O
n is a sequence of priorities for tasks in Γ, which we denote as P
O
n
=
p
1
n
,
p
2
n
,
…
,
p
Γ
n.  The inverse mapping of each priority ordering P
O
n is a task ordering from the lowest priority to the highest priority, which we denote as P
O
n
-
1
=
T
O
n
=
〈
i
,
j
,
…
,
k
〉 where each number represents a task index. We also denote the inverse mapping of task ordering T
O
n as T
O
n
-
1
=
P
O
n.We denote a higher priority with a larger value: 1 is the lowest priority value andΓ is the highest priority value. Note that it is meaningful to assign a task a preemption threshold that is no less than its regular priority since a preemption threshold is used as an effective run-time priority to control unnecessary preemptions [1]: which means that ∀
τ
i, p
t
i
≥
p
i. Notation section summarizes the notations and associated descriptions used in this paper.


### 2.1. Feasibility Analysis

As the feasibility test under PTS, we adopt the worst-case response time analysis equations of [9]. The original equations were introduced by [1] and their errors were fixed by [27]. These results were refined by [26], whose results in turn were concisely arranged by [9]. We rewrite the relevant equations of [9] for calculating the worst-case response time R
i of task τ
i as follows: (1)
R
i
=
max
q
∈
1
,
Q
i
⁡
F
i
,
q
-
q
-
1
·
T
i
,
(2)
Q
i
=
L
i
T
i
,
(3)
L
i
=
B
i
+
∑
∀
j
,
p
j
≥
p
i
L
i
T
j
·
C
j
,
(4)
F
i
,
q
=
S
i
,
q
+
C
i
+
∑
∀
j
,
p
j
>
pt
i
F
i
,
q
T
j
-
1
+
S
i
,
q
T
j
·
C
j
,
(5)
S
i
,
q
=
B
i
+
q
-
1
·
C
i
+
∑
∀
j
,
p
j
≥
p
i
1
+
S
i
,
q
T
j
·
C
j
,
(6)
B
i
=
max
⁡
C
j
-
1
∣
∀
j
,
pt
j
≥
p
i
>
p
j
,where L
i is the longest level-p
i busy period [28], q is the index of instances of task τ
i within L
i, Q
i is the last index of instances of task τ
i within L
i, F
i
,
q is the finish time of the qth instance of task τ
i, S
i
,
q is the start time of the qth instance of task τ
i, and B
i is the worst-case blocking time of task τ
i. Whenever a variable appears on both sides of an equation (i.e., L
i in (3) and F
i
,
q in (4)), its value can be found by iterating until the value converges [27]. Refer to [9] for the appropriate initial values for the iterations. With this, we define formally the feasibility of a task or a task set as follows.Definition 1 (task feasibility).
Taskτ
i with the assignment of p
i and p
t
i isfeasible
↔
R
i
≤
D
i.Definition 2 (task set feasibility).
Task setΓ with priority ordering P
O
n
=
〈
p
1
n
,
p
2
n
,
…
,
p
Γ
n
〉 or task ordering T
O
n
=
P
O
n
-
1 isfeasible
↔ every τ
i in Γ is feasible such that τ
i with p
i
n in P
O
n and p
t
i determined by OPT-ASSIGN-THRESHOLD is feasible.


### 2.2. A Walk-Through Example Task Set

As a walk-through example, we use the task set in Table1 that is composed of four tasks. The deadline monotonic priority ordering (DMPO) is optimal in the fully preemptive fixed priority scheduling [22] and is so even though there are blockings if there is no jitter [21]. Therefore, the approach of assigning priorities using DMPO and then assigning preemption thresholds using OPT-ASSIGN-THRESHOLD of [1] is widely used in practice, which was also employed in [9] when comparing PTS with other limited preemptive scheduling policies. Since the task indexes of the example task set happen to be in the deadline monotonic decreasing order, the resultant priority ordering of DMPO is P
O
D
=
〈
1,2
,
3,4
〉. However, as shown in Table 1, this priority ordering makes task τ
4 miss its deadline since (
R
4
=
14
)
>
(
D
4
=
11
). Figure 1(a) demonstrates such a deadline miss: the fifth instance of task τ
4 completes at time point 69 while its absolute deadline is 5
-
1
·
T
4
+
D
4
=
67. Note that the worst-case response time cannot be obtained at the critical instant [29] when there is a nonpreemptiveness of tasks [9].Table 1
A walk-through example task set. Bold and italicR
i’s represent infeasible response times.
Tasks
C
i
T
i
D
i
DMPO [9]
GREEDY-SA( ) [3]
PA-DMMPT( ) [24]
SEARCH( ) [1]
TRAVERSE( ) [13]
p
i
p
t
i
R
i
p
i
p
t
i
R
i
p
i
p
t
i
R
i
p
i
p
t
i
R
i
p
i
p
t
i
R
i
τ
1
8
43
36
1
4
31
4
4
14
1
4
31
2
4
30
3
3
26
τ
2
4
33
33
2
4
30
2
2
23
3
3
25
3
3
25
2
4
30
τ
3
5
48
31
3
3
26
3
3
19
2
4
30
1
4
31
1
4
31
τ
4
7
14
11
4
4
14
1
5
24
4
4
14
4
4
14
4
4
11
(i) DMPO: deadline monotonic priority ordering + OPT-ASSIGN-THRESHOLD( ) employed in [9].
(ii) GREEDY-SA( ): Greedy( ) + SimulatedAnnealing( ) proposed in [3].Figure 1
Schedule produced for the walk-through example task set of Table1 by various priority assignment algorithms. Note that some instances of task τ
4 in (a)~(d) miss their deadlines while every task in (e) does not miss its deadline.
(a)
DMPO employed in [9]
(b)
GREEDY-SA (Greedy + SimulatedAnnealing) [3]
(c)
PA-DMMPT [24]
(d)
SEARCH [1]
(e)
TRAVERSE [13], CORRECTED-SEARCH, and PRUNED-TRAVERSEOn the other hand, [3, 24] proposed heuristic priority assignment algorithms for PTS. Reference  [3] proposed an algorithm that combines Greedy and SimulatedAnnealing, which we refer to GREEDY-SA in this paper. Reference  [24] proposed PA-DMMPT, which means priority assignment algorithm assuming Deadline Monotonic and Maximum Preemption Threshold for the remaining tasks in the unassigned task set. The resultant priority ordering of GREEDY-SA and PA-DMMPT is, respectively, P
O
G
=
〈
4,2
,
3,1
〉 and P
O
P
A
=
〈
1,3
,
2,4
〉 as shown in Table 1. These priority orderings also make task τ
4 miss its deadline as shown in Table 1.Figures1(b) and 1(c) demonstrate such deadline misses of task τ
4. In Figure 1(b), the first, the second, and the fifth instances of task τ
4 complete at time points 24, 31, and 69, respectively, while their absolute deadlines are D
4
=
11, 2
-
1
·
T
4
+
D
4
=
25, and 5
-
1
·
T
4
+
D
4
=
67, respectively. In Figure 1(c), the fifth instance of task τ
4 completes at time point 69 while its absolute deadline is 5
-
1
·
T
4
+
D
4
=
67. As such, widely used DMPO or heuristic priority assignment algorithms may not produce a feasible priority assignment while there is actually one, as will be shown in Section 3.1. This motivated our work.


## 2.1. Feasibility Analysis

As the feasibility test under PTS, we adopt the worst-case response time analysis equations of [9]. The original equations were introduced by [1] and their errors were fixed by [27]. These results were refined by [26], whose results in turn were concisely arranged by [9]. We rewrite the relevant equations of [9] for calculating the worst-case response time R
i of task τ
i as follows: (1)
R
i
=
max
q
∈
1
,
Q
i
⁡
F
i
,
q
-
q
-
1
·
T
i
,
(2)
Q
i
=
L
i
T
i
,
(3)
L
i
=
B
i
+
∑
∀
j
,
p
j
≥
p
i
L
i
T
j
·
C
j
,
(4)
F
i
,
q
=
S
i
,
q
+
C
i
+
∑
∀
j
,
p
j
>
pt
i
F
i
,
q
T
j
-
1
+
S
i
,
q
T
j
·
C
j
,
(5)
S
i
,
q
=
B
i
+
q
-
1
·
C
i
+
∑
∀
j
,
p
j
≥
p
i
1
+
S
i
,
q
T
j
·
C
j
,
(6)
B
i
=
max
⁡
C
j
-
1
∣
∀
j
,
pt
j
≥
p
i
>
p
j
,where L
i is the longest level-p
i busy period [28], q is the index of instances of task τ
i within L
i, Q
i is the last index of instances of task τ
i within L
i, F
i
,
q is the finish time of the qth instance of task τ
i, S
i
,
q is the start time of the qth instance of task τ
i, and B
i is the worst-case blocking time of task τ
i. Whenever a variable appears on both sides of an equation (i.e., L
i in (3) and F
i
,
q in (4)), its value can be found by iterating until the value converges [27]. Refer to [9] for the appropriate initial values for the iterations. With this, we define formally the feasibility of a task or a task set as follows.Definition 1 (task feasibility).
Taskτ
i with the assignment of p
i and p
t
i isfeasible
↔
R
i
≤
D
i.Definition 2 (task set feasibility).
Task setΓ with priority ordering P
O
n
=
〈
p
1
n
,
p
2
n
,
…
,
p
Γ
n
〉 or task ordering T
O
n
=
P
O
n
-
1 isfeasible
↔ every τ
i in Γ is feasible such that τ
i with p
i
n in P
O
n and p
t
i determined by OPT-ASSIGN-THRESHOLD is feasible.


## 2.2. A Walk-Through Example Task Set

As a walk-through example, we use the task set in Table1 that is composed of four tasks. The deadline monotonic priority ordering (DMPO) is optimal in the fully preemptive fixed priority scheduling [22] and is so even though there are blockings if there is no jitter [21]. Therefore, the approach of assigning priorities using DMPO and then assigning preemption thresholds using OPT-ASSIGN-THRESHOLD of [1] is widely used in practice, which was also employed in [9] when comparing PTS with other limited preemptive scheduling policies. Since the task indexes of the example task set happen to be in the deadline monotonic decreasing order, the resultant priority ordering of DMPO is P
O
D
=
〈
1,2
,
3,4
〉. However, as shown in Table 1, this priority ordering makes task τ
4 miss its deadline since (
R
4
=
14
)
>
(
D
4
=
11
). Figure 1(a) demonstrates such a deadline miss: the fifth instance of task τ
4 completes at time point 69 while its absolute deadline is 5
-
1
·
T
4
+
D
4
=
67. Note that the worst-case response time cannot be obtained at the critical instant [29] when there is a nonpreemptiveness of tasks [9].Table 1
A walk-through example task set. Bold and italicR
i’s represent infeasible response times.
Tasks
C
i
T
i
D
i
DMPO [9]
GREEDY-SA( ) [3]
PA-DMMPT( ) [24]
SEARCH( ) [1]
TRAVERSE( ) [13]
p
i
p
t
i
R
i
p
i
p
t
i
R
i
p
i
p
t
i
R
i
p
i
p
t
i
R
i
p
i
p
t
i
R
i
τ
1
8
43
36
1
4
31
4
4
14
1
4
31
2
4
30
3
3
26
τ
2
4
33
33
2
4
30
2
2
23
3
3
25
3
3
25
2
4
30
τ
3
5
48
31
3
3
26
3
3
19
2
4
30
1
4
31
1
4
31
τ
4
7
14
11
4
4
14
1
5
24
4
4
14
4
4
14
4
4
11
(i) DMPO: deadline monotonic priority ordering + OPT-ASSIGN-THRESHOLD( ) employed in [9].
(ii) GREEDY-SA( ): Greedy( ) + SimulatedAnnealing( ) proposed in [3].Figure 1
Schedule produced for the walk-through example task set of Table1 by various priority assignment algorithms. Note that some instances of task τ
4 in (a)~(d) miss their deadlines while every task in (e) does not miss its deadline.
(a)
DMPO employed in [9]
(b)
GREEDY-SA (Greedy + SimulatedAnnealing) [3]
(c)
PA-DMMPT [24]
(d)
SEARCH [1]
(e)
TRAVERSE [13], CORRECTED-SEARCH, and PRUNED-TRAVERSEOn the other hand, [3, 24] proposed heuristic priority assignment algorithms for PTS. Reference  [3] proposed an algorithm that combines Greedy and SimulatedAnnealing, which we refer to GREEDY-SA in this paper. Reference  [24] proposed PA-DMMPT, which means priority assignment algorithm assuming Deadline Monotonic and Maximum Preemption Threshold for the remaining tasks in the unassigned task set. The resultant priority ordering of GREEDY-SA and PA-DMMPT is, respectively, P
O
G
=
〈
4,2
,
3,1
〉 and P
O
P
A
=
〈
1,3
,
2,4
〉 as shown in Table 1. These priority orderings also make task τ
4 miss its deadline as shown in Table 1.Figures1(b) and 1(c) demonstrate such deadline misses of task τ
4. In Figure 1(b), the first, the second, and the fifth instances of task τ
4 complete at time points 24, 31, and 69, respectively, while their absolute deadlines are D
4
=
11, 2
-
1
·
T
4
+
D
4
=
25, and 5
-
1
·
T
4
+
D
4
=
67, respectively. In Figure 1(c), the fifth instance of task τ
4 completes at time point 69 while its absolute deadline is 5
-
1
·
T
4
+
D
4
=
67. As such, widely used DMPO or heuristic priority assignment algorithms may not produce a feasible priority assignment while there is actually one, as will be shown in Section 3.1. This motivated our work.


## 3. Previously Proposed Optimal Priority Assignment Algorithms for PTS

This section analyzes previously proposed optimal priority assignment algorithms for PTS: TRAVERSE [13] and SEARCH [1].


### 3.1. TRAVERSE( ) Algorithm

Algorithm1(a) shows the pseudo code for TRAVERSE. As shown in Algorithm 1(a), TRAVERSE depends on its recursive subroutine, _TRAVERSE, which has three parameters: (
1
)
prio, the next priority to assign, (
2
)
UnAssigned, the set of tasks that are waiting for priority assignment, and (
3
)  Γ, the set of total tasks (line (
3
)). _TRAVERSE assigns preemption thresholds by calling OPT-ASSIGN-THRESHOLD of [1] when a complete priority ordering is generated (line (
4
)). When any preemption threshold assignment is not feasible, OPT-ASSIGN-THRESHOLD returns fail. With this, returning at the last lines (line (
9
)) happens when a specific priority ordering is not feasible.Algorithm 1:Pseudo code for (a) TRAVERSE( ) [13] and (b) SEARCH( ) [1].
(1)TRAVERSE(Γ: set of tasks)
(2)return  _TRAVERSE(1, Γ, Γ);
(3)_TRAVERSE (prio: priority,  UnAssigned: set of tasks,  Γ: set of tasks)
(4)if (UnAssigned = )  return  OPT-ASSIGN-THRESHOLD(Γ);
(5)foreach (τ
i
∈
U
n
A
s
s
i
g
n
e
d)
(6)
p
i
←
p
r
i
o;
(7)
if(_TRAVERSE(prio+ 1, UnAssigned −  τ
i, Γ) = success) return
success;
(8) // end-foreach
(9)return  fail;
(a) TRAVERSE( ) [13]
(1)SEARCH (Γ:set of tasks)
(2)return  _SEARCH(1, Γ, Γ);
(3)_SEARCH (prio: priority,  UnAssigned: set of tasks,  Γ:set of tasks)
(4)if (UnAssigned = )  return OPT-ASSIGN-THRESHOLD(Γ);
(5)foreach (τ
i
∈
U
n
A
s
s
i
g
n
e
d)
//WCRT(τ
i
, prio):  R
i with (p
i
←
p
r
i
o) under fully preemptive fixed priority scheduling
//       assuming all tasks in UnAssigned have the highest priority.
(6)
D
e
l
a
y
i
←
WCRT(τ
i
, prio) −  D
i;
(7)
if (D
e
l
a
y
i
≤
0)
(8)p
i
←
p
r
i
o;
(9)return _SEARCH(prio+ 1, UnAssigned −  τ
i, Γ);
(10) // end-if
(11) // end-foreach
(12)SortedList ← ascendingSort(UnAssigned, D
e
l
a
y
i);
(13)RefinedList ← Refine(SortedList); // eliminating infeasible tasks even with the highest preemption threshold
(14)foreach (τ
i
∈
R
e
f
i
n
e
d
L
i
s
t)
(15)p
i
←
p
r
i
o;
(16)if(_SEARCH(prio + 1, UnAssigned −  τ
i, Γ) = success)return
success;
(17) // end-foreach
(18)return  fail;
(b) SEARCH( ) [1]The remaining part is composed of a loop that recursively invokes _TRAVERSE: each task inUnAssigned at line (
5
) is assigned the priorityprio at line (
6
) and remaining unassigned tasks (U
n
A
s
s
i
g
n
e
d
-
τ
i) are recursively assigned p
r
i
o
+
1 at line (
7
). Note that the recursive invocation of _TRAVERSE returns only when the return value of the recursive invocation issuccess (line (
7
)). We call this priority assignment as thetentative priority assignment since if the return value of the recursion isfail, the next task inUnAssigned is tried for assigning priorityprio.With such tentative priority assignments, _TRAVERSE recursively generates a priority assignment tree for the set of tasks with task orderings from the lowest priority to the highest priority, which is similar to the priority permutation tree of [21]. Figure 2(a) shows the priority assignment tree of _TRAVERSE for the walk-through example task set of Table 1.   In Figure 2, each solid-lined circle node represents a tentative priority assignment to a task and its depth corresponds to its assigned priority. Each triangle node represents an invocation of OPT-ASSIGN-THRESHOLD: white one for infeasible (failed) assignment return and black one for feasible (successful) assignment return. Each path from the root to a leaf node corresponds to a possible priority ordering. Each number with round braces “(n)” besides a node represents nth feasibility test performed for the operation of the node.Figure 2
Priority assignment trees for the walk-through example task set of Table1.In Figure2(a), 15 complete task orderings T
O
1
=
〈
1,2
,
3
,
4
〉, T
O
2
=
〈
1,2
,
4,3
〉
,
…,  T
O
15
=
〈
3,2
,
1,4
〉 were generated. The last task ordering T
O
15
=
T
O
T
=
〈
3,2
,
1,4
〉 has a dangled black triangle node, which indicates a feasible preemption threshold assignment. Task ordering T
O
T corresponds to the priority ordering P
O
T
=
T
O
T
-
1
=
〈
3,2
,
1,4
〉 for TRAVERSE of Table 1. As shown in Table 1, TRAVERSE makes no tasks miss their deadlines, which is also demonstrated in Figure 1(e). While [13] did not formally prove the optimality of TRAVERSE, we can easily see that TRAVERSE is optimal since it traverses all possible priority orderings in P
O
Γ until it finds a feasible priority ordering. Besides, it is a simple application of traverse_orderings [21], which is for fully preemptive fixed priority scheduling and its optimality was proved.However, TRAVERSE is very inefficient since it generates Γ
! tentative priority orderings in the worst-case, each of which requires maximally Γ
2 feasibility tests [3] via OPT-ASSIGN-THRESHOLD. For example, the priority assignment tree of Algorithm 3(a) requires 91 feasibility tests as the numbers besides triangle nodes indicate. Such a large number of feasibility tests can be significantly reduced in our proposed algorithm in Section 5.


### 3.2. SEARCH( ) Algorithm

Algorithm1(b) shows the pseudo code for SEARCH, which becomes exactly the same as TRAVERSE if we remove lines (5)~(13) and replacingRefinedList withUnAssigned at line (14). The additional part of SEARCH is composed of one loop (lines (5)~(11)) and refiningUnAssigned to prepareRefinedList (lines (12) and (13)). In contrast to the priority assignment loop of TRAVERSE, this additional first loop in SEARCH assigns priorityprio to task τ
i only when D
e
l
a
y
i (calculated at line (
6
)) is not larger than zero (line (
7
)) and unconditionally returns from the recursion (line (
9
)). We call this priority assignment in the first loop as theassertive priority assignment since once priorityprio is assigned to τ
i, the other unassigned tasks are not tested for assigning priorityprio.The second loop of SEARCH (lines (14)~(18)) performs the tentative priority assignment as TRAVERSE but it works forRefinedList instead ofUnAssigned. TheRefinedList is generated by sorting tasks inUnAssigned in the ascending order of D
e
l
a
y
i (line (12)) and eliminating infeasible tasks even with the highest preemption threshold assignment (line (13)).With the assertive and tentative priority assignments, _SEARCH generates a priority assignment tree like Figure 2(b), which is for the walk-through example task set of Table 1. In the tree, each solid-lined square node represents an assertive priority assignment to a task while each dashed-lined node represents pruning a priority assignment to a task. In Figure 2(b), two complete task orderings were generated: 〈
1,2
,
3,4
〉 and 〈
3,1
,
2,4
〉. Both orderings failed to assign feasible preemption thresholds to tasks as the dangled white triangle nodes indicate. The last task ordering T
O
S
=
〈
3,1
,
2,4
〉 corresponds to the priority ordering P
O
S
=
T
O
S
-
1
=
〈
2,3
,
1,4
〉 for SEARCH of Table 1. As shown in Table 1, SEARCH makes task τ
4 miss its deadline since (
R
4
=
14
)
>
(
D
4
=
11
). Figure 1(d) demonstrates such a deadline miss of task τ
4 where the second instance of task τ
4 completes at time point 26 while its absolute deadline is T
4
+
D
4
=
25. However, the walk-through example task set has a feasible priority ordering P
O
T
=
〈
3,2
,
1,4
〉 from TRAVERSE algorithm as we have shown in Section 3.1. This clearly shows SEARCH is not an optimal priority assignment algorithm for PTS.If we compare the priority assignment trees of TRAVERSE and SEARCH in Figures 2(a) and 2(b), we can see that T
O
S
=
〈
3,1
,
2,4
〉 is the 13th task ordering generated by TRAVERSE. The reason why SEARCH failed is due to the assertive priority assignment of p
1
S
←
2 with the 21st feasibility test, which we marked with a red dashed-line circle in Figure 2(b). We correct SEARCH in the next section.


## 3.1. TRAVERSE( ) Algorithm

Algorithm1(a) shows the pseudo code for TRAVERSE. As shown in Algorithm 1(a), TRAVERSE depends on its recursive subroutine, _TRAVERSE, which has three parameters: (
1
)
prio, the next priority to assign, (
2
)
UnAssigned, the set of tasks that are waiting for priority assignment, and (
3
)  Γ, the set of total tasks (line (
3
)). _TRAVERSE assigns preemption thresholds by calling OPT-ASSIGN-THRESHOLD of [1] when a complete priority ordering is generated (line (
4
)). When any preemption threshold assignment is not feasible, OPT-ASSIGN-THRESHOLD returns fail. With this, returning at the last lines (line (
9
)) happens when a specific priority ordering is not feasible.Algorithm 1:Pseudo code for (a) TRAVERSE( ) [13] and (b) SEARCH( ) [1].
(1)TRAVERSE(Γ: set of tasks)
(2)return  _TRAVERSE(1, Γ, Γ);
(3)_TRAVERSE (prio: priority,  UnAssigned: set of tasks,  Γ: set of tasks)
(4)if (UnAssigned = )  return  OPT-ASSIGN-THRESHOLD(Γ);
(5)foreach (τ
i
∈
U
n
A
s
s
i
g
n
e
d)
(6)
p
i
←
p
r
i
o;
(7)
if(_TRAVERSE(prio+ 1, UnAssigned −  τ
i, Γ) = success) return
success;
(8) // end-foreach
(9)return  fail;
(a) TRAVERSE( ) [13]
(1)SEARCH (Γ:set of tasks)
(2)return  _SEARCH(1, Γ, Γ);
(3)_SEARCH (prio: priority,  UnAssigned: set of tasks,  Γ:set of tasks)
(4)if (UnAssigned = )  return OPT-ASSIGN-THRESHOLD(Γ);
(5)foreach (τ
i
∈
U
n
A
s
s
i
g
n
e
d)
//WCRT(τ
i
, prio):  R
i with (p
i
←
p
r
i
o) under fully preemptive fixed priority scheduling
//       assuming all tasks in UnAssigned have the highest priority.
(6)
D
e
l
a
y
i
←
WCRT(τ
i
, prio) −  D
i;
(7)
if (D
e
l
a
y
i
≤
0)
(8)p
i
←
p
r
i
o;
(9)return _SEARCH(prio+ 1, UnAssigned −  τ
i, Γ);
(10) // end-if
(11) // end-foreach
(12)SortedList ← ascendingSort(UnAssigned, D
e
l
a
y
i);
(13)RefinedList ← Refine(SortedList); // eliminating infeasible tasks even with the highest preemption threshold
(14)foreach (τ
i
∈
R
e
f
i
n
e
d
L
i
s
t)
(15)p
i
←
p
r
i
o;
(16)if(_SEARCH(prio + 1, UnAssigned −  τ
i, Γ) = success)return
success;
(17) // end-foreach
(18)return  fail;
(b) SEARCH( ) [1]The remaining part is composed of a loop that recursively invokes _TRAVERSE: each task inUnAssigned at line (
5
) is assigned the priorityprio at line (
6
) and remaining unassigned tasks (U
n
A
s
s
i
g
n
e
d
-
τ
i) are recursively assigned p
r
i
o
+
1 at line (
7
). Note that the recursive invocation of _TRAVERSE returns only when the return value of the recursive invocation issuccess (line (
7
)). We call this priority assignment as thetentative priority assignment since if the return value of the recursion isfail, the next task inUnAssigned is tried for assigning priorityprio.With such tentative priority assignments, _TRAVERSE recursively generates a priority assignment tree for the set of tasks with task orderings from the lowest priority to the highest priority, which is similar to the priority permutation tree of [21]. Figure 2(a) shows the priority assignment tree of _TRAVERSE for the walk-through example task set of Table 1.   In Figure 2, each solid-lined circle node represents a tentative priority assignment to a task and its depth corresponds to its assigned priority. Each triangle node represents an invocation of OPT-ASSIGN-THRESHOLD: white one for infeasible (failed) assignment return and black one for feasible (successful) assignment return. Each path from the root to a leaf node corresponds to a possible priority ordering. Each number with round braces “(n)” besides a node represents nth feasibility test performed for the operation of the node.Figure 2
Priority assignment trees for the walk-through example task set of Table1.In Figure2(a), 15 complete task orderings T
O
1
=
〈
1,2
,
3
,
4
〉, T
O
2
=
〈
1,2
,
4,3
〉
,
…,  T
O
15
=
〈
3,2
,
1,4
〉 were generated. The last task ordering T
O
15
=
T
O
T
=
〈
3,2
,
1,4
〉 has a dangled black triangle node, which indicates a feasible preemption threshold assignment. Task ordering T
O
T corresponds to the priority ordering P
O
T
=
T
O
T
-
1
=
〈
3,2
,
1,4
〉 for TRAVERSE of Table 1. As shown in Table 1, TRAVERSE makes no tasks miss their deadlines, which is also demonstrated in Figure 1(e). While [13] did not formally prove the optimality of TRAVERSE, we can easily see that TRAVERSE is optimal since it traverses all possible priority orderings in P
O
Γ until it finds a feasible priority ordering. Besides, it is a simple application of traverse_orderings [21], which is for fully preemptive fixed priority scheduling and its optimality was proved.However, TRAVERSE is very inefficient since it generates Γ
! tentative priority orderings in the worst-case, each of which requires maximally Γ
2 feasibility tests [3] via OPT-ASSIGN-THRESHOLD. For example, the priority assignment tree of Algorithm 3(a) requires 91 feasibility tests as the numbers besides triangle nodes indicate. Such a large number of feasibility tests can be significantly reduced in our proposed algorithm in Section 5.


## 3.2. SEARCH( ) Algorithm

Algorithm1(b) shows the pseudo code for SEARCH, which becomes exactly the same as TRAVERSE if we remove lines (5)~(13) and replacingRefinedList withUnAssigned at line (14). The additional part of SEARCH is composed of one loop (lines (5)~(11)) and refiningUnAssigned to prepareRefinedList (lines (12) and (13)). In contrast to the priority assignment loop of TRAVERSE, this additional first loop in SEARCH assigns priorityprio to task τ
i only when D
e
l
a
y
i (calculated at line (
6
)) is not larger than zero (line (
7
)) and unconditionally returns from the recursion (line (
9
)). We call this priority assignment in the first loop as theassertive priority assignment since once priorityprio is assigned to τ
i, the other unassigned tasks are not tested for assigning priorityprio.The second loop of SEARCH (lines (14)~(18)) performs the tentative priority assignment as TRAVERSE but it works forRefinedList instead ofUnAssigned. TheRefinedList is generated by sorting tasks inUnAssigned in the ascending order of D
e
l
a
y
i (line (12)) and eliminating infeasible tasks even with the highest preemption threshold assignment (line (13)).With the assertive and tentative priority assignments, _SEARCH generates a priority assignment tree like Figure 2(b), which is for the walk-through example task set of Table 1. In the tree, each solid-lined square node represents an assertive priority assignment to a task while each dashed-lined node represents pruning a priority assignment to a task. In Figure 2(b), two complete task orderings were generated: 〈
1,2
,
3,4
〉 and 〈
3,1
,
2,4
〉. Both orderings failed to assign feasible preemption thresholds to tasks as the dangled white triangle nodes indicate. The last task ordering T
O
S
=
〈
3,1
,
2,4
〉 corresponds to the priority ordering P
O
S
=
T
O
S
-
1
=
〈
2,3
,
1,4
〉 for SEARCH of Table 1. As shown in Table 1, SEARCH makes task τ
4 miss its deadline since (
R
4
=
14
)
>
(
D
4
=
11
). Figure 1(d) demonstrates such a deadline miss of task τ
4 where the second instance of task τ
4 completes at time point 26 while its absolute deadline is T
4
+
D
4
=
25. However, the walk-through example task set has a feasible priority ordering P
O
T
=
〈
3,2
,
1,4
〉 from TRAVERSE algorithm as we have shown in Section 3.1. This clearly shows SEARCH is not an optimal priority assignment algorithm for PTS.If we compare the priority assignment trees of TRAVERSE and SEARCH in Figures 2(a) and 2(b), we can see that T
O
S
=
〈
3,1
,
2,4
〉 is the 13th task ordering generated by TRAVERSE. The reason why SEARCH failed is due to the assertive priority assignment of p
1
S
←
2 with the 21st feasibility test, which we marked with a red dashed-line circle in Figure 2(b). We correct SEARCH in the next section.


## 4. Corrected SEARCH( ) Algorithm

In this section, we propose CORRECTED-SEARCH algorithm that corrects SEARCH algorithm. We first develop a theorem that is required in correcting SEARCH.Lemma 3.
Under PTS, if priorityp
i of task τ
i is fixed, its worst-case response time R
i does not decrease when its preemption threshold p
t
i is lowered.Proof.
WhileR
i is calculated from (1)~(6), p
t
i is only included in (4) for calculating F
i
,
q, specifically in the last term of the right side of (4): ∑
∀
j
,
p
j
>
pt
i
F
i
,
q
/
T
j
-
1
+
S
i
,
q
/
T
j
·
C
j. We refer to this term as I
i
,
q
F for the convenience of proving. I
i
,
q
F is the summation of the interference time by task τ
j such that ∀
j, p
j
>
p
t
i after S
i
,
q. Accordingly, the set of tasks that can interfere task τ
i with the lower p
t
i is always the superset of the set of such tasks with the higher p
t
i value. Consequently, I
i
,
q
F does not decrease with lower p
t
i. From (1), R
i monotonically increases with respect to to F
i
,
q and F
i
,
q is proportional to I
i
,
q
F from (4). Therefore, R
i is also proportional to I
i
,
q
F and thus R
i does not decrease with lower p
t
i.Theorem 4.
Under PTS, if taskτ
i with priority p
i
n in priority ordering P
O
n and the highest preemption threshold p
t
i (p
t
i
=
Γ) is infeasible, task set Γ with P
O
n is also infeasible.Proof.
From Definition1, task τ
i is feasible if and only if R
i
≤
D
i. From Lemma 3, if p
i is fixed (as p
i
n), p
t
i
=
Γ guarantees the minimal R
i for τ
i. Accordingly, if task τ
i with fixed p
i and p
t
i
=
Γ is infeasible, no other preemption threshold assignment can make R
i reduced, that is, τ
i feasible. From Definition 2, Γ with P
O
n is feasible if and only if all tasks with P
O
n in Γ are feasible. This proves the theorem.Algorithm2(a) shows the pseudo code of CORRECTED-SEARCH, which corrects SEARCH in Algorithm 1(b) as follows:(i)
deletion of the first loop of the assertive priority assignment and sorting tasks (lines (5)~(12) of Algorithm 1(b)),
(ii)
replacement ofSortedList withUnAssigned (line (13) of Algorithm 1(b)),
(iii)
adding “p
t
i
←
p
r
i
o;” after “p
i
←
p
r
i
o;” (line (15) of Algorithm 1(b)),
(iv)
replacement of OPT-ASSIGN-THRESHOLD(Γ) at line (
4
) with RESTORING-OPT-ASSIGN-THRESHOLD(Γ) of Algorithm 2(b).Algorithm 2:Pseudo code for (a) CORRECTED-SEARCH( ) and (b) RESTORING-OPT-ASSIGN-THRESHOLD( ).
(1)CORRECTED-SEARCH (Γ:set of tasks)
(2)
return  _CORRECTED-SEARCH(1, Γ, Γ);
(3)_CORRECTED-SEARCH (prio: priority,  UnAssigned: set of tasks,  Γ:set of tasks)
(4)
if (UnAssigned = ) return RESTORING-OPT-ASSIGN-THRESHOLD(Γ);
(5)RefinedList ← Refine(UnAssigned); // eliminating infeasible tasks even with the highest preemption threshold
(6)
foreach (τ
i
∈
R
e
f
i
n
e
d
L
i
s
t)
(7)p
i
←
p
r
i
o;
(8)p
t
i
←
p
r
i
o;
(9)if(_SEARCH(prio+ 1, UnAssigned −  τ
i, Γ) = success)return
success;
(10) // end-foreach
(11)return  fail;
(a) CORRECTED-SEARCH( )
(1)RESTORING-OPT-ASSIGN-THRESHOLD (Γ:set of tasks)
(2)
r
e
t
← OPT-ASSIGN-THRESHOLD(Γ);
(3)
if (ret = fail)foreach (τ
i
∈
Γ)   p
t
i
←
p
i;  // restore preemption thresholds
(4)
return  ret;
(b) RESTORING-OPT-ASSIGN-THRESHOLD( )Algorithm 3:Pseudo code for the proposed PRUNED-TRAVERSE( ) algorithm.
(1)PRUNED-TRAVERSE(Γ: set of tasks)
(2)    Γ← descendingSort(Γ, D
i);
(3)foreach (τ
i
∈
Γ)
(4)i
n
f
e
a
s
i
b
l
e
P
r
i
o
M
a
x
i
←
0;
(5)p
i
←
|
Γ
|;
(6)p
t
i
←
|
Γ
|;
(7) // end-foreach
(8)return_PRUNED-TRAVERSE(1, Γ,Γ);
(9)_PRUNED-TRAVERSE (prio: priority,  UnAssigned: set of tasks,  Γ:set of tasks)
(10)foreach (τ
i
∈
U
n
A
s
s
i
g
n
e
d)
(11)
if (prio < i
n
f
e
a
s
i
b
l
e
P
r
i
o
M
a
x
i)  continue;  // pruning this path with condition C2
(12)
p
i
←
p
r
i
o;
(13)
p
t
i
←
|
Γ
|;
(14)
if (prio = |Γ|)
(15)ret
= RESTORING-OPT-ASSIGN-THRESHOLD(Γ);
(16)
if(ret
=
fail)  i
n
f
e
a
s
i
b
l
e
P
r
i
o
M
a
x
i
←
|
Γ
|;
(17)
returnret;
(18)
// end-if
(19)
if (R
i
>
D
i)
(20)
p
i
←
|
Γ
|;  // restore to the highest priority
(21) if (prio > infeasiblePrioMax
i)  i
n
f
e
a
s
i
b
l
e
P
r
i
o
M
a
x
i
←
p
r
i
o;
(22)
continue;    // pruning this path with condition C1
(23)
// end-if
(24)
p
t
i
←
p
r
i
o;
(25)
if(_PRUNED-TRAVERSE(prio+ 1, UnAssigned −  τ
i, Γ) = success)return  success;
// The following line is executed when the above _PRUNED-TRAVERSE( ) returned fail.
(26)
foreach (τ
j
∈
U
n
A
s
s
i
g
n
e
d) p
j
←
|
Γ
|;  // restore to the highest priority
(27) // end-foreach
(28)return  fail;First, CORRECTED-SEARCH does not employ the first loop of SEARCH, the assertive priority assignment, which is the main cause of the nonoptimality of SEARCH as shown in the previous section. If we change the assertive priority assignment to a tentative priority assignment by replacing line (9) with line (16) in Algorithm 1(b), it just induces additional feasibility tests (due to invocation of operation WCRT) when a given task set is indeed infeasible. In other words, the first loop just becomes a performance bottleneck even though it is corrected and thus we remove it.Second, without the first loop of SEARCH, D
e
l
a
y
i is not calculated and thus the task sorting of line (12) of Algorithm 1(b) is not also employed. Note that the second loop of SEARCH is exactly the same as TRAVERSE except that it works forRefinedList instead ofUnAssigned. From Theorem 4, pruning at line (
5
) that makesRefinedList is valid. With this, we can easily see that CORRECTED-SEARCH is optimal since TRAVERSE is optimal.Third, we assign taskτ
i preemption threshold p
t
i as the same value of its priority at line (
8
) whenever its priority p
i is assigned (line (
7
)). This is to make sure that any priority assigned task is preemptable by higher priority tasks. For the feasibility test for refiningUnAssigned by subroutine Refine at line (
5
) to work correctly, it should be guaranteed that any task inUnAssigned can preempt the preassigned lower priority tasks in Γ
-
U
n
A
s
s
i
g
n
e
d. SEARCH does not need this preemption threshold assignment due to WCRT invocation at line (
6
) of Algorithm 1(b) where every task’s preemption threshold is set as its priority.Finally, RESTORING-OPT-ASSIGN-THRESHOLD in Algorithm 2(b) restores the preemption threshold of each task to its priority in the case of the failed (infeasible) preemption threshold assignment return. Without this correction, after OPT-ASSIGN-THRESHOLD has assigned preemption thresholds to tasks, preemption threshold values of tasks are contaminated and thus subroutine Refine at line (
5
) cannot work correctly.Figure2(c) shows the priority assignment tree of CORRECTED-SEARCH for the walk-through example task set of Table 1. In the figure, six complete task orderings were generated. The last task ordering T
O
C
=
〈
3,2
,
1,4
〉 is the same as T
O
T, and the resultant feasible task ordering of TRAVERSE. CORRECTED-SEARCH requires 74 feasibility tests while TRAVERSE requires 91 feasibility tests as the numbers besides triangle nodes indicate in Figures 2(a) and 2(c). As such, it is obvious that the overall performance of CORRECTED-SEARCH is much better than that of TRAVERSE since CORRECTED-SEARCH prunes infeasible paths while TRAVERSE does not. We develop the more performance enhanced algorithm in the next section.


## 5. PRUNED-TRAVERSE( ) Algorithm

SEARCH is not optimal since it prunes even feasible priority orderings. As such, pruning exhaustively without harming the optimality is important. In this section, we propose our optimal priority assignment algorithm for PTS, which we named PRUNED-TRAVERSE. We first develop required theorems for our proposed algorithm.Lemma 5.
Under any priority assignment algorithm that assigns distinctive priorities to tasks for PTS, if the priorityp
i of a task τ
i is lowered to p
i
′ (p
i
′
<
p
i), there exists at least one lower priority task τ
j (p
j
<
p
i) that heightens its priority p
j to p
j
′ with p
j
′
>
p
i
′.Proof.
The lemma can be easily proved by observing task orderings in priority assignment trees like Figure2(a). If task τ
i is moved to a lower priority level (the higher place), at least one of the lower priority tasks should be moved to a higher priority level (the lower place) since the total priority levels are fixed.Theorem 6.
Under PTS, if preemption thresholdp
t
i of task τ
i is fixed, its worst-case response time R
i does not decrease when its priority p
i is lowered.Proof.
For the convenience of proving, we refer to the last terms of the right sides of (4) and (5) as I
i
,
q
F and I
i
,
q
S, respectively. We prove the theorem by contradiction. Suppose that R
i of task τ
i decreases to R
i
′ when its priority p
i is lowered to p
i
′: R
i
′
<
R
i and p
i
′
<
p
i. For R
i to decrease, F
i
,
q should decrease from (1). For F
i
,
q to decrease, S
i
,
q or I
i
,
q
F should decrease from (4). Since the condition for calculating I
i
,
q
F is p
j
>
p
t
i, the change of priority p
i does not affect I
i
,
q
F. Therefore, S
i
,
q should decrease to S
i
,
q
′ such that S
i
,
q
-
S
i
,
q
′
>
0. Then, from (5), (
B
i
+
I
i
,
q
S
)
-
(
B
i
′
+
I
i
,
q
S
′
)
>
0 follows where B
i
′ and I
i
,
q
S
′ are changed values of B
i and I
i
,
q
S due to the lower priority. Then, (
B
i
-
B
i
′
)
>
(
I
i
,
q
S
′
-
I
i
,
q
S
) follows.
From Lemma5, if p
i is lowered to p
i
′ there exists at least one lower priority task τ
j (p
j
<
p
i) that heightens its priority p
j to p
j
′ such that p
j
′
>
p
i
′. Let the set of such additionally introduced higher priority tasks after the priority of task τ
i is lowered be A
d
d
e
d
H
P
i
=
τ
j
∣
p
j
<
p
i
a
n
d
p
j
′
>
p
i
′. The maximum possible value of (B
i
-
B
i
′) is achieved when B
i
′
=
0, which infers that at least one task in A
d
d
e
d
H
P
i contributes in making B
i. Let such a task in A
d
d
e
d
H
P
i be task τ
k; that is B
i
=
C
k. Then, max(
B
i
-
B
i
′
)
=
C
k follows. On the other hand, from (5), it follows that I
i
,
q
S
′
-
I
i
,
q
S
=
∑
∀
j
,
p
j
∈
A
d
d
e
d
H
P
i
1
+
S
i
,
q
′
/
T
j
·
C
j
≥
C
k. Then, (B
i
-
B
i
′
)
≤
(
I
i
,
q
S
′
-
I
i
,
q
S
) follows. This is a contradiction, which proves the theorem.Theorem 7.
Under PTS, if taskτ
i with priority p
i
n in priority ordering P
O
n and the highest preemption threshold p
t
i
=
Γ is infeasible, task set Γ with another priority ordering P
O
m that assigns task τ
i the lower priority p
i
m (such that p
i
m
<
p
i
n) is also infeasible.Proof.
Let the worst-case response time of taskτ
i with p
t
i
=
Γ and p
i
n be R
i. Let the worst-case response time of task τ
i with p
t
i
=
Γ and p
i
m be R
i
′. From Lemma 3, both R
i and R
i
′ are the minimal possible worst-case response time with each given priority. From Theorem 6, R
i
′
≥
R
i follows. Since task τ
i with p
i
n and p
t
i
=
Γ is infeasible, R
i
>
D
i follows from Definition 1. Therefore, R
i
′
>
D
i follows. Accordingly, task τ
i with p
i
m and p
t
i
=
Γ is infeasible. Consequently, from Theorem 4, task set Γ with P
O
m is also infeasible.Now we propose PRUNED-TRAVERSE that extends TRAVERSE by exhaustively pruning infeasible paths. PRUNED-TRAVERSE prunes such priority ordering P
O
n that assigns task τ
i priority p
i
n when the following condition is true: (7)
C
1
∨
C
2
,where C
1 is p
t
i
=
Γ
∧
R
i
>
D
i, and C
2 is p
i
n
<
max
⁡
p
i
∣
C
1.Apparently, ConditionC
1 is from Theorem 4 and Condition C
2 is from Theorem 7.Algorithm3 shows the pseudo code for PRUNED-TRAVERSE. Like TRAVERSE, PRUNED-TRAVERSE depends on its subroutine, _PRUNED-TRAVERSE, which has the same parameters as _TRAVERSE:prio,UnAssigned, and Γ (line (
9
)). Like _TRAVERSE, _PRUNED-TRAVERSE assigns priorities to tasks from the lowest priority 1 to the highest priority Γ: it assigns each task τ
i inUnAssigned (line (
10
)) priorityprio (line (
12
)) and the remaining unassigned tasks (U
n
A
s
s
i
g
n
e
d
-
τ
i) are recursively assigned priority p
r
i
o
+
1 at line (
21
).Unlike TRAVERSE, PRUNED-TRAVERSE first sorts tasks in a deadline monotonic decreasing order since DMPO also works well in many cases (line (
2
)). PRUNED-TRAVERSE introduces for task τ
i new attribute i
n
f
e
a
s
i
b
l
e
P
r
i
o
M
a
x
i
=
max
⁡
p
i
∣
C
1, which is the right side of the Condition C2. It initializes i
n
f
e
a
s
i
b
l
e
P
r
i
o
M
a
x
i as zero at line (
4
).Unlike _TRAVERSE, _PRUNED-TRAVERSE needs to perform a feasibility test for task τ
i (getting R
i) while assigning each priority in order to prune infeasible paths. For this, we need to make sure that all tasks inUnAssigned have higher priorities than the priorities of the previously priority assigned tasks. For this, PRUNED-TRAVERSE assigns the highest priority Γ to all unassigned tasks initially at line (
5
). _PRUNED-TRAVERSE also does so conditionally at line (
26
) whenever the next priority (p
r
i
o
+
1) assignment fails at line (
25
). Preemption thresholds of all tasks are also initialized as the same value of their priorities at line (
6
).Before assigning taskτ
i priorityprio (line (
12
)), _PRUNED-TRAVERSE first prunes any infeasible priority ordering at line (
11
) ifprio is smaller than i
n
f
e
a
s
i
b
l
e
P
r
i
o
M
a
x
i, which is Condition C2. Condition C1 is applied at lines (
13
) and (
19
) and the priority ordering with Condition C1 is pruned at line (
22
). Line (
20
) is for restoring the priority of the pruned task. Line (
21
) is for updating i
n
f
e
a
s
i
b
l
e
P
r
i
o
M
a
x
i. If task τ
i is assigned priorityprio without being pruned, its preemption threshold is assigned the same as its priority at line (
24
), without which PTS becomes the fully nonpreemptive scheduling (NPS) due to the highest preemption threshold assignment at line (
13
).Onceprio of the maximum priority |
Γ
| is assigned (line (
14
)), which means that a complete priority ordering is generated, _PRUNED-TRAVERSE assigns preemption thresholds by invoking RESTORING-OPT-ASSIGN-THRESHOLD in Algorithm 2(b). Note that there are two differences with TRAVERSE in assigning preemption thresholds: (
1
) invoking RESTORING-OPT-ASSIGN-THRESHOLD instead of OPT-ASSIGN-THRESHOLD and (
2
) assigning preemption thresholds to tasks once the maximum priority is assigned instead onceUnAssinged is . (
1
) is for the proper pruning operation as we explained in proposing CORRECTED-SEARCH in Section 4. (
2
) is for reducing one recursive function call for a performance benefit: one recursive function call is reduced for each complete priority ordering in PRUNED-TRAVERSE compared to TRAVERSE or CORRECTED-SEARCH.When any preemption threshold assignment is not feasible, RESTORING-OPT-ASSIGN-THRESHOLD returns fail. In that case, i
n
f
e
a
s
i
b
l
e
P
r
i
o
M
a
x
i is set to Γ at line (
16
). This is because the fail return of RESTORING-OPT-ASSIGN-THRESHOLD infers that the highest priority assigned task τ
i is not feasible due to some blocking task whose preemption threshold should be raised for it to be feasible. The recursive invocation of _PRUNED-TRAVERSE returns only when the return value of the recursive invocation issuccess (line (
25
)). With this, returning at the last lines (line (
28
)) happens when a specific ordering is not feasible._PRUNED-TRAVERSE requires careful restorations of priorities and preemption thresholds of tasks, which are repetitively and tentatively assigned. Since SEARCH and CORRECTED-SEARCH prune infeasible paths within subroutine Refine, such restoration is easier and less error-prone. However, PRUNED-TRAVERSE prunes infeasible paths as earlier as possible for the better efficiency and thus requires careful restoring operations. Priorities are restored before pruning at line (
20
) and after the failed priority assignment at line (
26
). Preemption thresholds are restored in RESTORING-OPT-ASSIGN-THRESHOLD at line (
15
). Assigning the preemption threshold as same as the priority of the priority assigned task at line (
24
) is also important for the proper pruning.Now we prove the optimality of PRUNED-TRAVERSE.Theorem 8.
PRUNED-TRAVERSE is optimal for PTS: it finds a feasible scheduling attributes assignment if there exists one.Proof.
PRUNED-TRAVERSE extends TRAVERSE by pruning infeasible priority orderings with Condition C1 or C2. Condition C1 is valid from Theorem 4 and condition C2 is valid from Theorem 7. Consequently, since TRAVERSE is optimal, PRUNED-TRAVERSE is optimal.Figure2(d) shows the priority assignment tree of PRUNED-TRAVERSE for the walk-through example task set of Table 1. In the figure, a gray dashed-lined circle represents pruning a priority ordering without any feasibility test, which is achieved by application of Condition C2 from Theorem 7. By comparing Figures 2(c) and 2(d), we can easily see this additional pruning helps much in reducing the number of feasibility tests: the feasibility tests of (
7
), (21)~(39), (55)~(62) in Figure 2(c) do not happen in Figure 2(d). We can also see that the earlier pruning with condition C1 of PRUNED-TRAVERSE instead of using subroutine Refine of CORRECTED-SEARCH reduces the number of feasibility tests: the feasibility tests of (
4
), (
42
), (
64
) in Figure 2(c) do not happen in Figure 2(d).The resultant last task orderingT
O
P
=
〈
3,2
,
1,4
〉 is the same as T
O
C and T
O
T, which are the resultant feasible task ordering of CORRECTED-SEARCH and TRAVERSE, respectively. PRUNED-TRAVERSE produces four complete priority orderings and requires 47 feasibility tests while CORRECTED-SEARCH produces six complete priority orderings and requires 74 feasibility tests. As such, it is obvious that the overall performance of PRUNED-TRAVERSE is much better than that of CORRECTED-SEARCH since PRUNED-TRAVERSE prunes more infeasible paths than CORRECTED-SEARCH exploiting Theorem 7 and the earlier pruning. We show the empirical performance comparison results in Section 7.


## 6. Complexity

Letn
=
Γ and E the nonpolynomial [20] complexity of the feasibility test (calculating R
i from (1)~(6)). Since the pruning operation is conditional, all these algorithms in the worst-case produce n
! priority orderings of P
O
Γ, each of which requires O
(
n
2
) feasibility tests [3] via OPT-ASSIGN-THRESHOLD. With this, TRAVERSE has the complexity of O
(
E
·
n
!
·
n
2
).On the other hand, each pruning operation of CORRECTED-SEARCH and PRUNED-TRAVERSE requires one feasibility test for each tentative priority assignment or pruning (circle) node. The number of circle nodes in a priority assignment tree in the worst-case is n
+
n
·
(
n
-
1
)
+
n
·
(
n
-
1
)
·
(
n
-
2
)
+
⋯
+
n
!, which is O
(
n
!
). Therefore, the worst-case complexity of CORRECTED-SEARCH and PRUNED-TRAVERSE is O
(
E
·
n
!
·
n
2
)
+
O
(
E
·
n
!
)
=
O
(
E
·
n
!
·
n
2
), which is the same as that of TRAVERSE. However, the pruning operation obviously works as a branch and bound mechanism and derives much better performances in most cases as the following empirical comparison shows.


## 7. Empirical Performance Evaluations

We set the performance metrics of priority assignment algorithms for PTS as(
1
) schedulability as the ratio of feasible task sets and (
2
) actual runtimes for executing algorithms. The experiments for getting the actual runtimes of the algorithms were done on Intel Core i7-4770, 3.40 GHz with 8 GB RAM. We set the total utilization of each task set as U
=
0.9. This utilization represents high-demanding workloads, which makes the feasibility of a given task set be greatly dependent on a proper priority assignment algorithm. Note that the utilization bound U
B under the rate monotonic scheduling (RMS) [29] when Γ
=
n is U
B
=
n
·
2
n
-
1
. For example, if Γ
=
10 and U
≤
0.72 (≅
10
·
(


2
10
-
1)=
U
B), we even do not need PTS if task deadlines are the same as periods since the fully preemptive fixed priority scheduling with DMPO always makes the task set feasible.We generated each task set in the same manner as [9]. Specifically, for a given total utilization U
=
0.9, we generated each task’s utilization u
i using UUniFast [30] algorithm. For each task τ
i, we generated C
i as a random integer uniformly distributed in the interval [
100,500
], T
i
=
C
i
/
u
i, and D
i as a random integer uniformly distributed in the interval [
C
i
+
0.5
·
(
T
i
-
C
i
)
,
T
i
]. For each experiment with a specific parameter setting, we generated 2,000 task sets. To focus on the effectiveness of pruning operations of PRUNED-TRAVERSE, each task set was ordered in the deadline monotonic decreasing order. Since TRAVERSE took too much time when the number of tasks is large, we applied timeout for executing TRAVERSE when Γ
≥
10. The actual runtimes of TRAVERSE with timeout were set as the real actual runtime of TRAVERSE when a task set was not feasible.


### 7.1. Schedulability

Figure3 shows the schedulability results with U
=
0.9 and Γ
=
10. Figure 3(a) shows the percentage ratio of feasible task sets and Figure 3(b) shows the Venn diagram for the number of feasible task sets. The ratio of feasible task sets was calculated as the number of feasible task sets divided by the total number of generated task sets. The resultant feasible task set ratios of TRAVERSE, CORRECTED-SEARCH, and PRUNED-TRAVERSE were exactly the same and thus we omitted the results of TRAVERSE and CORRECTED-SEARCH in Figure 3.Figure 3
Schedulability withU
=
0.9 and Γ
=
10.
(a)
Ratio of feasible task sets in percentage
(b)
Venn diagram for the number of feasible task sets in 2,000 task setsFigure3(a) clearly shows that the schedulability performance results of PA-DMMPT [24], SEARCH [1], GREEDY-SA [3], DMPO [9], and PRUNED-TRAVERSE are uniformly improved in order. Specifically, PA-DMMPT, SEARCH, GREEDY-SA, DMPO, and PRUNED-TRAVERSE could, respectively, schedule 50.6%, 53.45%, 59.9%, 64.65%, and 67.65%. Note that PRUNED-TRAVERSE outperforms than any other priority assignment algorithms, which clearly shows that the other algorithms are nonoptimal.Figure3(b) shows the Venn diagram for the number of feasible task sets in 2,000 task sets. As shown, PRUNED-TRAVERSE could schedule 27 task sets that could not be scheduled by any other existing heuristic priority assignment algorithms. It is notable that each heuristic algorithm could schedule some task sets that could not be scheduled by the other heuristic algorithms. For example, SEARCH could schedule two task sets that could not be scheduled by the other heuristic algorithms.DMPO is a very efficient algorithm that requires almost no implementation efforts as well as computation time burden. Accordingly, it is practical to combine DMPO with another heuristic algorithm. Figure3(b) shows that SEARCH, GREEDY-SA, and PA-DMMPT, respectively, could schedule 5 (2 + 0 + 2 + 1), 19 (9 + 8 + 2 + 0), and 22 (11 + 1 + 2 + 8) task sets that could not be schedule by DMPO. On the other hand, DMPO + SEARCH, DMPO + GREEDY-SA, and DMPO + PA-DMMPT, respectively, could schedule 64.9%, 65.6%, and 65.75%. With this, we conclude that PA-DMMPT is the most effective heuristic priority assignment algorithm as the best candidate to be combined with DMPO. Therefore, we compare its actual runtimes with our proposed algorithms in the next subsection. Note that any DMPO combined heuristic algorithm cannot become optimal due to the existence of task sets that can be scheduled only by PRUNED-TRAVERSE as shown in Figure 3(b).


### 7.2. Actual Runtimes

We compare the actual runtimes for executing optimal priority assignment algorithms and PA-DMMPT, which is the most effective heuristic algorithm to be combined with DMPO as shown in the previous section. Figures 4(a) and 4(b) show the actual runtime results in seconds as box plots when U
=
0.9 for Γ
=
5 and Γ
=
10, respectively. Y axis is in a log scale to better show the distributions of result values. Each box in a box plot shows data results between 25% and 75% of performance distribution. The middle line within each box shows the median value of the results while the filled circle mark shows the average value of the results.Figure 4
Actual runtimes in seconds whenU
=
0.9.
(a)
Γ
=
5
(b)
Γ
=
10Figures4(a) and 4(b) clearly show that the actual runtime performance distribution results of TRAVERSE, CORRECTED-SEARCH, and PRUNED-TRAVERSE are uniformly improved in order. In Figure 4(a) with Γ
=
5, the maximum and average runtimes were decreased by 72.6% and 87.0%, respectively, in CORRECTED-SEARCH compared to the TRAVERSE (from 0.84 sec to 0.23 sec and from 0.23 sec to 0.03 sec). PRUNED-TRAVERSE further decreased the maximum and average actual runtime values of CORRECTED-SEARCH by 8.7% and 33.3%, respectively (to 0.21 sec and to 0.02 sec).Such performance differences become drastically large as the number of tasksΓ increases. In Figure 4(b) with Γ
=
10, the maximum and average actual runtimes of CORRECTED-SEARCH compared to TRAVERSE were decreased by 98.0% and 99.95%, respectively (from 67809 sec to 1331 sec and from 21947 sec to 10.73 sec). Moreover, PRUNED-TRAVERSE decreased the maximum and average values of CORRECTED-SEARCH by 61.2% and 58.3%, respectively (to 517 sec and to 4.47 sec).On the other hand, we can see the median values of actual runtimes of TRAVERSE were always smaller than any other algorithms. This is because TRAVERSE does not perform any feasibility test for priority assignments that are required by the other algorithms. When a task set is feasible with DMPO, the actual runtimes of TRAVERSE are the same as DMPO.Figures4(a) and 4(b) also show that the actual runtimes of PA-DMMPT are much larger than PRUNED-TRAVERSE and even larger than CORRECTED-SEARCH. Specifically in Figure 4(b) with Γ
=
10, the maximum and average actual runtimes of PA-DMMPT compared to PRUNED-TRAVERSE were increased by 1167% and 150% (from 517 sec to 6551 sec and from 4.47 sec to 11.18 sec). This is because PA-DMMPT calculates task blocking limits by generating candidate pairs of start and finish times of tasks. As well investigated in [31], the execution requirements of such an approach that generates scheduling points grow exponentially with an increasing range of task periods. Our experimental task sets were generated in the same manner as [9], where the range of task periods increases as the number of tasks increases.However, PRUNED-TRAVERSE still cannot be used as an online feasibility test algorithm since its performance is also degraded much as the number of tasks increases. For example, for a task set Γ with U
=
0.9 and Γ
=
20, PRUNED-TRAVERSE took 7 hours to determine that the task set was after all infeasible. Nevertheless, the above experimental results clearly show that PRUNED-TRAVERSE outperforms than any other optimal priority assignment algorithms as well as the best effective heuristic priority assignment algorithm for PTS.


## 7.1. Schedulability

Figure3 shows the schedulability results with U
=
0.9 and Γ
=
10. Figure 3(a) shows the percentage ratio of feasible task sets and Figure 3(b) shows the Venn diagram for the number of feasible task sets. The ratio of feasible task sets was calculated as the number of feasible task sets divided by the total number of generated task sets. The resultant feasible task set ratios of TRAVERSE, CORRECTED-SEARCH, and PRUNED-TRAVERSE were exactly the same and thus we omitted the results of TRAVERSE and CORRECTED-SEARCH in Figure 3.Figure 3
Schedulability withU
=
0.9 and Γ
=
10.
(a)
Ratio of feasible task sets in percentage
(b)
Venn diagram for the number of feasible task sets in 2,000 task setsFigure3(a) clearly shows that the schedulability performance results of PA-DMMPT [24], SEARCH [1], GREEDY-SA [3], DMPO [9], and PRUNED-TRAVERSE are uniformly improved in order. Specifically, PA-DMMPT, SEARCH, GREEDY-SA, DMPO, and PRUNED-TRAVERSE could, respectively, schedule 50.6%, 53.45%, 59.9%, 64.65%, and 67.65%. Note that PRUNED-TRAVERSE outperforms than any other priority assignment algorithms, which clearly shows that the other algorithms are nonoptimal.Figure3(b) shows the Venn diagram for the number of feasible task sets in 2,000 task sets. As shown, PRUNED-TRAVERSE could schedule 27 task sets that could not be scheduled by any other existing heuristic priority assignment algorithms. It is notable that each heuristic algorithm could schedule some task sets that could not be scheduled by the other heuristic algorithms. For example, SEARCH could schedule two task sets that could not be scheduled by the other heuristic algorithms.DMPO is a very efficient algorithm that requires almost no implementation efforts as well as computation time burden. Accordingly, it is practical to combine DMPO with another heuristic algorithm. Figure3(b) shows that SEARCH, GREEDY-SA, and PA-DMMPT, respectively, could schedule 5 (2 + 0 + 2 + 1), 19 (9 + 8 + 2 + 0), and 22 (11 + 1 + 2 + 8) task sets that could not be schedule by DMPO. On the other hand, DMPO + SEARCH, DMPO + GREEDY-SA, and DMPO + PA-DMMPT, respectively, could schedule 64.9%, 65.6%, and 65.75%. With this, we conclude that PA-DMMPT is the most effective heuristic priority assignment algorithm as the best candidate to be combined with DMPO. Therefore, we compare its actual runtimes with our proposed algorithms in the next subsection. Note that any DMPO combined heuristic algorithm cannot become optimal due to the existence of task sets that can be scheduled only by PRUNED-TRAVERSE as shown in Figure 3(b).


## 7.2. Actual Runtimes

We compare the actual runtimes for executing optimal priority assignment algorithms and PA-DMMPT, which is the most effective heuristic algorithm to be combined with DMPO as shown in the previous section. Figures 4(a) and 4(b) show the actual runtime results in seconds as box plots when U
=
0.9 for Γ
=
5 and Γ
=
10, respectively. Y axis is in a log scale to better show the distributions of result values. Each box in a box plot shows data results between 25% and 75% of performance distribution. The middle line within each box shows the median value of the results while the filled circle mark shows the average value of the results.Figure 4
Actual runtimes in seconds whenU
=
0.9.
(a)
Γ
=
5
(b)
Γ
=
10Figures4(a) and 4(b) clearly show that the actual runtime performance distribution results of TRAVERSE, CORRECTED-SEARCH, and PRUNED-TRAVERSE are uniformly improved in order. In Figure 4(a) with Γ
=
5, the maximum and average runtimes were decreased by 72.6% and 87.0%, respectively, in CORRECTED-SEARCH compared to the TRAVERSE (from 0.84 sec to 0.23 sec and from 0.23 sec to 0.03 sec). PRUNED-TRAVERSE further decreased the maximum and average actual runtime values of CORRECTED-SEARCH by 8.7% and 33.3%, respectively (to 0.21 sec and to 0.02 sec).Such performance differences become drastically large as the number of tasksΓ increases. In Figure 4(b) with Γ
=
10, the maximum and average actual runtimes of CORRECTED-SEARCH compared to TRAVERSE were decreased by 98.0% and 99.95%, respectively (from 67809 sec to 1331 sec and from 21947 sec to 10.73 sec). Moreover, PRUNED-TRAVERSE decreased the maximum and average values of CORRECTED-SEARCH by 61.2% and 58.3%, respectively (to 517 sec and to 4.47 sec).On the other hand, we can see the median values of actual runtimes of TRAVERSE were always smaller than any other algorithms. This is because TRAVERSE does not perform any feasibility test for priority assignments that are required by the other algorithms. When a task set is feasible with DMPO, the actual runtimes of TRAVERSE are the same as DMPO.Figures4(a) and 4(b) also show that the actual runtimes of PA-DMMPT are much larger than PRUNED-TRAVERSE and even larger than CORRECTED-SEARCH. Specifically in Figure 4(b) with Γ
=
10, the maximum and average actual runtimes of PA-DMMPT compared to PRUNED-TRAVERSE were increased by 1167% and 150% (from 517 sec to 6551 sec and from 4.47 sec to 11.18 sec). This is because PA-DMMPT calculates task blocking limits by generating candidate pairs of start and finish times of tasks. As well investigated in [31], the execution requirements of such an approach that generates scheduling points grow exponentially with an increasing range of task periods. Our experimental task sets were generated in the same manner as [9], where the range of task periods increases as the number of tasks increases.However, PRUNED-TRAVERSE still cannot be used as an online feasibility test algorithm since its performance is also degraded much as the number of tasks increases. For example, for a task set Γ with U
=
0.9 and Γ
=
20, PRUNED-TRAVERSE took 7 hours to determine that the task set was after all infeasible. Nevertheless, the above experimental results clearly show that PRUNED-TRAVERSE outperforms than any other optimal priority assignment algorithms as well as the best effective heuristic priority assignment algorithm for PTS.


## 8. Conclusion

Preemption threshold scheduling (PTS) has been widely accepted in the industrial domain for its effectiveness of scalable real-time embedded system design with the increased real-time schedulability (feasibility). However, without an available optimal scheduling attributes assignment algorithm (optimal in the sense that it is guaranteed to find a feasible scheduling attributes assignment if one exists), we cannot achieve the full benefits of PTS.Since there exists an optimal and efficientO
(
n
2
) preemption threshold assignment algorithm [1] that operates with fully assigned priority orderings, we need an optimal priority assignment algorithm for PTS. In this paper, we analyzed previously proposed optimal priority assignment algorithms for PTS: TRAVERSE [13] and SEARCH [1]. Using priority assignment trees, we showed the inefficiency of TRAVERSE due to its lack of any pruning operation. We also showed the nonoptimality of SEARCH due to its pruning of even feasible priority orderings.We developed some theorems for safely and exhaustively pruning infeasible priority ordering paths while assigning priorities to tasks before assigning feasible preemption thresholds for PTS. Using these theorems, we corrected SEARCH and presented CORRECTED-SEARCH algorithm. We also proposed PRUNED-TRAVERSE that enhances the performance of CORRECTED-SEARCH while proving its optimality. Our empirical evaluation results clearly showed the effectiveness of PRUNED-TRAVERSE both in schedulability and actual runtimes compared to any other existing priority assignment algorithms for PTS.



---

*Source: 837472-2015-11-25.xml*