A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> WCET Derivation <s> The determination of upper bounds on execution times, commonly called worst-case execution times (WCETs), is a necessary step in the development and validation process for hard real-time systems. This problem is hard if the underlying processor architecture has components, such as caches, pipelines, branch prediction, and other speculative components. This article describes different approaches to this problem and surveys several commercially available tools1 and research prototypes. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> WCET Derivation <s> Chip multicore processors (CMPs) have emerged as the dominant architecture choice for modern computing platforms and will most likely continue to be dominant well into the foreseeable future. As with any system, CMPs offer a unique set of challenges. Chief among them is the shared resource contention that results because CMP cores are not independent processors but rather share common resources among cores such as the last level cache (LLC). Shared resource contention can lead to severe and unpredictable performance impact on the threads running on the CMP. Conversely, CMPs offer tremendous opportunities for mulithreaded applications, which can take advantage of simultaneous thread execution as well as fast inter thread data sharing. Many solutions have been proposed to deal with the negative aspects of CMPs and take advantage of the positive. This survey focuses on the subset of these solutions that exclusively make use of OS thread-level scheduling to achieve their goals. These solutions are particularly attractive as they require no changes to hardware and minimal or no changes to the OS. The OS scheduler has expanded well beyond its original role of time-multiplexing threads on a single core into a complex and effective resource manager. This article surveys a multitude of new and exciting work that explores the diverse new roles the OS scheduler can successfully take on. <s> BIB002
The main objective of cache management schemes for real-time systems is to deal with the described problems, simplifying the estimation of the tasks' WCET. WCET estimation typically follows one of two main approaches: static analysis or empirical measurement BIB001 . In the former approach, a tool attempts to provide the WCET by analyzing the application binary code without executing it directly on the hardware. Generally, WCET estimation tools are available only for simple processors, due to sophisticated hardware features, such as caches, branch predictors and pipelines, which make the static analysis extremely difficult or overly pessimistic BIB001 . In the latter approach, the application binary code is executed on the hardware platform for multiple times, and an estimation of the WCET with an adjustable confidence is extracted from these executions. Moreover, in measurementbased approaches, the resulting value of WCET is typically inflated further with an error margin (20% to 30% the observed value) in order to account for unobserved conditions that can delay the execution. Consequently, measurement-based approaches can also lead to overestimated WCET. The use of caches makes both static and measurement-based WCET estimation more complex because the execution time of an instruction may vary depending on (a) the data/instruction location in the memory hierarchy; (b) if a memory access results in a miss or a hit in any of the cache levels; (c) which cache coherence protocol is being used in case of true or false sharing; and (D) which cache replacement policy is implemented on the cache controller BIB002 . Note that while several real-time cache analysis frameworks have been proposed for single-core systems BIB001 , current static analysis methodologies provide pessimistic bounds on cache misses for shared caches. Furthermore, to the best of our knowledge, no existing static analysis technique is able to account for the coherence protocol effects. Note that, even if WCET estimation is possible, the presence of intercore interference greatly complicates validation and certification of multicore real-time systems. Allowing hardware components of commodity multicore platforms to operate in an unrestricted manner makes it significantly harder to provide temporal and spatial isolation for systems that demand such isolation (avionics for instance). In fact, if no predictable arbitration mechanism for shared resources is in place, the pessimism on task WCET can easily result to be unacceptable. This problem has been recognized by the Certification Authorities Software Team (CAST), an international group of avionics certification and regulatory representatives from North and South America, Europe, and Asia [Certification Authorities Software Team (CAST) 2014].