[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Interference-aware fixed-priority schedulability analysis on multiprocessors

  • Published:
Real-Time Systems Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

Notes

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

  2. 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).

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

  4. 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.

  5. 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.

  6. 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.

References

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

    Google Scholar 

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

    Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  • 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  Google Scholar 

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

    Article  MATH  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  • 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

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

  • 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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  • 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)

    Google Scholar 

  • 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

    Chapter  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  • 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

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Chalmers University of Technology, 412-96, Göteborg, Sweden

    Risat Mahmud Pathan & Jan Jonsson

Authors
  1. Risat Mahmud Pathan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan Jonsson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Risat Mahmud Pathan.

Additional information

This is an extended version of a paper (Pathan and Jonsson 2011) that was presented at the EuroMicro Conference on Real-Time Systems, Porto (Portugal), July 2011.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pathan, R.M., Jonsson, J. Interference-aware fixed-priority schedulability analysis on multiprocessors. Real-Time Syst 50, 411–455 (2014). https://doi.org/10.1007/s11241-013-9198-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11241-013-9198-9

Keywords

Search

Navigation