Page replacement — FIFO, Optimal, LRU আর Clock

১ · RAM ভরা — তবু নতুন page লাগবে

পর্ব ৩৫-এ দেখেছেন, demand paging-এ একটি প্রোগ্রামের সব page শুরুতেই RAM-এ আনা হয় না; যেটি প্রথম ছোঁয়া হয়, তখনই আসে। Page RAM-এ না থাকলে CPU একটি page fault দেয়, kernel ডিস্ক থেকে page এনে একটি ফাঁকা frame-এ বসায়, page table হালনাগাদ করে, আর থেমে যাওয়া instruction আবার চালায়। কিন্তু একটি প্রশ্ন সেখানে খোলা ছিল: ফাঁকা frame না থাকলে?

Multiprogramming-এ RAM প্রায় সবসময় ভরা থাকে (খালি RAM মানে অপচয়), তাই নতুন page আনতে হলে কাউকে সরাতে হয়। কাকে — সেই সিদ্ধান্তই page replacement. ভুল সিদ্ধান্ত মানে এমন page সরানো, যা একটু পরেই আবার লাগবে; তখন আরেকটি page fault, আরেকবার ডিস্কে যাওয়া।

Page fault-এ replacement-সহ পুরো ধাপ

1. ডিস্কে (swap বা ফাইলে) চাওয়া page-টি কোথায় আছে খুঁজে বের করা।
2. একটি ফাঁকা frame খোঁজা। থাকলে সেটিই নেওয়া।
3. ফাঁকা না থাকলে replacement algorithm দিয়ে একটি victim frame বাছা।
4. Victim page-টি dirty হলে আগে ডিস্কে লেখা; তারপর তার page table entry-কে “নেই” (invalid) চিহ্ন দেওয়া, আর TLB-তে তার পুরোনো অনুবাদ থাকলে মুছে দেওয়া (multicore-এ অন্য core-এর TLB-ও — TLB shootdown).
5. চাওয়া page ডিস্ক থেকে এই frame-এ পড়া; page table আর frame-এর হিসাব হালনাগাদ করা।
6. যে instruction-এ fault হয়েছিল, সেটি আবার চালানো।

Dirty bit — অর্ধেক I/O বাঁচানোর কৌশল

উপরের ধাপ ৪ খরচের মূল জায়গা। Victim RAM-এ আসার পর না বদলালে (যেমন প্রোগ্রামের code) ডিস্কের কপি হুবহু একই — লেখার দরকার নেই। কিন্তু OS কীভাবে জানবে বদলেছে কি না? প্রতিটি page table entry-তে hardware একটি modify bit বা dirty bit রাখে: page-এ কোনো byte লেখা হলেই CPU নিজে সেটি ১ করে দেয়। x86-এ এটি PTE-র D (Dirty) বিট; পাশেই থাকে A (Accessed) বিট, যার কথা অংশ ৭-এ আসবে।

• Dirty bit না থাকলে: প্রতিটি replacement-এ দুটি ডিস্ক-transfer — victim লেখা, তারপর নতুন page পড়া।
• Dirty bit থাকলে: victim পরিষ্কার হলে একটিই transfer — শুধু পড়া। Fault-এর সেবার সময় প্রায় অর্ধেক।

ছোট হিসাব: ধরুন পরিষ্কার victim হলে fault সামলাতে লাগে ৮ ms, dirty হলে (লেখা + পড়া) ২০ ms, আর ৭০% ক্ষেত্রে victim dirty. গড় সময় = ০.৩ × ৮ + ০.৭ × ২০ = ২.৪ + ১৪ = ১৬.৪ ms. Dirty bit না থাকলে প্রতিটিতেই ২০ ms লাগত। তাই কিছু নীতি (অংশ ৭-এর enhanced second chance) পরিষ্কার page-কেই আগে সরাতে চায়।

কেন fault-এর সংখ্যা নিয়ে এত মাথাব্যথা? পর্ব ৩৫-এর effective access time-এর সূত্র মনে করুন: EAT = (১ − p) × memory access + p × fault-এর সময়. Memory access ২০০ ns আর fault ৮ ms হলে, প্রতি ১,০০০টি access-এ মাত্র একটি fault (p = ০.০০১) হলেও EAT ≈ ০.৯৯৯ × ২০০ + ০.০০১ × ৮০,০০,০০০ ≈ ৮,২০০ ns — অর্থাৎ মেমরি প্রায় ৪১ গুণ ধীর। তাই replacement নীতির লক্ষ্য: সবচেয়ে কম page-fault rate.

২ · Reference string — ঠিকানার স্রোত থেকে page-এর ধারা

কোনো algorithm কতটা ভালো, মাপতে হলে একটি প্রোগ্রাম মেমরির কোন কোন জায়গা কোন ক্রমে ছোঁয়, সেই তালিকা লাগে — address trace. বাস্তবে এটি লাখ লাখ ঠিকানার লম্বা তালিকা। কিন্তু replacement-এর প্রশ্নে পুরো ঠিকানা লাগে না, শুধু page নম্বর লাগে; আর একই page পরপর কয়েকবার ছোঁয়া হলে প্রথমটির পর বাকিগুলো কখনো fault দিতে পারে না। এই দুই পর্যবেক্ষণে ছোট করা তালিকাটিই reference string.

উদাহরণ: page-এর আকার ১০০ byte (হিসাব সহজ রাখতে)। একটি প্রোগ্রাম এই ঠিকানাগুলো ছোঁয়:

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103,
0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105

