Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Cluster scheduling for real-time systems: utilization bounds and run-time overhead

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

Abstract

Cluster scheduling, where processors are grouped into clusters and the tasks that are allocated to one cluster are scheduled by a global scheduler, has attracted attention in multiprocessor real-time systems research recently. In this paper, assuming that an optimal global scheduler is adopted within each cluster, we investigate the worst-case utilization bounds for cluster scheduling with different task allocation/partitioning heuristics. First, we develop a lower limit on the utilization bounds for cluster scheduling with any reasonable task allocation scheme. Then, the lower limit is shown to be the exact utilization bound for cluster scheduling with the worst-fit task allocation scheme. For other task allocation heuristics (such as first-fit, best-fit, first-fit decreasing, best-fit decreasing and worst-fit decreasing), higher utilization bounds are derived for systems with both homogeneous clusters (where each cluster has the same number of processors) and heterogeneous clusters (where clusters have different number of processors). In addition, focusing on an efficient optimal global scheduler, namely the boundary-fair (Bfair) algorithm, we propose a period-aware task allocation heuristic with the goal of reducing the scheduling overhead (e.g., the number of scheduling points, context switches and task migrations). Simulation results indicate that the percentage of task sets that can be scheduled is significantly improved under cluster scheduling even for small-size clusters, compared to that of the partitioned scheduling. Moreover, when comparing to the simple generic task allocation scheme (e.g., first-fit), the proposed period-aware task allocation heuristic markedly reduces the scheduling overhead of cluster scheduling with the Bfair scheduler.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Andersson B, Jonsson J (2003) The utilization bounds of partitioned and pfair static-priority scheduling on multiprocessors are 50%. In: Proc of the 15th Euromicro conference on real-time systems, pp 33–40

    Chapter  Google Scholar 

  • Anderson J, Srinivasan A (2000a) Early-release fair scheduling. In: Proc of the 12th Euromicro conference on real-time systems, pp 35–43

    Google Scholar 

  • Anderson J, Srinivasan A (2000b) Pfair scheduling: Beyond periodic task systems. In: Proc of the 7th int’l workshop on real-time computing systems and applications, pp 297–306

    Google Scholar 

  • Anderson J, Srinivasan A (2001) Mixed pfair/erfair scheduling of asynchronous periodic tasks. In: Proc of the 13th Euromicro conference on real-time systems, pp 76–85

    Chapter  Google Scholar 

  • Andersson B, Tovar E (2006) Multiprocessor scheduling with few preemptions. In: Proc of the IEEE int’l conference on embedded and real-time computing systems and applications, pp 322–334

    Google Scholar 

  • Andersson B, Baruah S, Jonsson J (2001) Static-priority scheduling on multiprocessors. In: Proc of the 22th IEEE real-time systems symposium, pp 193–202

    Google Scholar 

  • Andersson B, Bletsas K, Baruah S (2008) Scheduling arbitrary-deadline sporadic task systems on multiprocessors. In: Proc of the IEEE real-time systems symposium, pp 385–394

    Google Scholar 

  • Baker T (2003) Multiprocessor edf and deadline monotonic schedulability analysis. In: Proc. of the 24th IEEE real-time systems symposium, pp 120–129

    Google Scholar 

  • Baruah S (2007) Techniques for multiprocessor global schedulability analysis. In: Proc of the IEEE real-time systems symposium, pp 119–128

    Google Scholar 

  • Baruah S, Baker T (2008) Schedulability analysis of global edf. Real-Time Syst 38(3):223–235

    Article  MATH  Google Scholar 

  • Baruah SK, Gehrke J, Plaxton CG (1995) Fast scheduling of periodic tasks on multiple resources. In: Proc of the international parallel processing symposium, pp 280–288

    Chapter  Google Scholar 

  • Baruah SK, Cohen NK, Plaxton CG, Varel DA (1996) Proportionate progress: a notion of fairness in resource allocation. Algorithmica 15(6):600–625

    Article  MATH  MathSciNet  Google Scholar 

  • Bletsas K, Andersson B (2009) Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound. In: Proc of the IEEE real-time systems symposium, pp 447–456

    Google Scholar 

  • Burchard A, Liebeherr J, Oh Y, Son SH (1996) New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans Comput 44(12):1429–1442

    Article  MathSciNet  Google Scholar 

  • Calandrino JM, Anderson JH, Baumberger DP (2007) A hybrid real-time scheduling approach for large-scale multicore platforms. In: Proc of the Euromicro conference on real-time systems, pp 247–258

    Google Scholar 

  • Cho H, Ravindran B, Jensen E (2006) An optimal real-time scheduling algorithm for multiprocessors. In: Proc of the IEEE real-time systems symposium, pp 101–110

    Google Scholar 

  • Cho H, Ravindran B, Jensen ED (2010) T-l plane-based real-time scheduling for homogeneous multiprocessors. J Parallel Distrib Comput 70(3):225–236

    Article  Google Scholar 

  • Darera VN (2006) Bounds for scheduling in non-identical uniform multiprocessor systems. Master’s thesis, Indian Institute of Science, India

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

    Google Scholar 

  • Davis R, Burns A (2009b) A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems. Tech Rep YCS-2009-443, University of York, Department of Computer Science

  • Dertouzos ML, Mok AK (1989) Multiprocessor on-line scheduling of hard-real-time tasks. IEEE Trans Softw Eng 15(12):1497–1505

    Article  Google Scholar 

  • Devi U, Anderson J (2005) Tardiness bounds under global edf scheduling on a multiprocessor. In: Proc of the 26th IEEE real-time systems symposium, pp 330–341

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  • Funaoka K, Kato S, Yamasaki N (2008) Work-conserving optimal real-time scheduling on multiprocessors. In: Proc of the Euromicro conference on real-time systems, pp 13–22

    Chapter  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 the IEEE real-time systems symposium, pp 387–397

    Google Scholar 

  • Guan N, Stigge M, Yi W, Yu G (2010) Fixed-priority multiprocessor scheduling with Liu & Layland’s utilization bound. In: Proc of the 16th IEEE real-time and embedded technology and applications symposium, pp 165–174

    Chapter  Google Scholar 

  • Herbert S, Marculescu D (2007) Analysis of dynamic voltage/frequency scaling in chip-multiprocessors. In: Proc of Int’l symposium on low power electronics and design, pp 38–43

    Google Scholar 

  • Holman P, Anderson J (2001) Guaranteeing pfair supertasks by reweighting. In: Proc of the 22nd IEEE real-time systems symposium, pp 203–212

    Google Scholar 

  • Kato S, Yamasaki N (2007) Real-time scheduling with task splitting on multiprocessors. In: Proc of the IEEE int’l conference on embedded and real-time computing systems and applications, pp 441–450

    Google Scholar 

  • Kato S, Yamasaki N (2008) Portioned edf-based scheduling on multiprocessors. In: Proc of the 8th ACM int’l conference on embedded software, pp 139–148

    Google Scholar 

  • Kato S, Funaoka K, Yamasaki N (2009) Semi-partitioned scheduling of sporadic task systems on multiprocessors. In: Proc of the 21th Euromicro conference on real-time systems, pp 249–258

    Chapter  Google Scholar 

  • Lauzac S, Melhem R, Mossé D (2003) An improved rate-monotonic admission control and its applications. IEEE Trans Comput 52:337–350

    Article  Google Scholar 

  • Levin G, Funk S, Sadowski C, Pye I, Brandt S (2010) Dp-fair: a simple model for understanding optimal multiprocessor scheduling. In: Proc of the Euromicro conference on real-time systems, pp 3–13

    Google Scholar 

  • Liu JW (2000) Real-time systems. Prentice Hall/PTR, New York

    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 

  • Liu D, Lee YH (2004) Pfair scheduling of periodic tasks with allocation constraints on multiple processors. In: Proc of the 18th int’l parallel and distributed processing symposium, pp 119–126

    Google Scholar 

  • Lopez J, Garcia M, Diaz J, Garcia D (2000) Worst-case utilization bound for edf scheduling on real-time multiprocessor systems. In: Prof of the 12th Euromicro conference on real-time systems, pp 25–33

    Chapter  Google Scholar 

  • Lopez J, Diaz J, Garcia D (2001) Minimum and maximum utilization bounds for multiprocessor rm scheduling. In: Proc. of the 13th Euromicro conference on real-time systems, pp 67–75

    Chapter  Google Scholar 

  • Lopez J, Diaz J, Garcia D (2004) Utilization bound for edf scheduling on real-time multiprocessor systems. Real-Time Syst 28(1):39–68

    Article  MATH  Google Scholar 

  • Moir M, Ramamurthy S (1999) Pfair scheduling of fixed and migrating tasks on multiple resources. In: Proc. of the 20th IEEE real-time systems symposium, pp 294–303

    Google Scholar 

  • Oh D, Baker T (1998) Utilization bound for n-processor rate monotone scheduling with stable processor assignment. Real-Time Syst 15(2):183–193

    Article  Google Scholar 

  • Qi X, Zhu D (2008) Power management for real-time embedded systems on block-partitioned multicore platforms. In: Proc of the int’l conference on embedded software and systems, pp 110–117

    Chapter  Google Scholar 

  • Shin I, Easwaran A, Lee I (2008) Hierarchical scheduling framework for virtual clustering of multiprocessors. In: Proc of the 20th Euromicro conference on real-time systems, pp 181–190

    Google Scholar 

  • Zhu D, Mossé D, Melhem R (2003) Periodic multiple resource scheduling problem: how much fairness is necessary. In: Proc of the 24th IEEE real-time systems symposium, pp 142–151

    Google Scholar 

  • Zhu D, Qi X, Mossé D, Melhem R (2009) An optimal boundary-fair scheduling algorithm for multiprocessor real-time systems. Tech Rep CS-TR-2009-005, Dept of CS, Univ of Texas at San Antonio

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Texas at San Antonio, One UTSA Circle, San Antonio, TX, 78249, USA

    Xuan Qi & Dakai Zhu

  2. Department of Computer Science, George Mason University, 4400 University Drive, Fairfax, VA, 22030, USA

    Hakan Aydin

Authors
  1. Xuan Qi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dakai Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hakan Aydin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dakai Zhu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Qi, X., Zhu, D. & Aydin, H. Cluster scheduling for real-time systems: utilization bounds and run-time overhead. Real-Time Syst 47, 253–284 (2011). https://doi.org/10.1007/s11241-011-9121-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11241-011-9121-1

Keywords

Search

Navigation