Algorithms for resolving conflicts in dynamic storage allocation
Brenda S. Baker, Dan E. Willard · Journal of the ACM · 1985
In dynamic storage allocation, successive allocation and freeing of blocks normally leads to fragmentation of storage.When a new block is to.beallocated, fragmentation may prevent any single region of available storage from being large enough for the new block, even though the total amount of available space is sufftcient.When such a conflict arises, dynamic storage allocation systems typically require time-consuming garbage collection or they simply break down.This paper investigates strategies for maintaining storage that allow allocation of blocks to proceed in spite of fragmentation conflicts, at the cost of moving some blocks already allocated are investigated.Such a scheme is reasonable only if it can be guaranteed that the cost of moving blocks never becomes too large relative to the size of the.block to be allocated.Two such schemes are described.They are similar to the buddy system in that they always align the left end of a block of size n at a position that is a multiple of 2"005"'.The schemes differ in the criterion for choosing an interval to free up when no interval of the right size is empty: the Not Full (NF) scheme chooses an interval that is not full, while the Not Too Full (NTF) scheme chooses an interval that is at most as full as all of memory.Tight worst-case bounds are obtained for these schemes as a function of the proportion of memory tilled.The results show that the worst-case cost for NF, the simpler of the two schemes, can be much worse than that for NTF when memory is not too full.However, simulations suggest that the average cost may be much less than the worst-case.cost.