Performance analyses on the generalised buddy system

For the past three decades, the buddy system has been the method of choice for memory allocation because of its speed and simplicity. However, the sof tware realisation indicates that the buddy system incurs the overhead of in ternal fragmentation, external fragmentation, and memory traffic due to spl itting and coalescing memory blocks. This paper presents a thorough analysi s of the buddy system and its generalised extension, i.e. the generalised b uddy system. All problems associating with the generalised buddy system wil l be extensively investigated. These problems include internal fragmentatio n, boundary and size blind spots that are the major causes for external fra gmentation, and lastly splitting and coalescing overhead that can slow down the system performance. In 1996, Chang and Gehringer introduced the modifi ed buddy system which eliminates two major drawbacks. First, it eliminates the splitting and coalescing overhead associated with the buddy system. Sec ondly, it also eliminates the internal fragmentation by using a new marking algorithm that only allocates a requested size. However, the severity of e xternal fragmentation resulting from boundary and size blind spot remains t o be studied. We propose an extension to the design that can solve existing issues. The extension also includes the first-fit algorithm into hardware domain. Two solutions that can solve the issues of size and boundary blind spots are also proposed. These solutions involve bit shifting to solve the boundary blind spot and the generalised buddy system to solve the size blin d spot. We also present the simulation results of the proposed solutions. T hese results clearly indicate that both the shifting and the generalised bu ddy system yield minimal improvement over the modified buddy system. Howeve r, we believe that for some applications, these approaches enhance memory u tilisation.