An Accurate Instruction Cache Analysis Technique for Real-time Systems

An accurate and reliable estimation of a task's worst case execution time (WCET) is crucial for scheduling of real-time tasks. However, instruction caches, which are extensively used in computer systems today, impose a serious problem in analyzing the WCETs of tasks. The problem stems from the fact that the cache hit or miss of an instruction reference can be known only after the worst case execution path has been found and the worst case execution path, on the other hand, can be located only after the cache hit or miss of every instruction reference is known. This cyclic dependency, in many cases, leads to a pessimistic estimation of WCETs. This paper proposes an analysis technique that is immune from the above cyclic dependency and accurately predicts the WCETs of tasks in the presence of instruction caches. The key to the proposed technique is an extension of the timing schema[16] so that the timing variation due to instruction caches can be accurately accounted for. This paper also..