nach oben

Real-Time Systems

Erschienen in:

01.07.2014

Interference-aware fixed-priority schedulability analysis on multiprocessors

verfasst von: Risat Mahmud Pathan, Jan Jonsson

Erschienen in: Real-Time Systems | Ausgabe 4/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents new schedulability tests for preemptive global fixed-priority (FP) scheduling of sporadic tasks on identical multiprocessor platform. One of the main challenges in deriving a schedulability test for global FP scheduling is identifying the worst-case runtime behavior, i.e., the critical instant, at which the release of a job suffers the maximum interference from the jobs of its higher priority tasks. Unfortunately, the critical instant is not yet known for sporadic tasks under global FP scheduling. To overcome this limitation, pessimism is introduced during the schedulability analysis to safely approximate the worst-case. The endeavor in this paper is to reduce such pessimism by proposing three new schedulability tests for global FP scheduling.

Another challenge for global FP scheduling is the problem of assigning the fixed priorities to the tasks because no efficient method to find the optimal priority ordering in such case is currently known. Each of the schedulability tests proposed in this paper can be used to determine the priority of each task based on Audsley’s approach. It is shown that the proposed tests not only theoretically dominate but also empirically perform better than the state-of-the-art schedulability test for global FP scheduling of sporadic tasks.

Nächster Artikel An optimal boundary fair scheduling

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Finding an optimal task assignment to processors is known as an NP-hard problem (Garey and Johnson 1979).

Recently, researchers in the real-time systems community have addressed scheduling tasks with different “criticality” or “importance”—so called, Mixed Criticality (MC) systems—inspired by an observation by Vestal (2007): the higher level of assurance or confidence needed in estimating the WCET of a piece of code, the larger the WCET tends to be in practice. Different upper bounds on the WCET for a piece of code can be considered according to the level of assurance needed for designing a MC system. Global FP scheduling of MC systems assuming different WCET of the same task has been addressed elsewhere (Pathan 2012).

The name “RTA-LC” test (response-time analysis with limited carry-in tasks) is introduced by Davis and Burns (2011a).

The H-ODA-LC test was proposed in our ECRTS-11 paper (Pathan and Jonsson 2011). Both IA-DA and IA-RT tests are new contributions in this paper.

The response-time based test that will be used for IA-RT test is not the OPA-incompatible RTA-LC test; rather an OPA-compatible response-time-based test proposed in Davis and Burns (2010) is used.

In this paper, it is assumed without loss of generality that a task having priority level 1 (n) has the lowest (highest) fixed priority. This simplifies the mathematical reasoning in proving the correctness and domination of the IA-DA test.

Andersson B (2008) Global static-priority preemptive multiprocessor scheduling with utilization bound 38 %. In: Proc of OPODIS, pp 73–88

Andersson B, Baruah S, Jonsson J (2001) Static-priority scheduling on multiprocessors. In: Proc of RTSS, pp 193–202

Audsley NC (2001) On priority assignment in fixed priority scheduling. Inf Process Lett 79(1):39–44 CrossRefMATH

Baker TP (2006) An analysis of fixed-priority schedulability on a multiprocessor. Real-Time Syst 32(1–2):49–71 CrossRefMATH

Baruah S (2007) Techniques for multiprocessor global schedulability analysis. In: Proc of RTSS, pp 119–128

Baruah S, Goossens J (2003) Rate-monotonic scheduling on uniform multiprocessors. IEEE Trans Comput 52(7):966–970 CrossRef

Bastoni A, Brandenburg BB, Anderson JH (2010) An empirical comparison of global, partitioned, and clustered multiprocessor EDF schedulers. In: Proc of RTSS, pp 14–24

Bertogna M, Cirinei M (2007) Response-time analysis for globally scheduled symmetric multiprocessor platforms. In: Proc of RTSS, pp 149–160

Bertogna M, Cirinei M, Lipari G (2005) New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors. In: Proc of OPODIS, pp 306–321

Bertogna M, Cirinei M, Lipari G (2009) Schedulability analysis of global scheduling algorithms on multiprocessor platforms. IEEE Trans Parallel Distrib Syst 20(4):553–566 CrossRef

Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Syst 30:129–154 CrossRefMATH

Borkar S, Chien AA (2011) The future of microprocessors. Commun ACM 54(5):67–77 CrossRef

Brandenburg BB, Calandrino JM, Anderson JH (2008) On the scalability of real-time scheduling algorithms on multicore platforms: a case study. In: Proc of RTSS, pp 157–169

Carpenter J, Funk S, Holman P, Anderson JH, Baruah S (2004) A categorization of real-time multiprocessor scheduling problems and algorithms. In: Handbook on scheduling algorithms, methods, and models

