Memory Allocation Algorithms — Deep Dive & Solved Numericals

CSS Optional — Paper-II, Section-A · P-II.III.V (cont.) · Extra worked numericals for [Memory Management]'s allocation algorithms, Buddy System, compaction, and address translation.

1. First-Fit vs Best-Fit vs Worst-Fit vs Next-Fit — Same Requests, Compared

Free blocks: B1=100K, B2=500K, B3=200K, B4=300K, B5=600K

Requests (in order): R1=212K, R2=417K, R3=112K, R4=426K

First-Fit — Step by Step

1. R1=212 → scan from start: B1(100, no) → B2(500, yes) → allocate in B2, remainder = 500−212 = 288
2. R2=417 → scan from start: B1(100,no) → B2(288,no) → B3(200,no) → B4(300,no) → B5(600,yes) → allocate in B5, remainder = 600−417 = 183
3. R3=112 → scan from start: B1(100,no) → B2(288,yes) → allocate in B2, remainder = 288−112 = 176
4. R4=426 → scan from start: B1(100,no) → B2(176,no) → B3(200,no) → B4(300,no) → B5(183,no) → no block fits — FAILS

Best-Fit — Step by Step

1. R1=212 → candidates ≥212: {500,300,600} → smallest = 300 → allocate in B4, remainder = 300−212 = 88
2. R2=417 → candidates ≥417 among {100,500,200,88,600}: {500,600} → smallest = 500 → allocate in B2, remainder = 500−417 = 83
3. R3=112 → candidates ≥112 among {100,83,200,88,600}: {200,600} → smallest = 200 → allocate in B3, remainder = 200−112 = 88
4. R4=426 → candidates ≥426 among {100,83,88,88,600}: only {600} → allocate in B5, remainder = 600−426 = 174

All four requests succeed under Best-Fit.

Worst-Fit — Step by Step

1. R1=212 → largest block = 600(B5) → allocate, remainder = 600−212 = 388
2. R2=417 → largest among {100,500,200,300,388} = 500(B2) → allocate, remainder = 500−417 = 83
3. R3=112 → largest among {100,83,200,300,388} = 388(B5 remainder) → allocate, remainder = 388−112 = 276
4. R4=426 → largest among {100,83,200,300,276} = 300(B4) → 300 < 426 → no block fits — FAILS

Next-Fit — Step by Step (pointer starts at B1, wraps around)

1. R1=212 → scan from B1: B1(100,no) → B2(500,yes) → allocate, remainder=288, pointer parked at B2
2. R2=417 → scan from after B2: B3(200,no) → B4(300,no) → B5(600,yes) → allocate, remainder=183, pointer at B5
3. R3=112 → scan from after B5, wrap to B1(100,no) → B2(288,yes) → allocate, remainder=176, pointer at B2
4. R4=426 → scan from after B2: B3(200,no) → B4(300,no) → B5(183,no) → wrap → B1(100,no) → B2(176,no) → full cycle, no fit — FAILS

Result Summary

• Only Best-Fit satisfies all four requests here — a deliberately built counter-example to the common assumption that Best-Fit "wastes more space so performs worse."
• Exam takeaway: no single algorithm is universally best — the correct answer to "which is optimal?" is always "it depends on the request pattern," backed by a worked contrast like this one.

2. Buddy System — Split and Merge, Step by Step

Setup: 256 KB total. Allocate A = 60K (rounds up to 64K), then B = 15K (rounds up to 16K). Then free both.

Step 1 — Allocate A (needs a 64K block, none free yet):

