CS代考计算机代写 data structure Carnegie Mellon

Carnegie Mellon
Fragmentation
 Poor memory utilization caused by fragmentation  internal fragmentation
 external fragmentation
1

Carnegie Mellon
Internal Fragmentation
 For a given block, internal fragmentation occurs if payload is smaller than block size
Internal fragmentation
 Caused by
Internal fragmentation
Block
Payload
 Overhead of maintaining heap data structures
 Padding for alignment purposes
 Explicit policy decisions
(e.g., to return a big block to satisfy a small request)
 Depends only on the pattern of previous requests  Thus, easy to measure
2

Carnegie Mellon
External Fragmentation
 Occurs when there is enough aggregate heap memory, but no single free block is large enough
p1 = malloc(4)
p2 = malloc(5)
p3 = malloc(6)
free(p2)
p4 = malloc(6) Oops! (what would happen now?)
 Depends on the pattern of future requests  Thus, difficult to measure
3