10.9.5 Implementation issues
A practical allocator that strikes a better balance between throughput and utilization must consider the following issues:
- Free block organization: how do we keep track of free blocks?
- Placement: How do we choose an appropriate free block in which to place a newly allocated block?
- Splitting: After we place a newly allocated block in some free block, what do we do with the remainder of the free block?
- Coalescing: What do we do with a block that has just been freed?
Any practical allocator needs some data structure that allows it to distinguish block boundaries and to distinguish between allocated and free blocks. Most allocators embed this information in the block themselves. An example is as follow.
A block consists of a one-word (4 bytes) header, the payload, and possibly some additional padding. The header encodes the block size as well as whether the block is allocated or free. If we impose a double-word alignment constraint, then the block size is always a multiple of eight and the three low-order bits of the block size are always zero.
This organization is called implicit free list because the free blocks are linked implicitly by the size fields in the headers. The allocator can indirectly traverse the entire set of free blocks by traversing all of the blocks in the heap. We also need some kind of specially marked end block. The advantage of an implicit free list is simplicity. A significant disadvantage is the cost of any operation, such as placing allocated blocks, requires a search of the free list will be linear in the total number of allocated and free blocks in the heap.
10.9.7 Placing Allocated Blocks
Three common placement policies are: first fit, next fit and best fit. All of them have advantages and disadvantages.
10.9.8 Splitting Free Blocks
If the fit is not good, then the allocator will usually opt to split the free block into two parts. The first part becomes the allocated block, and the remainder becomes a new free block.
10.9.9 Getting Additional Heap Memory
If the allocator is unable to find a fit for the requested block, it will ask the kernel for additional memory, either by calling the mmap or sbrk functions.
10.9.10 Coalescing Free Blocks
There are free blocks adjacent to the newly freed block, which is known as false fragmentation. Coalescing comes in to rescue this phenomenon by merge adjacent free blocks. When to perform such operations??? Immediate coalescing Vs Defer coalescing. The former could introduce a form of thrashing, where a block is repeatedly coalesced and then split soon thereafter.. Fast allocators often opt for some form of deferred coalescing.
10.9.11 Coalescing with Boundary Tags
Coalescing the next free block is straightforward and efficient. How would we coalesce the previous block? Knuth developed boundary tags, which allows for constant-time coalescing of the previous block. The idea is to add a footer (the boundary tag) at the end of each block, where the footer is a replica of the header. If each block includes such a footer, then the allocator can determine the starting location and status of the previous block by inspecting its footer, which is always one word away from the start of the current block.
10.9.14 Segregated Free Lists (A popular choice with production-quality allocators such as GNU malloc)
Segregated storage: maintain multiple free lists, where each list holds blocks that are roughly the same size. Two basic approaches: simple segregated storage and segregated fits.
Simple segregated storage: the free list for each size class contains same-sized blocks, each the size of the largest element of the size class.
Segregated Fits: Each list contains potentially different-sized blocks whose sizes are members of the size class.
No comments:
Post a Comment