Free Space Management Flashcards
How do we keep track of the size of blocks on a free list?
We give blocks a fixed size header, which will contain information about the block itself, most importantly its size. We can also use pointers in this header to help navigate the free list more easily.
Where does the free list reside?
Within memory itself. We keep a pointer to the first block in the free list, and then use pointers in the headers to navigate the free list.
Describe the Best Fit strategy for memory management.
Search the free list, and pick out the chunks of memory which is closest or bigger than the size requested. Return the smallest of these. This would require searching the entire free list though.
Describe Worst Fit strategy for memory management.
Find the largest free chunk, split it and return the requested size. Again, we must search the whole list, and this can still lead to fragmentation.
Describe First Fit strategy for memory management.
Find the first block which is large enough, and return the requested amount. This is fast, but pollutes the beginning of the free list with small objects.
Describe Next Fit strategy for memory management.
Instead of always looking from the start of the free list, keep a pointer to the location in the free list that we were last looking at, and start there. This spreads out searches more evenly.
What is a segregated free list?
This is where we keep multiple free lists to manage objects of particular sizes (such as 8, 16, 24 bytes…) which makes fragmentation less of a problem.
What is buddy allocation?
This is where we split memory up into lots of pairs, and when one of each of the pairs is freed, we check if the other pair is free also. If they are both free, we coalesce them.
What are some pros and cons of buddy allocation?
Pros: it is efficient for allocating frames, and for coalescing. It deals with external fragmentation well.
Cons: Not so good with dealing with internal fragmentation. A request for 9 bytes will be given 16, for example.
