Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Real-Time Systems
Published in: Real-Time Systems 6/2012

01-11-2012

FPSL, FPCL and FPZL schedulability analysis

Authors: Robert I. Davis, Shinpei Kato

Published in: Real-Time Systems | Issue 6/2012

Log in

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

search-config
loading …

Abstract

This paper presents the Fixed Priority until Static Laxity (FPSL), Fixed Priority until Critical Laxity (FPCL) and Fixed Priority until Zero Laxity (FPZL) scheduling algorithms for multiprocessor real-time systems. FPZL is similar to global fixed priority pre-emptive scheduling; however, whenever a task reaches a state of zero laxity it is given the highest priority. FPSL and FPCL are variants of FPZL that introduce no additional scheduling points beyond those present with fixed priority scheduling. FPSL, FPCL and FPZL are minimally dynamic algorithms, in that the priority of a job can change at most once during its execution, bounding the number of pre-emptions.
Polynomial time and pseudo-polynomial time sufficient schedulability tests are derived for these algorithms. The tests are then improved by computing upper bounds on the amount of execution that each task can perform at the highest priority. An empirical evaluation shows that FPSL, FPCL, and FPZL are highly effective, with a significantly larger number of tasksets deemed schedulable by the tests derived in this paper, than by state-of-the-art schedulability tests for EDZL scheduling.
previous article Laxity dynamics and LLF schedulability analysis on multiprocessor platforms
next article Analysis and implementation of the multiprocessor bandwidth inheritance protocol

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
Footnotes
1
Note we adopt the approach to time representation used by Bertogna et al. (2009). Time is represented by non-negative integer values, with each time value t viewed as representing the whole of the interval [t,t+1). This enables mathematical induction on clock ticks and avoids confusion with respect to end points of execution.
 
2
In the case of an unschedulable taskset, more than m jobs could become critical-laxity jobs, in which case the RUN set arbitrarily contains the first m of them found. In this case some job is inevitably going to miss its deadline assuming that all jobs take their worst-case execution times.
 
