[SOLVED] CS代考计算机代写 Carnegie Mellon

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