Tailored-List and Recombination-Delaying Buddy Systems

Abstract

Two improved variations of the binary buddy system for dynamic memory management, the tailoredlist buddy system (TLBS) and the recombination-delaying buddy system (RDBS), are introduced. In an attempt to save on execution time, these variations do not recombine free buddies every time recombination is possible. In the TLBS recombination is delayed in such a way as to tailor the available free-space lists to the request-size distribution. In the RDBS time is saved by recombining buddies only when larger blocks are unavailable during allocation. Comparative simulation experiments indicate that for not very heavy loads the TLBS is slightly faster than the RDBS, which, in turn, is significantly faster than the traditional system. Since no significant variation has been found among the memory utilizations of the three systems, the TLBS is preferable to the other systems provided that the load is not very heavy and the expected requestsize distribution is at hand. Otherwise, the RDBS is recommended.