nach oben

Real-Time Systems

Erschienen in:

01.09.2012

Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems

verfasst von: Sebastian Altmeyer, Robert I. Davis, Claire Maiza

Erschienen in: Real-Time Systems | Ausgabe 5/2012

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Without the use of caches the increasing gap between processor and memory speeds in modern embedded microprocessors would have resulted in memory access times becoming an unacceptable bottleneck. In such systems, cache related pre-emption delays can be a significant proportion of task execution times. To obtain tight bounds on the response times of tasks in pre-emptively scheduled systems, it is necessary to integrate worst-case execution time analysis and schedulability analysis via the use of an appropriate model of pre-emption costs.

In this paper, we introduce a new method of bounding pre-emption costs, called the ECB-Union approach. The ECB-Union approach complements an existing UCB-Union approach. We improve upon both of these approaches via the introduction of Multiset variants which reduce the amount of pessimism in the analysis. Further, we combine these Multiset approaches into a simple composite approach that dominates both. These approaches to bounding pre-emption costs are integrated into response time analysis for fixed priority pre-emptively scheduled systems. Further, we extend this analysis to systems where tasks can access resources in mutual exclusion, in the process resolving omissions in existing models of pre-emption delays. A case study and empirical evaluation demonstrate the effectiveness of the ECB-Union, Multiset and combined approaches for a wide range of different cache configurations including cache utilization, cache set size, reuse, and block reload times.

Nächster Artikel Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks

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

The concept of UCBs and ECBs cannot be applied to FIFO or PLRU replacement policies as shown by Burguière et al. (2009).

If all resource accesses are non-pre-emptive, then there are no additional pre-emption costs to be accounted for.

http://www.arm.coms/products/CPUs/families/ARM7Family.html.

Evaluation for constrained deadlines, i.e., D _i∈[C _i;T _I] gives broadly similar results although fewer tasksets are deemed schedulable by all approaches.

The set of ECBs generated may exceed the number of cache sets. In this case, the set of ECBs used within the response time analysis is limited to the number of cache sets. However, for the generation of the UCBs, the original set of ECBs is used.

Altmeyer S, Burguière C (2009) A new notion of useful cache block to improve the bounds of cache-related preemption delay. In: Proceedings ECRTS, pp 109–118

Altmeyer S, Burguière C (2010) Influence of the task model on the precision of scheduling analysis for preemptive systems. In: Proceedings RTSOPS, pp 5–6

Altmeyer S, Maiza C (2011) Cache-related preemption delay via useful cache blocks: survey and redefinition. J Syst Archit 57:707–719 CrossRef

Altmeyer S, Maiza C, Reineke J (2010) Resilience analysis: tightening the crpd bound for set-associative caches. In: Proceedings LCTES, New York, NY, USA. ACM Press, New York, pp 153–162

Altmeyer S, Davis R, Maiza C (2011a) Pre-emption cost aware response time analysis for fixed-priority pre-emptive systems. Tech rep. Available from http://www-users.cs.york.ac.uk/~robdavis/

Altmeyer S, Davis I, Maiza C (2011b) Cache related pre-emption aware response time analysis for fixed priority pre-emptive systems. In: Davis I, Fisher N (eds) Proceedings of the 32nd IEEE real-time systems symposium (RTSS’11), pp 261–271 CrossRef

Audsley N, Burns A, Richardson M, Tindell K, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8:284–292 CrossRef

Baker TP (1991) Stack-based scheduling for realtime processes. Real-Time Syst 3:67–99 CrossRef

Bastoni A, Brandenburg B, Anderson J (2010) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: Proceedings OSPERT, pp 33–44

Bertogna M, Buttazzo G, Marinoni M, Yao G, Esposito F, Caccamo M (2010) Preemption points placement for sporadic task sets. In: Proceedings ECRTS, pp 251–260

