Optimising Task Layout to Increase Schedulability via Reduced Cache Related Pre-emption Delays

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.