Orges Xhani, "Effects of real-time scheduling on cache performance and worst case execution times"
Cache memories in real-time systems can increase performance, but at the
cost of unpredictable behaviour and loose bounds of the worst case execution
time analysis. Preemptive schedulers, while necessary for overall schedulabi-
lity, introduce further uncertainty in such systems because, when resuming
execution after a preemption, a task can find some of the useful cache lines
evicted by the preempting task and suffer further delays (CRPD - cache
related preemption delay) not expected by the static code analysis. These
delays are strictly dependent on the execution environment of the task, such
as the scheduling algorithm and other tasks running in the system. Mean-
while schedulability analysis, essential to guarantee the correct behaviour
of hard real-time systems such as avionic and automotive controllers, re-
quires worst-case bounds on the execution time of each task. It is easy to
see how the CRPD (and therefore WCET) of the tasks and the scheduling
reciprocally depend on each other. Hence providing firm guarantees on the
schedulability of these systems is complex.
In more complex systems, the main processor is not the only master of
the bus: there are several co-processors and direct memory access devices.
In particular in personal computers there are even more than one powerful
general purpose processors. Nowadays these solutions are often used even in
embedded and safety critical systems because of the lower production costs,
earlier time to market and lower power requirements. In these systems the
delay introduced by each cache miss strongly depends on the time needed
to gain access to the bus, hence the worst case execution time depends on
the number and traffic profile of the other DMA devices and on the bus
arbiter. In systems with high bus contention (many and memory intensive
devices) the CRPD can severely increase the WCET and jeopardize system
schedulability. Therefore accurately bounding the number of cache misses
is crucial to ensure the safety of these systems.
In this thesis we observe the cache misses introduced by scheduling and
preemption and their effects. Since the events we are interested in, such as
cache misses and bus access, happen in hardware and at high frequencies,
they are difficult to monitor in real systems. For this reason, to observe
these phenomenons we used a cycle accurate software simulator mimicking
a real hardware architecture and running real software. Furthermore we
report a survey of current state of the art approaches to bound the effects
of the CRPD. In addition we propose a new technique which can, not only
bound, but actually reduce the number of cache misses and thus the WCET
of a task, by limiting the preemptions a task can suffer but still maintaining
the schedulability of the system. Finally we demonstrate the benefits of our
approach by implementing it in the simulation environment.