Head-First Memory Allocation on Best-Fit with Space-Fitting
Adam Noto Hakarsa






  Harvard University
  Cambridge
  MA
  USA

adb819@g.harvard.edu



§ ABSTRACT 
Although best-fit is known to be slow, it excels at optimizing memory space utilization. Interestingly, by keeping the free memory region at the top of the memory, the process of memory allocation and deallocation becomes approximately 34.86% faster while also maintaining external fragmentation at minimum.





Head-First Memory Allocation on Best-Fit with Space-Fitting
    Adam Noto Hakarsa
    September 9, 2024
===========================================================







§ INTRODUCTION


Memory management is a fundamental part of any robust operating system <cit.>. Architecturally, this is because CPU must cooperate with the memory <cit.>, which is currently the fastest and cheapest storage medium next to the register. Even if such architectural limitations were absent, memory management would still be essential because it is generally impractical for any program to accurately estimate its memory needs in advance, hence the need for dynamic memory allocation. Speed, too, matters as 30-60% of programs spend their execution time in allocating dynamic memory <cit.>. The fact that main memory is limited in size further underscores the importance of memory management.

From an OS perspective, memory management typically involves a linked list to keep track of memory usage. Several dynamic memory management algorithms, simply referred to as allocator, operate on this large chunk of space, among which the most commonly reviewed are first-fit, next-fit, best-fit, and quick-fit. 

The first-fit algorithm scans the memory from the beginning until it finds the first free segment large enough for the request <cit.>. The next-fit algorithm operates similarly, except it starts scanning from the point where it stopped last time <cit.>. In contrast, the best-fit algorithm searches the entire list to find the smallest free segment that meets the request <cit.>. Alternatively, the quick-fit algorithm maintains lists of memory segments of specific sizes and, upon receiving an allocation request, searches the list of segments closest in size to the requested one <cit.>.

The choice of an allocation algorithm is a compromise between efficient use of memory and low allocation overhead <cit.>. This is why first-fit and best-fit are popular, especially since it does not require computing statistical distributions or maintaining an extraneous data structure which requires an additional time and space.



§ BACKGROUND


Due to its simplicity, the first-fit and next-fit algorithms may result in memory waste through internal fragmentation, which occurs when the allocated block is larger than the requested size, leaving some space within the block unused. Consequently, best-fit or quick-fit algorithms are often preferred because they aim to allocate the smallest possible block. However, these algorithms still suffer from external fragmentation. This type of fragmentation can prevent the operating system from allocating memory even if sufficient free space exists. Techniques such as compaction, coalescing, segmentation, and paging attempt to address this issue. Despite this, best-fit is effective in optimizing the use of limited memory space. Therefore, we aim to explore a simple technique to expedite the best-fit algorithm.



§ ALGORITHM


Our allocator does not have a minimum allocation size, although blocks must always be located at addresses that are multiples of eight (double word) to ensure compatibility with systems such as Sun workstations <cit.>. Each allocated memory block includes a bookkeeping structure that records essential data. We have minimized the size of this bookkeeping structure to 16KB, storing only key information: whether the block is free, the block’s owner process ID, the block’s addressable space size, and a link to the previous block in the chain. This link is necessary because, although we can move forward using pointer arithmetic, we cannot move backward since we do not know the size of the block to the left.

It is important to note that the best-fit algorithm alone can lead to increased external fragmentation. To address this issue, we employ functions such as  and , which we will discuss in detail later. The allocation process is managed by a function called . We have observed that a small change in the  implementation can significantly speed up the memory allocation process, which we will demonstrate later.



 §.§ Allocation


The process to assign an area in memory to a program is called (storage) allocation <cit.>. Such a process may fail for reasons such as the lack of free block to accommodate the request.





The two algorithms are evidently very similar to each other, except that in the head-first algorithm, we do not call , unlike in Algorithm <ref> at line 10. Additionally, the  function (or macro) ensures that memory blocks are aligned on a double-word boundary.

The  algorithm simply partitions a block into 2 smaller block, as long as the partition results in a usable memory block that can fit the initial request.



With or without , we employ space-fitting to reduce external fragmentation by calling . This function calculates the extra, redundant bytes and then transfers them to any possible adjacent block or carves a new one if possible.



