Exact speedup factors and sub-optimality for non-preemptive scheduling
Tóm tắt
Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive earliest deadline first (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.
Tài liệu tham khảo
Abugchem F, Short M, Xu D (2015) A note on the suboptimality of nonpreemptive real-time scheduling. IEEE Embed Syst Lett 7(3):69–72. https://doi.org/10.1109/LES.2015.2426657
Altmeyer S, Davis RI, Maiza C (2011) Cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. In: Real-time systems symposium (RTSS), pp 261–271. https://doi.org/10.1109/RTSS.2011.31
Altmeyer S, Davis RI, Maiza C (2012) Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real-Time Syst 48(5):499–526. https://doi.org/10.1007/s11241-012-9152-2
Altmeyer S, Douma R, Lunniss W, Davis RI (2014) Evaluation of cache partitioning for hard real-time systems. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 15–26. https://doi.org/10.1109/ECRTS.2014.11
Altmeyer S, Douma R, Lunniss W, Davis RI (2016) On the effectiveness of cache partitioning in hard real-time systems. Real-Time Syst pp 1–46. https://doi.org/10.1007/s11241-015-9246-8
Audsley N (1991) Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Dept Computer Science, University of York, Technical Report YCS, p 164
Audsley NC (2001) On priority asignment in fixed priority scheduling. Inf Process Lett 79(1):39–44. https://doi.org/10.1016/S0020-0190(00)00165-4
Audsley N, Burns A, Richardson M, Tindell K, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8(5):284–292
AUTOSAR (2007) Autosar specification of operating system, v4.10. Tech. rep. http://www.autosar.org/
Baker TP (1991) Stack-based scheduling for realtime processes. Real-Time Syst 3(1):67–99. https://doi.org/10.1007/BF00365393
Baruah SK, Mok AK, Rosier LE (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proceedings real-time systems symposium (RTSS), pp 182–190. https://doi.org/10.1109/REAL.1990.128746
Bastoni A, Brandenburg BB, Anderson JH (2010) Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. In: Proceedings operating systems platforms for embedded real-time applications (OSPERT)
Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Syst 30(1–2):129–154. https://doi.org/10.1007/s11241-005-0507-9
Bril RJ, Lukkien JJ, Verhaegh WF (2009) Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption. Real-Time Syst 42(1–3):63–119. https://doi.org/10.1007/s11241-009-9071-z
Bui BD, Caccamo M, Sha L, Martinez J (2008) Impact of cache partitioning on multi-tasking real time embedded systems. In: proceedings Real-Time Computing Systems and Applications (RTCSA), pp 101–110, https://doi.org/10.1109/RTCSA.2008.42
Burns A, Gutierrez M, Aldea Rivas M, Gonzalez Harbour M (2015) A deadline-floor inheritance protocol for edf scheduled embedded real-time systems with resource sharing. IEEE Trans Comput 64(5):1241–1253. https://doi.org/10.1109/TC.2014.2322619
Buttazzo GC, Bertogna M, Yao G (2013) Limited preemptive scheduling for real-time systems. A survey. IEEE Trans Ind Inform 9(1):3–15. https://doi.org/10.1109/TII.2012.2188805
Chen JJ, von der Brggen G, Huang WH, Davis RI (2017) On the pitfalls of resource augmentation factors and utilization bounds in real-time scheduling. In: Proceedings Euromicro conference on real-time systems (ECRTS)
Davis RI (2017) On the evaluation of schedulability tests for real-time scheduling algorithms. In: Proceedings international workshop on analysis tools and methodologies for embedded and real-time systems (WATERS)
Davis RI, Bertogna M (2012) Optimal fixed priority scheduling with deferred pre-emption. In: Proceedings real-time systems symposium (RTSS), pp 39–50, https://doi.org/10.1109/RTSS.2012.57
Davis RI, Burns A, Bril RJ, Lukkien JJ (2007) Controller area network (can) schedulability analysis: refuted, revisited and revised. Real-Time Syst 35(3):239–272. https://doi.org/10.1007/s11241-007-9012-7
Davis RI, Rothvoss T, Baruah SK, Burns A (2009a) Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Real-Time Syst 43(3):211–258. https://doi.org/10.1007/s11241-009-9079-4
Davis RI, Rothvoss T, Baruah SK, Burns A (2009b) Quantifying the sub-optimality of uniprocessor fixed priority pre-emptive scheduling for sporadic tasksets with arbitrary deadlines. In: Proceedings real-time and network systems (RTNS), pp 23–31
Davis RI, George L, Courbin P (2010) Quantifying the sub-optimality of uniprocessor fixed priority non-pre-emptive scheduling. In: Proceedings real-time and network systems (RTNS), pp 1–10
Davis RI, Burns A, Baruah S, Rothvoss T, George L, Gettings O (2015a) Exact comparison of fixed priority and edf scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms. Real-Time Syst 51(5):566–601. https://doi.org/10.1007/s11241-015-9233-0
Davis RI, Gettings O, Thekkilakattil A, Dobrin R, Punnekkat S (2015b) What is the exact speedup factor for fixed priority pre-emptive versus fixed priority non-pre-emptive scheduling? In: Proceedings real-time scheduling open problems seminar (RTSOPS), pp 23–24
Davis RI, Thekkilakattil A, Gettings O, Dobrin R, Punnekkat S (2015c) Quantifying the exact sub-optimality of non-preemptive scheduling. In: Proceedings real-time systems symposium (RTSS), pp 96–106. https://doi.org/10.1109/RTSS.2015.17
Davis RI, Cucu-Grosjean L, Bertogna M, Burns A (2016) A review of priority assignment in real-time systems. J Syst Archit 65:64–82. https://doi.org/10.1016/j.sysarc.2016.04.002, http://www.sciencedirect.com/science/article/pii/S1383762116300200
Dertouzos ML (1974) Control robotics: the procedural control of physical processes. In: Proceedings IFIP congress, pp 807–813
George L, Rivierre N, Spuri M (1996) Preemptive and non-preemptive real-time uniprocessor scheduling. Research report, INRIA
Jeffay K, Stanat DF, Martel CU (1991) On non-preemptive scheduling of period and sporadic tasks. In: Proceedings real-time systems symposium (RTSS), pp 129–139. https://doi.org/10.1109/REAL.1991.160366
Joseph M, Pandya P (1986) Finding response times in a real-time system. Comput J 29(5):390–395. https://doi.org/10.1093/comjnl/29.5.390, http://comjnl.oxfordjournals.org/content/29/5/390.abstract, http://comjnl.oxfordjournals.org/content/29/5/390.full.pdf+html
Kalyanasundaram B, Pruhs K (2000) Speed is as powerful as clairvoyance. J ACM 47(4):617–643. https://doi.org/10.1145/347476.347479
Lehoczky JP (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: Proceedings real-time systems symposium (RTSS), pp 201–209. https://doi.org/10.1109/REAL.1990.128748
Lehoczky J, Sha L, Ding Y (1989) The rate monotonic scheduling algorithm: exact characterization and average case behavior. In: Proceedings real time systems symposium (RTSS), pp 166–171. https://doi.org/10.1109/REAL.1989.63567
Leung JYT, Whitehead J (1982) On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perform Eval 2(4):237–250. https://doi.org/10.1016/0166-5316(82)90024-4, http://www.sciencedirect.com/science/article/pii/0166531682900244
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46–61. https://doi.org/10.1145/321738.321743
Lunniss W, Davis RI, Maiza C, Altmeyer S (2013) Integrating cache related pre-emption delay analysis into edf scheduling. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 75–84. https://doi.org/10.1109/RTAS.2013.6531081
OSEK/VDX (2007) OSEK/VDX operating system specification, version 2.2.3. Tech. rep. http://www.irisa.fr/alf/downloads/puaut/TPNXT/images/os223.pdf
Ripoll I, Crespo A, Mok AK (1996) Improvement in feasibility testing for real-time tasks. Real-Time Syst 11(1):19–39. https://doi.org/10.1007/BF00365519
Short M (2010) The case for non-preemptive, deadline-driven scheduling in real-time embedded systems. In: Proceedings of the world congress on engineering (WCE), pp 399–404
Spuri M (1996) Analysis of deadline scheduled real-time systems. INRIA Research Report RR-2772 .https://hal.inria.fr/inria-00073920/document
Thekkilakattil A, Dobrin R, Punnekkat S (2013) Quantifying the sub-optimality of non-preemptive real-time scheduling. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 113–122. https://doi.org/10.1109/ECRTS.2013.22
Thekkilakattil A, Baruah S, Dobrin R, Punnekkat S (2014) The global limited preemptive earliest deadline first feasibility of sporadic real-time tasks. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 301–310. https://doi.org/10.1109/ECRTS.2014.21
Thekkilakattil A, Dobrin R, Punnekkat S (2015) The limited-preemptive feasibility of real-time tasks on uniprocessors. Real-Time Syst 51(3):247–273. https://doi.org/10.1007/s11241-015-9222-3
Tindell K, Burns A, Wellings AJ (1994) An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Syst 6(2):133–151. https://doi.org/10.1007/BF01088593
von der Bruggen G, Chen JJ, Huang WH (2015) Schedulability and optimization analysis for non-preemptive static priority scheduling based on task utilisation and blocking factors. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 90–101
von der Bruggen G, Chen JJ, Davis RI, Huang WH (2016) Exact speedup factors for linear-time schedulability tests for fixed-priority preemptive and non-preemptive scheduling. Inf Process Lett. https://doi.org/10.1016/j.ipl.2016.08.001, http://www.sciencedirect.com/science/article/pii/S0020019016301090