Topic:
memory management by buddy system
Topic:
heap memory management
| |
Summary
A free list is a list of available memory pages or objects. Pages may be sorted by address. A list may be limited to one size. An allocation request may be satisified by the first available page that is sufficiently large (first fit), by exact fit, or best fit.
Adjacent regions may need to be coalesced. Memory fragmentation may make large requests difficult to satisfy. (cbb 12/07)
Subtopic: fixed-size free list 
| Quote: for most programs, the vast majority of objects allocated are of only a few sizes; 90% allocated from 6.1 sizes; why buddy system works badly [»johnMS10_1998]
| | Quote: free lists of exact-fit blocks dramatically reduces cost of memory management; either static or dynamic [»oldeRR5_1985]
| | QuoteRef: lampBW_1974 ;;6 Storage allocation by memory blocks each 10% larger than previous size eg 10,12,14,16...200,220 etc
| | Quote: LOOM uses freelists for the forty smallest sizes [»kaehT9_1986]
| | Quote: memory allocation using free-lists with geometric sizes (1/8) in 16KB blocks; 2% fragmentation on average; lazy page formatting and collection [»bacoDF1_2003]
|
Subtopic: slabs of fixed-sized buffers
| Quote: DLmalloc -- small blocks in bins of same size, large blocks coalesced in mixed bins; best [»larsPA10_1998]
| | Quote: the slab allocator allocates non-cached objects from 30 slabs of 8 bytes to 9K; larger requests allocated by the back-end page supplier [»bonwJ6_1994]
| | Quote: a slab is one or more pages of contiguous memory divided into equal size chunks; reference count of allocated chucks [»bonwJ6_1994]
| | Quote: the slab allocator is both fast and space-efficient; half the fragmentation of its nearest competitor; constant-time allocate and free [»bonwJ6_1994]
| | Quote: for small to mid-size buffers, slab data, freelist links, and buffers on a single page [»bonwJ6_1994]
| | Quote: easier debugging if freelist links at the end of a buffer
| | Quote: unlink the slab instead of unlinking each buffer; freed slabs may be returned to the system; keeps a 15-second working set of recently-used slabs [»bonwJ6_1994]
| | Quote: for cache utilization and bus balance, each slab allocates buffers at slightly different offsets [»bonwJ6_1994]
|
Subtopic: problems with free list
| Quote: free-list allocation has poor spatial locality; contiguous allocation for young objects is better; use free-list for mature objects [»blacSM6_2004]
|
Subtopic: LIFO
| Quote: freed memory should be reused in a LIFO order. Cyclical reuse may cause memory faults under LRU replacement policies [»wilsPR9_1992]
|
Subtopic: exact fit
| Quote: free lists of exact-fit blocks dramatically reduces cost of memory management; either static or dynamic [»oldeRR5_1985]
| | Quote: with class-specific allocators and deallocators, free store is inexpensive
| | Quote: use an exact-fit cache of recently freed blocks to improve memory management [»oldeRR5_1985]
|
Subtopic: first-fit
| Quote: first-fit with multiple segments, heap of max-sized blocks per segment and linear search/coalesce; 1 word/block, logarithmic time [»brenRP7_1989]
| | Quote: for first-fit memory allocation allocation is faster than deallocation; use common list structure for faster deallocation [»chanJM_2000]
| | Quote: improve first-fit with a separate 'sliver' list for small blocks of free storage; only available for recombination [»teneA_1980]
| | Quote: for first-fit memory allocation allocation is faster than deallocation; use common list structure for faster deallocation [»chanJM_2000]
|
Subtopic: best fit
| Quote: use best fit and address-ordered first fit for near-zero memory fragmentation; implementation available [»johnMS10_1998]
| | Quote: best memory allocators: best fit, address-ordered first fit, and FIFO-ordered first fit; 22% fragmentation, reduced to 14% fragmentation [»wilsPR9_1995]
| Quote: best fit and address-ordered first fit tend to place together blocks allocated together; these blocks also tend to die together
[»johnMS10_1998]
|
Related Topics
Topic: memory management by buddy system (9 items)
Topic: heap memory management
(33 items)
|
