Releasing an Area

To release an area of size , we first examine its buddy to see if it is reserved or free. If the area and its buddy are both free, the two free areas can be combined into a single area of size . We then repeat the process to release the combined area of size . Eventually we get an area whose buddy is reserved or, if k=m, the area does not have a buddy. When this occurs, we simply insert the area into the appropriate free list. Program  shows how this algorithm can be implemented.

  
Program: BuddyPool Class Release Member Function Definition

The Release member function of the BuddyPool class takes a pointer to the user part of a reserved area and it frees the area as described above. The Release function begins by determining the block which corresponds to the given area and checking that this block is indeed a part of the memory pool (lines 3-7). Then the block is marked free (line 9).

Each iteration of the main loop (lines 11-19) determines whether the buddy of the area to be released is also free and combines the two areas as needed. The buddy of the area is determined by calling the private member function Buddy (line 13). This function takes as its lone argument a reference to the first block of the area whose buddy we seek. The Buddy function returns a reference to the first block of the buddy. (Since the size of the block, k, is found in the block itself, it is not necessary to pass it as a parameter to the Buddy function). If the buddy is found to be reserved, no more combinations are possible and the main loop terminates (lines 14-15).

If the area and its buddy are both free, the buddy is withdrawn from its free list using the private member function Unlink (line 16). Since the free lists are all doubly-linked lists, it is possible to withdraw the buddy from its free list in constant time. After combining the two areas of size , the combined area has size and is represented by the buddy with the smaller address (lines 17-18). Eventually, when no more combining is possible, the main loop terminates and we insert the area into the appropriate free list (line 20). This insertion makes use of the private member function InsertAfter which runs in constant time.

The running time of the Release function depends on the number of iterations of the main loop. If the buddy of the area to be released is reserved, then the Release function runs in constant time. In the worst case, there is only one reserved area of size in the storage pool. If we release this area, m iterations of the main loop are required. Therefore, the worst-case running time for the Release function is , where N is the number of blocks in the storage pool.

In the preceding analysis (and in the implementation) we have assumed the smallest area has size . However, since every area must contain a Header, the smallest area that will ever occur has size . For example, on a 32-bit machine the size of the header is likely to be four bytes. Since we cannot have an area of size or , the corresponding free lists are never used.

It is also quite common to limit the maximum size of an area to a size where m'<m. Consequently, since there are never any blocks of sizes between and , the corresponding free lists are never used. Limiting the maximum size of the free lists improves matters slightly, since the worst-case running times for both the Acquire and the Release functions become O(m').

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.