17. Free-space management Flashcards
What do variable-sized chunks of memory lead to?
External fragmentation
What is free list?
A data structure that contains a set of elements describing free space remaining in heap
What is splitting?
It’s a technique which divides a free chunk into 2 - one is given to requester and other remains on free list
What is coalescing?
It’s a technique when free separate chunks of memory are merged into a single free chunk, if they are located next to each other
How does free() determine how much spaces should be freed, considering it’s only given a pointer?
Most allocators store a bit of extra information in a header block which is kept in memory right before allocated chunk
What does header minimally contain?
Size of chunk and magic number to verify integrity
How is header found and how is it used to know how much of memory to free?
We can obtain header address by substracting 1 from the pointer to a chunk of memory. We can then add “size” of header to the size of header to get amount of memory freed.
When free space is freed, how is free list constructed?
The head will now point to the newly freed space of memory (to the start of header) and it will contain a “next” which points to an address of the next “free node”
How does “best fit” allocating strategy work?
Goes through the free list and finds chunks of memory that are as big or bigger than requested. Then return the smallest from this group of candidates. Not the best performance due to exhaustive search
How does “worst fit” allocating strategy work?
Goes through the free list and finds the largest chunk and return the requested amount. It aims at having large chunks left.
Not the best performance due to exhaustive search
How does “first fit” allocating strategy work?
Finds the first block that matches the request
How does “next fit” allocating strategy work?
Instead of always beginning the first-fit search at the beginning of the list, the next fit algorithm keeps an extra pointer to the location within the list where one was looking last. The idea is to spread the searches for free space throughout the list more uniformly, thus avoiding splintering of the beginning of the list.
What is an idea behind segregated lists approach?
If particular process has one or few popular-sized requests, keep a separate list to manage objects of that size. All other requests are forwarded to more general memory allocator. This leads to less fragmentation and less searching through the list
How does binary buddy allocator work?
It starts dividing a free chunk of memory in 2 until further division will not meet the requested size. When this region of memory is freed, it checks if the neighboring (since divided by 2) region is also free and coalesces them, going up while both neighbours are free
