Contiguous allocation needs one unbroken hole per process. First / Best / Worst fit pick that hole differently — and all eventually scatter free space into unusable gaps.
Under contiguous allocation, each process needs one unbroken run of memory. So the OS keeps a list of free gaps — holes — and must place an arriving process into a hole at least as large as it needs. The placement strategy decides *which* qualifying hole to use.
Three placement strategies
1First fit — scan from the start and take the first hole big enough. Fast, because it stops early.
2Best fit — take the smallest hole that still fits, to waste the least space. Tends to leave tiny unusable slivers.
3Worst fit — take the largest hole, hoping the leftover stays big enough to reuse later.
Worked example
Free holes, in order, are 100, 500, 200, 300, 600 (KB). A process needs 212 KB. Each strategy picks a different hole:
Holes: 100 500 200 300 600 request = 212
First fit -> 500 (first hole that is >= 212)
Best fit -> 300 (smallest hole that is >= 212)
Worst fit -> 600 (largest hole)
External fragmentation is the real enemy
As processes come and go, free space scatters into many small holes. Soon there's plenty of free memory in total, but no single hole is large enough for the next request — external fragmentation. Compaction slides allocated blocks together to merge the gaps, but it's expensive.
Don't confuse the two fragmentations
External fragmentation is wasted space *between* allocations (contiguous allocation's problem). Internal fragmentation is wasted space *inside* a fixed-size block that's bigger than needed (paging's problem).
OperationTimeSpace
First fit · stops at first match; usually fastestO(holes)O(holes)
Best / Worst fit · must scan all holes to find the extremeO(holes)O(holes)
Check yourself
Holes are 100, 500, 200, 300, 600 KB and a process needs 212 KB. Which hole does best fit choose?
