Skip to main content
Erschienen in: Real-Time Systems 3/2015

01.06.2015

The limited-preemptive feasibility of real-time tasks on uniprocessors

verfasst von: Abhilash Thekkilakattil, Radu Dobrin, Sasikumar Punnekkat

Erschienen in: Real-Time Systems | Ausgabe 3/2015

Einloggen

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

search-config
loading …

Abstract

The preemptive scheduling paradigm is known to strictly dominate the non-preemptive scheduling paradigm with respect to feasibility. On the other hand, preemptively scheduling real-time tasks on uniprocessors, unlike non-preemptive scheduling, may lead to unschedulability due to, e.g., preemption related overheads. The limited-preemptive scheduling paradigm, which is a generalization of preemptive and non-preemptive paradigms, has, however, the potential to reduce the preemption related overheads while enabling high processor utilization. In this paper, we focus on the characterization of the effects of increasing the computational resources on the limited-preemptive feasibility of real-time tasks in order to quantify the sub-optimality of limited-preemptive scheduling. Specifically, we first derive the required processor speed-up bound that guarantees limited-preemptive feasibility of any uniprocessor feasible taskset. Secondly, we demonstrate the applicability of the results in the context of controlling preemption related overheads while minimizing the required processor speed-up. In particular, we identify the preemptive behavior that minimizes preemption-related overheads, as well as derive the optimal processor speed associated with it. Finally, we examine the consequences of having more processors on limited-preemptive feasibility and derive the bound on the number of processors that guarantees a specified limited-preemptive behavior for any uniprocessor feasible real-time taskset. This paper essentially bridges the preemptive and non-preemptive real-time scheduling paradigms by providing significant theoretical results building on the limited-preemptive scheduling paradigm, as well as provides analytical inputs to developers in order to perform various trade-offs, e.g., code refactoring, to control the preemptive behavior of real-time tasks.

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!

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!

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!

Fußnoten
1
Note that design parameters such as deadlines and time periods in many systems are negotiable not only in many soft real-time applications, but also in many hard real-time applications (please refer to Buttazzo and Abeni 2002 for more details).
 