1. Page নম্বর = ঠিকানা ÷ page-এর আকার (ভাগফলের পূর্ণ অংশ)। ০১০০ → page ১, ০৪৩২ → page ৪, ০৬১২ → page ৬… ফলে ২১টি page নম্বর: 1, 4, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1.
2. পরপর একই page-কে একটি ধরা। page ১ পরপর চারবার ছোঁয়া হলে প্রথমবারের পর সে RAM-এ আছেই। ফল: 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 — ১১টি reference.

দুটি সীমা চোখে পড়ে। frame ৩ বা বেশি হলে fault হবে মাত্র ৩টি — প্রতিটি আলাদা page-এর প্রথম আসা (এগুলোকে compulsory বা cold-start fault বলে, কোনো algorithm এদের এড়াতে পারে না)। আর frame মাত্র ১টি হলে প্রতিটি reference-ই fault — ১১টি। মাঝের সংখ্যা algorithm-নির্ভর। সাধারণত frame বাড়লে fault কমে — ব্যতিক্রম অংশ ৩-এ।

এই পর্বজুড়ে দুটি string বারবার আসবে। প্রথমটি Silberschatz-এর পাঠ্যবইয়ের পরিচিত ২০টি reference: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 (ছয়টি আলাদা page: 0, 1, 2, 3, 4, 7). দ্বিতীয়টি Belady's anomaly-র ১২টি reference: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

৩ · FIFO — যে আগে এসেছে, সে আগে যাবে

সবচেয়ে সহজ নীতি: FIFO (first-in, first-out). প্রতিটি page RAM-এ আসার সময় একটি queue-র শেষে বসে; সরাতে হলে queue-র মাথার page — যে সবচেয়ে আগে এসেছিল। বাস্তবায়নে কোনো hardware লাগে না, প্রতি reference-এ কোনো কাজও নেই; শুধু fault-এর সময় queue-তে একটি যোগ আর একটি বাদ।

ঠিক এই দুর্বলতা পাঠ্যবইয়ের string-এ দেখা যায় (পুরো trace অংশ ৫-এর stepper-এ)। Page 0 এই string-এর সবচেয়ে ব্যস্ত page — ২০টির মধ্যে ৬ বার আসে। FIFO ধাপ ১০-এ (page 3 আনার সময়) 0-কে সরায়, কারণ সে তখন queue-র মাথায়; আর পরের ধাপেই, ধাপ ১১-এ, 0 আবার লাগে — আরেকটি fault. FIFO-র মোট fault ১৫টি, তিন নীতির মধ্যে সবচেয়ে বেশি।

Belady's anomaly — বেশি frame, বেশি fault

স্বাভাবিক বুদ্ধি বলে, একটি প্রসেসকে বেশি frame দিলে fault কমবে বা অন্তত বাড়বে না। ১৯৬৯ সালে László Bélády, R. A. Nelson আর G. S. Shedler (IBM) দেখান, FIFO-তে এটি সবসময় সত্য নয়। এটিই Belady's anomaly. নিচে ১২টি reference-এর string-টি ৩ আর ৪ frame-এ পাশাপাশি চলছে।

1 ref 12 ref 23 ref 34 ref 45 ref 16 ref 27 ref 58 ref 19 ref 210 ref 311 ref 412 ref 5

ফল: ৩ frame-এ ৯টি fault, ৪ frame-এ ১০টি. ধাপ ৪ পর্যন্ত ৪-frame মেমরি ৩-frame মেমরির সব page ধরে রেখেছিল, তাই ধাপ ৫ আর ৬-এ সে hit পেল, ৩-frame পেল না — এ পর্যন্ত প্রত্যাশিত। কিন্তু সেই hit-গুলোর কারণে ৪-frame-এর queue-তে 1 আর 2 “পুরোনো” থেকে গেল (FIFO hit-এ queue বদলায় না), আর ধাপ ৭-এ page 5 আসতেই 1 বিদায় নিল — অথচ ৩-frame মেমরি তখন 1-কে রেখে দিয়েছে। বড় মেমরির page-সেট আর ছোটটিকে ধারণ করে না — অংশ ৬-এ এটিই মূল চাবি।

নিচের finder একই string-এ frame ১ থেকে ৭ পর্যন্ত FIFO আর LRU চালায়, আর যেখানে frame বাড়ানোয় fault বেড়েছে, সেখানে ANOMALY লেখে।

// Belady's anomaly finder: page faults for 1..7 frames, FIFO vs LRU.
function faults(refs, n, policy) {
  const mem = [];                                  // mem[0] is always the next victim
  let f = 0;
  for (const p of refs) {
    const i = mem.indexOf(p);
    if (i >= 0) {                                  // hit
      if (policy === "LRU") { mem.splice(i, 1); mem.push(p); }  // move to most-recent end
      continue;                                    // FIFO ignores hits
    }
    f++;
    if (mem.length === n) mem.shift();             // evict oldest load / least recent use
    mem.push(p);
  }
  return f;
}
function report(title, refs) {
  console.log(title + ": " + refs.join(","));
  for (const policy of ["FIFO", "LRU"]) {
    const c = [];
    for (let n = 1; n <= 7; n++) c.push(faults(refs, n, policy));
    const bad = [];
    for (let n = 2; n <= 7; n++) if (c[n - 1] > c[n - 2]) bad.push((n - 1) + "->" + n + " frames");
    console.log("  " + policy.padEnd(4) + " frames 1..7: " + c.join(" ") +
                (bad.length ? "   ANOMALY at " + bad.join(", ") : "   never increases"));
  }
}
report("Belady string", [1,2,3,4,1,2,5,1,2,3,4,5]);
report("Classic string", [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1]);

