A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache Interferences <s> The major obstacle to use multicores for real-time applications is that we may not predict and provide any guarantee on real-time properties of embedded software on such platforms; the way of handling the on-chip shared resources such as L2 cache may have a significant impact on the timing predictability. In this paper, we propose to use cache space isolation techniques to avoid cache contention for hard real-time tasks running on multicores with shared caches. We present a scheduling strategy for real-time tasks with both timing and cache space constraints, which allows each task to use a fixed number of cache partitions, and makes sure that at any time a cache partition is occupied by at most one running task. In this way, the cache spaces of tasks are isolated at run-time. As technical contributions, we have developed a sufficient schedulability test for non-preemptive fixed-priority scheduling for multicores with shared L2 cache, encoded as a linear programming problem. To improve the scalability of the test, we then present our second schedulability test of quadratic complexity, which is an over approximation of the first test. To evaluate the performance and scalability of our techniques, we use randomly generated task sets. Our experiments show that the first test which employs an LP solver can easily handle task sets with thousands of tasks in minutes using a desktop computer. It is also shown that the second test is comparable with the first one in terms of precision, but scales much better due to its low complexity, and is therefore a good candidate for efficient schedulability tests in the design loop for embedded systems or as an on-line test for admission control. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache Interferences <s> Schedulability analysis for hard real-time systems requires bounds on the execution times of its tasks. To obtain useful bounds in the presence of caches, static timing analyses must predict cache hits and misses with high precision. For caches with least-recently-used (LRU) replacement policy, precise and efficient cache analyses exist. However, other widely used policies like first-in first-out (FIFO) are inherently harder to analyze. The main contributions of this paper are precise and efficient must- and may-analyses of FIFO based on the novel concept of static phase detection. The analyses statically partition sequences of memory accesses as they will occur during program execution into phases. If subsequent phases contain accesses to the same (similar) set of memory blocks, each phase contributes a bit to the overall goal of predicting hits (misses). The new must-analysis is significantly more precise than prior analyses. Both analyses can be implemented space-efficiently by sharing information using abstract LRU-stacks. <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Cache Interferences <s> Many modern multi-core processors sport a large shared cache with the primary goal of enhancing the statistic performance of computing workloads. However, due to resulting cache interference among tasks, the uncontrolled use of such a shared cache can significantly hamper the predictability and analyzability of multi-core real-time systems. Software cache partitioning has been considered as an attractive approach to address this issue because it does not require any hardware support beyond that available on many modern processors. However, the state-of-the-art software cache partitioning techniques face two challenges: (1) the memory co-partitioning problem, which results in page swapping or waste of memory, and (2) the availability of a limited number of cache partitions, which causes degraded performance. These are major impediments to the practical adoption of software cache partitioning. In this paper, we propose a practical OS-level cache management scheme for multi-core real-time systems. Our scheme provides predictable cache performance, addresses the aforementioned problems of existing software cache partitioning, and efficiently allocates cache partitions to schedule a given task set. We have implemented and evaluated our scheme in Linux/RK running on the Intel Core i7 quad-core processor. Experimental results indicate that, compared to the traditional approaches, our scheme is up to 39% more memory space efficient and consumes up to 25% less cache partitions while maintaining cache predictability. Our scheme also yields a significant utilization benefit that increases with the number of tasks. <s> BIB003
The execution time of a real-time task in a multicore processor 1 can be affected by a number of different types of interference, depending on the behavior of the cache hierarchy: -Intratask interference: Intratask interference occurs when tasks have their working set sizes larger than a specific cache level, or, in general, when two memory entries in the working set are mapped in the same cache set. The consequence in this case is that a task evicts its own cache lines. Intratask interference also happens in single-core systems. -Intracore interference: Intracore interference happens locally in a core. 2 Specifically, when a preempting task evicts the preempted task's cached data. As a result, the preempted task will experience an increase in its data access time (and thus a delay) as soon as it is rescheduled. The severity of the experienced delay depends on the particular cache line replacement policy implemented by the cache, as well as the length of the preemption and the data access pattern of the preempting task  BIB002 BIB003 ]. -Intercore interference: Intercore interference is present when tasks running on different cores concurrently access a shared level of cache BIB003 . When this happens, if two lines in the two addressing spaces of the running tasks map to the same cache line, said tasks can repeatedly evict each other in cache, leading to complex timing interactions and thus unpredictability. Intercore interference can also occur due to Simultaneous Multithreading (SMT), when two or more hardware threads share the same private cache levels (L1 and/or L2). Since this type of interference is suffered by tasks that can run in parallel, an exact analysis requires analyzing all the possible interleaving of task executions. This combinatorial problem is clearly intractable; thus, intercore interference results extremely difficult to integrate into a static analysis framework BIB001 ]. Furthermore, memory accesses originating from a core can be classified as either demand accesses, if required by instructions executed on the core, or prefetch accesses, if speculatively issued by a hardware prefetcher unit. Although important for the average performance of the system, it is common practice (in real-time systems) to disable hardware prefetchers to eliminate prefetch interference, thus making the processor more predictable. Hence, in this survey, we assume that prefetchers are disabled and do not cause additional interference. In Section 7, we discuss open issues and future directions considering also the usage of prefetchers in real-time systems.