1. Split 256 → 128 + 128
2. Split one 128 → 64 + 64
3. Allocate A in one 64K block. Free list = {64 (A's buddy), 128}

Step 2 — Allocate B (needs a 16K block, none free yet):

1. Split the free 64 → 32 + 32
2. Split one 32 → 16 + 16
3. Allocate B in one 16K block. Free list = {16 (B's buddy), 32, 64 (A's buddy), 128}
4. Check: allocated (64 for A + 16 for B = 80) + free (16+32+64+128 = 240) = 256 ✓

Step 3 — Free A:

1. A's 64K becomes free.
2. Check A's buddy (the other original 64K) — it was subdivided for B, so it is not fully free.
3. No merge. Free list = {64, 16, 32, 128}

Step 4 — Free B:

1. B's 16K frees → its buddy (the other 16) is free → merge → 32
2. That new 32's buddy (the other free 32) is free → merge → 64
3. That new 64's buddy is A's already-free 64 → merge → 128
4. That new 128's buddy is the other free 128 → merge → full 256K restored

Key exam point: Buddy System only merges when a block's exact buddy is entirely free — freeing in the "wrong" order can delay coalescing even though enough total free space exists elsewhere.

3. Compaction — Worked Numerical

Scattered free holes between allocated blocks: 10K, 4K, 20K, 18K, 7K, 9K, 12K, 15K.

1. Total free memory = 10+4+20+18+7+9+12+15 = 95K
2. Largest single hole = 20K
3. A request for 50K → check every hole individually: none reaches 50K → fails before compaction, even though 95K is free overall (classic external fragmentation).
4. After compaction (sliding all allocated blocks together): all 95K becomes one contiguous hole.
5. The 50K request is retried against the single 95K hole → succeeds.

Cost to name in an answer: compaction needs CPU time proportional to the amount of data moved, and processes are typically paused during the shift — it is not free.

4. Paging Address Translation — Worked Numerical (hex-based)

Given: 32-bit logical address space, page size = 4 KB (2¹²), physical memory = 1 GB (2³⁰), frame size = 4 KB.

Step 1 — sizing:

1. Number of pages = 2³² / 2¹² = 2²⁰ = 1,048,576 pages
2. Number of frames = 2³⁰ / 2¹² = 2¹⁸ = 262,144 frames
3. Physical address width = 18 bits (frame #) + 12 bits (offset) = 30 bits ✓ matches 2³⁰

Step 2 — translate logical address 0x00405078:

1. Offset = lowest 12 bits = last 3 hex digits = 0x078
2. Page number = remaining upper bits = 0x405 (decimal 1029)

Step 3 — apply the page table (given: page 1029 → frame 700 = 0x2BC):

Physical address = (frame number x page size) + offset
                 = (700 x 4096) + 120
                 = 2,867,200 + 120
                 = 2,867,320        (hex: 0x2BC078)

Shortcut worth stating in an exam: the offset bits never change between logical and physical address — only the page-number bits get replaced by the frame number. That's why translation can just concatenate the frame number with the untouched offset.

---

🎯 CSS Exam Angle

• State why an allocation fails ("no single hole ≥ request size"), not just that it fails — examiners reward identifying external fragmentation by name.
• For address-translation numericals, always show the bit-width breakdown first (how many bits for offset vs page number) before computing a specific translation — it's usually worth marks on its own.

📌 Related Past CSS Paper Questions

See [Memory Management] → Worked Numericals for the exact past-paper versions; this page's numericals are additional verified practice for Buddy System, compaction, and fit-algorithm comparison — syllabus topics without a dedicated past-paper numerical yet.

⚠️ MCQ Traps

• Best-Fit is not "always safest" — section 1's table is a real counter-example where it's the only algorithm that succeeds, but in other request patterns it can be the worst (leaves many tiny unusable slivers).
• Buddy System merging needs the EXACT buddy free — having enough free space elsewhere in memory does not trigger a merge.
• Compaction fixes external fragmentation, not internal fragmentation — internal fragmentation (wasted space inside an allocated block) cannot be compacted away.
• Offset bits are copied unchanged from logical to physical address — only the page-number portion is translated via the page table.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2021 · Paper-II · Q3 · 20 marks (bitmap memory management)

Q. Memory is managed by the bitmap (rows of 6, 1 = used, 0 = free):

111110 / 011000 / 100111 / 100000 / 110000 / 000011

(a) Show the memory with index starting from zero. (b) Insert a page H of size 3 using first-fit. (c) Insert a page K of size 2 using next-fit. (d) Show the linked-list representation. (e) Use a hash table to track the active pages.

Ans.

• (a) Memory map (36 allocation units, index 0–35; U = used, – = free):

Free holes (contiguous runs of zeros): units 5–6 (size 2), 9–11 (size 3), 13–14 (size 2), 19–23 (size 5), 26–33 (size 8).

• (b) First-fit, H = 3 units: scan from the start and take the first hole with size ≥ 3: units 9–11. Bitmap row 1 becomes 011111.
• (c) Next-fit, K = 2 units: continue the search from where the last allocation ended (unit 11). The next hole of size ≥ 2 is units 13–14. Bitmap row 2 becomes 111111.
• Bitmap after both insertions: 111110 / 011111 / 111111 / 100000 / 110000 / 000011.
• (d) Linked list (each node: Process or Hole, start, length):

P 0,5 → H 5,2 → P 7,2 → P(H) 9,3 → P 12,1 → P(K) 13,2 → P 15,4 → H 19,5 → P 24,2 → H 26,8 → P 34,2

• (e) Hash table for active pages (key → start, length), for example with 5 buckets and index = page-name code mod 5:

bucket 0: ...
bucket 1: K → (13, 2)
bucket 2: ...
bucket 3: H → (9, 3)
bucket 4: ... (chains hold other active pages)

Looking up a page by name gives its location in O(1) on average.

MCQs

2024 P-II · Q8. Which type of algorithms is applicable to scheduling resources in operating systems?

• (A) State space search ✅
• (B) Machine learning
• (C) Bayesian learning
• (D) None of these
• Answer: (A) State space search (best reading).
• Why: scheduling can be seen as a search over the possible orderings of jobs for the best one. Machine-learning schedulers exist only in research and some modern systems, and Bayesian learning is a learning method.
• Note: the key is arguable, since classical OS schedulers (FCFS, round robin, priority) are simple rules, and (D) could also be argued.