Belady string: 1,2,3,4,1,2,5,1,2,3,4,5
  FIFO frames 1..7: 12 12 9 10 5 5 5   ANOMALY at 3->4 frames
  LRU  frames 1..7: 12 12 10 8 5 5 5   never increases
Classic string: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
  FIFO frames 1..7: 20 15 15 10 9 6 6   never increases
  LRU  frames 1..7: 20 17 12 8 7 6 6   never increases

৪ · OPT (MIN) — ভবিষ্যৎ জানলে কী করতাম

পাঠ্যবইয়ের string-এ ধাপ ৪-এ (page 2 এল, frame-এ 7, 0, 1) সামনের দিকে তাকান: 0 আবার লাগবে ধাপ ৫-এ, 1 লাগবে ধাপ ১৪-এ, 7 লাগবে ধাপ ১৮-এ — সবচেয়ে দূরে, তাই 7 যায়। ধাপ ৮-এ (page 4; frame-এ 2, 0, 3) 2 লাগবে ধাপ ৯-এ, 3 ধাপ ১০-এ, 0 ধাপ ১১-এ — তাই 0 যায়। এভাবে চালালে মোট fault ৯টি; এর মধ্যে ৬টি compulsory (ছয়টি আলাদা page), অর্থাৎ replacement-এর কারণে মাত্র ৩টি। এই string-এ ৩ frame দিয়ে ৯-এর কম fault অসম্ভব।

কেন OPT সর্বোত্তম — প্রমাণের রূপরেখা

এটি পর্ব ১৭-এর SJF-এর আত্মীয়: দুজনেই “ভবিষ্যৎ জানলে সেরা”, আর দুজনেরই একই সমস্যা — বাস্তবে ভবিষ্যৎ জানা যায় না। কোন ঠিকানা কখন ছোঁয়া হবে, তা নির্ভর করে input আর ব্যবহারকারীর ওপর।

তাহলে OPT কী কাজে লাগে? মাপকাঠি হিসেবে। একটি প্রোগ্রামের address trace আগে রেকর্ড করে রাখা হলে (অফলাইনে) পুরো ভবিষ্যৎ জানা থাকে; সেই trace-এ OPT চালিয়ে জানা যায় সম্ভাব্য সেরা ফল কত। নতুন নীতি OPT-এর চেয়ে কয়েক শতাংশ বেশি fault দিলে উন্নতির জায়গা কম; বহু গুণ বেশি দিলে চিন্তার বিষয়।

৫ · LRU — অতীত দেখে ভবিষ্যতের অনুমান

ভবিষ্যৎ না জানলে সবচেয়ে ভালো আন্দাজ কী? পর্ব ৪-এর locality of reference: যে page সম্প্রতি ব্যবহৃত হয়েছে, সেটি শিগগির আবার লাগার সম্ভাবনা বেশি (temporal locality); যে page অনেকক্ষণ ছোঁয়া হয়নি, সেটি হয়তো আর লাগবে না। তাই LRU (least recently used) নীতি: যে page সবচেয়ে বেশি সময় ধরে ব্যবহৃত হয়নি, সেটি সরানো। OPT সামনে তাকায় — “কে সবচেয়ে দেরিতে লাগবে”; LRU পেছনে তাকায় — “কে সবচেয়ে আগে লেগেছিল”। সময়ের দিক উল্টে দেওয়া OPT.

একটি সুন্দর প্রতিসাম্য আছে: কোনো string S-এ LRU-র fault-সংখ্যা, উল্টো string-এ (শেষ থেকে শুরু) LRU-র fault-সংখ্যার সমান; OPT-এর বেলায়ও তাই। এই পর্বের simulator দিয়ে পাঠ্যবইয়ের string উল্টে চালালে ৩ frame-এ LRU আবার ১২, OPT আবার ৯ দেয়। (খেয়াল করুন: “উল্টো string-এ LRU = মূল string-এ OPT” — এমন দাবি ভুল; এখানে ১২ ≠ ৯.)

নিচের stepper-এ তিন নীতি একই string-এ পাশাপাশি চলছে — পরীক্ষার খাতায় যেভাবে টেবিল আঁকতে হয়, প্রতিটি কলাম একেকটি ধাপ। প্রতিটি fault-এ কেন ওই victim, তা ডান দিকের বাক্সে লেখা; ক্যাপশনের “মোট fault” FIFO / LRU / OPT ক্রমে।

1 ref 7   next: 0 1 2 0 3 0 …2 ref 0   next: 1 2 0 3 0 4 …3 ref 1   next: 2 0 3 0 4 2 …4 ref 2   next: 0 3 0 4 2 3 …5 ref 0   next: 3 0 4 2 3 0 …6 ref 3   next: 0 4 2 3 0 3 …7 ref 0   next: 4 2 3 0 3 2 …8 ref 4   next: 2 3 0 3 2 1 …9 ref 2   next: 3 0 3 2 1 2 …10 ref 3   next: 0 3 2 1 2 0 …11 ref 0   next: 3 2 1 2 0 1 …12 ref 3   next: 2 1 2 0 1 7 …13 ref 2   next: 1 2 0 1 7 0 …14 ref 1   next: 2 0 1 7 0 115 ref 2   next: 0 1 7 0 116 ref 0   next: 1 7 0 117 ref 1   next: 7 0 118 ref 7   next: 0 119 ref 0   next: 120 ref 1   next: -