The space-fitting process operates as follows: after identifying a block that is significantly larger than required, any extra bytes are transferred to the right-hand block if it is free. If only the left-hand block is free, the extra bytes are transferred there. In the rare case where neither block is free, the block will divide itself as long as no resulting block has zero addressable space. If none of these options are viable, the block remains as-is.

Lastly,  is a simple function that attempts to coalesce free blocks from the bottom to the top. This process can result in a larger block by combining several free blocks. Without coalescing, it is possible that a user might request memory that no single block can serve unless some blocks are stitched together.



 §.§ Deallocation


The  function as demonstrated by Algorithm <ref> returns a status indicating whether the block is freed (), un-freed because it wasn't allocated to begin with (), or un-freed because the block is owned by another process (). It accepts  which points to a region of memory previously allocated by the  function.





§ SIMULATION


When the memory is initialized, its underlying linked list will be laid out in the following manner:



The position, denoted as  starts counting from zero. The  represents the memory address accessible by the user. While  accounts for the bookkeeping struct, the  does not; thus, it refers to the addressable allocated memory that can be read, written, and freed. The  indicates the memory block to its left-hand side in the chain. The  field indicates whether a block is currently reserved or not. The  field reports the size of the addressable bytes. When aggregating the , the sum will be smaller than the total free memory space in the kernel-fresh state due to overhead from the bookkeeping structs created for each memory block.

It is easy to distinguish head-first from otherwise the non head-first allocation. In the head-first implementation, the unallocated region of the memory can be seen at the top as evident from table <ref>.



On a non head-first implementation, the unallocated region is at the bottom of the list, as evident from table <ref>.



If we want to allocate 8 bytes of memory using the best-fit strategy, we would scan the linked list to find the smallest block that can accommodate at least 8 bytes. In a non head-first approach, we would split the block located at position 48 to create the required allocation.



However, on a head-first implementation, we don't need to traverse the list. Since the unallocated memory is at the top, we can simply request a new block that immediately fits the request, as evident from table <ref>.



In both implementations, a block will be merged with its right-hand or left-hand buddy whenever possible to minimizes external fragmentation. Therefore, according to Table <ref>, freeing the 32-byte block results in a larger block of size 128 bytes. The size is 128 bytes instead of 112 bytes because we only need one overhead struct for each memory block. Hence, any redundant bookkeeping structs get dissolved to be a part of the addressable space.







§ BENCHMARK TEST


Our benchmark test suite aims to execute  rounds of memory allocation and deallocation requests, with each allocation not exceeding 1,024 bytes. Each request is handled by a separate thread to simulate multiprocessing scenarios. We randomize both the number of bytes to allocate, and whether to allocate or deallocate at any given time. Consequently, each trial may result in a different state of the linked list, while the total CPU time remains quite consistent across different trials. It is noteworthy that the number of allocation and deallocation requests are pretty well balanced.

We record the results of executing the non head-first best-fit algorithm with space-fitting in Table <ref>. It illustrates the number of requests performed, the execution time, the percentage of successful memory allocations and deallocations, and the total external fragmentation in bytes. The entire memory is initialized to a size of 16 megabytes.




Table <ref> illustrates the experiment on head-first best-fit with space-fitting. In addition, it shows the improvement of execution time in percentage over the experiment illustrated by Table <ref>.



Demonstrably, the same best-fit mechanism produces different results under different operation modes, namely head-first and non head-first. We observe a significant improvement in execution time with the head-first mechanism, while also maintaining, if not improving, algorithm effectiveness.



§ FUTURE WORKS


We compare head-first versus non head-first specifically for the best-fit algorithm. We can investigate whether similar benefits apply to other memory allocation algorithms such as first-fit, next-fit, worst-fit, as well as other algorithms like fast-fits <cit.> and half-fit <cit.>. Additionally, benchmarking on real-world examples, as demonstrated in <cit.>, can provide further insights and practical applicability.



§ CONCLUSION


We compared two best-fit implementations that are only slightly different from one another. Our benchmark has shown that operating in head-first mode, where the free unallocated region is kept near the head of the memory, speeds up best-fit operations.



ACM-Reference-Format

