Cache related pre-emption delays in hierarchical scheduling

详细信息    查看全文

• 作者：Will Lunniss ; Sebastian Altmeyer ; Giuseppe Lipari ; Robert I. Davis
• 关键词：Cache related pre ; emption delays ; Hierarchical scheduling ; Fixed priority pre ; emptive scheduling ; Earliest deadline first pre ; emptive scheduling ; Response time analysis
• 刊名：Real-Time Systems
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：52
• 期：2
• 页码：201-238
• 全文大小：2,102 KB
• 参考文献：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–512CrossRef MATH
  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–154CrossRef MATH
  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–1276CrossRef MathSciNet
  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–263CrossRef MATH
  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–713CrossRef MathSciNet
  Leung JY-T, Merrill ML (1980) A note on preemptive scheduling of periodic, real-time tasks. Inf Process Lett 11(3):115–118CrossRef MathSciNet MATH
  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
  Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46–61CrossRef MathSciNet MATH
  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–1258CrossRef MathSciNet
  
• 作者单位：Will Lunniss (1)
  Sebastian Altmeyer (2)
  Giuseppe Lipari (3) (4)
  Robert I. Davis (1)
  
  1. Department of Computer Science, University of York, York, UK
  2. LASSY Group, University of Luxembourg, Luxembourg, Luxembourg
  3. CRIStAL, UMR 9189, Univ. Lille, 59650, Villeneuve d’Ascq, France
  4. IRCICA, USR 3380, 59650, Villeneuve d’Ascq, France
  
• 刊物类别：Computer Science
• 刊物主题：Computer Systems Organization and Communication Networks
  Communications Engineering and Networks
  Special Purpose and Application-Based Systems
  Performance and Reliability
  Control Engineering
  
• 出版者：Springer Netherlands
• ISSN：1573-1383

文摘

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.