Literatur
Zurück zum Zitat Abdelzaher T, Andersson B, Jonsson J (2002) The aperiodic multiprocessor utilization bound for liquid tasks. In: The real-time and embedded technology and applications symposium Abdelzaher T, Andersson B, Jonsson J (2002) The aperiodic multiprocessor utilization bound for liquid tasks. In: The real-time and embedded technology and applications symposium
Zurück zum Zitat Altmeyer S, Davis RI, Maiza C (2012) Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real Time Syst 48:499–526MATHCrossRef Altmeyer S, Davis RI, Maiza C (2012) Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real Time Syst 48:499–526MATHCrossRef
Zurück zum Zitat Amdahl GM (1967) Validity of the single processor approach to achieving large scale computing capabilities. In: American Federation of Information Processing Societies spring joint computer conference Amdahl GM (1967) Validity of the single processor approach to achieving large scale computing capabilities. In: American Federation of Information Processing Societies spring joint computer conference
Zurück zum Zitat Audsley N, Burns A, Richardson MF, Wellings AJ (1991) Hard real-time scheduling: the deadline-monotonic approach. In: The IEEE workshop on real-time operating systems and software Audsley N, Burns A, Richardson MF, Wellings AJ (1991) Hard real-time scheduling: the deadline-monotonic approach. In: The IEEE workshop on real-time operating systems and software
Zurück zum Zitat Baruah S (2005) The limited-preemption uniprocessor scheduling of sporadic task systems. In: The Euromicro conference on real-time systems Baruah S (2005) The limited-preemption uniprocessor scheduling of sporadic task systems. In: The Euromicro conference on real-time systems
Zurück zum Zitat Baruah SK, Rosier LE, Howell RR (1990b) Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real Time Syst 2(4):301–324CrossRef Baruah SK, Rosier LE, Howell RR (1990b) Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real Time Syst 2(4):301–324CrossRef
Zurück zum Zitat Baruah S, Burns A (2006) Sustainable scheduling analysis. In: The real-time systems symposium Baruah S, Burns A (2006) Sustainable scheduling analysis. In: The real-time systems symposium
Zurück zum Zitat Baruah S, Burns A (2008) Quantifying the sub-optimality of uniprocessor fixed-priority scheduling. In: The international conference on real-time and network systems Baruah S, Burns A (2008) Quantifying the sub-optimality of uniprocessor fixed-priority scheduling. In: The international conference on real-time and network systems
Zurück zum Zitat Baruah S, Mok A, Rosier L (1990a) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: The real-time systems symposium Baruah S, Mok A, Rosier L (1990a) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: The real-time systems symposium
Zurück zum Zitat Bertogna M, Baruah S (2010) Limited preemption EDF scheduling of sporadic task systems. IEEE Trans Ind Inform 6:579–591CrossRef Bertogna M, Baruah S (2010) Limited preemption EDF scheduling of sporadic task systems. IEEE Trans Ind Inform 6:579–591CrossRef
Zurück zum Zitat Bertogna M, Buttazzo G, Marinoni M, Yao G, Esposito F, Caccamo M (2010) Preemption points placement for sporadic task sets. In: The Euromicro conference on real-time systems Bertogna M, Buttazzo G, Marinoni M, Yao G, Esposito F, Caccamo M (2010) Preemption points placement for sporadic task sets. In: The Euromicro conference on real-time systems
Zurück zum Zitat Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real Time Syst 30:129–154MATHCrossRef Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real Time Syst 30:129–154MATHCrossRef
Zurück zum Zitat Bui BD, Caccamo M, Sha L, Martinez J (2008) Impact of cache partitioning on multi-tasking real time embedded systems. In: The international conference on embedded and real-time computing systems and applications Bui BD, Caccamo M, Sha L, Martinez J (2008) Impact of cache partitioning on multi-tasking real time embedded systems. In: The international conference on embedded and real-time computing systems and applications
Zurück zum Zitat Busquets-Mataix JV, Serrano JJ, Ors R, Gil P, Wellings A (1996) Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In: The IEEE real-time technology and applications symposium Busquets-Mataix JV, Serrano JJ, Ors R, Gil P, Wellings A (1996) Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In: The IEEE real-time technology and applications symposium
Zurück zum Zitat Buttazzo G, Abeni L (2002) Adaptive workload management through elastic scheduling. Real Time Syst 23:7–24MATHCrossRef Buttazzo G, Abeni L (2002) Adaptive workload management through elastic scheduling. Real Time Syst 23:7–24MATHCrossRef
Zurück zum Zitat Buttazzo G, Bertogna M, Yao G (2012) Limited preemptive scheduling for real-time systems: a survey. IEEE Trans Ind Inform 9:3–15CrossRef Buttazzo G, Bertogna M, Yao G (2012) Limited preemptive scheduling for real-time systems: a survey. IEEE Trans Ind Inform 9:3–15CrossRef
Zurück zum Zitat Davis RI, Rothvoss T, Baruah SK, Burns A (2009b) Quantifying the sub-optimality of uniprocessor fixed priority pre-emptive scheduling for sporadic tasksets with arbitrary deadlines. In: The international conference on real-time and network systems Davis RI, Rothvoss T, Baruah SK, Burns A (2009b) Quantifying the sub-optimality of uniprocessor fixed priority pre-emptive scheduling for sporadic tasksets with arbitrary deadlines. In: The international conference on real-time and network systems
Zurück zum Zitat Davis R, Rothvoss T, Baruah S, Burns A (2009a) Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Real Time Syst 43:211–258MATHCrossRef Davis R, Rothvoss T, Baruah S, Burns A (2009a) Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling. Real Time Syst 43:211–258MATHCrossRef
Zurück zum Zitat Davis R, George L, Courbin P (2010) Quantifying the sub-optimality of uniprocessor fixed priority non-pre-emptive scheduling. In: The international conference on real-time and network systems Davis R, George L, Courbin P (2010) Quantifying the sub-optimality of uniprocessor fixed priority non-pre-emptive scheduling. In: The international conference on real-time and network systems
Zurück zum Zitat Dertouzos ML (1974) Control robotics: the procedural control of physical processes. In: IFIP congress Dertouzos ML (1974) Control robotics: the procedural control of physical processes. In: IFIP congress
Zurück zum Zitat George L, Muhlethaler P, Rivierre N (1995) Optimality and non-preemptive real-time scheduling revisited. Research report, INRIA George L, Muhlethaler P, Rivierre N (1995) Optimality and non-preemptive real-time scheduling revisited. Research report, INRIA
Zurück zum Zitat George L, Rivierre N, Spuri M (1996) Preemptive and non-preemptive real-time uniprocessor scheduling. Research report, INRIA George L, Rivierre N, Spuri M (1996) Preemptive and non-preemptive real-time uniprocessor scheduling. Research report, INRIA
Zurück zum Zitat Jeffay K, Stanat DF, Martel CU (1991) On non-preemptive scheduling of periodic and sporadic tasks. In: The real-time systems symposium Jeffay K, Stanat DF, Martel CU (1991) On non-preemptive scheduling of periodic and sporadic tasks. In: The real-time systems symposium
Zurück zum Zitat Ju L, Chakraborty S, Roychoudhury A (2007) Accounting for cache-related preemption delay in dynamic priority schedulability analysis. In: IEEE design automation and test in Europe Ju L, Chakraborty S, Roychoudhury A (2007) Accounting for cache-related preemption delay in dynamic priority schedulability analysis. In: IEEE design automation and test in Europe
Zurück zum Zitat Lam TW, To KK (1999) Trade-offs between speed and processor in hard-deadline scheduling. In: The ACM-SIAM symposium on Discrete algorithms Lam TW, To KK (1999) Trade-offs between speed and processor in hard-deadline scheduling. In: The ACM-SIAM symposium on Discrete algorithms
Zurück zum Zitat Lee CG, Hahn J, Seo JM, Min SL, Ha R, Hong S, Park CY, Lee M, Kim CS (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47:700–713MathSciNetCrossRef Lee CG, Hahn J, Seo JM, Min SL, Ha R, Hong S, Park CY, Lee M, Kim CS (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47:700–713MathSciNetCrossRef
Zurück zum Zitat Leontyev H, Anderson J (2008) A hierarchical multiprocessor bandwidth reservation scheme with timing guarantees. In: The Euromicro conference on real-time systems Leontyev H, Anderson J (2008) A hierarchical multiprocessor bandwidth reservation scheme with timing guarantees. In: The Euromicro conference on real-time systems
Zurück zum Zitat Marinoni M, Buttazzo G (2007) Elastic DVS management in processors with discrete voltage/frequency modes. IEEE Trans Ind Inform 3:51–62CrossRef Marinoni M, Buttazzo G (2007) Elastic DVS management in processors with discrete voltage/frequency modes. IEEE Trans Ind Inform 3:51–62CrossRef
Zurück zum Zitat McKee SA (2004) Reflections on the memory wall. In: Proceedings of the conference on computing frontiers McKee SA (2004) Reflections on the memory wall. In: Proceedings of the conference on computing frontiers
Zurück zum Zitat Peng B, Fisher N, Bertogna M (2014) Explicit preemption placement for real-timeconditional code. In: The Euromicro conference on real-time systems Peng B, Fisher N, Bertogna M (2014) Explicit preemption placement for real-timeconditional code. In: The Euromicro conference on real-time systems
Zurück zum Zitat Pillai P, Shin KG (2001) Real-time dynamic voltage scaling for low-power embedded operating systems. In: The ACM symposium on operating systems principles Pillai P, Shin KG (2001) Real-time dynamic voltage scaling for low-power embedded operating systems. In: The ACM symposium on operating systems principles
Zurück zum Zitat Saha S, Ravindran B (2012) An experimental evaluation of real-time dvfs scheduling algorithms. In: Proceedings of the annual international systems and storage conference Saha S, Ravindran B (2012) An experimental evaluation of real-time dvfs scheduling algorithms. In: Proceedings of the annual international systems and storage conference
Zurück zum Zitat Short M (2010) The case for non-preemptive, deadline-driven scheduling in real-time embedded systems. In: Proceedings of the world congress on engineering, engineering and computer science. Lecture Notes Short M (2010) The case for non-preemptive, deadline-driven scheduling in real-time embedded systems. In: Proceedings of the world congress on engineering, engineering and computer science. Lecture Notes
Zurück zum Zitat Staschulat J, Schliecker S, Ernst R (2005) Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In: The Euromicro conference on real-time systems Staschulat J, Schliecker S, Ernst R (2005) Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In: The Euromicro conference on real-time systems
Zurück zum Zitat Tan Y, Mooney V (2007) Timing analysis for preemptive multitasking real-time systems with caches. ACM Trans Embed Comput Syst 6:7CrossRef Tan Y, Mooney V (2007) Timing analysis for preemptive multitasking real-time systems with caches. ACM Trans Embed Comput Syst 6:7CrossRef
Zurück zum Zitat Thekkilakattil A, Baruah S, Dobrin R, Punnekkat S (2014) The global limited preemptive earliest deadline first feasibility of sporadic real-time tasks. In: The Euromicro conference on real-time systems Thekkilakattil A, Baruah S, Dobrin R, Punnekkat S (2014) The global limited preemptive earliest deadline first feasibility of sporadic real-time tasks. In: The Euromicro conference on real-time systems
Zurück zum Zitat Thekkilakattil A, Dobrin R, Punnekkat S (2013) Quantifying the sub-optimality of non-preemptive real-time scheduling. In: The Euromicro conference on real-time systems Thekkilakattil A, Dobrin R, Punnekkat S (2013) Quantifying the sub-optimality of non-preemptive real-time scheduling. In: The Euromicro conference on real-time systems
Zurück zum Zitat Ward B, Thekkilakattil A, Anderson J (2014) Optimizing preemption-overhead accounting in multiprocessor real-time systems. In: The international conference on real-time networks and systems Ward B, Thekkilakattil A, Anderson J (2014) Optimizing preemption-overhead accounting in multiprocessor real-time systems. In: The international conference on real-time networks and systems
Zurück zum Zitat Yao G, Buttazzo G, Bertogna M (2010) Comparitive evaluation of limited preemptive methods. In: The international conference on emerging technologies and factory automation Yao G, Buttazzo G, Bertogna M (2010) Comparitive evaluation of limited preemptive methods. In: The international conference on emerging technologies and factory automation
Metadaten
Titel
The limited-preemptive feasibility of real-time tasks on uniprocessors
verfasst von
Abhilash Thekkilakattil
Radu Dobrin
Sasikumar Punnekkat
Publikationsdatum
01.06.2015
Verlag
Springer US
Erschienen in
Real-Time Systems / Ausgabe 3/2015
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-015-9222-3