Dynamic Memory Flashcards
Throughput vs good memory utilization
good memory utilization requre more operations to decide where to allocate memory so this increases throughput.
Memory utilisation
total bytes allocated / total bytes of heap or page
Internal fragmentation
= payload / block size
payload is the bytes occupied
the heap is usually divided into blocks of a certain byte. exp. 16 bytes, malloc(10) like have frag = 10/16
External fragmentation
when the total aggregated available heap memory is enough but there’s no free block large enough
Heap
a contiguous block of memory for dynamically allocated memory in a program. Usually invoked by malloc
Explicit memory management
explicitly allocating and freeing memory (exp. malloc & free)
Implicit memory management
an application allocates memory but implicitly deallocates. (exp. garbage collector that cleans up unused memory)
Implicit free list
contains a list where each element has a header for every block of memory. If header is 8 bits, the first bit is to determine it is used/unused 1/0.
when memory is allocated to a free block, the block will be split into two, occupied and unoccupied.
when memory is freed, the list should join adjacent free blocks together.
Explicit free list
doubly linked list of pointers pointing to the starting location of free blocks in the heap.
when memory is allocated, find the best fit block by traversing the list.
when memory is freed, the list will be inserted either in LIFO or in address-order. Free block with lowest address is at the start of the list.
Segregated free lists
multiple lists where lists of the same sizes are grouped together. Each list has a size class.
when memory is allocated, the first block in the class size list requested is used. If list is empty, the next size up list is used. If no lists can fit, then sbrk() is called to request OS to increase size of heap.
when memory is freed, the block is added to the appropriate free list.
Bidirectional coalescing
Can be applied to any list. Add boundary tags where the size of the block is written at the start and end of the block (header & footer). This allows traversing the list backwards from any node. Joining/coalescing takes constant time with boundary tags O(no. of nodes to join).
Cons of implicit free list
linear time operation based on the number of blocks in a heap because it requires traversing the entire list to find free blocks that fit.
Pros of explicit free list
malloc operation requires linear time based on the no. of free blocks instead of total blocks in the heap.
Explicit free list LIFO vs Address-order
LIFO causes more fragmentation than address-order but it takes contsant time O(1) for insertion. Address-order is not constant time, requires searching the list for insertion.
Pros of Segregated free lists
high throughput and better memory utilizaiton. Search the first fit list is faster then finding the best fit block in an entire heap most of the time.
