Memory Allocation

Question 1

what does a dynamic memory allocator do?

Answer 1

• initially has a pool of free memory
• needs to satisfy arbitrary allocate and free requests from that pool
• can’t control the order or the number of requests
• can’t move allocated regions (no compaction!)
• needs to track which parts are in use and which parts are free

Question 2

Three factors required for fragmentation to occur

Answer 2

1. different lifetimes
2. different sizes
3. inability to relocate previous allocations

Question 3

Best-fit

Answer 3

Idea: tries to avoid breaking up large contiguous areas
-> Allocate the smallest free block that is large enough to fulfill the allocation request, during free coalesce adjacent blocks
- must search entire list
- Sawdust: external fragments of allocations are so small that over time leftovers with unusable sawdust are everywhere

Question 4

Worst-fit

Answer 4

Idea: minimize sawdust by turning best-fit strategy around
-> Allocate the largest free block
- must search the entire list
- worse fragmentation that best-fit

Question 5

First-fit

Answer 5

Idea: if you produce fragmentation anyway, try to optimize for allocation speed
-> Allocate the first hole that is big enough
-fastest allocation policy
-produces leftovers of variable size

Question 6

Buddy Allocator

Answer 6

• to dynamically allocate contiguous chunks of fixed-size elements
• allocates memory in powers of 2
• if no sufficiently small memory block is available, select larger available chunk and split it into two equal-sized buddies
• if two buddies are both free, merge them

Question 7

SLAB allocator

Answer 7

• a slab is made up of multiple pages of contiguous physical memory
• a cache consists of one or multiple slabs
• each cache stores only one kind of object (fixed-size)
• Linux uses Buddy Allocator as the underlying allocator for slabs

Question 8

Why can’t you easily mitigate external fragmentation on the heap with compactification?

Answer 8

There is no memory translation on the heap, so compactification would break allocated areas- it would change start and other addresses referring to the allocated area and we can’t change pointers once they have been handed out

Question 9

Which information can’t be extracted from the bitmap and needs to be kept separately?

Answer 9

A bitmap doesn’t store the length of an allocation: one can’t decide whether two adjacent allocations belong together or not from a bitmap alone.
A heap allocator need this info to release allocations.