Will Lunniss
Sebastian Altmeyer
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. While one solution is to flush the cache after every application context switch, this can potentially lead to a degradation in performance. 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.
- Altmeyer, S., Davis, R.I., and Maiza, C. Cache Related Preemption Delay Aware Response Time Analysis for Fixed Priority Pre-emptive Systems. In Proceedings of the 32nd IEEE Real-Time Systems Symposium (RTSS) (Vienna, Austria 2011), 261--271. Google Scholar
Digital Library
- Altmeyer, S., Davis, R.I., and Maiza, C. Improved Cache Related Pre-emption Delay Aware Response Time Analysis for Fixed Priority Pre-emptive Systems. Real-Time Systems, 48, 5 (September 2012), 499--512. Google ScholarDigital Library
- ARINC. ARINC 651: Design Guidance for Integrated Modular Avionics. Airlines Electronic Engineering Committee (AEEC), 1991.Google Scholar
- ARINC. ARINC 653: Avionics Application Software Standard Interface (Draft 15). Airlines Electronic Engineering Committee (AEEC), 1996.Google Scholar
- Åsberg, M., Behnam, M., and Nolte, T. An Experimental Evaluation of Synchronization Protocal 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 2013). Google ScholarDigital Library
- Audsley, N. C., Burns, A., Richardson, M., and Wellings, A.J. Applying new Scheduling Theory to Static Priority Preemptive Scheduling. Software Engineering Journal, 8, 5 (1993), 284--292.Google Scholar
- Bastoni, A., Brandenburg, B., and Anderson, J. Cache-Related Preemption and Migration Delays: Empirical Approximation and Impact on Schedulability. In Proceedings of OSPERT (Brussels, Belgium 2010), 33--44.Google Scholar
- Behnam, M., Shin, I., Nolte, T., and Nolin, M. 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) (2007), 279--288. Google ScholarDigital Library
- Bini, E. and Buttazzo, G. Measuring the Performance of Schedulability Tests. Real-Time Systems, 30, 1 (2005), 129--154. Google ScholarDigital Library
- Busquets-Mataix, J. V., Serrano, J. J., Ors, R., Gil, P., and Wellings, A. 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) (1996), 204--212. Google ScholarDigital Library
- Davis, R. I. and Burns, A. An Investigation into Server Parameter Selection for Hierarchical Fixed Priority Preemptive Systems. In Proceedings 16th International Conference on Real-Time and Network Systems (RTNS) (Renne, France 2008), 19--28.Google Scholar
- Davis, R. I. and Burns, A. Hierarchical Fixed Priority Preemptive Scheduling. In Proceedings of the 26th IEEE Real-Time Systems Symposium (RTSS) (2005). Google ScholarDigital Library
- Davis, R. I. and Burns, A. Resource Sharing in Hierarchical Fixed Priority Pre-Emptive Systems. In Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS) (Rio de Janeiro, Brazil 2006), 257--270. Google ScholarDigital Library
- Davis, R. I., Zabos, A., and Burns, A. Efficient Exact Schedulability Tests for Fixed Priority Real-Time Systems. IEEE Transactions on Computers, 57, 9 (September 2008), 1261--1276. Google ScholarDigital Library
- Deng, Z. and Liu, J. W. S. Scheduling Real-Time Applications in Open Environment. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS) (San Francisco, USA 1997). Google ScholarDigital Library
- Feng, X. and Mok, A. K. A Model of Hierarchical Real-Time Virtual Resources. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS) (Austin, TX, USA 2002), 26--35. Google ScholarDigital Library
- Kuo, T-W. and Li, C-H. A Fixed Priority Driven Open Environment for Real-Time Applications. In Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS) (Madrid, Spain 1998). Google ScholarDigital Library
- Lee, C., Hahn, J., Seo, Y. et al. Analysis of Cache-related Preemption Delay in Fixed-priority Preemptive Scheduling. IEEE Transactions on Computers, 47, 6 (June 1998), 700--713. Google ScholarDigital Library
- Lipari, G. and Bini, E. A Methodology for Designing Hierarchical Scheduling Systems. Journal of Embedded Computing, 1, 2 (December 2005), 257--269. Google ScholarDigital Library
- Lunniss, W., Altmeyer, S., and Davis, R. I. Optimising Task Layout to Increase Schedulability via Reduced Cache Related Pre-emption Delays. In In proceedings of the International Conference on Real-Time Networks and Systems (RTNS) (Pont à Mousson, France 2012), 161--170. Google ScholarDigital Library
- Lunniss, W., Altmeyer, S., Lipari, G., and Davis, R. I. Accounting for Cache Related Pre-emption Delays in Hierarchical Scheduling. Technical Report YCS-2014-491 Available from http://www-users.cs.york.ac.uk/~wlunniss/, University of York, York, 2014.Google ScholarDigital Library
- Lunniss, W., Altmeyer, S., Maiza, C., and Davis, R. I. 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 2013), 75--84. Google ScholarDigital Library
- Richter, K. Compositional Scheduling Analysis Using Standard Event Models. PhD Dissertation, Technical University Carolo-Wilhelmina of Braunschweig, 2005.Google Scholar
- Saewong, S., Rajkumar, R., Lehoczky, J., and Klein, M. Analysis of Hierarchical Fixed Priority Scheduling. In Proceedings of the 14th Euromicro Conference on Real-Time Systems (ECRTS) (Vienna, Austria 2002), 173--181. Google ScholarDigital Library
- Shin, I. and Lee, I. Periodic Resource Model for Compositional Real-Time Guarantees. In Proceedings of the 24th IEEE Real-Time Systems Symposium (RTSS) (Cancun, Mexico 2003), 2--13. Google ScholarDigital Library
- Staschulat, J., Schliecker, S., and Ernst, R. Scheduling Analysis of Real-Time Systems with Precise Modeling of Cache Related Preemption Delay. In In Proceedings 17th Euromicro Conference on Real-Time Systems (ECRTS) (Balearic Islands, Spain 2005), 41--48. Google ScholarDigital Library
- Tan, Y. and Mooney, V. Timing Analysis for Preemptive Multitasking Real-Time Systems with Caches. ACM Transactions on Embedded Computing Systems (TECS), 6, 1 (February 2007). Google ScholarDigital Library
- Watkins, C. B. and Walter, R. Transitioning from Federated Avionics Architectures to Integrated Modular Avionics. In Proceedings of the 26th IEE/AIAA Digital Avionics Systems Conference (DASC) (2007).Google ScholarCross Ref
- Xu, M., Phan, L. T.X., Lee, I., Sokolsky, O., Xi, S., Lu, C., and Gill, C. Cache-Aware Compositional Analysis of Real-Time Multicore Virtualization Platforms. In Proceedings of the 34th IEEE Real-Time Systems Symposium (RTSS) (Vancouver, Canada 2013). Google ScholarDigital Library
Index Terms
- Accounting for Cache Related Pre-emption Delays in Hierarchical Scheduling
Recommendations
Cache related pre-emption delays in hierarchical scheduling
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 ...
Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems
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 ...
Fixed priority scheduling with pre-emption thresholds and cache-related pre-emption delays: integrated analysis and evaluation
Commercial off-the-shelf programmable platforms for real-time systems typically contain a cache to bridge the gap between the processor speed and main memory speed. Because cache-related pre-emption delays (CRPD) can have a significant influence on the ...
Comments