Optimising task layout to increase schedulability via reduced cache related pre-emption delays

Will Lunniss, Sebastian Altmeyer, Robert I Davis

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


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.
Original languageEnglish
Title of host publicationProceedings of the 20th International Conference on Real-Time and Network Systems
Publication statusPublished - Nov 2012
EventProceedings of the 20th International Conference on Real-Time and Network Systems - Pont a Mousson, France
Duration: 8 Nov 20129 Nov 2012


ConferenceProceedings of the 20th International Conference on Real-Time and Network Systems
CityPont a Mousson


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

Cite this