- LPU MCA Semester 1
- CAP366
- Unit 7
CAP366 · Unit 7: Memory management
Contiguous allocation
10 practice questions · in the ETE syllabus
Key points
- Internal: waste inside a block; external: scattered holes
- First, best and worst fit choose different holes
- 50-percent rule: one third of memory may be lost
- Compaction needs execution-time binding
In contiguous allocation each process occupies a single contiguous block of memory. Memory can be split into fixed partitions (simple, but wastes space inside each partition) or variable partitions (processes get exactly what they need, leaving holes between them).
Internal fragmentation is wasted space inside an allocated block; external fragmentation is free memory scattered in holes too small to use even though the total would suffice.
Hole-selection strategies:
| Strategy | Choice |
|---|---|
| First fit | First hole that is big enough |
| Best fit | Smallest hole that is big enough |
| Worst fit | Largest hole |
Worked example: holes 100, 500, 200, 300, 600 KB and requests 212, 417, 112, 426 KB: first fit and worst fit cannot place 426 KB, but best fit places all four.
The 50-percent rule says that with first fit, for N allocated blocks about 0.5N more are lost to fragmentation, so one third of memory may be unusable. Compaction slides allocated blocks together to merge holes, but it needs run-time (execution-time) binding. Paging avoids external fragmentation entirely.
Exam trap: best fit is not always best; it scans the whole list and leaves many tiny holes.
Try two questions
Holes of 150 KB, 350 KB, 120 KB and 80 KB exist, and requests of 100 KB, 200 KB and 50 KB are served with worst fit in that order. What is the size of the largest remaining hole afterwards?
- 250 KB
- 350 KB
- 100 KB
- 120 KB
Show the answer
D. Worst fit takes 350 KB for 100 KB (250 left), then 250 KB for 200 KB (50 left), then 150 KB for 50 KB (100 left). Holes are 100, 50, 120 and 80, so the largest is 120 KB.
Why not A: 250 KB is the hole left after the first request but it is used by the second.
Why not B: 350 KB is the original largest hole before any allocation.
Why not C: 100 KB is a leftover but not the largest one.
Memory has free holes of 100 KB, 50 KB, 30 KB and 20 KB scattered between processes, and a new process of 120 KB arrives. What is the outcome?
- Allocated to the 100 KB hole with 20 KB borrowed from the next
- Allocated immediately because total free memory is 200 KB
- Rejected although 200 KB is free; compaction would create a 200 KB hole
- Rejected, and compaction cannot help because total free is below 120 KB
Show the answer
C. No single hole holds 120 KB, but the total is 200 KB, so compaction would create one 200 KB hole.
Why not A: Contiguous allocation cannot borrow from a neighbouring hole.
Why not B: The holes are not contiguous, so the total does not matter until compaction.
Why not D: Total free is 200 KB, which is above 120 KB.