A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> INTRODUCTION <s> The problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program functions that need guaranteed service. It is shown that an optimum fixed priority scheduler possesses an upper bound to processor utilization which may be as low as 70 percent for large task sets. It is also shown that full processor utilization can be achieved by dynamically assigning priorities on the basis of their current deadlines. A combination of these two scheduling techniques is also discussed. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> INTRODUCTION <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> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> INTRODUCTION <s> Efficient management of shared on-chip resources such as the shared level 2 (L2) cache has become an important problem with the emergence of chip multiprocessors (CMPs). Partitioning the shared cache in chip multiprocessors (CMPs) among concurrently executing applications can provide important benefits such as throughput improvement, fairness guarantees, and quality of service (QoS) enhancements. We pose an interesting related question, which is, if partitioning the shared cache space among concurrently executing threads of the same application can enhance the application performance. We address this problem by identifying and speeding up the slowest thread, also termed as the critical path thread, during each execution interval since the overall performance of a multithreaded application is determined by the critical path thread. To do so, we propose a dynamic, runtime system based, cache partitioning scheme that partitions the shared cache space dynamically among the individual threads of a given application. In a nutshell, we wish to take some cache space away from the faster threads and give it to the critical path thread at each execution interval. We show that speeding up the critical path thread this way, results in overall performance enhancement of the application execution in the long term. Our experimental evaluation indicates that, the proposed dynamic cache partitioning scheme yields benefits up to 15% over a shared cache with no partitions, up to 23% over a statically partitioned cache (private cache) and up to 20% over a throughput-oriented scheme. <s> BIB003 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> INTRODUCTION <s> This survey covers hard real-time scheduling algorithms and schedulability analysis techniques for homogeneous multiprocessor systems. It reviews the key results in this field from its origins in the late 1960s to the latest research published in late 2009. The survey outlines fundamental results about multiprocessor real-time scheduling that hold independent of the scheduling algorithms employed. It provides a taxonomy of the different scheduling methods, and considers the various performance metrics that can be used for comparison purposes. A detailed review is provided covering partitioned, global, and hybrid scheduling algorithms, approaches to resource sharing, and the latest results from empirical investigations. The survey identifies open issues, key research challenges, and likely productive research directions. <s> BIB004 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> INTRODUCTION <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> BIB005
Real-time embedded systems are nowadays present in virtually any environment. Areas such as automotive, avionics, and telecommunications are examples where realtime embedded systems can be vastly found. In a real-time system, the correctness of the system depends not only on its logical behavior but also on the time in which the computation is performed BIB001 . The main distinction is between soft real-time (SRT) and hard real-time (HRT) systems. In both, applications are typically realized as a collection of real-time tasks associated with timing constraints and scheduled according to a chosen scheduling algorithm. However, in an HRT, the loss of a time constraints (i.e., a deadline) may cause uncountable or catastrophic damage, such as human lives or a considerable amount of money. In an SRT, instead, missing a deadline results in just a degradation of the qualify of service (QoS) provided by the system. Hence, in order to provide a correct behavior and a good QoS, real-time embedded applications must be designed to always meet their deadlines. At the same time, the continuous evolution of processor technology, together with its decreasing cost, has enabled multicore architectures (e.g., Symmetric Multiprocessing -SMP) to be also used in the real-time embedded system domain. Besides, real-time embedded applications are demanding more processing power due to the evolution and integration of features that can only be satisfied, in a cost-effective way, by the use of a multicore platform. In an automotive environment, for instance, new safety functionalities like "automatic emergency breaking" and "night view assist" must read and fuse data from sensors, process video streams, and rise warnings when an obstacle is detected on the road under real-time constraints  . This is a typical scenario where an increasing demand for advanced features results in a proportional demand for additional computational power. Moreover, an increase of system functionalities determines additional costs in terms of power consumption, heat dissipation, and space occupation (e.g., wiring)  . Thereby, multicore processors represent a cost-effective solution to decrease the mentioned costs, since the additional computational demand can be allocated on a single processing unit, instead of several processing units spread over the vehicle. In general, the capability of a real-time system to meet its deadline is verified through a schedulability analysis BIB004 . A basic assumption, which is common to all such schedulability analysis techniques, is that an upper bound on the WorstCase Execution Time (WCET) of each task is known. However, deriving safe yet tight bounds on task WCET is becoming increasingly difficult. This is especially true on multicore architectures, because processors (or cores) share hardware resources, such as cache memory hierarchy, buses, DRAM, and I/O peripherals. Therefore, operations performed by one processing unit can result in unregulated contention at the level of any shared resource and thus unpredictably delay the execution of a task running on a different core. One of the main factors for unpredictability, which is also the focus of this survey, is the CPU cache memory hierarchy BIB002 BIB003 BIB005 . CPU caches of a modern multicore typically consist of two or three levels of cache memory placed between the core and the main memory to bridge the gap on the high processor speed and low memory performance. Usually, a smaller Level 1 (L1) cache is private to each core, while a larger Level 2 (L2) and/or a Level 3 (L3) cache is shared among all the cores or a cluster of cores. The last level of cache before the main memory is usually referred as Last-Level Cache (LLC). In case of a cache miss, the requested instruction or data must be brought from the higher levels of cache or from the main memory, occurring in larger execution times. CPU caches are hardware components that are mostly transparent to the programmer and that rely on temporal and space locality of memory accesses to reduce the average execution time of applications. Thereby, they employ a set of heuristics to keep data that are more likely to be accessed in a near future and displace old, nonreferenced entries. At a high level, the heuristic behavior of a cache means that a memory access in the same location throughout the execution of a task may or may not result in a cache hit, depending on the history of the system. In fact, as it will be clear in Section 2.1, the execution pattern of the task itself, of different tasks on the same core, or even of a set of tasks on a different core can impact the cache hit ratio of a given memory access pattern. This means that a complex function of the system history can directly impact the time required by a task to retrieve data from the memory hierarchy, explaining why cache memories are one of the main sources of unpredictability. Also, the memory access behavior of a real-time application is driven by its functionalities. For instance, simple HRT control loops do not demand a high memory bandwidth, while video processing applications demand both memory bandwith and latency. In this work, our focus is on techniques that address conflicts in the allocation of cache lines (spatial contention). However, as multiple cores perform contemporary accesses to the same cache level, contention on the temporal domain can also occur. Although temporal contention can produce nonnegligible effects, we only set our focus on spatial contention for two main reasons. First, because the magnitude of time unpredictability that arises from spatial contention is typically higher than what observable due to temporal contention. This is generally true for embedded multicore systems that are not classified as many-core systems (i.e., up to 16 or 32 cores that do not use complex on-chip networks). Second, because the problem of managing temporal contention at the cache level is not significantly different than DRAM bus management. To cope with a space contention problem, CPU caches need to be directly or indirectly managed according to an allocation scheme. Allocation schemes can exhibit different properties, applicability, and can be more or less effective in protecting the timing behavior of real-time tasks (see Section 2).