Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems
Tóm tắt
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.
Tài liệu tham khảo
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
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
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
Baker TP (1991) Stack-based scheduling for realtime processes. Real-Time Syst 3:67–99
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
Bini E, Buttazzo G (2005) Measuring the performance of schedulability tests. Real-Time Syst 30:129–154
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
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
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
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
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
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
Wang Y, Saksena M (1999) Scheduling fixed-priority tasks with pre-emption threshold. In: Proceedings RTCSA, pp 328–338