CPSC 313 Lecture 12: [11/27] Virtual Memory cont.
Document Summary
Each block knows if its freed or occupied. First- t: search the list of blocks from the beginning and return the rst free block that is large enough. Tends to leave large free blocks near the end of the list. Slow because we go through the allocated blocks repeatedly. Next- t: similar but start searching from the last allocated block instead of the beginning. Best- t: nd the free block whose size is closest to requested size. Splitting: if the block used is larger than the requested size, we can: use the whole block (increases internal fragmentation) divide the block in two (may end up with many small blocks) We merge adjacent free blocks to avoid ending up with lots of small free blocks all adjacent. + spreads out cost of coalescing may end up splitting and coalescing the same block repetitively. Trick: we store the block size at the end of the block as well as the beginning.