[SOLVED] 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