×

zbMATH — the first resource for mathematics

Implementation and evaluation of global and partitioned scheduling in a real-time OS. (English) Zbl 1291.68082
Summary: We provide an experimental comparison between Global-EDF and Partitioned-EDF, considering the run-time overhead of a real-time operating system (RTOS). Recent works have confirmed that OS implementation aspects, such as the choice of scheduling data structures and interrupt handling mechanisms, impact real-time schedulability as much as scheduling theoretic aspects. However, these studies used real-time patches applied into a general-purpose OS. By measuring the run-time overhead of an RTOS designed from scratch, we show how close the schedulability ratio of task sets is to the theoretical hard real-time schedulability tests. Moreover, we show how a well-designed object-oriented RTOS allows code reuse of scheduling components (e.g., thread, scheduling criteria, and schedulers) and easy real-time scheduling extensions. We compare our RTOS to a real-time patch for Linux in terms of the task set schedulability ratio of several generated task sets. In some cases, Global-EDF considering the overhead of the RTOS is superior to Partitioned-EDF considering the overhead of the patched Linux, which clearly shows how different OSs impact hard real-time schedulers.
MSC:
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68N20 Theory of compilers and interpreters
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abeni, L; Buttazzo, G, Resource reservation in dynamic real-time systems, Real-Time Syst, 27, 123-167, (2004) · Zbl 1078.68586
[2] 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 1-28 · Zbl 1243.68094
[3] AMD (2010) Amd64 architecture programmer’s manual, volume 2: System programming. Publication No. 24593. Revision: 3.17, June 2010
[4] Anderson, JH; Block, A, Early-release fair scheduling, 35-43, (2000)
[5] Anderson, JH; Block, A; Srinivasan, A, Quick-release fair scheduling, 130, (2003), Washington
[6] Anderson, JH; Bud, V; Devi, UC, An edf-based scheduling algorithm for multiprocessor soft real-time systems, 199-208, (2005), Washington
[7] Anderson, JH; Calandrino, JM; Devi, UC, Real-time scheduling on multicore platforms, 179-190, (2006)
[8] Aparicio, L; Segarra, J; Rodríguez, C; Viñals, V, Improving the wcet computation in the presence of a lockable instruction cache in multitasking real-time systems, J Syst Archit, 57, 695-706, (2011)
[9] Åsberg, M; Nolte, T; Kato, S; Rajkumar, R, Exsched: an external cpu scheduler framework for real-time systems, (2012)
[10] Azimi, R; Stumm, M; Wisniewski, R, Online performance analysis by statistical sampling of microprocessor performance counters, 101-110, (2005), New York
[11] Azimi, R; Tam, D; Soares, L; Stumm, M, Enhancing operating system support for multicore processors by using hardware performance monitoring, Oper Syst Rev, 43, 56-65, (2009)
[12] Baker, TP, Multiprocessor edf and deadline monotonic schedulability analysis, 120, (2003), Washington
[13] Baker, TP, An analysis of edf schedulability on a multiprocessor, IEEE Trans Parallel Distrib Syst, 16, 760-768, (2005)
[14] Baker TP (2005b) A comparison of global and partitioned edf schedulability tests for multiprocessors. Tech rep. In: International conference on real-time and network systems
[15] Baker, TP; Baruah, S, An analysis of global edf schedulability for arbitrary-deadline sporadic task systems, Real-Time Syst, 43, 3-24, (2009) · Zbl 1186.68056
[16] Baruah, S, Techniques for multiprocessor global schedulability analysis, 119-128, (2007), Washington
[17] Baruah, S; Bonifaci, V; Spaccamela, AM; Stiller, S, Implementation of a speedup-optimal global edf schedulability test, 259-268, (2009), Washington
[18] Baruah, SK; Cohen, NK; Plaxton, CG; Varvel, DA, Proportionate progress: a notion of fairness in resource allocation, Algorithmica, 15, 600-625, (1996) · Zbl 0848.68020
[19] Bastoni, A; Brandenburg, BB; Anderson, JH, Cache-related preemption and migration delays: empirical approximation and impact on schedulability, Brussels, Belgium
[20] Bastoni, A; Brandenburg, BB; Anderson, JH, An empirical comparison of global, partitioned, and clustered multiprocessor edf schedulers, 14-24, (2010), Washington
[21] Bastoni, A; Brandenburg, BB; Anderson, JH, Is semi-partitioned scheduling practical?, 125-135, (2011), Washington
[22] Bertogna, M; Baruah, S, Tests for global edf schedulability analysis, J Syst Archit, 57, 487-497, (2011)
[23] Bertogna, M; Cirinei, M, Response-time analysis for globally scheduled symmetric multiprocessor platforms, 149-160, (2007), Washington
[24] Bertogna, M; Cirinei, M; Lipari, G, Improved schedulability analysis of edf on multiprocessor platforms, 209-218, (2005), Washington
[25] Bletsas, K; Andersson, B, Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound, 447-456, (2009), Washington
[26] Brandenburg BB (2011) Scheduling and locking in multiprocessor real-time operating systems. PhD thesis, The University of North Carolina at Chapel Hill
[27] Brandenburg, BB; Anderson, JH, Feather-trace: a light-weight event tracing toolkit, 61-70, (2007)
[28] Brandenburg, BB; Anderson, JH, On the implementation of global real-time schedulers, 214-224, (2009), Washington
[29] Brandenburg, BB; Calandrino, JM; Anderson, JH, On the scalability of real-time scheduling algorithms on multicore platforms: a case study, 157-169, (2008), Washington
[30] Brandenburg, BB; Leontyev, H; Anderson, JH, An overview of interrupt accounting techniques for multiprocessor real-time systems, J Syst Archit, 57, 638-654, (2011)
[31] Burns, A; Davis, R; Wang, P; Zhang, F, Partitioned edf scheduling for multiprocessors using a C=D task splitting scheme, Real-Time Syst, 48, 3-33, (2012) · Zbl 1243.68101
[32] Calandrino, JM; Anderson, JH, Cache-aware real-time scheduling on multicore platforms: heuristics and a case study, 299-308, (2008), Washington
[33] Calandrino, JM; Leontyev, H; Block, A; Devi, UC; Anderson, JH, Litmusrt: a testbed for empirically comparing real-time multiprocessor schedulers, 111-126, (2006), Washington
[34] Carpenter, J; Funk, S; Holman, P; Srinivasan, A; Anderson, J; Baruah, S, A categorization of real-time multiprocessor scheduling problems and algorithms, (2004), Boca Raton
[35] Cho, H; Ravindran, B; Jensen, ED, An optimal real-time scheduling algorithm for multiprocessors, 101-110, (2006), New York
[36] Cullmann, C; Ferdinand, C; Gebhard, G; Grund, D; Maiza, C; Reineke, J; Triquet, B; Wegener, S; Wilhelm, R, Predictability considerations in the design of multi-core embedded systems, Ing Automob, 807, 36-42, (2010)
[37] Czarnecki K, Eisenecker UW (2000) Generative programming: methods, tools, and applications. ACM/Addison-Wesley, New York
[38] David, FM; Carlyle, JC; Campbell, RH, Context switch overheads for Linux on arm platforms, (2007), New York
[39] Dijkstra, EW; Genuys, F (ed.), Cooperating sequential processes, 43-112, (1968), New York
[40] Dongarra, J; London, K; Moore, S; Mucci, P; Terpstra, D; You, H; Zhou, M, Experiences and lessons learned with a portable interface to hardware performance counters, 289.2, (2003), Washington
[41] EPOS (2012) Epos website. URL http://epos.lisha.ufsc.br · Zbl 1083.68007
[42] Faggioli, D; Checconi, F; Trimarchi, M; Scordino, C, An EDF scheduling class for the Linux kernel, Dresden, Germany
[43] Fröhlich AA (2001) Application-oriented operating systems. GMD research series, vol 17. GMD—Forschungszentrum Informationstechnik, Sankt Augustin
[44] Fröhlich, AA, A comprehensive approach to power management in embedded systems, Int J Distrib Sens Netw, 2011, 19, (2011)
[45] Fröhlich, AA; Gracioli, G; Santos, JF, Periodic timers revisited: the real-time embedded system perspective, Comput Electr Eng, 37, 365-375, (2011)
[46] Garey MR, Johnson DS (1990) Computers and intractability; a guide to the theory of NP-completeness. Freeman, New York
[47] Goossens, J; Funk, S; Baruah, S, Priority-driven scheduling of periodic task systems on multiprocessors, Real-Time Syst, 25, 187-205, (2003) · Zbl 1081.68006
[48] Gracioli, G; Fröhlich, AA, An embedded operating system API for monitoring hardware events in multicore processors, Porto Alegre, Brazil
[49] Guan, N; Stigge, M; Yi, W; Yu, G, Cache-aware scheduling and analysis for multicores, 245-254, (2009), New York
[50] Hardy, D; Puaut, I; George, L (ed.); Chetto, M (ed.); Sjodin, M (ed.), Estimation of cache related migration delays for multi-core processors with shared instruction caches, Paris, France
[51] Hennessy JL, Patterson DA (2006) Computer architecture: a quantitative approach, 4th edn. Morgan Kaufmann, San Mateo
[52] Intel Corporation (2009) An introduction to the Intel quickpath interconnect. Document Number: 320412-001US, January 2009 · Zbl 1243.68101
[53] Intel Corporation (2011) Intel\^{®} 64 and IA-32 architectures software developer’s manual. 253668-037US
[54] Intel Corporation (2012) Intel\^{®} 64 and IA-32 architectures optimization reference manual. 248966-026
[55] Johnson D (1973) Near-optimal bin packing algorithms. PhD thesis
[56] Kato S (2012) AIRS website. URL http://www.ertl.jp/ shinpei/airs/
[57] Kato, S; Yamasaki, N, Real-time scheduling with task splitting on multiprocessors, 441-450, (2007), Washington
[58] Kato, S; Yamasaki, N, Portioned edf-based scheduling on multiprocessors, 139-148, (2008), New York
[59] Lelli, J; Faggioli, D; Cucinotta, T; Lipari, G, An experimental comparison of different real-time schedulers on multicore systems, J Syst Softw, 85, 2405-2416, (2012) · Zbl 1264.91011
[60] Leontyev, H; Anderson, JH, Generalized tardiness bounds for global multiprocessor scheduling, 413-422, (2007), Washington
[61] Levin, G; Funk, S; Sadowski, C; Pye, I; Brandt, S, Dp-fair: a simple model for understanding optimal multiprocessor scheduling, 3-13, (2010), Washington
[62] Li, C; Ding, C; Shen, K, Quantifying the cost of context switch, (2007), New York
[63] Lin, J; Lu, Q; Ding, X; Zhang, Z; Zhang, X; Sadayappan, P, Gaining insights into multicore cache partitioning: bridging the gap between simulation and real systems, 367-378, (2008), New York
[64] Liu, CL; Layland, JW, Scheduling algorithms for multiprogramming in a hard-real-time environment, J ACM, 20, 46-61, (1973) · Zbl 0265.68013
[65] Liu J (2000) Real-time systems, 1st edn. Prentice Hall PTR, Upper Saddle River
[66] Ludwich, MK; Fröhlich, AA, Abstracting hardware devices to embedded Java applications, Rio de Janeiro, Brazil
[67] Marcondes, H; Cancian, R; Stemmer, M; Fröhlich, AA, On the design of flexible real-time schedulers for embedded systems, 382-387, (2009), Washington
[68] Masrur, A; Chakraborty, S; Färber, G, Constant-time admission control for partitioned edf, 34-43, (2010), Washington
[69] May, J, Mpx: software for multiplexing hardware performance counters in multithreaded programs, 8, (2001)
[70] Mogul, JC; Borg, A, The effect of context switches on cache performance, Oper Syst Rev, 25, 75-84, (1991)
[71] Mohan, S; Caccamo, M; Sha, L; Pellizzoni, R; Arundale, G; Kegley, R; Niz, D, Using multicore architectures in cyber-physical systems, Michigan, USA
[72] Mollison, M; Anderson, JH, Utilization-controlled task consolidation for power optimization in multi-core real-time systems, No. 1, (2012)
[73] Mück, TR; Fröhlich, AA, Hyra: a software-defined radio architecture for wireless embedded systems, St. Maarten, The Netherlands Antilles
[74] Muralidhara, SP; Kandemir, M; Raghavan, P, Intra-application cache partitioning, 1-12, (2010)
[75] Negi, HS; Mitra, T; Roychoudhury, A, Accurate estimation of cache-related preemption delay, 201-206, (2003), New York
[76] Oikawa, S; Rajkumar, R, Portable rk: a portable resource kernel for guaranteed and enforced timing behavior, 111-120, (1999)
[77] Palopoli, L; Cucinotta, T; Marzario, L; Lipari, G, Aquosa—adaptive quality of service architecture, Softw Pract Exp, 39, 1-31, (2009) · Zbl 1083.68007
[78] Polpeta, FV; Fröhlich, AA, Hardware mediators: a portability artifact for component-based systems, 271-280, (2004)
[79] SHARCNET (2012) Sharcnet cluster website. URL https://www.sharcnet.ca
[80] Sprunt, B, Pentium 4 performance-monitoring features, IEEE MICRO, 22, 72-82, (2002)
[81] Srikantaiah, S; Kandemir, M; Irwin, MJ, Adaptive set pinning: managing shared caches in chip multiprocessors, 135-144, (2008), New York
[82] Srinivasan, A; Holman, P; Anderson, JH; Baruah, S, The case for fair multiprocessor scheduling, 114.1, (2003), Washington
[83] Stärner, J; Asplund, L, Measuring the cache interference cost in preemptive real-time systems, 146-154, (2004), New York
[84] Staschulat, J; Ernst, R, Scalable precision cache analysis for preemptive scheduling, 157-165, (2005), New York
[85] Suhendra, V; Mitra, T, Exploring locking & partitioning for predictable shared caches on multi-cores, 300-303, (2008), New York
[86] Tsafrir, D, The context-switch overhead inflicted by hardware interrupts (and the enigma of do-nothing loops), (2007), New York
[87] Vera, X; Lisper, B; Xue, J, Data cache locking for higher program predictability, ACM SIGMETRICS Perform Eval Rev, 31, 272-282, (2003)
[88] Wanner, LF; Fröhlich, AA, Operating system support for wireless sensor networks, J Comput Sci, 4, 272-281, (2008)
[89] Wilhelm, R; Engblom, J; Ermedahl, A; Holsti, N; Thesing, S; Whalley, D; Bernat, G; Ferdinand, C; Heckmann, R; Mitra, T; Mueller, F; Puaut, I; Puschner, P; Staschulat, J; Stenström, P, The worst-case execution-time problem overview of methods and survey of tools, ACM Trans Embed Comput Syst, 7, (2008)
[90] Yan, J; Zhang, W, Wcet analysis for multi-core processors with shared l2 instruction caches, 80-89, (2008), Washington
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.