Coalescing (computer science)

  1. Home
  2. Wiki

In computer science, coalescing is a part of memory management in which two adjacent free blocks of computer memory are merged.[1][2]

Coalescing reduces external fragmentation by merging adjacent free blocks; it can be done eagerly on free or deferred until allocation pressure requires it.[2][1]

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.[1][2]

See also

[edit]

References

[edit]
  1. ^ a b c d Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (2008). "Memory Management". Operating System Concepts (8th ed.). Wiley.
  2. ^ a b c d 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.
  3. ^ Peterson, James L.; Norman, Theodore A. (1977). "Buddy Systems" (PDF). Communications of the ACM. 20 (6): 421–431. doi:10.1145/359605.359626.
  4. ^ Bonwick, Jeff (1994). "The Slab Allocator: An Object-Caching Kernel Memory Allocator" (HTML). USENIX Summer 1994 Technical Conference. USENIX Association.
[edit]