Carnegie Mellon
Summary of Key Allocator Policies
Placement policy:
First-fit, next-fit, best-fit, etc.
Trades off lower throughput for less fragmentation
Splitting policy:
When do we go ahead and split free blocks?
How much internal fragmentation are we willing to tolerate?
Coalescing policy:
Immediate coalescing: coalesce each time free is called
Deferred coalescing: try to improve performance of free by deferring coalescing until needed. Examples:
Coalesce as you scan the free list for malloc
Coalesce when the amount of external fragmentation reaches some threshold
1
Carnegie Mellon
Implicit Lists: Summary
Implementation: very simple
Allocate cost:
linear time worst case
Free cost:
constant time worst case even with coalescing
Memory usage:
will depend on placement policy First-fit, next-fit or best-fit
Not used in practice for malloc/free because of linear- time allocation
used in many special purpose applications
However, the concepts of splitting and boundary tag coalescing are general to all allocators
2