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 schedulare 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 preWhile 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 schedulpriority 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 based on back-tracking, i.e. it traverses the space of potential executing task. This means that as soon as the task starts 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 algocomplexity 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 approaches 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 priware; •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 1. INTRODUCTION be scheduled provides task priorities and thresholds. The 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 to traverse the search space. Contributions: In this paper we propose an algorithm for optimal priority and threshold assignment. Moreover, we
∗This work is supported by the ARTEMIS Joint Undertaking project EMC2 (grant agreement 621429).
EWiLi’16, October 6th, 2016, Pittsburgh, USA. Copyright retained by the authors. show by means of experimental results that the computation time for finding a priority and threshold assignment for a set of tasks that can make them schedulable, if such a combination exists, is growing considerably slower compared to the existing solution when the number of tasks increases. Further, we present the schedulability results of comparing our proposed algorithm with FPPS and FPTS under a deadline monotonic assignment. Finally, we present a comparative evaluation of FPTS with a deadline monotonic priority assignment and optimal preemption thresholds and our OPTA, which clearly illustrates the advantage of our OPTA.
In this section we show by means of an example that the deadline monotonic priority assignment is not optimal for FPTS.
Let us consider a task set TI which consists of 4 tasks as presented in Table 1. The tasks are characterized by their worst-case computation time Ci, minimum inter-arrival time Ti, deadline Di, preemption thresholds θi, and priority πi. The smaller numbers denote higher priorities. All tasks have implicit deadlines, i.e. Ti = Di, and the priorities πiDM are assigned based on deadline monotonic priority assignment, i.e. the task with the smallest deadline has the highest priority. At utilization U TI ≈ 0.982, TI is not schedulable under FPTS. If the priorities of τ3 and τ4 are exchanged (as in πi) TI becomes schedulable under FPTS with preemption thresholds θi and worst-case response times Ri.
Preemption Threshold Scheduling (PTS) has been
proposed by Wang and Saksena in [
Deferred Preemptions Scheduling (DPS) has first been
introduced by Baruah [
Fixed Preemption Points (FPP) has been proposed by
Burns [
Worst-case response time analysis for FPTS as well as
an optimal priority and preemption threshold assignment
algorithm was first presented in [
Worst-case response time analysis of periodic real-time
tasks under fixed-priority scheduling with deferred preemption
(FPDS)has been studied in [
The system consist of a single processor including a set of n independent sporadic tasks. Each task τi is denoted by < Ci, Di, Ti >, where Ci ∈ R+ denotes the worst-case execution time, Di ∈ R+ denotes the relative deadline and Ti ∈ R+ is the minimum inter-arrival time. We assume a constrained-deadline task model, i.e., Di ≤ Ti (even though we use a generalized analysis). 4.2
Tasks are further annotated by unique priorities πi ∈ N and preemption thresholds θi ∈ N. For both, smaller values denote higher priorities. Whenever we compare priorities or thresholds, we compare their numerical values, i.e. πi < πj means that task πi has a higher priority than πj. Preemption thresholds are always greater than or equal to the corresponding priorities θi ≤ πi.
Given these priorities and thresholds, the tasks are scheduled as follows. If there are no running tasks, the task τi with the highest priority among the simultaneously released tasks starts executing. As soon as it starts executing it can be preempted only by tasks τj that have priority greater than its preemption threshold πj < θi. In the situation when the executing task has a higher priority than the preempted task τi and waiting task τj where θi ≤ πj, τi will always start executing before τj. 5. 5.1
While worst-case response time analysis for FPTS policy
has been published several times [
A task τi releases an infinite series of jobs τik. Each of these jobs faces two kinds of delays to its execution: blocking and interference. Blocking (1) comes from the lower priority tasks that have a preemption threshold equal to or higher than the priority of the current task.
Bi = max(0,
max ∀j:θj≤πi<πj
Cj) (1)
Since the sequence of jobs released by the task τi is infinite,
we need to determine how many jobs should be analyzed to
determine whether the entire task is schedulable or not. This
calculation is based on the worst-case level-i active period
[
Li = Bi +
Li Tj
Cj ∀j:πj≤πi li =
Li
Ti
The maximum number li of jobs of τi that can be executed in this level-i active period is given by (3). (2) (3)
Given the knowledge of how many jobs need to be analyzed, we can compute their worst-case start time Sik for 0 ≤ k < li as the smallest positive value Sik that satisfies (4).
⎧ Sik = ⎪⎪⎨ ⎪⎩⎪
Bi + kCi + kCi +
Sik Cj ∀j:πj<πi Tj
if Bi > 0 ∀j:πj<πi 1 +
Sik Tj
Cj if Bi = 0 (4)
Likewise, other tasks may preempt the observed job, thus causing interference. This quantity is encompassed by calculating each job’s worst-case finalization time Fik. It can be found as the smallest positive Fik that satisfies (5).
⎧ Fik = ⎪⎪⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎪⎪⎩
Sik + Ci+
∀j:πj<θi Sik + Ci+ ∀j:πj<θi
Fik Tj Fik Tj −
Sik
Tj − 1 +
Cj Sik Tj
if Bi > 0 Cj if Bi = 0 (5)
Finally, according to (6), we compute the worst-case response time as the maximum of response times of all jobs within the worst-case level-i active period.
Ri =
max ∀k:0≤k<li (Fik − kTi) (6) 5.2
First, let us define the key concept that is the basis of our
algorithm. Blocking tolerance for tasks with non-preemptive
regions was introduced by Lortz and Shin [
Definition 1 (Blocking tolerance). Given a schedulable task τi in the context of a set of tasks T , its blocking tolerance βi is the maximum amount of blocking that it can experience from a lower priority task while staying schedulable.
In other words, blocking tolerance is the maximum computation time that can be assigned to a task of a lower priority that blocks the observed task without compromising the observed task’s schedulability. Next, let us derive two observations that will be utilized in our algorithm.
Corollary 1. Given two tasks τi and τj with Cj > βi, task τi will be rendered unschedulable if task τj blocks it (πj > πi ∧ θj ≤ πi) or is assigned a priority greater than πi.
Based on Definition 1, the first part of Lemma 1 is immediately true. To observe that the second part is also true, we can inspect that while blocking value Bi in (4) influences only the start time of the task, if the same computation time is allocated to a higher priority, it is introduced into the computation of starting time (4) and optionally finishing time (5) as Cj .
Lemma 1. Let τi be a task and T be a set of schedulable tasks with assigned priorities and thresholds. If task τi is not schedulable in the context of T with the lowest priority ∀πj ∈ T : πi > πj and any preemption threshold, it will not be schedulable if additional tasks are added to T .
From the worst case response time equations, it is trivial to deduce that adding more interference will never reduce the response time. 6.
In this section, we present an OPTA algorithm for FPTS.
The algorithm is optimal in the sense that it will find a
feasible priority and thresholds assignment that makes a
task set schedulable if such solution exists. Similar to the
OPTA in the work by Wang and Saksena [
FPTS-OPT algorithm uses three types of pruning for infeasible priority orderings to reduce the searched state-space. All three types of pruning utilize the same information about blocking tolerance computed once per recursive call for every unassigned task.
First, any partial priority ordering that results in a blocking tolerance less than 0, for a yet unassigned task, is immediately rejected (lines 6–8 of Algorithm 1).
Second, if there are two tasks that have computation times greater then the blocking tolerance of the other task, there is no sequence of priority orderings that can make both tasks schedulable. Therefore we reject the current partial priority ordering (lines 9–11). This is the immediate consequence of Lemma 1. Even if these two tasks do not experience blocking from each other, the one at a higher priority will be introducing interference.
And third, let there be two unassigned tasks τi, and τj where the blocking tolerance βi of τi is smaller than the computation time Cj of the other task τj (βi < Cj ) and blocking tolerance of τj is larger than the computation time of the task τi (βj ≥ Ci). Then there is only one sequence of priorities under which these tasks can be made schedulable: τi at a higher priority than τj . Therefore, it is safe to remove the task τj from the current priority (lines 12–19).
Algorithm 1 FPTS-OPT Input:
H = ∅ A set of tasks L, and {Ci, Ti, Di} ∀τi ∈ L.
Prio = 1 The highest priority. Output:
The schedulability of the task set, πi, and θi ∀τi ∈ T . 1: function Search(H, L, Prio) 2: if L = ∅ then 3: return schedulable 4: end if 5: ∀τi ∈ L : βi, θi ← CalculateBT(H, τi); 6: if (∃τi ∈ L : βi < 0) then 7: return unschedulable 8: end if 9: if (∃τi, τj ∈ L : i = j ∧ βi < Cj ∧ βj < Ci) then 10: return unschedulable 11: end if
L is a list of tasks that can be assigned priority Prio.
L ← L for (τi ∈ L) do for (τj ∈ L \ {τi}) do
if (βi < Cj ∧ βj ≥ Ci) then
The idea behind assigning priorities in a descending order is that, if a task is at a lower priority, it will experience a higher amount of interference which in turn leads to a smaller tolerance for blocking.
On the other hand, smaller blocking tolerance reduces the opportunity for lower priority tasks (which are not schedulable by their current priority level) to increase their preemption threshold for a try to become schedulable. To exploit 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 blocking tolerance. 6.3
The algorithm divides the task set into two groups: (i) a set of higher priority tasks H which have their priorities and thresholds assigned (ii), and a set of lower priority tasks L with unassigned priorities and thresholds.
The algorithm starts with an empty set H, and all tasks to be processed in L. Additionally, a parameter of which priority should be processed is passed to the algorithm, which is initially the highest available priority in the system.
The algorithm finds a solution if no task remains in L (lines 2–4 in the algorithm). In each iteration of the algorithm, first the blocking tolerance and preemption thresholds of all tasks in L are calculated (line 5 in the algorithm). The preemption threshold θi is the highest one with which all tasks in H can be scheduled if the task were added to the set at the priority Prio. This preemption threshold is subsequently used to calculate blocking tolerance βi of the same task.
There are two pruning conditions to determine if the task set is unschedulable: In a given priority level, if (i) the blocking tolerance of any task is a negative value (lines 6– 8 in the algorithm), and (ii) there exist two tasks where blocking tolerance of each is lower than the execution time of the other, i.e., (∃τi, τj ∈ L : i = j ∧ βi < Cj ∧ βj < Ci) (lines 9–11 in the algorithm).
Another condition for pruning the tasks from a specific priority level is that, the execution time of those tasks cannot satisfy the blocking tolerance of some tasks at that priority level, i.e., (∃τi, τj ∈ L : i = j ∧βi < Cj ∧βj ≥ Ci) (lines 12–19 in the algorithm) which means that τi is not schedulable at a lower priority level, thus τj is pruned from the current priority level. The tasks that should be explored at the current priority level are added to list L . Tasks in L are then sorted in ascending order of their blocking tolerances by SortβInc function (line 20 in the algorithm).
The task τi at the head of L , i.e., the task with minimum blocking tolerance, is selected to be assigned to the current priority level, removed from L, and added to H (lines 22 to 25 in the algorithm).
The algorithm subsequently goes one step deeper in the recursion for the next (lower) priority level (line 26 in the algorithm). If the recursion returns a schedulable value, the value is returned, otherwise the algorithm proceeds to try to schedule the next task from the list L . 7.
A prerequisite for a comparative evaluation of our
algorithm and the algorithm presented by Wang and Saksena [
After inspecting the pseudo-code in Figure 3 of [
In this section we present the results of our experiments.
As the first set of experiments, we have measured the
complexity of our proposed algorithm compared to Wang and
Saksena’s algorithm1 [
As a second set of experiments, we compared the schedulability ratios of task sets under FPTS with deadline monotonic priority assignments and optimal preemption thresholds and under FPTS with our OPTA. 8.1
For both sets of experiments, 5000 task sets are randomly
generated using UUnifast algorithm [
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
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 values: (1) minimum value which is the lower point in the graph, (2) first quartile value which is the lower edge of the square, (3) median value which is the line in the middle of the rectangle, (4) third quartile value which is the upper edge of the rectangle, and (5) maximum value which is the top line.
As it can be observed from Figures 1 and 2, the number of WCRT calls as well as recursion depths are lower under our optimal algorithm compared to Wang-Saksena algorithm. 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 steeper under Wang-Saksena algorithm compared to FPTSOPT algorithm. It is interesting to observe that, in general, the maximum number of WCRT calls and recursion depths under the FPTS-OPT algorithm are smaller than the 25% of the WCRT calls and recursion depths under Wang-Saksena algorithm. However, the results show that the FPTS-OPT algorithm does not completely outperform the Wang-Saksena algorithm. In those cases, Wang-Saksena algorithm can find the solution faster, e.g., for 5 and 7 tasks in Figures 1 and 2. 8.3
In the second set of experiments we compared schedulability of different priority and threshold assignments while varying experiment parameters. The results in Figures 3, 4 and 5 show that FPTS-OPT clearly outperforms both FPPS and FPTS with deadline monotonic priority assignment. Our proposed algorithm can improve the schedulability up to 15%.
It can be observed from Figures 3 and 4 that system schedulability decreases by both increasing the number of the tasks in the task set as well as increasing the task set utilization. Moreover, Figure 5 shows that increasing α, i.e., larger deadlines, the system schedulability is increased, which are not surprising results. 9.
In this paper we proposed a new optimal priority and preemption threshold assignment algorithm for FPTS.
The algorithm is based on backtracking, pruning the search space and a heuristic for traversing the search space. By generating a large number of synthetic task sets, we have compared our algorithm with the original algorithm by Wang and Saksena. The results show that our algorithm clearly outperforms the Wang-Saksena algorithm in general in terms of number of recursive calls and number of worst-case response time calculations, although special cases exist for which Wang-Saksena performs better than our algorithm.
Further, we have used our algorithm to evaluate the relevance of using a complex algorithm to determine the priority assignment compared to simple deadline monotonic assignment. With up to 15% observed increase in schedulability, we can conclude that it is worth having the option of optimal priority assignment for cases that cannot be scheduled by means of deadline monotonic priorities and optimal preemption thresholds. However, since the algorithm still functions in exponential time, it may be impractical to execute it on very large task sets.
The problem itself of whether it is possible to construct an efficient algorithm for FPTS OPTA still remains open. 10.