LRU-র ১২টি fault, OPT-এর ৯-এর কাছাকাছি, FIFO-র ১৫-এর চেয়ে অনেক ভালো। LRU কোথায় OPT-এর কাছে হারে? ধাপ ৯-এ (page 2) LRU 3-কে সরায়, কারণ 3 শেষ ব্যবহৃত হয়েছিল ধাপ ৬-এ — কিন্তু 3 আবার লাগে ঠিক পরের ধাপে। অতীত দিয়ে ভবিষ্যৎ আন্দাজ করলে এমন ভুল হবেই; locality যত জোরালো, ভুল তত কম।

নিচের simulator একই কাজ চারটি নীতিতে করে — FIFO, OPT, LRU আর Clock (Clock অংশ ৭-এ) — আর খাতার মতো টেবিল ছাপে: প্রতিটি কলাম একটি reference, প্রতিটি সারি একটি frame, শেষ সারিতে F মানে fault, ফাঁকা মানে hit. refs আর N বদলে নিজের বইয়ের অঙ্ক যাচাই করতে পারেন — তবে আগে হাতে করুন।

// Page-replacement simulator: FIFO, OPT, LRU and Clock on one reference string.
const refs = [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1];
const N = 3;                                        // number of frames
const policies = {
  FIFO:  (s) => s.queue.shift(),                    // frame loaded longest ago
  OPT:   (s, t, fr) => { let best = 0, far = -1;    // page used farthest in the future
           fr.forEach((p, i) => { let nx = refs.indexOf(p, t + 1); if (nx < 0) nx = Infinity;
             if (nx > far) { far = nx; best = i; } }); return best; },
  LRU:   (s, t, fr) => fr.reduce((b, p, i) => s.last[p] < s.last[fr[b]] ? i : b, 0),
  Clock: (s) => { while (s.bit[s.hand]) { s.bit[s.hand] = 0; s.hand = (s.hand + 1) % N; }
           const v = s.hand; s.hand = (s.hand + 1) % N; return v; }  // give second chances
};
for (const [name, victim] of Object.entries(policies)) {
  const fr = Array(N).fill(null), s = { queue: [], last: {}, bit: Array(N).fill(0), hand: 0 };
  const rows = fr.map(() => []), mark = [];
  let faults = 0;
  refs.forEach((p, t) => {
    let i = fr.indexOf(p);
    if (i >= 0) mark.push(" ");                     // hit
    else {
      faults++; mark.push("F");
      i = fr.indexOf(null);                         // use a free frame if there is one
      if (i < 0) i = victim(s, t, fr);
      fr[i] = p; s.queue.push(i);
    }
    s.last[p] = t; s.bit[i] = 1;                    // every reference sets the reference bit
    fr.forEach((q, k) => rows[k].push(q === null ? "." : q));
  });
  console.log(name + " (" + faults + " faults)");
  console.log("ref    " + refs.join(" "));
  rows.forEach((r, k) => console.log("frame" + k + " " + r.join(" ")));
  console.log("fault  " + mark.join(" ") + "\n");
}

FIFO (15 faults)
ref    7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
frame0 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7
frame1 . 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
frame2 . . 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
fault  F F F F   F F F F F F     F F     F F F

OPT (9 faults)
ref    7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
frame0 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
frame1 . 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
frame2 . . 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
fault  F F F F   F   F     F     F       F

LRU (12 faults)
ref    7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
frame0 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
frame1 . 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0
frame2 . . 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7
fault  F F F F   F   F F F F     F   F   F

Clock (14 faults)
ref    7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
frame0 7 7 7 2 2 2 2 4 4 4 4 3 3 3 3 0 0 0 0 0
frame1 . 0 0 0 0 0 0 0 2 2 2 2 2 1 1 1 1 7 7 7
frame2 . . 1 1 1 3 3 3 3 3 0 0 0 0 2 2 2 2 2 1
fault  F F F F   F   F F   F F   F F F   F   F

LRU বাস্তবায়নের দুই উপায় — আর তাদের দাম

সমস্যাটা “প্রতি access-এ”। CPU সেকেন্ডে শত কোটি memory access করে; প্রতিটিতে software দিয়ে (interrupt-এ) হিসাব রাখলে মেমরি দশ গুণ বা বেশি ধীর হতো। তাই পুরো LRU প্রায় কোনো বাস্তব OS-এর page replacement-এ নেই; আছে তার সস্তা অনুকরণ (অংশ ৭)। ছোট, software-নিয়ন্ত্রিত cache-এ (যেখানে প্রতিটি access এমনিতেই software-এর ভেতর দিয়ে যায়) অবশ্য সত্যিকারের LRU সহজ — নিচের C প্রোগ্রামটি counter-পদ্ধতি দেখায়।

#include <stdio.h>
#define MAXF 8

/* LRU with a "counter" per frame: every access stores the current time;
   the victim is the frame with the smallest (oldest) time stamp. */
int lru_faults(const int *refs, int len, int nframes) {
    int page[MAXF], stamp[MAXF], used = 0, faults = 0;
    for (int t = 0; t < len; t++) {
        int i = -1;
        for (int k = 0; k < used; k++) if (page[k] == refs[t]) i = k;
        if (i < 0) {                                  /* page fault */
            faults++;
            if (used < nframes) i = used++;           /* free frame */
            else {                                    /* search all stamps: O(frames) */
                i = 0;
                for (int k = 1; k < used; k++) if (stamp[k] < stamp[i]) i = k;
            }
            page[i] = refs[t];
        }
        stamp[i] = t;                                 /* the "clock register" copy */
    }
    return faults;
}

