Leo Hatvani
Abstract
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.
- S. Baruah. The limited-preemption uniprocessor scheduling of sporadic task systems. In 17th Euromicro Conference on Real-Time Systems (ECRTS), pages 137--144, Jul. 2005. Google Scholar
Digital Library
- E. Bini and G. C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1--2):129--154, May 2005. Google ScholarDigital Library
- R. J. Bril, J. J. Lukkien, and W. F. J. Verhaegh. Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption revisited. In 19th Euromicro Conference on Real-Time Systems (ECRTS), pages 269--279, Jul. 2007. Google ScholarDigital Library
- A. Burns. Advances in real-time systems. chapter Preemptive Priority-based Scheduling: An Appropriate Engineering Approach, pages 225--248. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1995. Google ScholarDigital Library
- A. Burns and A. J. Wellings. Restricted tasking models. In 8th International Workshop on Real-Time Ada (IRTAW), pages 27--32, New York, NY, USA, 1997. ACM. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- L. Hatvani and R. J. Bril. Schedulability using native non-preemptive groups on an AUTOSAR/OSEK platform. In 20th Conference on Emerging Technologies Factory Automation (ETFA), pages 1--8, Sep. 2015.Google ScholarCross Ref
- 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, Sep. 2010.Google ScholarCross Ref
- S. Lee, C.-G. Lee, M. Lee, S. Min, and C. Kim. Limited preemptible scheduling to embrace cache memory in real-time systems. In F. Mueller and A. Bestavros, editors, Languages, Compilers, and Tools for Embedded Systems, volume 1474 of Lecture Notes in Computer Science, pages 51--64. Springer Berlin Heidelberg, 1998. Google ScholarDigital Library
- V. B. Lortz and K. G. Shin. Semaphore queue priority assignment for real-time multiprocessor synchronization. IEEE Transactions on Software Engineering, 21(10):834--844, Oct. 1995. Google ScholarDigital Library
- J. Regehr. Scheduling tasks with mixed preemption relations for robustness to timing faults. In 23rd IEEE Real-Time Systems Symposium (RTSS), pages 315--326, Dec. 2002. Google ScholarDigital Library
- M. Saksena and Y. Wang. Scalable real-time system design using preemption thresholds. In 21st IEEE Real-Time Systems Symposium (RTSS), pages 25--34, Nov. 2000. Google ScholarDigital Library
- Y. Wang and M. Saksena. Scheduling fixed-priority tasks with preemption threshold. In 6th International Conference on Real-Time Computing Systems and Applications (RTCSA), pages 328--335, Dec. 1999. Google ScholarDigital Library
- G. Yao, G. Buttazzo, and M. Bertogna. Bounding the maximum length of non-preemptive regions under fixed priority scheduling. In 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 351--360, Aug. 2009. Google ScholarDigital Library
Index Terms
- Optimal priority and threshold assignment for fixed-priority preemption threshold scheduling
Recommendations
Scheduling Fixed-Priority Tasks with Preemption Threshold
RTCSA '99: Proceedings of the Sixth International Conference on Real-Time Computing Systems and ApplicationsThe notion of preemption threshold is initiated in the industry to provide flexibility for real-time and embedded system designs. However, it also brings new contents to scheduling theory. Historically, the scheduling model are divided into two ...
Integration of Preemption Threshold and Quantum-Based Scheduling for Schedulability Enhancement of Fixed Priority Tasks
RTCSA '09: Proceedings of the 2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and ApplicationsFixed priority scheduling is an important real-time scheduling scheme widely used in practice. To improve the schedulability of fixed priority scheduling considerable effort has been made such as introduction of preemption threshold or deferred ...
Comments