basic dynamic memory allocation

Question 1

which area of memory does malloc manage

Answer 1

heap

Question 2

explicit vs implicit allocator

Answer 2

explicit: you do it. malloc and free

implicit: im nice :) garbage collection

Question 3

throughput

Answer 3

number of completed requests per unit of time

5000 mallocs and 5000 frees in 10 seconds = 1k operations/sec & mentally insane

Question 4

peak memory utilization

Answer 4

basically the most payload you’ve had thus far. you just care abt the peak. so if you free’d, no nah you didnt.

max payload over lifetime / heap size

so get your mallocs in

fragmentation ruins this :(

Question 5

internal fragmentation

Answer 5

payload / block size

caused by the need for headers & padding , or design implementation

Question 6

external fragmentation

Answer 6

holes left in the heap from a mix of mallocs and free

sometimes you have enough memory for a malloc, but they’re not together

Question 7

methods of tracking free blocks

Answer 7

1. implicit list - all blocks in one list (linear allocation time)
2. explicit list - all free blocks in one list (linear with respect to free blocks)
3. segregated free list (hw3) - different free list for different sizes (approximate a best fit)
4. free blocks sorted by size perfectly, such as with a red-black tree

Question 8

First fit policy

Answer 8

start from beginning of list, iterate until ones found

causes splinters

Question 9

Next fit

Answer 9

starting from where you last were, search until ones found

worse fragmentation

Question 10

best fit policy

Answer 10

do an exhaustive search of list and find the best one

slower, but best memory usage

Question 11

splitting

Answer 11

cutting a free block into two blocks so you only use whats absolutely needed

Question 12

coalescing

Answer 12

when freeing a block, merge it with any potential neighboring free blocks to avoid external fragmentation.

in order to have bidirectional coalescing you need a header and a footer

Question 13

immediate coalescing

Answer 13

coalesce when you free.

Question 14

deferred coalescing

Answer 14

coalesce when you malloc and search a list.

another option is to coalesce when your external fragmentation gets too high

Question 15

LIFO insertion policy

Answer 15

put free block at beginning of list

Question 16

address ordered insertion policy

Answer 16

insert free block so the list is in order by address

“studies suggest fragmentation is lower”