int main(void) {
    int belady[]  = {1,2,3,4,1,2,5,1,2,3,4,5};
    int classic[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
    for (int n = 3; n <= 4; n++)
        printf("Belady string,  %d frames: %d faults\n", n, lru_faults(belady, 12, n));
    printf("Classic string, 3 frames: %d faults\n", lru_faults(classic, 20, 3));
    return 0;
}

Belady string,  3 frames: 10 faults
Belady string,  4 frames: 8 faults
Classic string, 3 frames: 12 faults

৬ · Stack algorithm — কেন LRU আর OPT-এ anomaly হয় না

Belady's anomaly কেন FIFO-তে হয়, কিন্তু LRU-তে কখনো নয় — পরীক্ষার প্রিয় তাত্ত্বিক প্রশ্ন। উত্তর ১৯৭০ সালের গবেষণাপত্রে: R. L. Mattson, J. Gecsei, D. R. Slutz আর I. L. Traiger, “Evaluation techniques for storage hierarchies” (IBM Systems Journal).

FIFO-র বেলায় inclusion ভাঙার প্রমাণ আমরা Belady stepper-এই দেখেছি: ধাপ ৭-এর পর ৩-frame-এর সেট {1, 2, 5}, ৪-frame-এর সেট {2, 3, 4, 5} — 1 ছোট মেমরিতে আছে, বড়টিতে নেই। ঠিক পরের ধাপে 1 চাওয়া হলো: ৩ frame-এ hit, ৪ frame-এ fault.

একবার চালিয়ে সব মেমরি-আকারের উত্তর — stack distance

Mattson-এর গবেষণার ব্যবহারিক রত্ন এটি। LRU stack একবার পুরো string-এর ওপর চালান; প্রতিটি reference-এ দেখুন চাওয়া page stack-এর কত গভীরে ছিল — একে বলে stack distance (প্রথমবার এলে ∞)। তাহলে n frame-এর LRU-তে fault = যেসব reference-এর stack distance > n. একটি পাস, আর সব n-এর উত্তর একসাথে — cache-এর আকার ঠিক করার জন্য এটি আজও ব্যবহৃত হয়। Belady string-এ:

৭ · LRU-র কাছাকাছি — reference bit, second chance আর clock

পুরো LRU দামি, কিন্তু hardware একটি সস্তা সাহায্য দেয়: প্রতিটি page table entry-তে একটি reference bit (x86-এ A বা Accessed বিট)। Page-টি পড়া বা লেখা হলেই MMU নিজে সেটি ১ করে; শূন্য করে শুধু OS. এক বিটে ক্রম জানা যায় না, শুধু “শেষবার শূন্য করার পর ব্যবহৃত কি না”।

Additional-reference-bits — ৮ বিটের ইতিহাস

প্রতিটি page-এর জন্য memory-তে একটি ৮ বিটের byte রাখুন। নিয়মিত বিরতিতে (ধরুন প্রতি ১০০ ms-এ একটি timer interrupt-এ) OS প্রতিটি page-এর reference bit ওই byte-এর সবচেয়ে বাঁ দিকে (high-order) ঢুকিয়ে দেয়, বাকি বিটগুলো এক ঘর ডানে সরিয়ে দেয় (shift register), সবচেয়ে ডানের বিট ফেলে দেয়, তারপর reference bit শূন্য করে। ফলে byte-টি শেষ ৮টি বিরতির ব্যবহারের ইতিহাস।

• 00000000 — শেষ ৮টি বিরতিতে একবারও ব্যবহৃত হয়নি।
• 11111111 — প্রতিটি বিরতিতে ব্যবহৃত।
• 11000100 বনাম 01110111: unsigned সংখ্যা হিসেবে প্রথমটি ১৯৬, দ্বিতীয়টি ১১৯. প্রথমটি শেষ দুই বিরতিতে ব্যবহৃত, দ্বিতীয়টি সর্বশেষ বিরতিতে নয় — তাই সবচেয়ে ছোট সংখ্যার page-টিই আনুমানিক LRU, এখানে দ্বিতীয়টি সরবে।

সমান হলে তাদের মধ্যে FIFO. বেশি বিট মানে লম্বা ইতিহাস, কিন্তু বেশি কাজ; ইতিহাস-byte না রেখে শুধু reference bit দেখলে নিচের second chance.

Second chance আর clock

মূলে FIFO, শুধু একটি দয়া যোগ করা: queue-র মাথার page-এর reference bit ১ হলে তাকে সরানো হয় না — বিট শূন্য করে তাকে আবার queue-র শেষে পাঠানো হয়, যেন সে এইমাত্র এসেছে; এটিই তার “দ্বিতীয় সুযোগ”। বিট ০ হলে সে বিদায়। যে page এত ঘন ঘন ব্যবহৃত হয় যে প্রতি ঘুরতি পর্যন্ত বিট আবার ১ হয়ে যায়, সে কখনো সরে না।

Queue থেকে বের করে আবার ঢোকানোর ঝামেলা এড়াতে বাস্তবায়নটি হয় একটি circular queue-তে: frame-গুলো একটি ঘড়ির মুখের মতো বৃত্তে সাজানো, আর একটি pointer — ঘড়ির কাঁটা বা hand — পরের প্রার্থী দেখায়। Fault হলে hand এগোয়: বিট ১ পেলে শূন্য করে পরের frame-এ যায়, বিট ০ পেলে সেই page সরিয়ে সেখানে নতুন page বসায় আর এক ঘর এগিয়ে থামে। এই রূপটিই clock algorithm; Multics প্রকল্পের F. J. Corbató ১৯৬৮ সালের একটি গবেষণাপত্রে এর বর্ণনা দেন বলে সাধারণত কৃতিত্ব দেওয়া হয়।

1 ref 72 ref 03 ref 14 ref 25 ref 06 ref 37 ref 08 ref 49 ref 210 ref 311 ref 0… refs 12-20: 3 2 1 2 0 1 7 0 1

ধাপ ৪ আর ৮ লক্ষ করুন: তিনটি বিটই ১ থাকায় hand পুরো এক পাক ঘুরে সবাইকে শূন্য করে, তারপর যেখান থেকে শুরু করেছিল সেখানেই victim পায় — সব বিট ১ হলে clock হুবহু FIFO হয়ে যায়। এ কারণে clock-ও stack algorithm নয়; Belady string-এ এই পর্বের simulator-এর নিয়মে clock-ও ৩ frame-এ ৯, ৪ frame-এ ১০টি fault দেয় — FIFO-র মতোই anomaly. নিচের C প্রোগ্রাম একই নিয়মে প্রতিটি ধাপ ছাপে — JS simulator-এর Clock টেবিলের সাথে মিলিয়ে দেখুন।

#include <stdio.h>
#define N 3                                   /* frames */

int refs[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
int frame[N] = {-1, -1, -1};                  /* -1 = empty */
int bit[N];                                   /* reference bits */
int hand = 0;                                 /* the clock hand */

int main(void) {
    int len = sizeof refs / sizeof refs[0], faults = 0;
    for (int t = 0; t < len; t++) {
        int p = refs[t], i = -1;
        for (int k = 0; k < N; k++) if (frame[k] == p) i = k;
        char mark = ' ';
        if (i < 0) {                          /* page fault */
            faults++; mark = 'F';
            for (int k = 0; k < N && i < 0; k++) if (frame[k] == -1) i = k;
            if (i < 0) {                      /* no free frame: run the clock */
                while (bit[hand]) { bit[hand] = 0; hand = (hand + 1) % N; }
                i = hand; hand = (hand + 1) % N;
            }
            frame[i] = p;
        }
        bit[i] = 1;                           /* the hardware sets R on every access */
        printf("ref %d %c  frames", p, mark);
        for (int k = 0; k < N; k++) {
            if (frame[k] < 0) printf("  .");
            else printf(" %2d", frame[k]);
        }
        printf("  R=%d%d%d  hand->%d\n", bit[0], bit[1], bit[2], hand);
    }
    printf("Clock, %d frames: %d page faults\n", N, faults);
    return 0;
}

ref 7 F  frames  7  .  .  R=100  hand->0
ref 0 F  frames  7  0  .  R=110  hand->0
ref 1 F  frames  7  0  1  R=111  hand->0
ref 2 F  frames  2  0  1  R=100  hand->1
ref 0    frames  2  0  1  R=110  hand->1
ref 3 F  frames  2  0  3  R=101  hand->0
ref 0    frames  2  0  3  R=111  hand->0
ref 4 F  frames  4  0  3  R=100  hand->1
ref 2 F  frames  4  2  3  R=110  hand->2
ref 3    frames  4  2  3  R=111  hand->2
ref 0 F  frames  4  2  0  R=001  hand->0
ref 3 F  frames  3  2  0  R=101  hand->1
ref 2    frames  3  2  0  R=111  hand->1
ref 1 F  frames  3  1  0  R=010  hand->2
ref 2 F  frames  3  1  2  R=011  hand->0
ref 0 F  frames  0  1  2  R=111  hand->1
ref 1    frames  0  1  2  R=111  hand->1
ref 7 F  frames  0  7  2  R=010  hand->2
ref 0    frames  0  7  2  R=110  hand->2
ref 1 F  frames  0  7  1  R=111  hand->0
Clock, 3 frames: 14 page faults

Enhanced second chance — reference আর modify বিট একসাথে

অংশ ১-এর dirty bit মনে করুন: dirty page সরাতে দুটি I/O, পরিষ্কারটিতে একটি। তাই (reference, modify) জোড়া দিয়ে চারটি শ্রেণি করা হয়:

Clock-এর মতোই hand ঘোরে, কিন্তু প্রথমে সবচেয়ে নিচের যে শ্রেণিতে কেউ আছে, সেই শ্রেণির প্রথম page সরায়; দরকারে বৃত্তটি কয়েকবার ঘুরতে হতে পারে। ফল: সম্প্রতি অব্যবহৃত আর পরিষ্কার page-কে অগ্রাধিকার — I/O কম। Silberschatz-এর পাঠ্যবই এর একটি রূপ পুরোনো Macintosh-এর virtual memory-তে ব্যবহারের কথা বলে; Tanenbaum-এর বইয়ে প্রায় একই ধারণা NRU (not recently used) নামে আছে।

৮ · গণনা-ভিত্তিক নীতি আর page buffering

LFU আর MFU

প্রতিটি page কতবার ব্যবহৃত হয়েছে, একটি counter-এ গুনে রাখুন। তারপর দুই বিপরীত যুক্তি:

• LFU (least frequently used): সবচেয়ে কম ব্যবহৃত page সরানো — যুক্তি, যে বেশি ব্যবহৃত, সে গুরুত্বপূর্ণ। সমস্যা: যে page প্রোগ্রামের শুরুর দিকে খুব ব্যবহৃত হয়েছিল কিন্তু এখন আর লাগে না, তার বড় count তাকে চিরকাল রেখে দেয়। প্রতিকার: নিয়মিত সব count এক বিট ডানে সরিয়ে (অর্ধেক করে) পুরোনো ইতিহাস ক্ষয় করা।
• MFU (most frequently used): সবচেয়ে বেশি ব্যবহৃত page সরানো — যুক্তি, ছোট count-এর page হয়তো এইমাত্র এসেছে, তাকে এখনো ব্যবহারের সুযোগ দেওয়া উচিত।

দুটিই বাস্তবে কম ব্যবহৃত — LRU-র মতোই দামি, অথচ OPT-এর ভালো অনুকরণ নয়। এই পর্বের simulator-এ count = RAM-এ আসার পর থেকে ব্যবহারের সংখ্যা, আর সমান হলে সবচেয়ে ছোট নম্বরের frame — এই নিয়মে পাঠ্যবইয়ের string-এ ৩ frame-এ LFU ১৪টি fault দেয় (অনুশীলন ৪-এ নিজে যোগ করে দেখবেন), যা LRU-র ১২-এর চেয়ে খারাপ। তবে অ্যাপ্লিকেশন-cache-এ, যেখানে কিছু key সত্যিই চিরকাল জনপ্রিয় (একটি ওয়েবসাইটের হোমপেজ), ক্ষয়সহ LFU ভালো কাজ করে — অংশ ৯-এ Redis.

Page buffering — হাতে কয়েকটি ফাঁকা frame রাখা

উপরের যেকোনো algorithm-এর পাশে OS কয়েকটি কৌশল যোগ করে, যাতে fault-এর সময় অপেক্ষা কম হয়:

• ফাঁকা frame-এর পুল (free-frame pool): সবসময় কয়েকটি frame ফাঁকা রাখা। Fault হলে নতুন page সোজা একটি ফাঁকা frame-এ পড়া হয় — victim লেখার অপেক্ষা ছাড়াই। Victim পরে লেখা হয়ে পুলে যোগ হয়।
• Dirty page আগেভাগে লেখা: ডিস্ক অলস থাকলে বদলানো page-গুলো লিখে তাদের dirty bit শূন্য করা — পরে victim হলে আর লিখতে হবে না।
• পুলের frame-এ কে ছিল মনে রাখা: ফাঁকা পুলে যাওয়া frame-এর পুরোনো ডেটা তখনো মোছা হয়নি। সেই page আবার লাগলে, frame-টি অন্য কাউকে দেওয়ার আগেই, ডিস্কে না গিয়ে সোজা ফেরত — একটি “soft” fault. ফলে ভুল victim বাছাইয়ের ক্ষতি অনেকটা মুছে যায়।

শেষ কৌশলটির বিখ্যাত উদাহরণ DEC-এর VAX/VMS: পাঠ্যবইয়ের বর্ণনা অনুযায়ী VAX hardware-এ reference bit ছিল না, তাই VMS সাধারণ FIFO চালাত, আর সরানো page-গুলোকে ফাঁকা ও modified তালিকায় কিছুক্ষণ রেখে দিত — ভুল করে সরানো ব্যস্ত page দ্রুত ফেরত পাওয়া যেত (ভাবনার প্রশ্ন ৫)। আজকের Windows-এর standby আর modified list এই একই ধারণার উত্তরসূরি।

৯ · বাস্তব সিস্টেমে — Linux, Windows আর অ্যাপ্লিকেশন-cache

Linux: active/inactive list থেকে MGLRU

Linux বহু বছর ধরে (২.৬-এর যুগ থেকে) পুরো মেমরিকে কয়েকটি LRU তালিকায় রাখে — প্রতিটি ধরনের জন্য একটি active আর একটি inactive list; ২.৬.২৮ থেকে ফাইলের page (page cache) আর anonymous memory (heap, stack) আলাদা তালিকায়। নতুন page সাধারণত inactive list-এ ঢোকে; দ্বিতীয়বার ব্যবহৃত হলে active-এ ওঠে। মেমরি কম পড়লে kswapd নামের kernel thread inactive list-এর তলা থেকে page দেখে: hardware-এর accessed বিট ১ হলে তাকে আরেক সুযোগ দেয় (second chance-এর ছায়া), না হলে ফেরত নেয় — পরিষ্কার ফাইল-page সোজা ফেলে দিয়ে, dirty বা anonymous page লিখে বা swap করে।

দুই তালিকার কারণ একটি পরিচিত দুর্বলতা: একটি বড় ফাইল একবার পড়লে (ধরুন backup নেওয়া বা ভিডিও কপি করা) সাধারণ LRU সেই একবার-ব্যবহৃত page দিয়ে পুরো মেমরি ভরে ফেলে, আর সত্যিই ব্যস্ত page সরিয়ে দেয়। দুই তালিকায় একবার-ব্যবহৃত page inactive-এই থেকে যায় আর সেখান থেকেই বিদায় নেয় — একে scan resistance বলে।

Linux ৬.১ (ডিসেম্বর ২০২২) থেকে একটি বিকল্প নকশা kernel-এ এসেছে: MGLRU (multi-gen LRU), মূলত Google-এর Yu Zhao-র কাজ। দুই তালিকার বদলে page-গুলো কয়েকটি “প্রজন্মে” (generation) ভাগ হয়; বয়স বাড়ানোর জন্য kernel প্রসেসের page table ধরে ধরে accessed বিট পড়ে, আর সবচেয়ে পুরোনো প্রজন্ম থেকে ফেরত নেয়। Google ChromeOS আর Android-এর পরীক্ষায় kswapd-এর CPU খরচ আর low-memory kill কমার কথা জানিয়েছিল; বিভিন্ন workload-এ ফল ভিন্ন হতে পারে। এটি CONFIG_LRU_GEN দিয়ে compile হয়, আর অনেক distro-তে চালু থাকলেও সব জায়গায় ডিফল্ট নয় — নিজের মেশিনে দেখে নিন:

$ grep -E '^(Active|Inactive)' /proc/meminfo
Active:          5123456 kB
Inactive:        2345678 kB
Active(anon):    1987654 kB
Inactive(anon):   456789 kB
Active(file):    3135802 kB
Inactive(file):  1888889 kB
$ cat /sys/kernel/mm/lru_gen/enabled     # file absent = kernel built without MGLRU
0x0007

0x0007 মানে MGLRU চালু (বিটগুলো তার আলাদা অংশ নির্দেশ করে), 0x0000 মানে বন্ধ — তখন পুরোনো active/inactive নীতি চলে। পড়তে সাধারণ ব্যবহারকারীই যথেষ্ট; বদলাতে root লাগে — তার আগে kernel ডকুমেন্টেশনের multigen_lru অংশ পড়ে নিন। Linux-এর reclaim, page cache আর swap-এর বাস্তব দিক পর্ব ৩৮-এ।

Windows: working set আর trimming

Windows প্রতিটি প্রসেসের RAM-এ থাকা page-গুলোকে তার working set বলে (পর্ব ৩৭-এর তাত্ত্বিক working set-এর সাথে নামের মিল, অর্থ পুরো এক নয়)। ফাঁকা RAM কমে গেলে memory manager-এর একটি অংশ (working set manager) প্রসেসগুলোর working set থেকে কম ব্যবহৃত page ছেঁটে ফেলে — working-set trimming (accessed বিট দেখে বয়স হিসাব করে)। ছাঁটা page সঙ্গে সঙ্গে হারায় না: পরিষ্কার হলে যায় standby list-এ, dirty হলে modified list-এ (পরে modified page writer লেখে)। প্রসেস আবার সেটি চাইলে ডিস্ক ছাড়াই ফেরত পায় — অংশ ৮-এর page buffering. Task Manager-এর “Standby” মেমরি আসলে এই তালিকা।

OS-এর বাইরে — একই প্রশ্ন সবখানে

• CPU cache: set-associative cache-এ একটি set-এর কয়েকটি way-এর মধ্যে কোনটি সরবে, তা hardware ঠিক করে প্রতি clock cycle-এ — পুরো LRU সেখানে খুব দামি, তাই অনেক নকশা কয়েকটি বিট দিয়ে pseudo-LRU (যেমন tree-PLRU) ব্যবহার করে।
• Database-এর buffer pool: PostgreSQL তার shared buffers-এ clock-sweep চালায় — প্রতিটি buffer-এ একটি ছোট usage count, hand ঘোরার সময় কমে; MySQL-এর InnoDB একটি LRU তালিকা রাখে যার মাঝখানে নতুন page ঢোকে (midpoint insertion), যাতে বড় table scan পুরো pool ধুয়ে না দেয়। বিস্তারিত DBMS কোর্সের storage internals পর্বে।
• Redis: maxmemory ছাড়ালে allkeys-lru নীতিতে key সরায় — কিন্তু সত্যিকারের LRU তালিকা রাখে না; কয়েকটি key নমুনা হিসেবে তুলে (ডিফল্ট maxmemory-samples 5) তাদের মধ্যে সবচেয়ে পুরোনোটি সরায় — LRU-র সস্তা অনুকরণ। ৪.০ থেকে ক্ষয়সহ LFU নীতিও আছে।
• নিজের কোডে: ওয়েব অ্যাপের ছোট cache-এ সত্যিকারের LRU সহজ — hash table + doubly linked list, প্রতিটি get/put O(1). ইন্টারভিউর “LRU cache লিখুন” প্রশ্নটি ঠিক এটিই।

১০ · AI-এর যুগে page replacement

Page replacement-এর অঙ্ক AI সঙ্গে সঙ্গে করে দেয় — আর প্রায়ই ভুল করে। বারবার দেখা ভুলগুলো:

AI-এর উত্তর মানার আগে — চেকলিস্ট

• শুরুর fault গোনা হয়েছে কি না, আর প্রশ্নের নিয়মের সাথে মেলে কি না দেখেছি
• প্রতিটি কলামে frame-এ ঠিক N টি বা তার কম page আছে, কোনো page দুবার নেই — দেখেছি
• অন্তত তিনটি fault-এ victim-এর কারণ নিজে মিলিয়েছি (OPT-এর বেলায় সামনে গুনে)
• মোট fault এই পর্বের simulator দিয়ে যাচাই করেছি; সংখ্যাগুলো OPT ≤ LRU-র মতো যুক্তিসঙ্গত সম্পর্ক মানে কি না দেখেছি
• AI-এর দেওয়া simulator-কে একটি জানা উত্তরের string দিয়ে (Belady string: FIFO ৩ frame ৯, ৪ frame ১০) আগে পরীক্ষা করেছি
• বাস্তব সিস্টেমের দাবি (Linux, Windows, Redis) — কোন version, কোন OS — ডকুমেন্টেশন বা man page-এ মিলিয়েছি; কোনো sudo বা sysctl কমান্ড না বুঝে production-এ চালাইনি