Bertogna M, Xhani O, Marinoni M, Esposito F, Buttazzo G (2011) Optimal selection of preemption points to minimize preemption overhead. In: Proceedings of the 2011 23rd Euromicro conference on real-time systems. ECRTS, vol 11. IEEE Computer Society, Washington, pp 217–227 CrossRef

Bini E, Buttazzo G (2005) Measuring the performance of schedulability tests. Real-Time Syst 30:129–154 MATHCrossRef

Burguière C, Reineke J, Altmeyer S (2009) Cache-related preemption delay computation for set-associative caches—pitfalls and solutions. In: Proceedings WCET

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 RTAS, pp 204–212

Davis R, Merriam N, Tracey N (2000) How embedded applications using an rtos can stay within on-chip memory limits. In: Work progress session RTSS

Davis R, Zabos A, Burns A (2008) Efficient exact schedulability tests for fixed priority real-time systems. IEEE Trans Comput 57:1261–1276 MathSciNetCrossRef

Gustafsson J, Betts A, Ermedahl A, Lisper B (2010) The Mälardalen WCET benchmarks—past, present and future OCG, Brussels, pp 137–147

Joseph M, Pandya P (1986) Finding response times in a real-time system. Comput J 29(5):390–395 MathSciNetCrossRef

Keskin U, Bril R, Lukkien J (2010) Exact response-time analysis for fixed-priority preemption-threshold scheduling. In: Proceedings work-in-progress session ETFA

Lee CG, Hahn J, Seo YM, Min S, Ha R, Hong S, Park Y, Lee M, Kim CS (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47(6):700–713 MathSciNetCrossRef

Lundqvist T, Stenström P (1999) Timing anomalies in dynamically scheduled microprocessors. In: Proceedings RTSS, p 12

Marinho J, Nélis V, Petters SM, Puaut I (2012) Preemption delay analysis for floating non-preemptive region scheduling. In: DATE 2012, pp 497–502

Martin S, Minet P, George L (2007) Non pre-emptive fixed priority scheduling with fifo arbitration: uniprocessor and distributed cases. Tech rep, INRIA Rocquencourt

Meumeu Yomsi P, Sorel Y (2007) Extending rate monotonic analysis with exact cost of preemptions for hard real-time systems. In: Proceedings of the 19th Euromicro conference on real-time systems. IEEE Computer Society, Washington, pp 280–290

Petters SM, Farber G (2001) Scheduling analysis with respect to hardware related preemption delay. In: Workshop on real-time embedded systems

Ramaprasad H, Mueller F (2006) Tightening the bounds on feasible preemption points. In: Proceedings RTSS, pp 212–224

Regehr J (2002) Scheduling tasks with mixed preemption relations for robustness to timing faults. In: Proceedings RTSS, pp 315–325

Schneider J (2000) Cache and pipeline sensitive fixed priority scheduling for preemptive real-time systems. In: RTSS’2000, pp 195–204

Sha L, Rajkumar R, Lehoczky JP (1990) Priority inheritance protocols: an approach to real-time synchronization. IEEE Trans Comput 39:1175–1185 MathSciNetCrossRef

Staschulat J, Schliecker S, Ernst R (2005) Scheduling analysis of real-time systems with precise modeling of cache related preemption delay. In: Proceedings ECRTS, pp 41–48

Tan Y, Mooney V (2007) Timing analysis for preemptive multi-tasking real-time systems with caches. ACM Trans Embed Comput Syst 6(1):1210275 CrossRef

Tomiyama H, Dutt ND (2000) Program path analysis to bound cache-related preemption delay in preemptive real-time systems. In: Proceedings CODES, pp 67–71 CrossRef

Wang Y, Saksena M (1999) Scheduling fixed-priority tasks with pre-emption threshold. In: Proceedings RTCSA, pp 328–338

Titel: Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems
verfasst von: Sebastian Altmeyer
Robert I. Davis
Claire Maiza
Publikationsdatum: 01.09.2012
Verlag: Springer US
Erschienen in: Real-Time Systems / Ausgabe 5/2012
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-012-9152-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"