Lecture 17

So far

• OS illusion: memory virtualization

• Dynamic relocation via base and bounds

• Segmentation

A detour

• free-space management

• Needed by

  • malloc lib
  • OS

Low-level mechanisms

A 30-byte heap

Free list

• A 10 byte request can be serviced
• A 20 byte one cannot be serviced
• What about a 1 byte request?
• Solution: Splitting and coalescing

Splitting and coalescing

Splitting on a request for 1 byte

Free(10) ignoring the split leads to

Coalescing

Basic strategies for managing free space

Examples

Free list

Best-fit for size 15

Worst-fit for size 15

• First fit?
• same as worst fit
• Search cost: best/worst fit expensive as compared to first fit

Tracking allocation size

• free() does not take a size parameter. So, how does malloc library know the size of memory region to free up?

• Answer: Store extra information in a header

• Header contains the size of the allocated memory region, and a magic number for integrity checking

Illustration

Allocated region + header

Specific contents of the header

Heap allocation

• mem alloc library initializes the heap and puts the first element of the free list in the free space
  • The lib cannot use malloc to build a list

Heap with one free chunk

Heap after an allocation for 100 bytes (+ 8 byte header)

Free Space With Three Chunks Allocated

Free Space With Two Chunks Allocated

A Non-Coalesced Free List

Buddy allocation