Optimal FP Scheduling with Deferred Pre-emption
Robert Ian Davis, Marko Bertogna · 2013
A common misconception about fixed priority scheduling of sporadic tasks on a single processor is that fully pre-emptive scheduling is the best approach in terms of schedulability. Fixed priority non-pre-emptive scheduling (FPNS) and fixed priority pre-emptive scheduling (FPPS) are however incomparable; there are tasksets that are schedulable under FPNS that are not schedulable under FPPS and vice-versa. The term fixed priority scheduling with deferred pre-emption (FPDS) has been used to refer to a variety of techniques by which pre-emptions may be deferred for some period of time after a higher priority task becomes ready [4]. In this paper, we assume a form of FPDS where each task has a final non-pre-emptive region (FNR). If this region is of the minimum possible length1 for all tasks, then we have FPPS, whereas if the FNR constitutes all of the task’s execution time then we have FPNS; thus FPDS is a superset of, and dominates both FPPS and FPNS. With FPDS, there are two key parameters that affect taskset schedulability: the priority assigned to each task, and the length of each task’s FNR. The length of the FNR affects both the schedulability of the task itself, and the schedulability of tasks with higher priorities. This is a trade-off as increasing the length of the FNR can improve schedulability for the task itself by reducing the number of times it can be pre-empted, but potentially increases the blocking experienced by higher priority tasks reducing their schedulability. Here, we present an optimal algorithm for FPDS. This Final Non-pre-emptive Region and Priority Assignment (FNR-PA) algorithm is optimal in the sense that it is guaranteed to find a combination of priority assignment and FNR lengths that result in a schedulable system under FPDS whenever such a schedulable combination of these parameters exists. Full details are given in [4].