Memory allocation — contiguous (first-fit, best-fit, worst-fit)
WHAT is contiguous allocation?
WHY do we need a placement policy?
Memory is finite and requests arrive in unpredictable order. After many allocations/frees the free list looks like Swiss cheese. Which hole you pick changes the shape of the remaining holes, and therefore whether future requests succeed. There is no single best rule — each trades off speed, fragmentation, and leftover usefulness.
HOW each algorithm chooses
Worked Example 1 — same requests, three rules
Holes (in address order): A=100, B=500, C=200, D=300, E=600 (KB). Process requests arrive: P1=212, P2=417, P3=112, P4=426 (KB).
First-fit
- P1=212 → first hole : B(500). Leftover B=288. (Why? scan A=100<212, B=500≥212, stop.)
- P2=417 → scan A=100, B=288, C=200, D=300, E(600) ≥417. Leftover E=183.
- P3=112 → A(100)? no, 100<112. B=288≥112 → B. Leftover B=176.
- P4=426 → A=100,B=176,C=200,D=300,E=183 — none ≥426. P4 FAILS.
Best-fit
- P1=212 → candidates ≥212: B=500,D=300,E=600. Smallest = D(300). Leftover D=88.
- P2=417 → candidates ≥417: B=500,E=600. Smallest = B(500). Leftover B=83.
- P3=112 → candidates ≥112: A? 100 no. C=200,D=88? no,E=600,B=83 no. Smallest among {C=200,E=600} = C(200). Leftover C=88.
- P4=426 → candidates ≥426: E(600). Leftover E=174. All 4 succeed!
Worst-fit
- P1=212 → largest hole = E(600). Leftover E=388.
- P2=417 → largest = B(500). Leftover B=83.
- P3=112 → largest = E=388 → E. Leftover E=276.
- P4=426 → largest now = E=276 <426, B=83, A=100, C=200, D=300 — none ≥426. P4 FAILS.
Worked Example 2 — why best-fit can create slivers
Holes: 20, 15, 13. Requests: 12, 12, 12.
- Best-fit P1=12 → tightest ≥12 = 13 → leftover 1 (dead sliver).
- Best-fit P2=12 → tightest = 15 → leftover 3 (dead).
- Best-fit P3=12 → only 20 left → leftover 8. Now three useless slivers (1,3,8) totalling 12 KB but no single hole helps a future 12-request.
Common Mistakes
Recall Feynman: explain to a 12-year-old
Think of a parking lot. Cars are programs, parking spaces between cars are "holes". A bus needs several empty spots next to each other — it can't split itself across the lot. First-fit: the bus parks in the first gap big enough — quick, but maybe wasteful. Best-fit: find the tightest gap so almost no space is wasted — but you leave lots of tiny slots no car wants. Worst-fit: always park in the biggest gap so the leftover is still big and useful — but then huge buses later have nowhere to go. There's no perfect rule; it depends on who shows up next.
Active Recall
What does "contiguous" memory allocation require for a process?
First-fit selection rule?
Best-fit selection rule?
Worst-fit selection rule?
Leftover after placing size s in hole H?
External vs internal fragmentation?
Why can best-fit cause worse long-run fragmentation despite "smallest leftover"?
Which two algorithms must scan the entire free list?
Which algorithm is usually fastest and near-optimal in practice?
The 50% rule for first-fit states what?
Can a request fail even when total free memory ≥ request?
Worst-fit's intended advantage and its real weakness?
Connections
- Paging — eliminates external fragmentation by removing the contiguity requirement.
- Segmentation — variable-size contiguous chunks per logical segment.
- Virtual Memory — builds on these placement ideas at page granularity.
- Compaction — relocates blocks to merge holes; cure for external fragmentation.
- Buddy System — alternative allocator with power-of-two blocks.
- Free List Management — the data structure these policies scan.
- Fragmentation — internal vs external, the core cost metric.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Socho RAM ek lambi shelf hai aur har program ko ek continuous (tuta hua nahi) chunk chahiye. Jaise-jaise programs aate-jaate hain, beech mein holes (khaali jagah) ban jaate hain. Jab naya program size maangta hai, OS ko decide karna padta hai ki kaunse hole se jagah kaate. Yahi rule hai — first-fit, best-fit, worst-fit.
First-fit: address order mein jo pehla hole fit hota hai usi mein daal do, aur scan rok do — isliye sabse fast hai. Best-fit: sabse chhota hole dhundo jo phir bhi ho — leftover sabse kam, par poori list scan karni padti hai aur chhote-chhote slivers bach jaate hain jo aage kisi kaam ke nahi. Worst-fit: sabse bada hole use karo taaki leftover bhi bada aur reusable rahe — par bade holes jaldi khatam ho jaate hain, isliye baad mein bada request fail ho jata hai.
Important baat: request fail bhi ho sakta hai chahe total free memory request se zyada ho — kyunki contiguity chahiye. 30+30 free hone par bhi 50 ka block nahi milega. Isi problem ko external fragmentation kehte hain. Practical world mein first-fit generally winner hai — best-fit ke lagbhag barabar achha aur kaafi tej. Yeh saari dikkat aage paging se solve hoti hai, jahan contiguity ki zaroorat hi nahi rehti.