Top

Real-Time Systems

Published in:

01-01-2014

Fair lateness scheduling: reducing maximum lateness in G-EDF-like scheduling

Authors: Jeremy P. Erickson, James H. Anderson, Bryan C. Ward

Published in: Real-Time Systems | Issue 1/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In prior work on soft real-time (SRT) multiprocessor scheduling, tardiness bounds have been derived for a variety of scheduling algorithms, most notably, the global earliest-deadline-first (G-EDF) algorithm. In this paper, we devise G-EDF-like (GEL) schedulers, which have identical implementations to G-EDF and therefore the same overheads, but that provide better tardiness bounds. We discuss how to analyze these schedulers and propose methods to determine scheduler parameters to meet several different tardiness bound criteria. We employ linear programs to adjust such parameters to optimize arbitrary tardiness criteria, and to analyze lateness bounds (lateness is related to tardiness). We also propose a particular scheduling algorithm, namely the global fair lateness (G-FL) algorithm, to minimize maximum absolute lateness bounds. Unlike the other schedulers described in this paper, G-FL only requires linear programming for analysis. We argue that our proposed schedulers, such as G-FL, should replace G-EDF for SRT applications.

previous article Special issue on multiprocessor and mixed-criticality scheduling

next article Bounding and shaping the demand of generalized mixed-criticality sporadic task systems

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

Application-specific per-task lateness tolerances could be used instead of L _max.

As before, application-specific per-task proportional lateness tolerances could be used instead of I _max.

When Y _i=T _i for all i, S _i(Y _i)=0, and rather than defining G(x,Y) as the largest sum of U ⁺−1 values of x _i U _i+C _i, we can instead define G(x,Y) as the largest sum of only U ⁺−2 values of x _i U _i+C _i plus an additional C _i.

With uniform heavy utilizations and uniform long periods, EDF-CVA2 provided a very slightly smaller average proportional lateness bound when the system utilization was 8. Recall that the technique used by EDF-CVA2 only applies when proportional PPs equal minimum separation times.

Anderson JH, Srinivasan A (2004) Mixed pfair/erfair scheduling of asynchronous periodic tasks. J Comput Syst Sci 68(1):157–204 MathSciNetCrossRefMATH

Back H, Chwa HS, Shin I (2012) Schedulability analysis and priority assignment for global job-level fixed-priority multiprocessor scheduling. In: IEEE real-time and embedded technology and applications symposium, pp 297–306

Baker T, Cirinei M, Bertogna M (2008) EDZL scheduling analysis. Real-Time Syst 40:264–289 CrossRefMATH

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

Baruah SK, Mok AK, Rosier LE (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: RTSS, pp 182–190

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

Brandenburg BB (2011) Scheduling and Locking in Multiprocessor Real-Time Operating Systems. PhD thesis, The University of North Carolina at Chapel Hill

Chwa HS, Back H, Chen S, Lee J, Easwaran A, Shin I, Lee I (2012) Extending task-level to job-level fixed priority assignment and schedulability analysis using pseudo-deadlines. In: RTSS, pp 51–62

Devi UC, Anderson JH (2008) Tardiness bounds under global EDF scheduling on a multiprocessor. Real-Time Syst 38(2):133–189 CrossRefMATH

Erickson JP, Anderson JH (2012) Fair lateness scheduling: reducing maximum lateness in g-edf-like scheduling. In: ECRTS, pp 3–12

Erickson JP, Devi U, Baruah SK (2010a) Improved tardiness bounds for global EDF. In: ECRTS, pp 14–23

Erickson JP, Guan N, Baruah SK (2010b) Tardiness bounds for global EDF with deadlines different from periods. In: OPODIS, pp 286–301. Revised version at http://cs.unc.edu/~jerickso/opodis2010-tardiness.pdf

Kenna C, Herman J, Brandenburg BB, Mills AF, Anderson JH (2011) Soft real-time on multiprocessors: are analysis-based schedulers really worth it? In: RTSS, pp 99–103

Lee J, Easwaran A, Shin I (2011) Maximizing contention-free executions in multiprocessor scheduling. In: RTAS, pp 235–244

Lee SK (1994) On-line multiprocessor scheduling algorithms for real-time tasks. In: IEEE region 10 annual international conference, pp 607–611

Leontyev H, Anderson JH (2010) Generalized tardiness bounds for global multiprocessor scheduling. Real-Time Syst 44(1):26–71 CrossRefMATH

Leontyev H, Chakraborty S, Anderson JH (2009) Multiprocessor extensions to real-time calculus. In: RTSS, pp 410–421

Megel T, Sirdey R, David V (2010) Minimizing task preemptions and migrations in multiprocessor optimal real-time schedules. In: RTSS, pp 37–46

Ogryczak W, Tamir A (2003) Minimizing the sum of the k largest functions in linear time. Inf Process Lett 85(3):117–122 MathSciNetCrossRefMATH

Regnier P, Lima G, Massa E, Levin G, Brandt SRU (2011) Optimal multiprocessor real-time scheduling via reduction to uniprocessor. In: RTSS, pp 104–115

Srinivasan A, Baruah SK (2002) Deadline-based scheduling of periodic task systems on multiprocessors. Inf Process Lett 84(2):93–98 MathSciNetCrossRefMATH

Ward BC, Erickson JP, Anderson JH (2013) A linear model for setting priority points in soft real-time systems. In: Alanfest, pp 192–205

Title: Fair lateness scheduling: reducing maximum lateness in G-EDF-like scheduling
Authors: Jeremy P. Erickson
James H. Anderson
Bryan C. Ward
Publication date: 01-01-2014
Publisher: Springer US
Published in: Real-Time Systems / Issue 1/2014
Print ISSN: 0922-6443
Electronic ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-013-9190-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2014

Bounding and shaping the demand of generalized mixed-criticality sporadic task systems

Mixed-criticality scheduling on multiprocessors

Task assignment algorithms for two-type heterogeneous multiprocessors

Special issue on multiprocessor and mixed-criticality scheduling

Premium Partner