Memory Allocation Technique for Segregated Free List Based on Genetic Algorithm

Dynamic memory management is an important part of computer systems design. Efficient memory allocation, garbage collection and compaction are becoming increasingly more critical in parallel, distributed and real-time applications. The memory efficiency is related to the fragmentation. Segregation is one of the simplest allocation policies which use a set of free lists, where each list holds blocks of a particular size. When the process requests a memory. The free list for the appropriate size is used to satisfy the request. This paper proposes a scheme to reduce the internal fragmentation of a segregated free list for improving memory efficiency using genetic algorithm (GA) to find the optimal configuration. Because the genetic algorithms (GAs) are largely used in optimization problems, they facilitate a good alternative in problem areas where the number of constraints is too large for humans to efficiently evaluate. This GA is tested under five randomly created workloads to find the best configuration. The results are acceptable when compared with optimal configurations of these workloads. Keyword: Memory allocation, Segregated free list, Genetic algorithm, Crossover, Mutation. Introduction Dynamic memory allocation is a classic problem in computer systems. Typically, we start with a large block of memory (sometimes called a heap). When a user process needs memory, the request is granted by carving a piece out of the large block of memory. The user process may free some of the allocated memory explicitly, or the system will reclaim the memory when the process terminates. At any time the large memory block is split into smaller blocks (or chunks), some of which are allocated to a process (live memory), some are freed (available for future allocations), and some are no-longer used by the process but are not available for allocation (garbage). A dynamic memory management system must keep track of these three types of memory blocks and attempt to efficiently satisfy as many of the process’s requests for memory as possible [1]. Memory allocation schemes can be classified into Sequential Fit, Buddy System and Segregated free list algorithms. The Sequential Fit approach (including First Fit, Best Fit) keeps track of available chunks of memory on a list. Known sequential techniques differ in how they track the memory blocks and how they allocate memory requests from the free blocks. Normally the chunks of memory (or at least the free chunks) are maintained as a Linear Linked list. When a process releases memory, these chunks are added to the free list, either at the end or in place if the list is sorted by addresses; freed chunk may be coalesced with adjoining chunks to form larger chunks of free memory. When an allocation request arrives, the free list is searched until an appropriately sized chunk is found. The memory is allocated either by granting the entire chunk or by splitting the chunk (if the chunk is larger than the requested size). Best Fit methods try to find the smallest chunk that is at least as large as the request. First Fit methods will find the first chunk that is at least as large as the request. Best Fit method may involve delays in allocation while First Fit method may lead to more external fragmentation. If the free list is in address order, newly freed chunks may be combined with its surrounding blocks, leading to larger chunks. However, this requires a “linear” search through the free list when inserting a newly freed block of memory (or when searching for a suitable chunk of memory) [1]. Buddy system algorithm maintains free lists of different sized blocks. When a request for memory is made these free lists are