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