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