Fixed-priority preemption-threshold scheduling (FPTS) is a generalization of fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS). Since FPPS and FPNS are incomparable in terms of potential schedulability, FPTS has the advantage that it can schedule any task set schedulable by FPPS or FPNS and some that are not schedulable by either. FPTS is based on the idea that each task is assigned a priority and a preemption threshold. While tasks are admitted into the system according to their priorities, they can only be preempted by tasks that have priority higher than the preemption threshold.
This paper presents a new optimal priority and preemption threshold assignment (OPTA) algorithm for FPTS which in general outperforms the existing algorithms in terms of the size of the explored state-space and the total number of worst case response time calculations performed. The algorithm is based on back-tracking, i.e. it traverses the space of potential priorities and preemption thresholds, while pruning infeasible paths, and returns the first assignment deemed schedulable.
We present the evaluation results where we compare the complexity of the new algorithm with the existing one. We show that the new algorithm significantly reduces the time needed to find a solution. Through a comparative evaluation, we show the improvements that can be achieved in terms of schedulability ratio by our OPTA compared to a deadline monotonic priority assignment.
•Computer systems organization → Embedded software; •Software and its engineering → Real-time schedulability;
Scheduling theory has been widely studied over the years to provide effective scheduling solutions for real-time embedded systems. Scheduling algorithms can be divided into fixed-priority and dynamic-priority, where the priorities of tasks stay the same throughout the execution of the system for the former ones and change depending on some parameter for the latter ones. Even though it can be said that they lack * This work is supported by the ARTEMIS Joint Undertaking project EMC 2 (grant agreement 621429). EWiLi'16, October 6th, 2016, Pittsburgh, USA.
Copyright retained by the authors.
the flexibility of dynamic-priority algorithms, fixed-priority scheduling algorithms are a de facto standard in industry due to their lower implementation and execution overhead compared to dynamic-priority algorithms.
Another way of classifying scheduling algorithms is whether they allow a task that is currently executing to be preempted or not, these are preemptive and non-preemptive scheduling algorithms. Recently, new scheduling approaches have been proposed as an alternative to the extremes of fully preemptive and non-preemptive scheduling. One such scheduling approach is called fixed-priority preemption threshold scheduling (FPTS) [12,11] where each task τi is annotated by a preemption threshold θi besides its priority πi. Preemption threshold for a task specifies which tasks can preempt it and is always greater than or equal to the priority of that task. If a task's priority is higher than the preemption threshold of the currently executing task, it is allowed to preempt the executing task. This means that as soon as the task starts executing, its effective priority is increased to its preemption threshold.
There are two special cases of the FPTS scheduling algorithm. First, when the preemption threshold of every task is equal to the task's priority, FPTS becomes equivalent to the FPPS scheduling algorithm. Second, when all preemption thresholds are equal to the highest priority in the system, FPTS becomes equivalent to FPNS, as no task can preempt any other task.
FPTS improves the schedulability compared to both approaches by leveraging the preemption of higher priority tasks under FPPS and the blocking incurred by non-preemptive execution of lower priority tasks under FPNS. An optimal priority and threshold assignment (OPTA) algorithm for FPTS 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 original OPTA for FPTS has been introduced by Wang and Saksena [12]. However, the high computation time required to find a feasible solution using this algorithm, if such exists, warrants research into more efficient approaches [6]. In this paper, we introduce a new OPTA algorithm for FPTS which effectively can decrease the computation time of finding a feasible solution. Our algorithm is based on (i) backtracking, (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 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 π DM i are assigned based on deadline monotonic priority assignment, i.e. the task with the smallest deadline has the highest priority. At utilization U T I ≈ 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 [12]. Under this approach, besides a regular priority, each task is assigned a preemption threshold up to where it can prevent preemptions. The preemption is allowed only when the priority of a ready task is higher than the threshold of the running task.
Deferred Preemptions Scheduling (DPS) has first been introduced by Baruah [1] under Earliest Deadline First (EDF). Under this approach, for each task the longest interval that can be executed non-preemptively is specified. Two types of implementation exist for this approach based on how the non-preemptive regions are implemented: Floating model and Activation-triggered model implementation. Under the former model, non-preemptive regions are specified in the code by inserting specific primitives that disable and enable preemption. Under the later model, non-preemptive regions are specified by setting a timer at the arrival of a higher priority task which lasts for the specified non-preemptive interval.
Fixed Preemption Points (FPP) has been proposed by Burns [4]. Under FPP, preemption is allowed only at predefined points during a task's execution. As a results, a task is divided into a number of non-preemptive execution chunks.
The preemption of a higher priority task is postponed until the next preemption point of a running task. This approach is also referred to as cooperative scheduling.
Worst-case response time analysis for FPTS as well as an optimal priority and preemption threshold assignment algorithm was first presented in [12]. Later, in [10], it has been shown that the analysis in [12] was optimistic, and a revised analysis was presented.
Worst-case response time analysis of periodic real-time tasks under fixed-priority scheduling with deferred preemption (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 and optimistic where they have revised the analysis.
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).
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.
While worst-case response time analysis for FPTS policy has been published several times [12,10], in this paper we employ the exact analysis presented by Keskin et al. [7] with the added assumption that there is no jitter.
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
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 [3] and is given as the smallest positive Li that satisfies (2).
The maximum number li of jobs of τi that can be executed in this level-i active period is given by (3).
Given the knowledge of how many jobs need to be analyzed, we can compute their worst-case start time S ik for 0 ≤ k < li as the smallest positive value S ik that satisfies (4).
(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 F ik . It can be found as the smallest positive F ik that satisfies (5).
(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.
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 [9] and later exploited by Yao et al. [13]. The same concept is utilized in this work with the specialization that the entire task is considered either preemptive or non-preemptive depending on the relevant priorities and thresholds.
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.
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 [12] (including the correction discussed in Section 7), the algorithm proposed in this paper is based on (i) backtracking, (ii) pruning the search space, and (iii) a heuristic for traversing the search space. However, unlike the Wang-Saksena OPTA, our algorithm (1) assigns priorities in a descending order, i.e. from the highest to the lowest priority, rather than in ascending order, (2) determines preemption thresholds of tasks while the priority ordering is determined, rather than determining preemption thresholds after the priority ordering is completed and (3) uses the notion of blocking tolerance rather than lateness in the heuristic.
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). 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.
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 .
A prerequisite for a comparative evaluation of our algorithm and the algorithm presented by Wang and Saksena [12] was to implement both algorithms. During the implementation of the algorithm of Wang and Saksena, we noticed that it does not explore the entire state-space.
After inspecting the pseudo-code in Figure 3 of [12], we have determined that the most probable original intention for the algorithm was to continue the state space exploration if an unschedulable configuration was found. A simple removal of line 4 from the pseudo-code results in an algorithm that completely explores the state-space of the potential priority orderings. Further, this closely reflects the approach use in the same algorithm on lines 22-24.
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 [12]. Since both algorithms execute in exponential time, we chose two different measures to compare them, the number of recursive calls to the main function, and the number of worst-case response time (WCRT) computation calls. While Wang-Saksena algorithm uses WCRT 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 schedulability ratios of task sets under FPTS with deadline monotonic priority assignments and optimal preemption thresholds and under FPTS with our OPTA.
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 scaling factor. At α = 1, the deadlines are equal to periods, 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.
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 FPTS-OPT 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.
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.
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 opti- mal 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.