Integrating task scheduling and cache locking for real-time embedded systems

Abstract

Caches are commonly used in embedded systems to bridge the increasing speed gap between processors and off-chip memory. In real-time embedded systems, the embedded software consists of a set of concurrent tasks, which are subject to timing constraints such as release times and deadlines. The primary objective in designing such a system is to find a feasible schedule for the task set such that all the timing constraints are met. A basic requirement for finding a feasible schedule is to know the WCET (Worst Case Execution Time) of each task. However, caches make it significantly harder to compute the WCET of a task as it is difficult to know at compile time whether the corresponding data or instruction of each memory access is in the cache or not. To alleviate this problem, modern embedded processors provide hardware support for cache locking, a mechanism used to facilitate the WCET calculation of a task. In order to make efficient use of the cache locking mechanism, the compiler and the operating system need to cooperate closely. The compiler is in charge of selecting code and data as locked cache contents. On the other hand, operating system needs to inform the compiler of the schedule of the task set so that the compiler knows if two tasks can share the same section of a cache. In this thesis, we investigate the problems of I-cache (Instruction cache) locking, D-cache (Data cache) locking, and integrating task scheduling and cache locking for a set of preemptible task with individual release times and deadlines on a multi-core processor with two levels of caches. We propose a set of WCET-aware, dynamic cache locking approaches for I-cache and D-cache for a single task. Furthermore, we propose a novel integrated approach for scheduling the task set and allocating the selected cache contents to the caches.