Literature
Andersson B, Jonsson J (2000) Some insights on fixed-priority pre-emptive non-partitioned multiprocessor scheduling. In: Proceedings real-time systems symposium (RTSS)—work-in-progress session
Andersson B, Bletsas K, Baruah SK (2008) Scheduling arbitrary-deadline sporadic tasks on multiprocessors. In: Proceedings real-time systems symposium (RTSS)
Audsley NC (1991) Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical Report YCS 164, Dept Computer Science, University of York, UK, Dec 1991
Audsley NC (2001) On priority assignment in fixed priority scheduling. Inf Process Lett 79(1):39–44 MATHCrossRef
Baker TP (2003) Multiprocessor EDF and deadline monotonic schedulability analysis. In: Proceedings real-time systems symposium (RTSS), pp 120–129
Baker TP (2006) An analysis of fixed-priority scheduling on a multiprocessor. Real-Time Syst 32(1–2):49–71 MATHCrossRef
Baker TP, Baruah SK (2009) Sustainable multiprocessor scheduling of sporadic task systems. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 141–150
Baker TP, Cirinei M (2006) A necessary and sometimes sufficient condition for the feasibility of sets of sporadic hard-deadline tasks. In: Proceedings real-time systems symposium (RTSS)—work-in-progress (WIP) session
Baker TP, Cirinei M, Bertogna M (2008) EDZL scheduling analysis. Real-Time Syst 40(3):264–289 MATHCrossRef
Baruah SK (2007) Techniques for multiprocessor global schedulability analysis. In: Proceedings real-time systems symposium (RTSS), pp 119–128
Baruah SK, Baker TP (2009) An analysis of global EDF schedulability for arbitrary sporadic task systems. Real-Time Syst 43(1):3–24, ECRTS special issue MATHCrossRef
Baruah SK, Burns A (2006) Sustainable scheduling analysis. In: Proceedings real-time systems symposium (RTSS), pp 159–168
Baruah SK, Fisher N (2008) Global fixed-priority scheduling of arbitrary-deadline sporadic…. In: Proc of the 9th int’l conference on distributed computing and networking, pp 215–226
Baruah SK, Bonifaci V, Marchetti-Spaccamela A, Stiller S (2009) Implementation of a speedup-optimal global EDF schedulability test. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 259–268
Bastoni A, Brandenburg BB, Anderson JH (2010a) An empirical comparison of global, partitioned, and clustered multiprocessor real-time schedulers. In: Proceedings real-time systems symposium (RTSS)
Bastoni A, Brandenburg B, Anderson J (2010b) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: Proceedings of the sixth international workshop on operating systems platforms for embedded real-time applications (OSPERT 2010), July 2010, pp 33–44
Beal D, Bianchi E, Dozio L, Hughes S, Mantegazza P, Papacharalambous S (2000) RTAI: real time application interface. Linux J 29:10
Bertogna M (2007) Real-time scheduling analysis for multiprocessor platforms. PhD Thesis, Scuola Superiore Sant’Anna, Pisa
Bertogna M (2009) Evaluation of existing schedulability tests for global EDF. In: Proceedings of the first international workshop on real-time systems on multicore platforms: theory and practice
Bertogna M, Cirinei M (2007) Response time analysis for global scheduled symmetric multiprocessor platforms. In: Proceedings real-time systems symposium (RTSS), pp 149–158
Bertogna M, Cirinei M, Lipari G (2005) New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors. In: Proc 9th international conf on principles of distributed systems, 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(1–2):129–154 MATHCrossRef
Brandenburg BB, Calandrino JM, Anderson JH (2008) On the scalability of real-time scheduling algorithms on multicore platforms: a case study. In: Proceedings real-time systems symposium (RTSS), pp 157–169
Burns A, Davis RI, Wang P, Zhang F (2011) Partitioned EDF scheduling for multiprocessors using a C=D scheme. Real-Time Syst 48(1):3–33 CrossRef
Calandrino J, Leontyev H, Block A, Devi U, Anderson J (2006) LITMUSRT: a testbed for empirically comparing real-time multiprocessor schedulers. In: Proceedings real-time systems symposium (RTSS), pp 111–123
Chao Y-H, Lin S-S, Lin K-J (2008) Schedulability issues for EDZL scheduling on real-time multiprocessor systems. Inf Process Lett 107(5):158–164 MathSciNetMATHCrossRef
Cho S, Lee S-K, Han A, Lin K-J (2002) Efficient real-time scheduling algorithms for multiprocessor systems. IEICE Trans Commun E85-B(12):2859–2867
Cho H, Ravindran B, Jensen ED (2006) An optimal real-time scheduling algorithm for multiprocessors. In: Proceedings real-time systems symposium (RTSS), pp 101–110
Cirinei M, Baker TP (2007) EDZL scheduling analysis. In: Proceedings Euromicro conference on real-time systems (ECRTS), pp 9–18
Davis RI, Burns A (2009) Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In: Proceedings real-time systems symposium (RTSS), pp 398–409
Davis RI, Burns A (2010b) FPZL schedulability analysis. Technical Report YCS-2010-452, Dept of Computer Science, University of York, April 2010
Davis RI, Burns A (2011a) FPZL schedulability analysis. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 245–256
Faggioli D, Trimarchi M, Checconi F (2009) An implementation of the earliest deadline first algorithm in Linux. In: Proceedings ACM symposium on applied computing, pp 1984–1989 CrossRef
Fisher N, Baruah SK (2006) Global static-priority scheduling of sporadic task systems on multiprocessor platforms. In: Proceedings IASTED international conference on parallel and distributed computing and systems
Funk S, Nadadur V (2009) LRE-TL: an optimal multiprocessor algorithm for sporadic task sets. In: Proceedings real-time and network systems (RTNS), pp 159–168
Guan N, Stigge M, Yi W, Yu G (2009) New response time bounds for fixed priority multiprocessor scheduling. In: Proceedings real-time systems symposium (RTSS), pp 387–397
Guan N, Stigge M, Yi W, Yu G (2010) Fixed-priority multiprocessor scheduling with Liu & Layland’s utilization bound. In: Proceedings real-time and embedded technology and applications symposium (RTAS)
Kato S, Yamasaki N (2008) Global EDF-based scheduling with efficient priority promotion. In: Proceedings of real-time computing systems and applications (RTCSA), pp 197–206
Kato S, Yamasaki N (2009a) Semi-partitioned fixed-priority scheduling on multiprocessors. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 23–32
Kato S, Yamasaki N (2009b) Real-time scheduling module for Linux kernel. IPSJ Trans Adv Comput Syst 2(1 (ACS25)):75–86 (in Japanese)
Kato S, Takeda A, Yamasaki N (2010) Global rate-monotonic scheduling with priority promotion. Technical Report CMU-ECE-TR10-05, May 2010
Lee SK (1994) On-line multiprocessor scheduling algorithms for real-time tasks. In: Proc IEEE region 10’s ninth annual international conference, pp 607–611
Oikawa S, Rajkumar R (1999) Portable RT: a portable resource kernel for guaranteed and enforced timing behaviour. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 111–120
Park M, Han S, Kim H, Cho S, Cho Y (2005) Comparison of deadline-based scheduling algorithms for periodic real-time tasks on multiprocessor. IEICE Trans Inf Syst E88-D(3):658–661 CrossRef
Piao X, Han S, Kim H, Park M, Cho Y, Cho S (2006) Predictability of earliest deadline zero laxity algorithm for multiprocessor real time systems. In: Proc of the 9th IEEE international symposium on object and component-oriented real-time distributed computing, Gjeongju, Korea
Srinivasan B, Pather S, Hill R, Ansari F, Niehaus D (1998) A firm real-time system implementation using commercial off-the shelf hardware and free software. In: Proceedings real-time and embedded technology and applications symposium (RTAS), pp 112–119
Takeda A, Kato S, Yamasaki N (2009) Real-time scheduling based on rate monotonic for multiprocessors. IPSJ Trans Adv Comput Syst 2(1 (ACS25)):64–74 (in Japanese)
Metadata
Title
FPSL, FPCL and FPZL schedulability analysis
Authors
Robert I. Davis
Shinpei Kato
Publication date
01-11-2012
Publisher
Springer US
Published in
Real-Time Systems / Issue 6/2012
Print ISSN: 0922-6443
Electronic ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-012-9149-x

Other articles of this Issue 6/2012

Real-Time Systems 6/2012 Go to the issue

OriginalPaper

Laxity dynamics and LLF schedulability analysis on multiprocessor platforms

News

Guest editorial

OriginalPaper

Analysis and implementation of the multiprocessor bandwidth inheritance protocol

OriginalPaper

Memory-centric scheduling for multicore hard real-time systems

OriginalPaper

Timing analysis of concurrent programs running on shared cache multi-cores

Premium Partner

    Image Credits