Chattopadhyay S, Kee CL, Roychoudhury A, Kelter T, Marwedel P, Falk H (2012) A unified WCET analysis framework for multi-core platforms. In: Proc of the RTAS, pp 99–108

Davis RI, Burns A (2007) Robust priority assignment for fixed priority real-time systems. In: Proc of RTSS, pp 3–14

Davis R, Burns A (2009) Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In: Proc of RTSS, pp 398–409

Davis RI, Burns A (2010) On optimal priority assignment for response time analysis of global fixed priority pre-emptive scheduling in multiprocessor hard real-time systems. Tech report YCS-2010-451, University of York, Computer Science Dept, April

Davis R, Burns A (2011a) Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real-Time Syst 47:1–40 CrossRefMATH

Davis R, Burns A (2011b) A survey of hard real-time scheduling for multiprocessor systems. ACM Comput Surv 43(4):35:1–35:44 CrossRef

Dhall SK, Liu CL (1978) On a real-time scheduling problem. Oper Res 26(1):127–140 CrossRefMATHMathSciNet

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman & Co, New York. ISBN 0716710447 MATH

Goossens J, Funk S, Baruah S (2003) Priority-driven scheduling of periodic task systems on multiprocessors. Real-Time Syst 25(2–3):187–205 CrossRefMATH

Guan N, Stigge M, Yi W, Yu G (2009) New response time bounds for fixed priority multiprocessor scheduling. In: Proc of RTSS, pp 387–397

Guan N, Lv M, Yi W, Yu G (2012) WCET analysis with MRU caches: challenging LRU for predictability. In: Proc of RTAS, pp 55–64

Ha R, Liu JWS (1994) Validating timing constraints in multiprocessor and distributed real-time systems. In: Proc of ICDCS, pp 162–171

Hardy D, Piquet T, Puaut I (2009) Using bypass to tighten WCET estimates for multi-core processors with shared instruction caches. In: Proc of RTSS, pp 68–77

Huynh BK, Ju L, Roychoudhury A (2011) Scope-aware data cache analysis for WCET estimation. In: Proc of the RTAS, pp 203–212

Kamruzzaman M, Swanson S, Tullsen DM (2011) Inter-core prefetching for multicore processors using migrating helper threads. In: Proc of ASPLOS, pp 393–404

Kongetira P, Aingaran K, Olukotun K (2005) Niagara: a 32-way multithreaded Sparc processor. IEEE MICRO 25(2):21–29 CrossRef

Lauzac S, Melhem R, Mosse D (1998) Comparison of global and partitioning schemes for scheduling rate monotonic tasks on a multiprocessor. In: Euromicro workshop on real time systems, pp 188–195

Leung JYT, Whitehead J (1982) On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perform Eval 2:237–250 CrossRefMATHMathSciNet

Liang Y, Ding H, Mitra T, Roychoudhury A, Li Y, Suhendra V (2012) Timing analysis of concurrent programs running on shared cache multi-cores. Real-Time Syst 48(6):638–680 CrossRef

Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46–61 CrossRefMATHMathSciNet

Lundberg L (2002) Analyzing fixed-priority global multiprocessor scheduling. In: Proc of RTAS, pp 145–153

Olukotun K, Nayfeh BA, Hammond L, Wilson K, Chang K (1996) The case for a single-chip multiprocessor. SIGPLAN Not 31(9):2–11 CrossRef

Paolieri M, Quiñones E, Cazorla FJ, Bernat G, Valero M (2009) Hardware support for WCET analysis of hard real-time multicore systems. In: Proc of ISCA, pp 57–68

Pathan RM (2012) Schedulability analysis of mixed-criticality systems on multiprocessors. In: Proc of ECRTS, pp 309–320

Pathan RM, Jonsson J (2011) Improved schedulability tests for global fixed-priority scheduling. In: Proc of ECRTS

Puaut I, Potop-Butucaru D (2013) Integrated worst-case execution time estimation of multicore applications. In: 13th international workshop on worst-case execution time analysis (WCET 2013)

Sarkar A, Mueller F, Ramaprasad H, Mohan S (2009) Push-assisted migration of real-time tasks in multi-core processors. In: Proc of LCTES, pp 80–89 CrossRef

Sarkar A, Mueller F, Ramaprasad H (2011) Predictable task migration for locked caches in multi-core systems. In: Proc of LCTES, pp 131–140

Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: Proc of RTSS, pp 239–243

Yoon M-K, Kim J-E, Sha L (2011) Optimizing tunable wcet with shared resource allocation and arbitration in hard real-time multicore systems. In: Proc of the RTSS, pp 227–238

Titel: Interference-aware fixed-priority schedulability analysis on multiprocessors
verfasst von: Risat Mahmud Pathan
Jan Jonsson
Publikationsdatum: 01.07.2014
Verlag: Springer US
Erschienen in: Real-Time Systems / Ausgabe 4/2014
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-013-9198-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner