Internal Fragmentation
A placement strategy is a concrete policy used by an allocator for choosing a free block to satisfy an allocation request.
Three of the strategies are
First-fit:
It fits data into memory by scanning from the beginning of avail list to the end, until the first free space which is at least big enough to accept the data is found.
This space is then allocated to the data.
Any left over becomes a smaller, separate free space.
Best-fit:
It tries to determine the best place to put the new data.
The definition of “best” may differ between implementations.
One example might be to try and minimize the wasted space at the end of the block being allocated—i.e., use the smallest space which is big enough.
Worst-fit:
It always allocates from the largest free block.
Commonly implemented using a size-ordered free block chain (largest first).
In practice, this tends to work quite badly because it eliminates all large blocks, so large requests can not be met.
External Fragmentation
Three major approaches to solve the external fragmentation problems:
Compacting the storage: Was described in the previous slides.
Regenerate the file when external fragmentation becomes intolerable.
Coalescing the holes: If two record slots on the avail list are physically adjacent, combine them to make a single, larger record slot.
Adopting a placement strategy:
A good placement strategy could cut down both the external and internal fragmentation problems.
†In conclusion, no one placement strategy is superior under all circumstances.
A best strategy is found by observations and experience.
‡ With fixed-length records, placement is simply not an issue.
