A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Time-Predictable Allocators <s> The predictability of the computation time of program modules is very important for estimating an accurate worst-case execution time (WCET) of a task in real-time systems. Dynamic storage allocation (DSA) is a common programming technique. Although many DSA algorithms have been developed, they focus on the average execution time rather than the WCET, making it is very difficult to calculate their WCET accurately. In this paper, we propose a new algorithm called Half-Fit whose WCET can be calculated accurately. The algorithm finds a free block without searching on a free list or tree, allowing extra unusable memory called incomplete memory use. In a simulation following a queueing model of M/G//spl infin/, Half-Fit has the advantage over the binary buddy system of more efficient storage utilization. The binary buddy system is a conventional algorithm whose WCET can be calculated. <s> BIB001 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Time-Predictable Allocators <s> Dynamic memory management is an important aspect of modern software engineering techniques. However developers of real-time systems avoid using it because they fear that the worst-case execution time of the dynamic memory allocation routines is not bounded or is bounded with an excessively large bound. The degree to which this concern is valid is quantified in this paper by giving detailed average and worst-case measurements of the timing performance of a comprehensive panel of dynamic memory allocators. For each allocator we compare its worst-case behavior obtained analytically with the worst timing behavior observed by executing real and synthetic workloads, and with its average timing performance. The results provide a guideline to developers of real-time systems to choose whether to use dynamic memory management or not, and which dynamic allocation algorithm should be preferred from the viewpoint of predictability. <s> BIB002 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Time-Predictable Allocators <s> Dynamic storage allocation (DSA) algorithms play an important role in the modern software engineering paradigms and techniques (such as object oriented programming). Using DSA increases the flexibility and functionalities of applications. There exists a large number of references to this particular issue in the literature. However, the use of DSA has been considered a source of indeterminism in the real-time domain, due to the unconstrained response time of DSA algorithms and the fragmentation problem. Nowadays, real-time applications require more flexibility: the ability to adjust system configuration in response to workload changes and application reconfiguration. This aspect adds value to the definition and implementation of dynamic storage allocation algorithms. Considering these reasons, DSA algorithms with a bounded and acceptable timing behaviour must be developed to be used by real-time operating systems (RTOSs). In this paper a DSA algorithm called two-level segregated fit memory allocator (TLSF), developed specifically to be used by RTOS, is introduced. The TLSF algorithm provides explicit allocation and deallocation of memory blocks with a temporal cost /spl Theta/(1). <s> BIB003 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Time-Predictable Allocators <s> Real-Time applications can require dynamic storage management. However this feature has been sistematically avoided due to the general belief about the poor performance of allocation and deallocation operations in time and space. Actually, the use of Java technologies in real-time require to analyse in detail the performance of this feature due to its intensive use. In a previous paper, the authors proposed a new dynamic storage allocator that perform malloc and free operations in constant time (O(1)) with a very high efficiency. In this paper, we compare the behaviour of several allocators under "real-time" loads measuring the temporal cost and the fragmentation incurred by each allocator. In order to compare the temporal cost of the allocators, two parameters have been considered: number of instructions and processor cycles. To measure the fragmentation, we have calculated the relation between the maximum memory used by the each allocator relative to the point of the maximum amount of memory used by the load. Additionally, we have measured the impact of delayed deallocation in a similar way a periodic garbage collector server will do. The results of this paper show that TLSF allocator obtains the best resuts when both aspects, temporal and spatial are considered. <s> BIB004 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Time-Predictable Allocators <s> We propose a real real-time memory management system called Compact-fit that offers both time and space predictability. Compact-fit is a compacting memory management system for allocating, deallocating, and accessing memory in real time. The system provides predictable memory fragmentation and response times that are constant or linear in the size of the request, independently of the global memory state. We present two Compact-fit implementations and compare them to established memory management systems, which all fail to provide predictable memory fragmentation. The experiments confirm our theoretical complexity bounds and demonstrate competitive performance. In addition, we can control the performance versus fragmentation trade-off via our concept of partial compaction. The system can be parameterized with the needed level of compaction, improving the performance while keeping memory fragmentation predictable. <s> BIB005 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Time-Predictable Allocators <s> Current worst-case execution time (WCET) analyses do not support programs using dynamic memory allocation. This is mainly due to the unpredictable cache performance when standard memory allocators ::: are used. We present algorithms to compute a static allocation for programs using dynamic memory allocation. Our algorithms strive to produce static allocations that lead to minimal WCET times in a subsequent WCET analyses. Preliminary experiments suggest that static allocations for hard real-time applications can be computed at reasonable computational costs. <s> BIB006 </s> A Survey on Cache Management Mechanisms for Real-Time Embedded Systems <s> Time-Predictable Allocators <s> General-purpose dynamic memory allocation algorithms strive for small memory fragmentation and good av\-er\-age-case response times. Hard real-time settings, in contrast, place different demands on dynamic memory allocators: worst-case response times are more important than av\-er\-age-case response times. Furthermore, predictable cache behavior is a prerequisite for timing analysis to derive tight bounds on a program's execution time. This paper proposes a novel algorithm that meets these demands. It guarantees constant response times, does not cause unpredictable cache pollution, and allocations are cache-set directed, i.e., allocated memory is guaranteed to be mapped to a given cache set. The latter two are necessary to enable a subsequent precise static cache analysis. <s> BIB007
The Half-fit algorithm was the first dynamic memory allocator to perform allocation/deallocation in a constant and predictable time BIB001 . In Half-fit, free blocks of size in the range [2 i , 2 i+1 ) are grouped into a free list indexed by i. When a block is deallocated, it is immediately merged with neighboring free blocks. After merging, the index of the new free block of size r in a free list bit vector can be found using i = log 2 r . This logarithm operation in a bit vector can be executed in one cycle in several 32-bit CPUs. Half-fit eliminates the search on free lists for allocation by calculating the index i and taking a free block of memory from the list i. If the list i is empty, the allocation algorithm takes a block from the subsequent nonempty list whose index is closest to i. If allocated blocks are larger than request sizes, the allocated block is split in two parts: one is returned to the requester and another one is relinked on the free list. The allocation/deallocation time complexity is O(1) BIB001 . Two-Level Segregated Fit (TLSF) memory allocator uses a segregated fit mechanism and implements a good-fit policy BIB003 . TLSF limits the size of memory to be allocated in 16 bytes. It also uses the space of free blocks to store management information, such as pointers to next blocks. TLSF uses an array of free lists, which each list (accessed by a specific array position) holds free blocks within a size class. The array of lists is organized in two levels to speed up the access to free blocks and to reduce fragmentation. The first level divides free blocks in classes that are power of 2 (16, 32, 64, 128, etc.) , and the second level subdivides each first-level class linearly, where the number of divisions is a user configurable parameter. As in Half-fit, a bitmap is used to identify empty lists and lists with free blocks. The boundary tag, used by TLSF, adds a pointer to the beginning of the same block to each free or used block. Thus, this pointer is used to locate the previous physical memory block and free or merge it when a block is released BIB003 . Hence, each free block is linked in the segregated list and in a list ordered by physical address. Both allocation and deallocation have time complexity of O(1) BIB003 .  proposed the TLSF-I, an improved version of the TLSF algorithm. TLSF-I aims at improving the efficiency in allocating small blocks and reduce fragmentation of the original TLSF algorithm. The authors used different strategies to allocate blocks of memory depending on their sizes. When the size of a block is small, TLSF-I uses exact-fit policy instead of good-fit. To maintain an exact fit table, TLSF-I uses a two-level occupancy bitmap. When a memory block to be allocated has a small size, the algorithm uses the bitmap to to verify if that block fits in a free list. If it does not, the algorithm searches in the bitmap tree to find an available block. Comparative results have shown that TLSF-I has a better performance than TLSF and presented lower fragmentation  . Compact-FIT (CF) is a predictable memory allocation/deallocation system BIB005 . CF has a constant memory fragmentation rate and a linear response time, considering the size of a memory allocation request. Available memory in CF is partitioned in 16KB pages. Then, pages are further partitioned into same-sized pageblocks class. When an allocation request arrives, the algorithm searches the page of the smallest-sized class that is able to serve the request. The allocation of data larger than 16KB is not supported. CF aims at compacting the memory size-class whenever possible, allowing at most 1 page of each size-class to be not-full at a given moment. When data is released, it is moved to keep the consistency in the size-class BIB005 . There are two implementation of CF: "In the moving CF implementation, page-blocks are mapped directly to physically contiguous pieces of memory, which requires moving data memory for compaction. In this implementation, allocation takes constant time and deallocation takes linear time if compaction occurs. In the nonmoving implementation, a block table is used to map page-blocks into physical block-frames that can be located anywhere in memory. Compaction in this case is performed by re-programming the block table rather than moving data" BIB005 . Both allocation and deallocation in the nonmoving implementation take liner time. The authors compared CF with TLSF in terms of fragmentation. CF has presented a more controlled and predictable fragmentation than TLSF. In terms of allocation/deallocation time, Half-fit and TSLF are faster than CF due to compaction activities. A completely different approach for time analysis of dynamic memory allocation is proposed by BIB006 . The authors propose algorithms that transform dynamic memory allocations into static memory, aiming at minimizing the WCET in a subsequent WCET analyses BIB006 . In order to allow the transformation from dynamic to static allocation, assumptions are made. For instance, loop bounds and requested block sizes must be statically known BIB007 . Good performance is only achieved when dynamic allocations are statically derived, which may not be true for every application or may be limited by the hardware platform (i.e., when it has limited memory). BIB002 presented a performance analysis of several general-purpose memory allocators (first-fit, best-fit, btree-best-fit, fast-fit, quick-fit, buddy-bin, and buddy-fibo) with respect to real-time requirements. By comparing the worst-case performance of allocation and deallocation of memory blocks in two scenarios (analyically and running real and synthetic workloads), the author has concluded that "for applications with low allocation rates, the analytically worst-case times do not have an excessive impact on the application execution times for the most predictable allocators (buddy systems and quick-fit)" BIB002 ]. More recently, BIB004 compared the first-fit, best-fit, binarybuddy  ], DLmalloc  , Half-fit, and TLSF memory allocators for real-time applications. Results have indicated that TLSF and Half-fit can be used by real-time applications due to stable and bounded response times. In contrast, algorithms designed to optimize AVG execution times, such as DLmalloc and binary-buddy, are not suitable for real-time applications. Half-fit achieves bounded response times wasting more memory than TLSF BIB004 ].