Real-Time Scheduling on Uni- and Multiprocessors based on Priority Promotions
- Real-Time Systems,
- Priority Promotion,
- Schedulability Analysis,
- Schedulability Condition
How to Cite
This paper addresses the problem of real-time scheduling of a set of sporadic tasks on uni- and multiprocessor platform based on priority promotion. A new preemptive scheduling algorithm, called Fixed-Priority with Priority Promotion (FPP), is proposed. In FPP scheduling, tasks are executed similar to traditional fixed-priority (FP) scheduling but the priority of some tasks are promoted at fixed time interval (called, promotion point) relative to the release time of each job. A policy called Increase Priority at Deadline Difference (IPDD) to compute the promotion points and promoted priorities for each task is proposed. FPP scheduling prioritizes jobs according to Earliest-Deadline-First (EDF) priority when all tasks' priorities follow IPDD policy.
It is known that managing (i.e., inserting and removing) jobs in the ready queue of traditional EDF scheduler is more complex than that of FP scheduler. To avoid such problem in FPP scheduling, a simple data structure and efficient operations to manage jobs in the ready queue are proposed. In addition, techniques for implementing priority promotions with and without the use of a hardware timer are proposed.
Finally, an effective scheme to reduce the average number of priority promotions is proposed: if a task set is not schedulable using traditional FP scheduling, then promotion points are assigned only to those tasks that need them to meet the deadlines; otherwise, tasks are assigned traditional fixed priorities without any priority promotion. Empirical investigation shows the effectiveness of the proposed scheme in reducing overhead on uniprocessor and in accepting larger number of task sets in comparison to that of using state-of-the-art global schedulability tests for multiprocessors.
- Neil C. Audsley. On priority assignment in fixed priority scheduling. Inf. Process. Lett., 79(1):39– 44, 2001. doi:10.1016/S0020-0190(00)00165-4.
- Neil C. Audsley, Alan Burns, Mike M. Richardson, Ken Tindell, and Andy J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284–292, 1993. URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=238595.
- Sanjoy K. Baruah and Theodore P. Baker. Global EDF schedulability analysis of arbitrary sporadic task systems. In 20th Euromicro Conference on Real-Time Systems, ECRTS 2008, 2-4 July 2008, Prague, Czech Republic, Proceedings, pages 3– 12. IEEE Computer Society, 2008. doi:10.1109/ ECRTS.2008.27.
- Sanjoy K. Baruah, Aloysius K. Mok, and Louis E. Rosier. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Proceedings of the Real-Time Systems Symposium – 1990, Lake Buena Vista, Florida, USA, December 1990, pages 182–190. IEEE Computer Society, 1990. doi:10. 1109/REAL.1990.128746.
- Sanjoy K. Baruah, Louis E. Rosier, and Rodney R. Howell. Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Systems, 2(4):301– 324, 1990. doi:10.1007/BF01995675.
- Marko Bertogna and Sanjoy K. Baruah. Tests for global EDF schedulability analysis. Journal of Systems Architecture – Embedded Systems Design, 57(5):487–497, 2011. doi:10.1016/j.sysarc.2010. 09.004.
- Björn B. Brandenburg and James H. Anderson. On the implementation of global real-time schedulers. In Theodore P. Baker, editor, Proceedings of the 30th IEEE Real-Time Systems Symposium, RTSS 2009, Washington, DC, USA, 1-4 December 2009, pages 214–224. IEEE Computer Society, 2009. doi:10.1109/RTSS.2009.23.
- Björn B. Brandenburg, John M. Calandrino, and James H. Anderson. On the scalability of real-time scheduling algorithms on multicore platforms: A case study. In Proceedings of the 29th IEEE Real-Time Systems Symposium, RTSS 2008, Barcelona, Spain, 30 November to 3 December 2008, pages 157–169. IEEE Computer Society, 2008. doi:10. 1109/RTSS.2008.23.
- Alan Burns. Dual Priority Scheduling: Is the Processor Utilisation bound 100%? In Proc. of the 1st International Real-Time Scheduling Open Problems Seminar (RTSOPS), in conjunction with the ECRTS, 2010. URL: https://www.cs.york.ac.uk/ftpdir/papers/rtspapers/R:Burns:2010b.pdf.
- Alan Burns, Marina Gutierrez, Mario Aldea Rivas, and Michael González Harbour. A deadlinefloor inheritance protocol for EDF scheduled embedded real-time systems with resource sharing. IEEE Trans. Computers, 64(5):1241–1253, 2015. doi:10.1109/TC.2014.2322619.
- Alan Burns and Andrew J. Wellings. Dual priority assignment: A practical method for increasing processor utilisation. In Fifth Euromicro Workshop on Real-Time Systems, RTS 1993, Oulu, Finland, June 22-24, 1993. Proceedings., pages 48–53. IEEE, 1993. doi:10.1109/EMWRT.1993.639052. Giorgio C. Buttazzo. Rate monotonic vs. EDF: judgment day. Real-Time Systems, 29(1):5–26, 2005. doi:10.1023/B:TIME.0000048932.30002.d9.
- Robert I. Davis. Dual priority scheduling: A means of providing flexibility in hard real-time systems. Technical Report YCS 230, Dept of Computer Science, University of York, UK, 1994. URL: https://www.cs.york.ac.uk/ftpdir/reports/94/YCS/230/YCS-94-230.ps.Z.
- Robert I. Davis and Alan Burns. Improved priority assignment for global fixed priority preemptive scheduling in multiprocessor real-time systems. Real-Time Systems, 47(1):1–40, 2011. doi: 10.1007/s11241-010-9106-5.
- Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35, 2011. doi: 10.1145/1978802.1978814.
- Robert I. Davis and Andy J. Wellings. Dual priority scheduling. In 16th IEEE Real-Time Systems Symposium, Palazzo dei Congressi, Via Matteotti, 1, Pisa, Italy, December 4-7, 1995, Proceedings, pages 100–109. IEEE Computer Society, 1995. doi:10.1109/REAL.1995.495200.
- Michael L. Dertouzos. Control robotics: The procedural control of physical processes. In IFIP Congress, pages 807–813, 1974.
- Michael González Harbour, Mark H. Klein, and John P. Lehoczky. Fixed priority scheduling periodic tasks with varying execution priority. In Proceedings of the Real-Time Systems Symposium – 1991, San Antonio, Texas, USA, December 1991, pages 116–128. IEEE Computer Society, 1991. doi: 10.1109/REAL.1991.160365.
- Mike Holenderski, Wim Cools, Reinder J. Bril, and Johan J. Lukkien. Multiplexing real-time timed events. In Proceedings of 12th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2009, September 22-25, 2008, Palma de Mallorca, Spain, pages 1–4. IEEE, 2009. doi:10.1109/ETFA.2009.5347183.
- John P. Lehoczky. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings of the Real-Time Systems Symposium – 1990, Lake Buena Vista, Florida, USA, December 1990, pages 201–209. IEEE Computer Society, 1990. doi:10.1109/REAL.1990.128748.
- Charles E. Leiserson, Harald Prokop, and Keith H. Randall. Using de bruijn sequences to index a 1 in a computer word. MIT Technical Report, 1998. URL: http://supertech.csail.mit.edu/papers/debruijn.pdf.
- Joseph Y.-T. Leung and Jennifer Whitehead. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perform. Eval., 2(4):237–250, 1982. doi:10.1016/0166-5316(82)90024-4.
- C. L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM, 20(1):46–61, 1973. doi:10.1145/321738.321743.
- Risat Mahmud Pathan. Unifying fixed- and dynamic-priority scheduling based on priority promotion and an improved ready queue management technique. In 21st IEEE Real-Time and Embedded Technology and Applications Symposium, Seattle, WA, USA, April 13-16, 2015, pages 209–220. IEEE Computer Society, 2015. doi:10.1109/RTAS.2015.7108444.
- Risat Mahmud Pathan and Jan Jonsson. Improved schedulability tests for global fixed-priority scheduling. In Karl-Erik Årzén, editor, 23rd Euromicro Conference on Real-Time Systems, ECRTS 2011, Porto, Portugal, 5-8 July, 2011, pages 136–147. IEEE Computer Society, 2011. doi: 10.1109/ECRTS.2011.21.
- Risat Mahmud Pathan and Jan Jonsson. Interference-aware fixed-priority schedulability analysis on multiprocessors. Real-Time Systems, 50(4):411–455, 2014. doi:10.1007/s11241-013-9198-9.
- Michael Short. Improved task management techniques for enforcing EDF scheduling on recurring tasks. In Marco Caccamo, editor, 16th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2010, Stockholm, Sweden, April 12-15, 2010, pages 56–65. IEEE Computer Society, 2010. doi:10.1109/RTAS.2010.22.
- Youcheng Sun, Giuseppe Lipari, Nan Guan, and Wang Yi. Improving the response time analysis of global fixed-priority multiprocessor scheduling. In 2014 IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications, Chongqing, China, August 20-22, 2014, pages 1–9. IEEE Computer Society, 2014. doi:10.1109/RTCSA.2014.6910543.
- George Varghese and Anthony Lauck. Hashed and hierarchical timing wheels: Data structures for the efficient implementation of a timer facility. In Les Belady, editor, Proceedings of the Eleventh ACM Symposium on Operating System Principles, SOSP 1987, Stouffer Austin Hotel, Austin, Texas, USA, November 8-11, 1987, pages 25–38. ACM, 1987. doi:10.1145/41457.37504.
- Fengxiang Zhang and Alan Burns. Schedulability analysis for real-time systems with EDF scheduling. IEEE Trans. Computers, 58(9):1250–1258, 2009. doi:10.1109/TC.2009.58.