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

S. Altmeyer, R.I. Davis, C. Maiza

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)499-526
Number of pages28
JournalReal-Time Systems
Issue number5
Publication statusPublished - Sept 2012


  • cache related preemption delay
  • CRPD
  • fixed priority
  • schedulability analysis
  • real-time
  • uniprocessor

Cite this