A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> SMART, a technique for providing predictable cache performance for real-time systems with priority-based preemptive scheduling, is presented. The technique is implemented in a R3000 cache design. The value density acceleration (VDA) cache allocation algorithm is also introduced, and shown to be suitable for run-time cache allocation. > <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> The MIPS R6000 microprocessor relies on a new type of translation lookaside buffer — called a TLB slice — which is less than one-tenth the size of a conventional TLB and as fast as one multiplexer delay, yet has a high enough hit rate to be practical. The fast translation makes it possible to use a physical cache without adding a translation stage to the processor's pipeline. The small size makes it possible to include address translation on-chip, even in a technology with a limited number of devices. The key idea behind the TLB slice is to have both a virtual tag and a physical tag on a physically-indexed cache. Because of the virtual tag, the TLB slice needs to hold only enough physical page number bits — typically 4 to 8 — to complete the physical cache index, in contrast with a conventional TLB, which needs to hold both a virtual page number and a physical page number. The virtual page number is unnecessary because the TLB slice needs to provide only a hint for the translated physical address rather than a guarantee. The full physical page number is unnecessary because the cache hit logic is based on the virtual tag. Furthermore, if the cache is multi-level and references to the TLB slice are “shielded” by hits in a virtually indexed primary cache, the slice can get by with very few entries, once again lowering its cost and increasing its speed. With this mechanism, the simplicity of a physical cache can been combined with the speed of a virtual cache. <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> When a computer system supports both paged virtual memory and large real-indexed caches, cache performance depends in part on the main memory page placement. To date, most operating systems place pages by selecting an arbitrary page frame from a pool of page frames that have been made available by the page replacement algorithm. We give a simple model that shows that this naive (arbitrary) page placement leads to up to 30% unnecessary cache conflicts. We develop several page placement algorithms, called careful-mapping algorithms , that try to select a page frame (from the pool of available page frames) that is likely to reduce cache contention. Using trace-driven simulation, we find that careful mapping results in 10–20% fewer (dynamic) cache misses than naive mapping (for a direct-mapped real-indexed multimegabyte cache). Thus, our results suggest that careful mapping by the operating system can get about half the cache miss reduction that a cache size (or associativity) doubling can. <s> BIB003 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> Cache memories have become an essential part of modern processors to bridge the increasing gap between fast processors and slower main memory. Until recently, cache memories were thought to impose unpredictable execution time behavior for hard real-time systems. But recent results show that the speedup of caches can be exploited without a significant sacrifice of predictability. These results were obtained under the assumption that real-time tasks be scheduled non-preemptively.This paper introduces a method to maintain predictability of execution time within preemptive, cached real-time systems and discusses the impact on compilation support for such a system. Preemptive systems with caches are made predictable via software-based cache partitioning. With this approach, the cache is divided into distinct portions associated with a real-time task, such that a task may only use its portion. The compiler has to support instruction and data partitioning for each task. Instruction partitioning involves non-linear control-flow transformations, while data partitioning involves code transformations of data references. The impact on execution time of these transformations is also discussed. <s> BIB004 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> This paper presents a new technique, compiler-directed page coloring, that eliminates conflict misses in multiprocessor applications. It enables applications to make better use of the increased aggregate cache size available in a multiprocessor. This technique uses the compiler's knowledge of the access patterns of the parallelized applications to direct the operating system's virtual memory page mapping strategy. We demonstrate that this technique can lead to significant performance improvements over two commonly used page mapping strategies for machines with either direct-mapped or two-way set-associative caches. We also show that it is complementary to latency-hiding techniques such as prefetching.We implemented compiler-directed page coloring in the SUIF parallelizing compiler and on two commercial operating systems. We applied the technique to the SPEC95fp benchmark suite, a representative set of numeric programs. We used the SimOS machine simulator to analyze the applications and isolate their performance bottlenecks. We also validated these results on a real machine, an eight-processor 350MHz Digital AlphaServer. Compiler-directed page coloring leads to significant performance improvements for several applications. Overall, our technique improves the SPEC95fp rating for eight processors by 8% over Digital UNIX's page mapping policy and by 20% over a page coloring, a standard page mapping policy. The SUIF compiler achieves a SPEC95fp ratio of 57.4, the highest ratio to date. <s> BIB005 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> Data caches are essential in modern processors, bridging the widening gap between main memory and processor speeds. However, they yield very complex performance models, which make it hard to bound execution times tightly. This paper contributes a new technique to obtain predictability in preemptive multitasking systems in the presence of data caches. We explore the use of cache partitioning, dynamic cache locking, and static cache analysis to provide worst-case performance estimates in a safe and tight way. Cache partitioning divides the cache among tasks to eliminate inter-task cache interferences. We combine static cache analysis and cache locking mechanisms to ensure that all intra-task conflicts, and consequently, memory access times, are exactly predictable. To minimize the performance degradation due to cache partitioning and locking, two strategies are employed. First, the cache is loaded with data likely to be accessed so that their cache utilization is maximized. Second, compiler optimizations such as tiling and padding are applied in order to reduce cache replacement misses. Experimental results show that this scheme is fully predictable, without compromising the performance of the transformed programs. Our method outperforms static cache locking for all analyzed task sets under various cache architectures, with a CPU utilization reduction ranging between 3.8 and 20.0 times for a high performance system. <s> BIB006 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> The last line of defense in the cache hierarchy before going to off-chip memory is very critical in chip multiprocessors (CMPs) from both the performance and power perspectives. We investigate different organizations for this last line of defense (assumed to be L2 in this article) towards reducing off-chip memory accesses. We evaluate the trade-offs between private L2 and address-interleaved shared L2 designs, noting their individual benefits and drawbacks. The possible imbalance between the L2 demands across the CPUs favors a shared L2 organization, while the interference between these demands can favor a private L2 organization. We propose a new architecture, called Shared Processor-Based Split L2, that captures the benefits of these two organizations, while avoiding many of their drawbacks. Using several applications from the SPEC OMP suite and a commercial benchmark, Specjbb, on a complete system simulator, we demonstrate the benefits of this shared processor-based L2 organization. Our results show as much as 42.50% improvement in IPC over the private organization (with 11.52% on the average), and as much as 42.22% improvement over the shared interleaved organization (with 9.76% on the average). <s> BIB007 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> Cache hierarchies have been traditionally designed for usage by a single application, thread or core. As multi-threaded (MT) and multi-core (CMP) platform architectures emerge and their workloads range from single-threaded and multithreaded applications to complex virtual machines (VMs), a shared cache resource will be consumed by these different entities generating heterogeneous memory access streams exhibiting different locality properties and varying memory sensitivity. As a result, conventional cache management approaches that treat all memory accesses equally are bound to result in inefficient space utilization and poor performance even for applications with good locality properties. To address this problem, this paper presents a new cache management framework (CQoS) that (1) recognizes the heterogeneity in memory access streams, (2) introduces the notion of QoS to handle the varying degrees of locality and latency sensitivity and (3) assigns and enforces priorities to streams based on latency sensitivity, locality degree and application performance needs. To achieve this, we propose CQoS options for priority classification, priority assignment and priority enforcement. We briefly describe CQoS priority classification and assignment options -- ranging from user-driven and developer-driven to compiler-detected and flow-based approaches. Our focus in this paper is on CQoS mechanisms for priority enforcement -- these include (1) selective cache allocation, (2) static/dynamic set partitioning and (3) heterogeneous cache regions. We discuss the architectural design and implementation complexity of these CQoS options. To evaluate the performance trade-offs for these options, we have modeled these CQoS options in a cache simulator and evaluated their performance in CMP platforms running network-intensive server workloads. Our simulation results show the effectiveness of our proposed options and make the case for CQoS in future multi-threaded/multi-core platforms since it improves shared cache efficiency and increases overall system performance as a result. <s> BIB008 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> The usage of cache memories in time-critical applications has been limited as caches introduce unpredictable execution behavior. Cache partitioning techniques have been developed to reduce the impact of unpredictability owing to context switch effects. However, partitioning reduces the cache size available for each task resulting in capacity related cache misses. This paper introduces a fully associative cache architecture for multi-tasking applications where effective partition sizes are increased by tag compression in the cache. The proposed scheme uses a few don't care cells in its least significant bits of the tag to aggregate multiple tag entries into a single entry. The experimental results indicate that the proposed scheme is context switch resilient when eight different real-time benchmarks use the cache concurrently. Further, this cache architecture requires less time and less energy to perform tag table search compared to contemporary fully associative caches of the same size. <s> BIB009 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> The role of the operating system (OS) in managing shared resources such as CPU time, memory, peripherals, and even energy is well motivated and understood [23]. Unfortunately, one key resource — lower-level shared cache in chip multi-processors — is commonly managed purely in hardware by rudimentary replacement policies such as least-recently-used (LRU). The rigid nature of the hardware cache management policy poses a serious problem since there is no single best cache management policy across all sharing scenarios. For example, the cache management policy for a scenario where applications from a single organization are running under "best effort" performance expectation is likely to be different from the policy for a scenario where applications from competing business entities (say, at a third party data center) are running under a minimum service level expectation. When it comes to managing shared caches, there is an inherent tension between flexibility and performance. On one hand, managing the shared cache in the OS offers immense policy flexibility since it may be implemented in software. Unfortunately, it is prohibitively expensive in terms of performance for the OS to be involved in managing temporally fine-grain events such as cache allocation. On the other hand, sophisticated hardware-only cache management techniques to achieve fair sharing or throughput maximization have been proposed. But they offer no policy flexibility. This paper addresses this problem by designing architectural support for OS to efficiently manage shared caches with a wide variety of policies. Our scheme consists of a hardware cache quota management mechanism, an OS interface and a set of OS level quota orchestration policies. The hardware mechanism guarantees that OS-specified quotas are enforced in shared caches, thus eliminating the need for (and the performance penalty of) temporally fine-grained OS intervention. The OS retains policy flexibility since it can tune the quotas during regularly scheduled OS interventions. We demonstrate that our scheme can support a wide range of policies including policies that provide (a) passive performance differentiation, (b) reactive fairness by miss-rate equalization and (c) reactive performance differentiation. <s> BIB010 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> As part of the trend towards Chip Multiprocessors (CMPs) for the next leap in computing performance, many architectures have explored sharing the last level of cache among different processors for better performance-cost ratio and improved resource allocation. Shared cache management is a crucial CMP design aspect for the performance of the system. This paper first presents a new classification of cache misses - CII: Compulsory, Inter-processor and Intra-processor misses - for CMPs with shared caches to provide a better understanding of the interactions between memory transactions of different processors at the level of shared cache in a CMP. We then propose a novel approach, called set pinning, for eliminating inter-processor misses and reducing intra-processor misses in a shared cache. Furthermore, we show that an adaptive set pinning scheme improves over the benefits obtained by the set pinning scheme by significantly reducing the number of off-chip accesses. Extensive analysis of these approaches with SPEComp 2001 benchmarks is performed using a full system simulator. Our experiments indicate that the set pinning scheme achieves an average improvement of 22.18% in the L2 miss rate while the adaptive set pinning scheme reduces the miss rates by an average of 47.94% as compared to the traditional shared cache scheme. They also improve the performance by 7.24% and 17.88% respectively. <s> BIB011 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> Multi-core architectures consisting of multiple processing cores on a chip have become increasingly prevalent. Synthesizing hard real-time applications onto these platforms is quite challenging, as the contention among the cores for various shared resources leads to inherent timing unpredictability. This paper proposes the use of shared cache in a predictable manner through a combination of locking and partitioning mechanisms. We explore possible design choices and evaluate their effects on the worst-case application performance. Our study reveals certain design principles that strongly dictate the performance of a predictable memory hierarchy. <s> BIB012 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> Cache partitioning and sharing is critical to the effective utilization of multicore processors. However, almost all existing studies have been evaluated by simulation that often has several limitations, such as excessive simulation time, absence of OS activities and proneness to simulation inaccuracy. To address these issues, we have taken an efficient software approach to supporting both static and dynamic cache partitioning in OS through memory address mapping. We have comprehensively evaluated several representative cache partitioning schemes with different optimization objectives, including performance, fairness, and quality of service (QoS). Our software approach makes it possible to run the SPEC CPU2006 benchmark suite to completion. Besides confirming important conclusions from previous work, we are able to gain several insights from whole-program executions, which are infeasible from simulation. For example, giving up some cache space in one program to help another one may improve the performance of both programs for certain workloads due to reduced contention for memory bandwidth. Our evaluation of previously proposed fairness metrics is also significantly different from a simulation-based study. The contributions of this study are threefold. (1) To the best of our knowledge, this is a highly comprehensive execution- and measurement-based study on multicore cache partitioning. This paper not only confirms important conclusions from simulation-based studies, but also provides new insights into dynamic behaviors and interaction effects. (2) Our approach provides a unique and efficient option for evaluating multicore cache partitioning. The implemented software layer can be used as a tool in multicore performance evaluation and hardware design. (3) The proposed schemes can be further refined for OS kernels to improve performance. <s> BIB013 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> Cache partitioning techniques have been proposed in the past as a solution for the cache interference problem. Due to qualitative differences with general purpose platforms, real-time embedded systems need to minimize task real-time utilization (function of execution time and period) instead of only minimizing the number of cache misses. In this work, the partitioning problem is presented as an optimization problem whose solution sets the size of each cache partition and assigns tasks to partitions such that system worst-case utilization is minimized thus increasing real-time schedulability. Since the problem is NP-Hard, a genetic algorithm is presented to find a near optimal solution. A case study and experiments show that in a typical real-time embedded system, the proposed algorithm is able to reduce the worst-case utilization by 15% (on average) if compared to the case when the system uses a shared cache or a proportional cache partitioned environment. <s> BIB014 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <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> BIB015 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <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> BIB016 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <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, cache analysis is mandatory. The subject-matter of this article is the static analysis of the tree-based PLRU cache replacement policy (pseudo least-recently used), for which the precision of analyses lags behind those of other policies. We introduce the term subtree distance, which is important for the update behavior of PLRU and closely linked to the peculiarity of PLRU that allows cache contents to be evicted in “logarithmic time”. Based on an abstraction of subtree distance, we define a must-analysis that is more precise than prior ones by excluding spurious logarithmic-time eviction. <s> BIB017 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> Modern real-time embedded systems are moving from federated architectures, where logical applications and subsystems are implemented on different hardware components, to progressively more integrated architectures which use extensive sharing of different physical resources. These systems employ multiple active components, such as CPU cores, HW processors, coprocessors and peripherals, which can all autonomously perform computational and communication activities. Furthermore, they are increasingly built using Commercial Off-The-Shelf (COTS) components in an attempt to increase performance and reduce cost and time to market. ::: Integrated real-time systems such as those employed in the avionic, medical and automotive domain are often mixed-criticality systems: they implement different applications with widely varying levels of criticality. Therefore, a key issue is to provide sufficient isolation among different applications. In particular, safety-critical applications can expose requirements both in terms of functional isolation, e.g. fault containment, and in terms of physical isolation, e.g. safe sharing of physical resources such as CPU and communication time, memory and power. ::: In this work, we study the design of mechanisms and policies to support both functional and physical isolation, with a special focus on timing guarantees. In particular, since most available COTS components do not provide sufficient hardware isolation mechanisms, we propose the concept of a control abstraction: an unintrusive hardware device or software layer that is interposed between a COTS component and the rest of the system, allowing the system architect to predictably control all its resource accesses. By employing control abstractions, unverified COTS components can be used to implement low-criticality but high-performance applications, while still providing all required isolation guarantees to safety-critical modules. Functional isolation is provided by monitoring the run-time communication behavior of the component against a formal specification, and taking a recovery action whenever the specification is violated. Timing isolation is provided by coscheduling all computational and communication activities in such as way that there is no contention for access to system resources. ::: We show the validity of our methodology by applying it to two different embedded architectures. For System-on-Chip architectures, we detail a complete platform-based design process that automatically generates control abstractions for all integrated processors from a high-level functional system specification. We test the described design process on the case study of a medical pacemaker. ::: For COTS-based computational nodes, we focus on the contention between CPU tasks and peripherals for access both to shared communication infrastructures such as PCI and to main memory. Our experiments show that main memory interference can greatly increase the worst-case execution time of a task, up to almost 200% for a dual core system with a single PCIe peripheral. To overcome this issue, we propose both analysis techniques to compute upper bounds on the worst-case task delay, as well as hardware and software control abstractions to reduce such delay. In particular, we detail the design and implementation of a new hardware device, the real-time bridge, which is interposed between each COTS peripheral and the PCI bus. The real-time bridge buffers all incoming/outgoing traffic to/from the peripheral, and delivers it predictably according to a defined schedule. Furthermore, we propose to execute CPU tasks according to a new PRedictable Execution Model (PREM), which uses a combination of compiler techniques and OS modifications to precisely control all main memory accesses performed by a task. By combining PREM with the real-time bridge, we can coschedule all accesses in main memory by both peripherals and tasks, thus eliminating low-level contention and unpredictable access delays. Our experiments show reductions in worst-case execution time up to 40%-60% compared to a traditional execution model. <s> BIB018 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> Shared cache partitioning is a well-known technique used in multicore real-time systems to isolate task workloads and improve system predictability. Presently, the state-of-the-art studies that evaluate shared cache partitioning on multicore processors lack two key issues. First, the cache partitioning mechanism is typically implemented either in a simulation environment or in a general-purpose OS, and so the impact of kernel activities, such as interrupt handlers and context switching, on the task partitions tend to be overlooked. Second, the evaluation is typically restricted to either a global or partitioned scheduler, thereby by falling to compare the performance of cache partitioning when tasks are scheduled by different schedulers. In this work, we design and implement a shared cache partitioning mechanism in a multicore component-based RTOS capable of assigning partitions to internal OS data structures, including task and system stacks and interrupt handlers data. We evaluate our shared cache partitioning mechanism running task sets under global (G-EDF) and partitioned (P-EDF) multicore real-time scheduling algorithms. Our results indicate that a lightweight RTOS does not impact real-time tasks, and shared cache partitioning has different behavior depending on the scheduler and the task's working set size. <s> BIB019 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <s> Although most previous work in cache analysis for WCET estimation assumes the LRU replacement policy, in practise more processors use simpler non-LRU policies for lower cost, power consumption and thermal output. This paper focuses on the analysis of FIFO, one of the most widely used cache replacement policies. Previous analysis techniques for FIFO caches are based on the same framework as for LRU caches using qualitative always-hit/always-miss classifications. This approach, though works well for LRU caches, is not suitable to analyze FIFO and usually leads to poor WCET estimation quality. In this paper, we propose a quantitative approach for FIFO cache analysis. Roughly speaking, the proposed quantitative analysis derives an upper bound on the "miss ratio" of an instruction (set), which can better capture the FIFO cache behavior and support more accurate WCET estimations. Experiments with benchmarks show that our proposed quantitative FIFO analysis can drastically improve the WCET estimation accuracy over pervious techniques (the average overestimation ratio is reduced from around 70% to 10% under typical setting). <s> BIB020 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Hard/Soft real-time OS index-based partitioning. MC <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> BIB021
2 treats memory colors as shared resources to which accesses must be arbitrated by either a real-time locking protocol or a scheduling algorithm  . The OS associates a set of colors to each task. With the locking mechanism, a job must acquire a lock for each color it needs before execution, and it releases these locks when it finishes execution. Thus, the job entire execution is treated as a critical section, which may create a long priority inversion blocking. To mitigate this problem, the authors propose period splitting and job splitting as two ways to reduce the detrimental effect of lengthy critical sections. However, this may cause jobs to reload their working sets. Unlike the locking mechanism described above, the cache colors can be treated as preemptive resources in which the concurrent accesses can be mediated by scheduling. Instead of dealing with a scheduling problem over two preemptive resources (the processor and the cache), the authors reduce the problem into uniprocessor scheduling. They define a logical cache processor to whom they assign tasks that share either cache colors or processor. They then evaluated the schedulability of each cache processor as a uniprocessor and apply known schedulability tests. The authors compared both techniques in terms of schedulability of the Partitioned Rate-Monotonic (P-RM) algorithm and concluded that cache-locking approach is better than the scheduling approach. The target real-time system is composed of HRT and SRT tasks. Gracioli and Fröhlich uses page coloring to create application and OS heaps composed of only pages with the same colors BIB019 . User-level memory requests are served by application heaps, while OS-level memory requests are served by the OS heap. Thus, the work evaluated the cache interference caused by the RTOS into the schedulability of real-time tasks (SRT or HRT). For a lightweight RTOS, cache partitioning reduces cache interference in a level that applications are not delayed. The authors also proposed a user-level memory allocation mechanism. Hard real-time compiler index-based partitioning. BIB004 was the first to introduce compiler support for cache partitioning in the context of real-time systems. The compiler receives as additional inputs the cache size and the partition size of a task. The final object files are separated in code and data partitions for each task and are combined into an executable by the linker. To deal with code partitions larger than the partition size, the compiler inserts at the end of each code partition an unconditional jump to the next code partition. According to BIB004 , "Each partition is stored in a separate object file, which may be padded with no-ops at the end to extend it to the exact size given by the cache partition size. Global data is split into memory partitions of the data cache partition size. The compiler ensures that no data structure spans multiple partitions. If the size of a data structure exceeds the cache partition size, it is split over multiple partitions and the compiler needs to transform the access to the data structure." Local data on the stack is split into partitions by manipulating the stack pointer whenever necessary BIB004 . Dynamic allocation on the heap is supported as long as memory requests do not exceed the cache partition size BIB004 . OSs and libraries are also treated as separated partitions. The used cache partition mechanism is based on page coloring and the approach targets uniprocessor real-time systems. BIB006 used compiler techniques together with cache partitioning and locking to improve the predictability in preemptive multitasking uniprocessor systems in the presence of data caches. The proposed predictable framework works both with hardware or software cache-partitioning schemes. The compiler technique uses loop tiling and padding to reduce capacity and conflict misses, that is, it reduces intratask interference. Loop tiling reorders accesses, which shortens the reuse distance, while padding modifies the data layout of arrays and data structures. Cache locking is used to lock cache lines that are accessed by more than one task. The authors compared the proposed framework with static cache locking in which all tasks share the whole cache in terms of worst-case performance of a multitasking system. The results indicated that framework schedules tasks that need a high throughput. Cache Replacement Policy Analysis. In general, most discussed index-based partitioning methods are mainly concerned with avoiding intracore and/or intercore interference, by assigning disjoint index sets to either different tasks on a given core or to different cores. However, if locking is not used, a task can still suffer from intratask interference: loading a memory block of the task in an assigned associative set could cause another memory block in the same associative set to be evicted. To bound the number of such self-evictions that a task can suffer, a significant amount of effort has been spent to analyze the effects of various cache replacement policies in the context of static WCET analysis for HRT systems (e.g., see  for LRU, BIB016 and BIB020 for FIFO, and BIB017 for PLRU). Based on the seminal work in  , such techniques typically try to classify memory accesses in cache as either hits or misses by constructing must and may sets of memory blocks: at any given point in time, the must set represents the set of memory blocks that are known to be in cache, while the may set represents the set of blocks that may be in cache. Then, accesses to blocks in the must set can be safely categorized as hits, accesses in the complementary of the may set are misses, and accesses that are in neither are unknown. A related problem is to determine the maximum number of memory blocks that can be utilized in cache without conflicts BIB018 ]. For instance, a task cannot safely allocate more than one memory block per set with a random replacement policy, since otherwise in the worst case, fetching one block of the task could always evict another block in the same associative set. On the other hand, for an n-way associative cache, both LRU and FIFO allow a task to safely allocate n blocks per set, that is, the task can utilize the entire cache size. Table I summarizes the discussed index-based cache-partitioning works that rely on hardware-specific implementations. The works proposed by BIB007 , BIB011 , BIB008 , and BIB010 , although focused on multicore systems, were not proposed for real-time systems and, consequently, predictability is not the main concern. Instead, they aim at improving the QoS and the average execution time. However, they could be applied to SRT systems as well. SMART was the first hardware-based implementation of a cache mechanism designed to provide predictability for uniprocessors BIB001 . The SMART approach consists of dividing the cache into M segments and assigning these segments individually to tasks. A cache location address is divided in a segment and cache ID fields that identify how many segments a task owns and which they are. BIB009 were the first authors to propose a hardware-based implementation of a cache-partitioning mechanism to improve the predictability of multicore systems. Their approach focused on physical changes, using different technologies (CAM and TCAM cells) to implement cache memories. BIB012 were the first authors to combine a cache-partitioning mechanism that can be implemented in hardware or software with cache locking. In their work, the cache-partitioning mechanism performs task-based and core-based partitioning. Table II summarizes the discussed index-based cache-partitioning works that use a software approach, either implemented in the OS or in the compiler. The first works to use cache partitioning implemented in the OS did not focus on multicore real-time systems BIB002 BIB003  ; Sherwood et al. . Instead, their objectives were to improve the average performance in uniprocessors. Also, several works improved the average performance in multicore systems  BIB013 ].  was the first author to use a cache-partitioning mechanism to improve the predictability in uniprocessors. The work proposed by  was the first to use page coloring, also in the context of uniprocessor real-time systems. BIB014 proposed a genetic algorithm to optimize the worst-case system utilization by finding the best cache-partitioning assignment for a task set. BIB015 proposed a cache-aware multicore scheduling algorithm that uses page coloring. BIB021 used page coloring to propose a cache management scheme that assigns to each core a set of partitions.  proposed the cache management strategy called MC 2 , which treats the management of cache lines as scheduling and synchronization problems, targeting a realtime system formed by HRT and SRT tasks. All the discussed works so far used an OS implementation of a cache-partitioning mechanism based on page coloring. Other works proposed changes in the compiler to support cache partitioning at the compile time. BIB004 was the first author to introduce a compiler support for cache partitioning in the context of uniprocessor real-time systems. BIB005 implemented page coloring support in the SUIF parallelizing compiler targeting multicore processors. Both Bugnion et al. and Mueller's approaches used page coloring to partition the cache. Finally, BIB006 used compiler techniques together with cache partitioning and locking to improve the predictability in preemptive multitasking uniprocessor systems in the presence of data caches. The mechanism relies on a hardware/software cache partitioning and was the first compiler-based mechanism to combine cache partitioning with cache locking.