In computer science, coalescing is a part of memory management in which multiple adjacent free blocks of computer memory or cache are merged.12
Coalescing reduces external fragmentation by merging adjacent free blocks; it can be done eagerly when a block is freed, or deferred until allocation pressure requires it.21
In buddy allocation, coalescing is efficient because each free block has a uniquely determined buddy; when both are free they are merged to form a larger block.3
Some allocators (e.g., slab) avoid coalescing by reusing same-size objects from caches, trading flexibility for speed and reduced fragmentation.4
When a program no longer requires certain blocks of memory, these blocks of memory can be freed. Without coalescing, these blocks of memory stay separate from each other in their original requested size, even if they are next to each other. If a subsequent request for memory specifies a size that cannot be met with an integer number of these (potentially unequally sized) freed blocks, these neighboring blocks cannot be allocated for this request. Coalescing alleviates this issue by setting the neighboring blocks of freed memory to be contiguous without boundaries, such that part or all of it can be allocated for the request.1
Among other techniques, coalescing is used to reduce external fragmentation, but is not totally effective. Coalescing can be done as soon as blocks are freed, or it can be deferred until some time later (known as deferred coalescing), or it might not be done at all.2
Coalescing and related techniques (e.g., compaction) are used by memory managers and some garbage collectors to reclaim space and reduce external fragmentation.12
See also
See also
References
References
- Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (2008). "Memory Management". Operating System Concepts (8th ed.). Wiley.
- Wilson, Paul R.; Johnstone, Mark S.; Neely, Michael; Boles, David (1995). "Dynamic Storage Allocation: A Survey and Critical Review" (PDF). Proceedings of the 1995 International Workshop on Memory Management.
- Peterson, James L.; Norman, Theodore A. (1977). "Buddy Systems" (PDF). Communications of the ACM. 20 (6): 421–431. doi:10.1145/359605.359626.
- Bonwick, Jeff (1994). "The Slab Allocator: An Object-Caching Kernel Memory Allocator" (HTML). USENIX Summer 1994 Technical Conference. USENIX Association.
External links
External links
- The Memory Management Reference – overview of dynamic storage allocation (coalescing, fragmentation, policies).
- Free-Space Management (OSTEP) – textbook chapter covering fragmentation, splitting, and coalescing (PDF).
- Doug Lea’s malloc (dlmalloc) notes – allocator design details including split/merge (coalescing).
- Performance Considerations: Memory Coalescing in CUDA – slides from NVIDIA's GPU Teaching Kit (memory coalescing).
- How to Access Global Memory Efficiently in CUDA C/C++ Kernels – article by Mark Harris at NVIDIA (global memory coalescing).