A comparative study of rate monotonic schedulability tests
Tóm tắt
With the increased penetration of real-time systems into our surroundings, the selection of an efficient schedulability test under fixed priority system from a plethora of existing results, has become a matter of primary interest to real-time system designers. The need for a faster schedulability tests becomes more prominent when it applies to online systems, where processor time is a sacred resource and it is of central importance to assign processor to execute tasks instead of determining system schedulability. Under fixed priority nonpreemptive real-time systems, current schedulability tests (in exact form) can be divided into: response time based tests, and scheduling points tests. To the best of our knowledge, no comparative study of these test to date has ever been presented. The aim of this work is to assist the system designers in the process of selecting a suitable technique from the existing literature after knowing the pros and cons associated with these tests. We highlight the mechanism behind the feasibility tests, theoretically and experimentally. Our experimental results show that response time based tests are faster than scheduling points tests, which make the response time based tests an excellent choice for online systems.
Tài liệu tham khảo
Audsley NC, Burns, A, Richardson, M, Wellings, A (1993) Applying new scheduling theory to static priority preemptive scheduling. Softw Eng J 8(5):284–292
Bini E, Buttazzo GC (2004) Schedulability analysis of periodic fixed priority systems. IEEE Trans Comput 53(11):1462–1473
Bini E, Buttazzo GC, Buttazzo GM (2001) A hyperplanes bound for the rate monotonic algorithm. In: Proceedings of the 13th euromicro conference on real-time systems, pp 59–67
Bini E, Natale, MD, Buttazzo, G (2008) Sensitivity analysis for fixed-priority real-time systems. Real-Time Syst 39(1–3):5–30
Burns, A, Wellings, A (2001) Real-time systems and programming languages. Ada 95, Real-Time Java and real-time POSIX, 3rd edn. Addison Wesley Longman, Reading
Buttazzo GC (2005) Rate monotonic vs. edf: Judgment day. Real-Time Syst 29(1):5–26
Davis RI, Zabos A, Burns A (2008) Efficient exact schedulability tests for fixed priority real-time systems. IEEE Trans Comput 57:1261–1276
George L, Riverre N, Spuri M (1996) Preemptive and non-preemptive real-time uniprocessor scheduling. Technical report, 2966, INRIA
Liu JWS (2000) Real time systems, 1st edn. Prentice Hall, New York
Joseph M, Pandya P (1986) Finding response times in a real-time system. Comput J 29(5):390–395
Laplante PA (2004) Real-time systems design and analysis, 3rd edn. Wiley, Inc., New York
Lehoczky JP, Sha L, Ding Y (1989) The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In: Proceedings of the IEEE real-time system symposium, pp 166–171
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J ACM 20(1):40–61
Manabe Y, Aoyagi S (1998) A feasibility decision algorithm for rate monotonic and deadline monotonic scheduling. Real-Time Syst 14(2):171–181
Min-Allah N, Wang Y, Jian-Sheng X, Jiu-Xiang L (2007) Revisiting fixed priority techniques. In: Embedded and ubiquitous computing. LNCS, vol 4808. Springer, Berlin, pp 134–145
Min-Allah N, Ali I, Xing J, Wang Y (2010) Utilization bound for periodic task set with composite deadline. J Comput Electr Eng 36(6):1101–1109
Min-Allah N, Khan SU, Wang Y (2010) Optimal task execution times for periodic tasks using nonlinear constrained optimization. J Supercomput. doi:10.1007/s11227-010-0506-z
Orozco J, Cayssials R, Santos J, Santos R (1998) On the minimum number of priority levels required for the rate monotonic scheduling of real-time systems. In: Proceedings of the 10th euromicro workshop on real time system.
Sjodin M, Hansson H (1998) Improved response-time analysis calculations. In: Proceedings of the 19th IEEE real-time systems symposium, pp. 399–409