×

Exact comparison of fixed priority and EDF scheduling based on speedup factors for both pre-emptive and non-pre-emptive paradigms. (English) Zbl 1337.68047

Summary: This paper investigates the relative effectiveness of fixed priority (FP) scheduling in a uniprocessor system compared to earliest deadline first (EDF) scheduling. The quantitative metric used in this comparison is the processor speedup factor, defined as the factor by which processor speed needs to increase to ensure that any task set that is schedulable according to EDF can be scheduled using fixed priorities. In the pre-emptive case, exact speedup factors are known for sporadic task sets with implicit or constrained deadlines. In this paper, we derive exact speedup factors for both pre-emptive and non-pre-emptive fixed priority scheduling of arbitrary deadline sporadic task sets. We also show that the exact speedup factor for the pre-emptive case holds when tasks share resources according to the stack resource policy/deadline floor protocol.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Audsley NC (1991) Optimal priority assignment and feasibility of static priority tasks with arbitrary start times, Technical Report YCS 164. Department of Computer Science, University of York, UK · Zbl 1395.90151
[2] Audsley NC (2001) On priority assignment in fixed priority scheduling. Inf Process Lett 79(1):39-44 · Zbl 0998.68018 · doi:10.1016/S0020-0190(00)00165-4
[3] Audsley NC, Burns A, Richardson M, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8(5):284-292 · doi:10.1049/sej.1993.0034
[4] Baker TP (1991) Stack-based scheduling of real-time processes. Real-Time Syst J 3(1):67-100 · Zbl 0265.68013
[5] Baruah SK (2006) Resource sharing in edf-scheduled systems: a closer look. In:Proceedings real-time systems symposium (RTSS), pp 379-387 · Zbl 0496.90046
[6] Baruah SK, Mok AK, Rosier LE (1990a) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proceedings real-time systems symposium (RTSS), pp 182-190
[7] Baruah SK, Rosier LE, Howell RR (1990b) Algorithms and complexity concerning the preemptive scheduling of periodic real-time tasks on one processor. Real-Time Syst 2(4):301-324 · doi:10.1007/BF01995675
[8] Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Syst 30(1-2):129-154 · Zbl 1083.68008 · doi:10.1007/s11241-005-0507-9
[9] Bletsas, K.; Audsley, N., No article title, Optimal priority assignment in the presence of blocking information processing letters, 99, 83-86 (2006) · Zbl 1184.68119 · doi:10.1016/j.ipl.2006.03.002
[10] Bril RJ, Lukkien JJ, Verhaegh WF (2009) Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred pre-emption. Real-Time Syst 42(1-3):63-119 · Zbl 1185.68106 · doi:10.1007/s11241-009-9071-z
[11] 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. Comput, IEEE Trans on 64(5):1241-1253. doi:10.1109/TC.2014.2322619 · Zbl 1360.68259 · doi:10.1109/TC.2014.2322619
[12] Davis RI, George L, Courbin P (2010) Quantifying the sub-optimality of uniprocessor fixed priority non-pre-emptive scheduling. In: Proceedings of real-time and network systems (RTNS), pp 1-10 · Zbl 0998.68018
[13] Davis RI, Rothvoß T, Baruah SK, Burns A (2009a) Quantifying the sub-optimality of uniprocessor fixed priority pre-emptive scheduling for sporadic task sets with arbitrary deadlines. In: Proceedings of real-time and network systems (RTNS), pp 23-31 · Zbl 1185.68106
[14] Davis RI, Rothvoß T, Baruah SK, Burns A (2009b) Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Real-Time Syst 43(3):211-258 · Zbl 1184.68121 · doi:10.1007/s11241-009-9079-4
[15] Dertouzos ML (1974) Control robotics: the procedural control of physical processes. In: Proceedings of the IFIP congress, pp 807-813
[16] George L, Hermant J (2009) A norm approach for the partitioned EDF scheduling of sporadic task systems. In: Proceeding euromicro conference on real-time systems (ECRTS) · Zbl 1083.68008
[17] George L, Muhlethaler P, Rivierre N (1995) Optimality and non-preemptive real-time scheduling revisited. Rapport de Recherche RR-2516. INRIA, Le Chesnay Cedex, France
[18] George L, Rivierre N, Spuri M (1996) Preemptive and non-preemptive real-time uniprocessor scheduling. INRIA Research Report, No. 2966
[19] Howell RR, Venkatrao MK (1995) On non-preemptive scheduling of recurring tasks using inserted idle time. Inf Comput J 117(1) · Zbl 0828.68028
[20] Jeffay K, Stanat DF, Martel CU (1991) On non-preemptive scheduling of periodic and sporadic tasks. In: Proceedings real-time systems symposium (RTSS), pp 129-139
[21] Joseph M, Pandya PK (1986) Finding response times in a real-time system. Comput J 29(5):390-395 · doi:10.1093/comjnl/29.5.390
[22] Kalyanasundaram B, Pruhs K (1995) Speed is as powerful as clairvoyance. In: Proceedings of symposium on foundations of computer science, pp 214-221 · Zbl 0938.68545
[23] Kim N (1980) Prevention of task overruns in real-time non-preemptive multiprogramming systems. In: Proceedings of Perf., Assoc. Comp. Mach., pp 267-276
[24] Lehoczky J (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: Proceedings real-time systems symposium (RTSS), pp 201-209
[25] Lehoczky JP, Sha L, Ding Y (1989) The rate monotonic scheduling algorithm: exact characterization and average case behaviour. In: Proceedings real-time systems symposium (RTSS), pp 166-171
[26] Leung JY-T, Whitehead J (1982) On the complexity of fixed-priority scheduling of periodic real-time tasks. Perform Eval 2(4):237-250 · Zbl 0496.90046 · doi:10.1016/0166-5316(82)90024-4
[27] Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46-61 · Zbl 0265.68013 · doi:10.1145/321738.321743
[28] Mok AK (1983) Fundamental design problems of distributed systems for the hard-real-time environment, Ph.D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge
[29] Sha L, Rajkumar R, Lehoczky J (1990) Priority inheritance protocols: an approach to real-time synchronisation. IEEE Trans Comput 39(9):1175-1185 · Zbl 1395.90151 · doi:10.1109/12.57058
[30] Spuri M (1996) Analysis of deadline scheduled real-time systems. INRIA Technical, Report No 2772
[31] Thekkilakattil A, Dobrin R, Punnekkat S (2013) Quantifying the sub-optimality of non-preemptive real-time scheduling. In: Proceedings of euromicro conference on real-time systems (ECRTS), pp 113, 122 · Zbl 1330.68043
[32] Tindell KW, Burns A, Wellings AJ (1994) An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Syst 6(2):133-151 · doi:10.1007/BF01088593
[33] von der Brüggen G, Chen JJ, Huang W-H (2015) Schedulability and optimization analysis for non-preemptive static priority scheduling based on task utilization and blocking factors. In: Proceedings of euromicro conference on real-time systems (ECRTS), pp 90-101
[34] Zhang F, Burns A (2009) Schedulability analysis for real-time systems with edf scheduling. Comput, IEEE Trans on 58(9):1250-1258. doi:10.1109/TC.2009.58 · Zbl 1368.68169 · doi:10.1109/TC.2009.58
[35] Zhang F, Burns A (2011) Schedulability analysis of EDF scheduled embedded real-time systems with resource sharing. ACM Trans Embed Comput Syst 9, 4, Article 39
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.