A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> CACHE-LOCKING METHODS <s> Locking cache lines in hard real-time systems is a common means of achieving predictability of cache access behavior and tightening as well as reducing worst case execution time, especially in a multitasking environment. However, cache locking poses a challenge for multi-core hard real-time systems since theoretically optimal scheduling techniques on multi-core architectures assume zero cost for task migration. Tasks with locked cache lines need to proactively migrate these lines before the next invocation of the task. Otherwise, cache locking on multi-core architectures becomes useless as predictability is compromised. This paper proposes hardware-based push-assisted cache migration as a means to retain locks on cache lines across migrations. We extend the push-assisted migration model with several cache migration techniques to efficiently retain locked cache lines on a bus-based chip multi-processor architecture. We also provide deterministic migration delay bounds that help the scheduler decide which migration technique(s) to utilize to relocate a single or multiple tasks. This information also allows the scheduler to determine feasibility of task migrations, which is critical for the safety of any hard real-time system. Such proactive migration of locked cache lines in multi-cores is unprecedented to our knowledge. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> CACHE-LOCKING METHODS <s> Multi-core architectures are shaking the fundamental assumption that in real-time systems the WCET, used to analyze the schedulability of the complete system, is calculated on individual tasks. This is not even true in an approximate sense in a modern multi-core chip, due to interference caused by hardware resource sharing. In this work we propose (1) a complete framework to analyze and profile task memory access patterns and (2) a novel kernel-level cache management technique to enforce an efficient and deterministic cache allocation of the most frequently accessed memory areas. In this way, we provide a powerful tool to address one of the main sources of interference in a system where the last level of cache is shared among two or more CPUs. The technique has been implemented on commercial hardware and our evaluations show that it can be used to significantly improve the predictability of a given set of critical tasks. <s> BIB002
Cache locking prevents the eviction of cache lines by marking them as locked until an unlock operation is performed. Cache locking is a hardware-specific feature that it is not present in all of the modern multicore processors. There are two ways to lock a cache content: (a) through an atomic instruction to fetch and lock a given cache line into the cache or (b) defining, that is, for each single CPU in the system, the lock status of every cache way. The last mechanism is called lockdown by master in multicore systems BIB002 . Some embedded multicore platforms feature only an atomic instruction, such as Freescale P4040 and P4080 platforms, while other platforms, such as TI OMAP4460 and OMAP4430, Nvidia Tegra 2 and 3, Xilinx Zynq-7000, and Samsung Exynos 4412, implement a lockdown by master mechanism. To exemplify the utility of a cache-locking mechanism, consider a dual-core platform with a 2-way set-associative cache and a cache controller that implements a lockdown by master mechanism. We could set up the hardware so that way 1 is unlocked for CPU 1 and locked for CPU 2, while way 2 is locked for CPU 1 and unlocked for CPU 2. This means that a task running on CPU 1 would deterministically allocate blocks on way 1 and blocks allocated on way 1 could never be evicted by a task running on CPU 2. The same situation occurs on way 2 referring to CPU 2. This assignment can be easily changed at runtime by manipulating a set of registers provided by the cache controller interface. If the platform provides an atomic instruction to fetch and lock a cache line, a software procedure that realizes a mechanism functionally equivalent to the lockdown by master can be easily built BIB002 . Hence, cache locking provides a more predictable and controllable access to shared caches, easing the WCET estimation and improving the performance of real-time applications. We classify the works that use cache locking as hardware-only, when a specific hardware design is proposed, or hardware-software approaches, when the hardware available on current multicore processors is used by a software layer (RTOS, compiler, or specific algorithms for instance). We further state if the work provides a cache locking only for instruction caches, data caches, or both caches and if the work targets only SRT systems, HRT systems, or both.  . Then, the MT sorts the block addresses in descending order of the cache miss numbers. The proposed MT-based scheme was evaluated through the simulation of an 8-core processor with two levels of cache using the MPEG4 and H.264 decoding and FFT algorithms. The results have shown a predictability improvement in all algorithms. This technique can be applied to either SRT or HRT systems. BIB001 proposed a predictable task migration scheme using cache locking for the PFair scheduling algorithm, targeting HRT systems. The authors proposed several cache migration models in the presence of a cache-locking mechanism to deterministically bound the migration delay of tasks. The work uses the push model hardware feature, where every cache controller has a push logic block and each cache line has an identifier. When a task migrates, the new core receives a push request to start loading the cache lines for that task. Then, the modified hardware identifies locked lines pertaining to the migrated task and uses the cache line identifier to correctly manage locked cache lines. Simulation results have shown a reduction of the migration cost of up to 56%.