Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Real-Time Systems
Erschienen in: Real-Time Systems 2/2016

01.03.2016

Cache related pre-emption delays in hierarchical scheduling

Erschienen in: Real-Time Systems | Ausgabe 2/2016

Einloggen

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

search-config
loading …

Abstract

Hierarchical scheduling provides a means of composing multiple real-time applications onto a single processor such that the temporal requirements of each application are met. This has become a popular technique in industry as it allows applications from multiple vendors as well as legacy applications to co-exist in isolation on the same platform. However, performance enhancing features such as caches mean that one application can interfere with another by evicting blocks from cache that were in use by another application, violating the requirement of temporal isolation. In this paper, we present analysis that bounds the additional delay due to blocks being evicted from cache by other applications in a system using hierarchical scheduling when using either a local FP or EDF scheduler.
Vorheriger Artikel Combined task- and network-level scheduling for distributed time-triggered systems

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
The concept of UCBs and ECBs cannot be applied to the FIFO or Pesudo-LRU replacement policies as shown by Burguiere et al. (2009).
 
2
Although we used 12 cache sets in this example, we note that the result obtained is in fact independent of the total number of cache sets.
 
3
Strictly, h(t) is the maximum time required for the server to provide the processing time demand.
 
Literatur
Altmeyer S, Maiza C, Reineke J (2010) Resilience analysis: tightening the CRPD bound for set-associative caches. In: LCTES. New York, USA, pp 153–162
Altmeyer S, Davis RI, Maiza C (2011) Cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. In: Proceedings of the 32nd IEEE Real-Time Systems Symposium (RTSS). Vienna, Austria, pp 261–271
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(5):499–512CrossRefMATH
ARINC (1991) ARINC 651: Design Guidance for Integrated Modular Avionics. Airlines Electronic Engineering Committee (AEEC)
ARINC (1996) ARINC 653: Avionics Application Software Standard Interface (Draft 15). Airlines Electronic Engineering Committee (AEEC)
Åsberg M, Behnam M, Nolte T (2013) An experimental evaluation of synchronization protocol mechanisms in the domain of hierarchical fixed-priority scheduling. In: Proceedings of the 21st International Conference on Real-Time and Network Systems (RTNS). Sophia Antipolis, France
Audsley NC, Burns A, Richardson M, Wellings AJ (1993) Applying new scheduling theory to static priority preemptive scheduling. Softw Eng J 8(5):284–292CrossRef
Baruah SK, Mok AK, Rosier LE (1990a) Preemptive scheduling hard-real-time sporadic tasks on one processor. In: Proceedings of the 11th IEEE Real-Time Systems Symposium (RTSS). Lake Buena Vista, Florida, USA, pp 182–190
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
Bastoni A, Brandenburg B, Anderson J (2010) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: Proceedings of Operating Systems Platforms for Embedded Real-Time applications (OSPERT). Brussels, Belgium, pp 33–44
Behnam M, Shin I, Nolte T, Nolin M (2007) SIRAP: a synchronization protocol for hierarchical resource sharing real-time open systems. In: Proceedings of the 7th ACM & IEEE International Conference on Embedded Software (EMSOFT). pp 279–288
Bini E, Buttazzo G (2005) Measuring the performance of schedulability tests. Real-Time Syst 30(1):129–154CrossRefMATH
Burguière C, Reineke J, Altmeyer S (2009) Cache-related preemption delay computation for set-associative caches—pitfalls and solutions. In: Proceedings of the 9th International Workshop on Worst-Case Execution Time Analysis (WCET). Dublin, Ireland
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: Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium (RTAS). pp 204–212
Campoy AM, Sáez S, Perles A, Busquets JV (2004) Schedulability analysis in the EDF scheduler with cache memories. Lect Notes Comput Sci 2968:328–341CrossRef
Davis RI, Zabos A, Burns A (2008) Efficient exact schedulability tests for fixed priority real-time systems. IEEE Trans Comput 57(9):1261–1276CrossRefMathSciNet
Davis RI, Burns A (2008) An investigation into server parameter selection for hierarchical fixed priority pre-emptive systems. In: Proceedings of the 16th International Conference on Real-Time and Network Systems (RTNS). Rennes, France, pp 19–28
Davis RI, Burns A (2005) Hierarchical fixed priority pre-emptive scheduling. In: Proceedings of the 26th IEEE Real-Time Systems Symposium (RTSS)
Davis RI, Burns A (2006) Resource sharing in hierarchical fixed priority pre-emptive systems. In: Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS). Rio de Janeiro, Brazil, pp 257–270
Deng Z, Liu JWS (1997) Scheduling real-time applications in open environment. In: Proceedings of the IEEE Real-Time Systems Symposium (RTSS). San Francisco, USA
Dertouzos ML (1974) Control robotics: the procedural control of physical processes. In: Proceedings of the International Federation for Information Processing (IFIP) Congress. pp 807–813
Feng X, Mok AK (2002) A model of hierarchical real-time virtual resources. In: Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS). Austin, TX, USA, pp 26–35
Fisher N, Dewan F (2012) A bandwidth allocation scheme for compositional real-time systems with periodic resources. Real-Time Syst 48(3):223–263CrossRefMATH
George L, Rivierre N, Spuri M (1996) Preemptive and non-preemptive real-time uniprocessor scheduling. Technical Report, INRIA
Ju L, Chakraborty S, Roychoudhury A (2007) Accounting for cache-related preemption delay in dynamic priority schedulability analysis. In: Design, Automation and Test in Europe Conference and Exposition (DATE). Nice, France, pp 1623–1628
Kuo T-W, Li C-H (1998) A fixed priority driven open environment for real-time applications. In: Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS). Madrid, Spain
Lee C, Hahn J, Seo Y, Min S, Ha H, Hong S, Park C, Lee M, Kim C (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47(6):700–713CrossRefMathSciNet
Lipari G, Bini E (2005) A methodology for designing hierarchical scheduling systems. J Embed Comput 1(2):257–269
Lipari G, Baruah SK (2000a) Efficient scheduling of real-time multi-task applications in dynamic systems. In: Proceddings of the 6th IEEE Real-Time Technology and Applications Symposium (RTAS). pp 166–175
Lipari G, Carpenter J, Baruah S (2000b) A framework for achieving inter-application isolation in multiprogrammed, hard real-time environments. In: Proceedings of the 21st IEEE Real-Time Systems Symposium (RTSS). Orlando, FL, USA, pp 217–226
Lunniss W, Altmeyer S, Davis RI (2012) Optimising task layout to increase schedulability via reduced cache related pre-emption delays. In: Proceedings of the International Conference on Real-Time Networks and Systems (RTNS). Pont à Mousson, France, pp 161–170
Lunniss W, Altmeyer S, Maiza C, Davis RI (2013) Intergrating cache related pre-emption delay analysis into edf scheduling. In: Proceedings 19th IEEE Converence on Real-Time and Embedded Technology and Applications (RTAS). Philadelphia, USA, pp 75–84
Lunniss W, Altmeyer S, Lipari G, Davis RI (2014a) Accounting for cache related pre-emption delays in hierarchical scheduling. In: Proceedings of the 22nd International Conference on Real-Time Networks and Systems (RTNS). Versailles, France, pp 183–192
Lunniss W, Altmeyer S, Davis RI (2014b) Accounting for cache related pre-emption delays in hierarchical scheduling with local EDF scheduler. In: Proceedings of the 8th Junior Researcher Workshop on Real-Time Computing (JRWRTC). Versailles, France
Richter K (2005) Compositional scheduling analysis using standard event models. PhD Dissertation, Technical University Carolo-Wilhelmina of Braunschweig
Ripoll I, Crespo A, Mok AK (1996) Improvement in feasibility testing for real-time tasks. Real-Time Syst 11(1):19–39CrossRef
Saewong S, Rajkumar R, Lehoczky J, Klein M (2002) Analysis of hierarchical fixed priority scheduling. In: Proceedings of the 14th Euromicro Conference on Real-Time Systems (ECRTS). Vienna, Austria, pp 173–181
Shin I, Lee I (2003) Periodic resource model for compositional real-time guarantees. In: Proceedings of the 24th IEEE Real-Time Systems Symposium (RTSS). Cancun, Mexico, pp 2–13
Spuri M (1996) Analysis of deadline schedule real-time systems. Technical Report, INRIA
Staschulat J, Schliecker S, Ernst R (2005) Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In: Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS). Balearic Islands, Spain, pp 41–48
Tan Y, Mooney V (2007) Timing analysis for preemptive multitasking real-time systems with caches. ACM Trans Embed Comput Syst 6(1):7CrossRef
Watkins CB, Walter R (2007) Transitioning from federated avionics architectures to integrated modular avionics. In: Proceedings of the 26th IEE/AIAA Digital Avionics Systems Conference (DASC)
Xu M, Phan LTX, Lee I, Sokolsky O, Xi S, Lu C, Gill C (2013) Cache-aware compositional analysis of real-time multicore virtualization platforms. In: Proceedings of the 34th IEEE Real-Time Systems Symposium (RTSS). Vancouver, Canada
Zhang F, Burns A (2009) Schedulability analysis for real-time systems with EDF scheduling. IEEE Trans Comput 58(9):1250–1258CrossRefMathSciNet
Metadaten
Titel
Cache related pre-emption delays in hierarchical scheduling
Publikationsdatum
01.03.2016
Erschienen in
Real-Time Systems / Ausgabe 2/2016
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-015-9228-x