5.2Contiguous allocation and fragmentation
The idea
Contiguous allocation gives each process one block of memory. Placement uses first, best or worst fit, and creates fragmentation.
Think of it like this: Parking cars of different lengths in a single row: gaps appear that are too small for any car although together they would fit one.
Why it exists
Understanding the fragmentation it creates is the motivation for paging.
How it works
- First fit: first hole that fits.
- Best fit: smallest hole that fits.
- Worst fit: largest hole.
- External fragmentation: free space split into small holes; cure by compaction or paging. Internal: waste inside an allocated block.
Worked example: Holes 100, 500, 200, 300, 600 KB; requests 212, 417, 112, 426
First fit places 212 in 500, 417 in 600, 112 in the leftover 288, and 426 cannot be placed. Best fit places all four.
Now play with it
- →Run the lab with each strategy on the textbook numbers.
- →Make the last request smaller and see first fit succeed.
| Request | Placed in hole | Leftover | Holes after |
|---|---|---|---|
| 212 | #2 (500) | 288 | 100 | 288 | 200 | 300 | 600 |
| 417 | #5 (600) | 183 | 100 | 288 | 200 | 300 | 183 |
| 112 | #2 (500) | 176 | 100 | 176 | 200 | 300 | 183 |
| 426 | must wait (no hole fits) | - | 100 | 176 | 200 | 300 | 183 |
External fragmentation: total free space can be enough while no single hole is. Try the textbook sizes with each strategy: only best fit places all four requests.
| Strategy | Rule | Result |
|---|---|---|
| First fit | first hole that is large enough | fast, good in practice |
| Best fit | smallest hole that is large enough | leaves tiny holes, must search all |
| Worst fit | largest hole | leaves big leftovers, but wastes big holes |
| Next fit | first fit, starting where the last search ended | spreads allocations |
Check yourself
Compaction is possible only if
Exam notes (the dense version)
Each process gets one contiguous block. Placement policies for a request: first fit (first hole big enough), best fit (smallest hole big enough; leaves tiny useless holes, slow), worst fit (largest hole), next fit (first fit resuming from the last placement). External fragmentation: enough total free memory but no single hole large enough; cured by compaction (needs run-time binding) or by paging. Internal fragmentation: waste inside an allocated block, e.g. fixed partitions or the last page of a process.
Previous year questions: Memory Management (11)
PYQs are grouped by topic, so this is the full set for Memory Management; try the ones that match this subtopic. Open all 11 on the topic page.