Cache Related Pre-emption Delay Aware Response Time Analysis for Fixed Priority Pre-emptive Systems

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Without the use of cache 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 preemption 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 ECBUnion approach complements an existing UCB-Union approach. We combine the two into a simple composite approach that dominates both. These approaches 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 eectiveness of the ECBUnion and combined approaches for a wide range of dierent cache configurations including cache utilization, cache set size, reuse, and block reload times.
Original languageEnglish
Title of host publicationIEEE Real-Time Systems Symposium
Number of pages11
Publication statusPublished - Dec 2011


  • cache related preemption delay
  • CRPD
  • fixed priority
  • schedulability analysis

Cite this