Abstract
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
2
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.
The remainder of this thesis is composed of the following chapters: ∙ In “Introduction” we present in more details the delays introduced
by preemption and present a historical prespective of the problem. In addition we quantify the influence of CRPD on the WCET with references to related publications and our measurements. Furthermore we investigate several parameters that influence these delays such as cache size, memory access patterns, number of devices linked to the bus and their traffic profile.
∙ In “Simulated system” we present the simulated environment. First we describe the MPARM simulator with particular attention to the ac-curacy of simulation and the statistics it can provide. Furthermore we provide a quick overview of the statistics that the simulator can pro-vide. Later we describe the Erika real-time operating system, present-ing the overall architecture and describpresent-ing the typical field of usage. In addition we describe our efforts to port Erika to the simulated hard-ware and to improve their integration. These enhancements allowed us to obtain better and easier to interpret simulation results.
∙ In “State of the art” we present the existing techniques to provide firm bounds to the CRPD. First we present the currently most used techniques such as cache locking, cache partitioning, use of scratchpad memories. The majority of these approaches require special hardware (cache partitioning can be implemented in software) and all of them are ad-hoc solutions requiring manual tweaking while implementing the system. Furthermore, in this chapter we describe the static timing analysis of the code, highlighting the information it can provide and what is still unknown. At last we show how we can compute a bound to the number of preemptions required by the most commonly used real-time schedulers (Earliest Deadline First and Rate Monotonic). ∙ In “Limited preemption” we present our approach to improve the
bounds on the delay introduced by preemption on the execution time. First we present advantages of non preemptive scheduling and the limits of this approach. When the system is not schedulable in a non preemptive way we propose a limited preemption approach, where pre-emptions are limited to specific points in the task. With this technique
3 we can compute a bound on the amount of time a task can run with-out permitting preemption and use timing analysis results to place preemption points in the code in locations where we can respect this bound and minimize the total delay introduced by preemption. ∙ In “Simulation results” we implement the limited preemption in
some benchmark task-sets and measure their behaviour in the simu-lated environment comparing results to other approaches.
∙ In “Conclusions” we summarize the results of this work and present some possible future improvements to this research.
