Staschulat, J: Instruction and Data Cache Timing Analysis

associative instruction caches at a context switch. The preemption delays are calculated by considering the preempted as well as the preempting task. The proposed schedulability analysis bounds the number of preemptions more tightly by excluding infeasible cache interferences. The analysis is conservative, e.g. determines a safe upper bound of the preemption delay, and has a low time complexity. As a refinement, the cache interference by multiple task preemptions is analyzed. While previous approaches calculate the worst-case preemption point and assume that each preemption takes place at this preemption point, we consider the preemption history in the calculation of the total cost for multiple task preemptions. The advantage is that the bound of the total preemption delay for multiple task preemptions can consider the preemption history. Execution time verification is often used on different levels of the system design. Less precise estimates are acceptable in early design stages while highly accurate ones are necessary for verification of hard real time constraints. Two approaches to bound the preemption delay have been proposed which both use data flow techniques but differ significantly in respect to time-complexity and analysis precision. In this thesis we combine these two approaches in a single scalable precision cache analysis to scale the analysis precision and the time-complexity. In an automotive case study we found out that control intensive applications designed with ASCET-SD and Matlab/Simulink models contain only sequential code without loops. Caches cannot increase the performance for such applications because linear code significantly limits the spacial and temporal locality of memory accesses for which a cache is optimized. Existing timing analyses focus on a single task execution. However, embedded applications are activated very frequently if not regularly. Cache lines from a previous task activation might still be available in the cache and need not be loaded during a subsequent task execution. This effect of multiple task execution can result in a significantly reduced number of cache misses. In this thesis we estimate a conservative bound of the cache contents at the beginning of task activation and consider the effect in instruction cache timing behavior. While previous analysis techniques focus on instruction caches, we also provide a novel timing analysis for data caches. Data cache behavior is more difficult to predict because it depends on control flow of the application but also on the input data. While instruction addresses are fixed, a single instruction can access different data memory addresses, for example operations on an array. In this thesis we propose a static timing analysis for data caches which considers input data dependency of memory accesses. Finally, we integrate instruction and data cache timing analysis in a measurement-based WCET-analysis tool, which has been developed in previous work. Measuring the execution time requires insertion of instrumentation points which disturbs the temporal behavior of an application. In this thesis we present a novel instrumentation methodology that reduces the number of instrumentation points. In summary, this thesis provides a sophisticated framework to analyze instruction and data cache effects for fixed priority preemptive real-time systems.