4.2.23 · D5Operating Systems
Question bank — Memory allocation — contiguous (first-fit, best-fit, worst-fit)
First, nail the two symbols this page keeps using
Before any trap, let us pin down the two letters that appear over and over, so no line below asks you to guess.
Look at the strip above: the blue segment is the hole (), the yellow part is the request that lands inside it (), and the green tail is the leftover () that survives as a new, smaller hole.
The two fragmentations — one picture that separates them
These two words are cousins that people constantly swap. The figure below shows both on the same strip so you never confuse them again.
In the top strip (external), the red gaps between processes add up to plenty of free space, yet none is big enough alone. In the bottom strip (internal), the red slice lives inside the block, locked away by rounding.
How costly is each scan? (complexity picture)
The three rules differ not just in which hole they pick but in how long they look. With free holes:
The bars show relative work: first-fit's bar is short and variable (it may stop anywhere), while best-fit and worst-fit each sweep the whole list every time.
Where the "50% rule" comes from (a sketch)
The parent note invokes the 50% rule for first-fit. Here is the why in one breath, so the number is not magic.
The figure alternates allocated blocks (blue) and the small residual holes (red) they spawn — count them and you see roughly one hole per two blocks.
Compaction and paging — what the fixes actually do
The links below are not decoration; each is a different escape from fragmentation, and the figure shows the mechanism.
Top row (compaction): fragmented strip → blocks shuffle left → one merged free tail. Bottom row (paging): the same process is split into pages that occupy non-adjacent frames, so no contiguous hole is ever needed.
True or false — justify
True or false: best-fit always leaves less total wasted memory than first-fit over a long run.
False. Best-fit minimizes leftover per allocation, which tends to shave off tiny unusable slivers that pile up; empirically first-fit ≈ best-fit in long-run fragmentation.
True or false: if the total free memory is at least the request size, contiguous allocation will succeed.
False. The free space may be split across several holes; contiguity demands one single hole , so 30+30 free cannot serve a 50 request.
True or false: first-fit must compare the sizes of every free hole before choosing.
False. First-fit scans in address order and stops at the first hole — it never compares candidate sizes, which is exactly why it is fast.
True or false: worst-fit produces the largest single leftover per allocation.
True. By always cutting from the biggest hole, the leftover is maximized for that step — but this is a per-step property, not a guarantee of good utilization.
True or false: with exact-size splitting, pure contiguous allocation produces internal fragmentation.
False. When each hole is split to exactly the requested size , no space is trapped inside a block, so only external fragmentation arises; internal fragmentation needs fixed-unit rounding.
True or false: worst-fit is the safest choice when large requests are expected later.
False. Worst-fit burns through big holes greedily, so a large future request is the most likely to starve — it is usually the worst for utilization.
True or false: choosing a different hole for the same request changes which future requests can be served.
True. The chosen hole determines the shape and sizes of the remaining holes, so placement policy directly affects future success.
True or false: if every request exactly equals some hole size, all three algorithms behave identically.
False in general. All may find an exact fit (leftover 0), but when multiple exact matches exist, tie-breaking (address order vs size) can make later choices — and later successes — diverge.
Spot the error
Spot the error: "First-fit picks the smallest hole that is large enough, stopping early."
The "smallest hole" clause is wrong — that describes best-fit. First-fit takes the first fitting hole in address order regardless of size.
Spot the error: "Best-fit never scans the whole free list because it stops at a good-enough hole."
Wrong — best-fit must scan the entire list () to be sure it found the tightest fit; only first-fit can stop early.
Spot the error: "External fragmentation means unused bytes inside an allocated block."
That is internal fragmentation. External fragmentation is free memory scattered into too-small holes between allocated blocks.
Spot the error: "The 50% rule proves best-fit loses half its blocks to fragmentation."
The 50% rule is an analysis of first-fit: for allocated blocks about additional are lost to fragmentation — it is not a statement about best-fit.
Spot the error: "Compaction is unnecessary because worst-fit already keeps holes large."
Worst-fit's large leftovers still fragment over time; Compaction physically relocates blocks to merge scattered free space, solving a problem no placement rule can fully prevent.
Spot the error: "Since best-fit minimizes leftover, its leftover holes are the most reusable."
The opposite — minimizing leftover produces the smallest holes, which are the least likely to be reusable by future requests.
Why questions
Why does external fragmentation exist at all if we track total free memory correctly?
Because processes require a single contiguous block; free memory can be plentiful yet chopped into pieces each smaller than the request.
Why is first-fit the practical favorite despite best-fit sometimes packing more?
It is nearly as good as best-fit on average yet much faster — its scan can stop early ( best case) while best-fit is always .
Why does best-fit tend to create many tiny "dead" slivers?
Choosing the tightest hole repeatedly shaves off leftovers of size that are just a few units — too small to satisfy anything, so they accumulate as fragmentation.
Why does worst-fit fail large future requests specifically?
It consumes the biggest holes first, so no large hole survives for a subsequent big request even if many small holes remain.
Why can changing the placement rule turn a failing workload into a succeeding one?
Different rules leave differently-sized residual holes; a rule that preserves a hole a later request lets that request succeed where another rule fragmented that space away.
Why does Paging eliminate external fragmentation entirely?
It drops the contiguity requirement by mapping fixed-size pages to any free frames, so scattered free frames are fully usable.
Edge cases
Edge case: a request whose size exactly equals a hole — what is the leftover and what happens to the hole?
Leftover , so the hole vanishes completely from the free list.
Edge case: a request of size 0 arrives — how should allocation treat it?
Any hole (even size 0 conceptually) "fits" since ; in practice a 0-size request allocates nothing and leaves the free list unchanged.
Edge case: the free list is empty but the request is small — what do all three rules do?
All fail identically; with no holes, no rule can find , regardless of speed or strategy.
Edge case: two holes tie for "tightest" in best-fit — which is chosen?
The tie is broken by convention (usually the first in address order); the chosen one affects later hole layout, so implementations must define this explicitly.
Edge case: a single hole spans all of free memory and the request is tiny — do first-fit, best-fit, worst-fit differ?
No. With exactly one hole, all three pick it; they only diverge when multiple candidate holes exist.
Edge case: after many allocations and frees, two adjacent free holes exist — does contiguous allocation merge them?
Only if the Free List Management coalesces adjacent holes on free; without coalescing they stay separate and cannot jointly serve a large request.