Will Lunniss
Sebastian Altmeyer
ABSTRACT
Cache memories have been introduced into embedded systems to prevent memory access times from becoming an unacceptable performance bottleneck. For hard real-time systems, it is vital that an accurate estimate of the worst-case response time for each task can be determined. Memory and cache are split into blocks containing instructions and data. During a pre-emption, blocks from the pre-empting task can evict those of the pre-empted task. When the pre-empted task is resumed, if it then has to re-load the evicited blocks, cache related pre-emption delays (CRPD) are introduced which then affect the worst-case response times of the task. Because the position of code in memory determines where the code will be placed in cache, different layouts result in different CRPD and worst-case response times for tasks. We introduce an approach that uses simulated annealing to find layouts that minimise the CRPD incurred due to a pre-emption. This in turn reduces the worst-case response times of tasks, which increases the schedulability of the taskset. We use schedulability analysis that captures whether a block will have to be re-loaded after a pre-emption, to drive the algorithm towards a near optimal solution. After explaining our approach, we present a number of experiments which demonstrate its effectiveness for a number of different system, task and cache configurations.
- Altmeyer, S. and Burguière, C. Cache-related Preemption Delay via Useful Cache Blocks: Survey and Redefinition. Journal of Systems Architecture (2010). Google Scholar
Digital Library
- Altmeyer, S., Davis, R. I., and Maiza, C. 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 2011), 261--271. Google ScholarDigital 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
- Arnaud, A. and Puaut, I. Dynamic Instruction Cache Locking in Hard Real-Time Systems. In The 14th International Conference on Real-Time and Network Systems (2006).Google Scholar
- 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, Belgum 2010), 33--44.Google Scholar
- Bertogna, M., Xhani, O., Marinoni, M., Esposito, F., and Buttazzo, G. Optimal Selection of Preemption Points to Minimize Preemption Overhead. In Proceedings of 23rd Euromicro Conference on Real-Time Systems (ECRTS) (Porto, Portugal 2011), 217--227. 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
- Burns, A. Preemptive Priority-Based Scheduling: An Appropriate Engineering Approach. In Advances in Real-Time Systems. 1994. 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
- Campoy, A. M., Ivars, A. P., and Busquets-Mataix, J. V. Dynamic Use of Locking Caches in Multitask, Preemptive Real-Time Systems. In Proceedings of the 15th Triennial World Congress of the International Federation of Automatic Control (Barcelona 2002).Google ScholarCross Ref
- Campoy, A. M., Ivars, A. P., and Busquets-Mataix, J. V. Static Use of Locking Caches in Multitask Preemptive Real-Time Systems. In Proceedings of the IEEE/IEE Real-Time Embedded Systems Workshop (2001).Google Scholar
- Campoy, A. M., Puaut, I., Ivars, A. P., and Busquets-Mataix, J. V. Cache Contents Selection for Statically-locked Instrction Caches: An Algorithm Comparison. In Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS) (Palma de Mallorca, Balearic Islands, Spain 2005), 49--56. 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
- Falk, H. and Kotthaus, H. WCET-driven Cache-aware Code Positioning. In Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES) (Taipei, Taiwan 2011), 145--154. Google ScholarDigital Library
- Gebhard, G. and Altmeyer, S. Optimal Task Placement to Improve Cache Performance. In Proceedings of the 7th ACM & IEEE International Conference on Embedded Software (EMSOFT) (Salzburg, Austria 2007), 259--268. Google ScholarDigital Library
- Gustafsson, J., Betts, A., Ermedah, A., and Lisper, B. The Mälardalen WCET benchmarks -- past, present and future. In Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis (WCET'2010) (Brussels, Belgium September 2010), 137--147.Google Scholar
- Lee, C., Hahn, J., Seo, Y., Min, S., Ha, H., Hong, S., Park, C., Lee, M., and Kim, C. Analysis of Cache-related Preemption Delay in Fixed-priority Preemptive Scheduling. IEEE Transactions on Computers, 47, 6 (June 1998), 700--713. Google ScholarDigital Library
- Lehoczky, J. The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior. In Proceedings of the 10th Real Time Systems Symposium (RTSS) (Santa Monica, California, USA 1989), 166--171.Google Scholar
- Liu, T., Li, M., and Xue, C. J. Instruction Cache Locking for Multi-task Real-Time Embedded Systems. Real-Time Systems, 48, 2 (2011), 166--197. Google ScholarDigital Library
- Lokuciejewski, P., Falk, H., and Marwedel, P. WCET-driven Cache-based Procedure Positioning Optimizations. In Proceedings of the 20th Euromicro Conference on Real-Time Systems (ECRTS) (Prague, Czech Republic 2008), 321--330. Google ScholarDigital Library
- Puaut, I. and Decotigny, D. Low-complexity Algorithms for Static Cache Locking in Multitasking Hard Real-Time Systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS) (2002), 114--123. 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
Index Terms
- Optimising task layout to increase schedulability via reduced cache related pre-emption delays
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 ...
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 ...
Accounting for Cache Related Pre-emption Delays in Hierarchical Scheduling
RTNS '14: Proceedings of the 22nd International Conference on Real-Time Networks and SystemsHierarchical 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 ...
Comments