Frame allocation, thrashing আর working set

১ · প্রতিটি প্রসেস কয়টি frame পাবে — নিচের আর ওপরের সীমা

পর্ব ৩৫-এ দেখেছেন demand paging: প্রসেসের সব page শুরুতে RAM-এ আসে না; যে page দরকার, সেটি প্রথম ছোঁয়ার সময় page fault হয়, আর OS তখন ডিস্ক থেকে এনে একটি page frame-এ বসায়। পর্ব ৩৬-এ দেখেছেন frame খালি না থাকলে page replacement algorithm কাকে সরাবে — FIFO, Optimal, LRU, Clock. কিন্তু একটি প্রশ্ন এখনো খোলা: RAM-এ ধরুন মোট ৬২টি frame, আর চলছে দুটি বা দশটি প্রসেস। কে কয়টি frame পাবে? এই প্রশ্নের নাম frame allocation.

নিচের সীমা — instruction set ঠিক করে

একটি প্রসেসকে যত খুশি কম frame দেওয়া যায় না। কারণটি সূক্ষ্ম। Page fault হয় একটি instruction-এর মাঝখানে। OS page এনে দেওয়ার পর সেই instruction-টি আবার শুরু থেকে চালাতে হয়। এখন ধরুন একটি instruction তিনটি ভিন্ন page ছোঁয় — instruction নিজে এক page-এ, যে ঠিকানা থেকে পড়বে সেটি আরেক page-এ, যেখানে লিখবে সেটি তৃতীয় page-এ। প্রসেসের ভাগে মাত্র দুটি frame থাকলে কী হবে? তৃতীয় page আনতে প্রথমটি সরাতে হবে; instruction আবার শুরু হলে প্রথমটির জন্য আবার fault — চিরকাল ঘুরতেই থাকবে, একটি instruction-ও শেষ হবে না।

কয়েকটি উদাহরণ, সহজ থেকে কঠিন:

• সরল load/store মেশিন (বেশিরভাগ RISC — ARM, RISC-V): প্রতিটি memory instruction একটিমাত্র memory-ঠিকানা ছোঁয়। Instruction-এর page + data-র page = ২টি। (Instruction নিজে দুই page-এর সীমানায় পড়লে আরও একটি লাগত — কিন্তু ক্লাসিক RISC-এ instruction-এর দৈর্ঘ্য নির্দিষ্ট (৪ byte) আর ঠিকানা সাজানো (aligned), তাই একটি instruction দুই page-এ ভাগ হয় না। ARM-এর Thumb-2 বা RISC-V-র compressed instruction-এর মতো মিশ্র দৈর্ঘ্যের রূপে অবশ্য এটি ঘটতে পারে।)
• এক স্তরের indirect addressing: instruction-এর ভেতরের ঠিকানায় আসলে আরেকটি ঠিকানা লেখা, যেটি আসল ডেটার দিকে নির্দেশ করে। Instruction + ঠিকানার ঘর + ডেটা = ৩টি। বহু স্তরের indirection চললে তাত্ত্বিকভাবে পুরো virtual memory লাগতে পারে — তাই এমন মেশিন স্তরের একটি সীমা (একটি counter) বেঁধে দেয়।
• IBM System/370-এর MVC (memory থেকে memory-তে ২৫৬ byte পর্যন্ত কপি): instruction নিজে ৬ byte, দুই page-এর সীমানায় পড়তে পারে; উৎস-ব্লকও দুই page-এ ছড়াতে পারে; গন্তব্য-ব্লকও। সবচেয়ে খারাপ ক্ষেত্রে ৬টি frame — পাঠ্যবইয়ের বিখ্যাত উদাহরণ।
• x86: instruction-এর দৈর্ঘ্য পরিবর্তনশীল আর সাজানো থাকার বাধ্যবাধকতা নেই, আর movs-এর মতো string instruction উৎস আর গন্তব্য দুটোই memory-তে ছোঁয়; তাই x86-এর সর্বনিম্নও কয়েকটি page — নির্দিষ্ট সংখ্যা মডেলভেদে আলাদা হিসাব করা হয়।

২ · ভাগের নিয়ম — equal, proportional আর priority

নিচের আর ওপরের সীমার মাঝে OS কীভাবে ভাগ করবে? তিনটি ক্লাসিক নিয়ম, ধরুন m = মোট frame, n = প্রসেসের সংখ্যা।

পাঠ্যবইয়ের উদাহরণটি ধাপে ধাপে দেখুন — ৬২টি frame, দুটি প্রসেস: একটি ১০ page-এর ছাত্র-প্রসেস, আরেকটি ১২৭ page-এর ডেটাবেস। শেষ ধাপে একটি তৃতীয় প্রসেস আসে, আর দেখবেন সবার ভাগ কীভাবে ছোট হয়:

1 m = 62, s1 = 10, s2 = 1272 S = s1 + s2 = 1373 a1 = 10/137 x 62 = 4.53 -> 44 a2 = 127/137 x 62 = 57.47 -> 575 4 + 57 = 61, 1 frame free6 P3 (50 pages) arrives: S = 187

নিচের calculator একই হিসাব করে, আর সর্বনিম্ন frame-এর নিয়মও মানে — ভাগ সর্বনিম্নের কম হলে বাড়িয়ে দেয়, তাতে মোট m ছাড়ালে সবচেয়ে বড় ভাগ থেকে কেটে নেয়:

// Frame allocation: equal (m / n) vs proportional a_i = floor(s_i / S * m).
// Every process gets at least minF frames; frames left over stay in the free pool.
function allocate(m, sizes, minF) {
  const n = sizes.length, S = sizes.reduce((x, y) => x + y, 0);
  const exact = sizes.map(s => s / S * m);
  const a = exact.map(e => Math.max(minF, Math.floor(e)));
  let used = a.reduce((x, y) => x + y, 0);
  while (used > m) {                                  // a minimum pushed us over m:
    const big = a.indexOf(Math.max(...a));            // take back from the largest
    a[big]--; used--;
  }
  console.log("m = " + m + ", S = " + S + ", minimum = " + minF + ", equal share = " + Math.floor(m / n));
  sizes.forEach((s, i) => console.log("  P" + (i + 1) + ": s = " + String(s).padStart(3) +
    "  s/S*m = " + exact[i].toFixed(2).padStart(5) + "  -> " + String(a[i]).padStart(2) + " frames"));
  console.log("  given " + used + ", free pool " + (m - used));
}
allocate(62, [10, 127], 2);       // the textbook example
allocate(40, [3, 60, 137], 2);    // a tiny process meets the minimum
allocate(62, [10, 127, 50], 2);   // a third process arrives: everyone shrinks

m = 62, S = 137, minimum = 2, equal share = 31
  P1: s =  10  s/S*m =  4.53  ->  4 frames
  P2: s = 127  s/S*m = 57.47  -> 57 frames
  given 61, free pool 1
m = 40, S = 200, minimum = 2, equal share = 13
  P1: s =   3  s/S*m =  0.60  ->  2 frames
  P2: s =  60  s/S*m = 12.00  -> 12 frames
  P3: s = 137  s/S*m = 27.40  -> 26 frames
  given 40, free pool 0
m = 62, S = 187, minimum = 2, equal share = 20
  P1: s =  10  s/S*m =  3.32  ->  3 frames
  P2: s = 127  s/S*m = 42.11  -> 42 frames
  P3: s =  50  s/S*m = 16.58  -> 16 frames
  given 61, free pool 1

একটি সীমাবদ্ধতা মনে রাখুন: equal আর proportional দুটোই প্রসেসের আকার দেখে, আচরণ দেখে না। ১২৭ page-এর ডেটাবেস হয়তো এই মুহূর্তে মাত্র ২০টি page নিয়ে কাজ করছে, আর ১০ page-এর প্রসেস একটি টাইট লুপে তার সব ১০টিই চাইছে। আকার নয়, এখন কতটা লাগছে — এই প্রশ্নের উত্তরই অংশ ৬-এর working set.

৩ · কার frame কেড়ে নেওয়া হবে — global না local replacement

Page fault হলো, কোনো frame খালি নেই। Replacement algorithm একটি victim বাছবে — কিন্তু কোন সেট থেকে? দুটি পথ:

সাধারণ-উদ্দেশ্যের OS-এ global replacement বেশি প্রচলিত, কারণ মোট throughput বেশি। Linux-এর page reclaim মূলত global — cgroup-এর সীমা না থাকলে kernel প্রতিটি NUMA node-এ সব প্রসেসের page একই LRU তালিকাগুলোতে রাখে। তবে container-এর যুগে “একজন পাশের জনকে ধীর করে দিচ্ছে” (noisy neighbour) সমস্যাটি বড় হয়ে উঠেছে, তাই Linux cgroup দিয়ে প্রতিটি দলের জন্য আলাদা সীমা বসানো যায় — দলের ভেতরে reclaim হয় local-এর মতো (অংশ ৮)। Windows প্রতিটি প্রসেসের জন্য আলাদা working set রাখে আর নিজের working set-এর ভেতর থেকেই page সরায় — local-এর কাছাকাছি — কিন্তু মেমরি কম পড়লে সবার working set ছাঁটে, যা একটি global সিদ্ধান্ত। বাস্তব সিস্টেম তাই প্রায়ই দুটোর মিশ্রণ।

NUMA — কোন frame, সেটিও প্রশ্ন

বড় সার্ভারে সব RAM সমান দূরে নয়। NUMA মেশিনে প্রতিটি CPU-গুচ্ছের (node) নিজস্ব কাছের মেমরি থাকে; অন্য node-এর মেমরি পড়তে বেশি সময় লাগে। তাই প্রশ্ন শুধু “কয়টি frame” নয়, “কোন node-এর frame”. Linux-এর ডিফল্ট নীতি সাধারণত “first touch” — যে CPU প্রথম page-টি ছোঁয়, তার node থেকে frame দেওয়া হয়; আর scheduler প্রসেসকে সেই node-এর CPU-তেই রাখার চেষ্টা করে (affinity, পর্ব ২০)। numactl বা set_mempolicy() দিয়ে নীতি বদলানো যায়, আর Linux-এর automatic NUMA balancing প্রয়োজনে page-কে প্রসেসের কাছে সরিয়ে নিতে পারে। প্রতিটি node-এর জন্য আলাদা free list আর আলাদা reclaim thread থাকে — অর্থাৎ বড় মেশিনে allocation আসলে কয়েকটি ছোট মেশিনের allocation.

৪ · Thrashing — ব্যস্ত ডিস্ক, অলস CPU

একটি প্রসেস যে page-গুলো নিয়ে এই মুহূর্তে সক্রিয়ভাবে কাজ করছে, সেগুলোর জন্য যথেষ্ট frame না পেলে কী হয়? সে একটি page আনে, সেটি বসাতে আরেকটি সরায় — যেটি একটু পরেই আবার লাগবে। আবার fault, আবার সরানো। প্রসেসটি সময়ের বেশিরভাগ কাটায় page-এর জন্য অপেক্ষায়, কাজে নয়। এই অবস্থার নাম thrashing.

CPU utilisation-এর বক্ররেখা

পর্ব ২-এ 1 − pⁿ মডেলে দেখেছেন: প্রতিটি কাজ সময়ের p অংশ I/O-র অপেক্ষায় থাকলে, degree of multiprogramming n বাড়ালে CPU utilisation 1 − pⁿ-এর মতো বাড়ে। সেখানে ধরে নেওয়া হয়েছিল মেমরিতে সবার জায়গা আছে। কিন্তু frame সীমিত হলে n বাড়ানো মানে প্রত্যেকের ভাগ কমানো (অংশ ২-এর শেষ ধাপ)। একটা সময় পর ভাগ এত ছোট হয় যে fault-এর বন্যা শুরু হয়, আর সব fault যায় একটিই paging-ডিস্কে। ডিস্ক একসাথে একটির বেশি fault সামলাতে পারে না — সে-ই তখন সীমা।

নিচের খেলনা-মডেলটি এই দুই শক্তিকে একসাথে বসায়। ১২০টি frame, প্রতিটি প্রসেস এখন ৩০টি page নিয়ে কাজ করে, প্রতি ১ ms CPU কাজের সাথে ১.৫ ms সাধারণ I/O-র অপেক্ষা, আর প্রতিটি page fault ডিস্কে ৫ ms খায়। ভাগ ৩০-এর কম হলে fault-এর হার দ্রুত বাড়ে:

// Toy thrashing model. m frames shared equally by n identical processes.
// Per 1 ms of CPU work a process also waits io ms for ordinary I/O, and
// takes f page faults, each costing T ms on ONE shared paging disk.
const m = 120, wss = 30, io = 1.5, T = 5;            // frames, pages, ms, ms
const faultsPerMs = a => a >= wss ? 0.002 : 0.002 + 2 * (1 - a / wss) ** 2;
for (let n = 1; n <= 10; n++) {
  const a = Math.floor(m / n), f = faultsPerMs(a);
  const p = (io + f * T) / (1 + io + f * T);            // fraction of time waiting
  const multi = 1 - p ** n;                             // 1 - p^n
  const disk = 1 / (f * T);                             // disk can serve 1 fault per T ms
  const u = Math.min(multi, disk);
  console.log("n=" + String(n).padStart(2) + " frames/proc=" + String(a).padStart(3) +
    " faults/ms=" + f.toFixed(3) + " CPU " + String(Math.round(u * 100)).padStart(3) + "% " +
    "#".repeat(Math.round(u * 40)) + (disk < multi ? "  <- paging disk is the limit" : ""));
}

n= 1 frames/proc=120 faults/ms=0.002 CPU  40% ################
n= 2 frames/proc= 60 faults/ms=0.002 CPU  64% ##########################
n= 3 frames/proc= 40 faults/ms=0.002 CPU  78% ###############################
n= 4 frames/proc= 30 faults/ms=0.002 CPU  87% ###################################
n= 5 frames/proc= 24 faults/ms=0.082 CPU  88% ###################################
n= 6 frames/proc= 20 faults/ms=0.224 CPU  86% ##################################
n= 7 frames/proc= 17 faults/ms=0.378 CPU  53% #####################  <- paging disk is the limit
n= 8 frames/proc= 15 faults/ms=0.502 CPU  40% ################  <- paging disk is the limit
n= 9 frames/proc= 13 faults/ms=0.644 CPU  31% ############  <- paging disk is the limit
n=10 frames/proc= 12 faults/ms=0.722 CPU  28% ###########  <- paging disk is the limit

দুষ্টচক্র — OS নিজেই আগুনে ঘি ঢালে

১৯৬০-এর দশকের কিছু সিস্টেমে long-term scheduler-এর নিয়ম ছিল সরল: “CPU utilisation কম হলে আরও একটি কাজ মেমরিতে আনা হবে।” 1 − pⁿ-এর জগতে এটি যুক্তিসংগত। কিন্তু thrashing-এ CPU কম ব্যস্ত কারণ প্রসেস বেশি। নিচের stepper-এ মডেলের সংখ্যাগুলো দিয়েই চক্রটি ঘুরিয়ে দেখুন:

Thrashing-এর কারণগুলো

• অতিরিক্ত degree of multiprogramming — উপরের চক্র: সবার মোট সক্রিয় চাহিদা RAM-এর চেয়ে বেশি।
• Global replacement-এর ছোঁয়াচে প্রভাব — একটি প্রসেস locality বদলালে (নতুন ধাপে ঢুকলে) অন্যদের frame কাড়ে, তারা fault করে আরও কাড়ে।
• একটি প্রসেসের নিজের চাহিদা RAM-এর চেয়ে বড় — যেমন RAM-এর চেয়ে বড় একটি matrix সারি ধরে না পড়ে কলাম ধরে পড়া, বা RAM-এর চেয়ে বড় heap-এ garbage collector-এর পুরো heap ঘোরা। এখানে কোনো scheduling নীতিই বাঁচাতে পারে না।
• ভুল নীতি — FIFO-র মতো যে replacement সক্রিয় page-কেও সরিয়ে দেয় (পর্ব ৩৬), বা ভাগের হিসাবে আচরণ না দেখে শুধু আকার দেখা।

৫ · Locality model — প্রোগ্রাম এক পাড়া থেকে আরেক পাড়ায় যায়

Thrashing ঠেকাতে হলে জানতে হবে একটি প্রসেসের আসলে কতটা লাগে। উত্তরের চাবি locality of reference: একটি সময়ে প্রোগ্রাম তার মেমরির ছোট একটি অংশই বারবার ছোঁয়। Locality model এর সাথে একটি গুরুত্বপূর্ণ কথা যোগ করে: locality সময়ের সাথে বদলায়।

একটি ফাংশন ডাকা হলে প্রোগ্রাম নতুন locality-তে ঢোকে: সেই ফাংশনের কোডের page, তার local ভ্যারিয়েবলের stack page, আর সে যে ডেটা নিয়ে কাজ করে তার page. ফাংশন শেষ হলে এই locality ছেড়ে পুরোনোটিতে ফেরে বা নতুন একটিতে যায়। দুটি locality-র কিছু page মিলতেও পারে। একটি payroll প্রোগ্রাম কল্পনা করুন — প্রথমে কর্মীদের ফাইল পড়ার ধাপ (এক locality), তারপর বেতন হিসাবের ধাপ (আরেক), শেষে রিপোর্ট ছাপার ধাপ (আরেক)।

এখান থেকে thrashing-এর একটি নিখুঁত মানদণ্ড পাওয়া যায়: একটি প্রসেস তার বর্তমান locality-র সব page ধরে রাখার মতো frame পেলে সে locality বদলানোর সময় ছাড়া প্রায় fault করে না। তার চেয়ে কম পেলে সে thrash করবে। সমস্যা হলো, locality মাথায় রাখা সহজ, মাপা কঠিন — OS কীভাবে জানবে প্রসেস এখন কোন পাড়ায়?

৬ · Denning-এর working-set model

Δ-এর ভূমিকা ক্যামেরার লেন্সের মতো। Δ খুব ছোট হলে working set পুরো locality ধরে না — দরকারি page বাদ পড়ে। Δ খুব বড় হলে কয়েকটি পুরোনো locality মিলে যায় — অকারণ বড় হিসাব। Δ = ∞ হলে প্রসেসের জীবনে ছোঁয়া সব page. (এই কোর্সের পর্ব ৯-এ working set শব্দটি দেখেছেন সাধারণ অর্থে, “সাম্প্রতিক ব্যবহৃত page”; Denning-এর সংজ্ঞা সেটিকেই Δ দিয়ে নিখুঁত করে।)

সমাধান করা উদাহরণ — Δ = ১০

একটি প্রসেসের ২৬টি reference: 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4. শুরুতে প্রসেসটি page ১, ২, ৫, ৬, ৭ নিয়ে কাজ করে, শেষে শুধু ৩ আর ৪ নিয়ে। নিচে Δ = ১০-এর জানালাটি ডানে সরছে; ^ চিহ্নগুলো জানালার ভেতরের reference, t-সারির অঙ্কগুলো অবস্থানের শেষ অঙ্ক (১১ লেখা হয়েছে 1 হিসেবে):

নিচের calculator একই reference string-এ নির্দিষ্ট সময়গুলোর WS(t, ১০) ছাপে, তারপর তিনটি Δ-এর জন্য প্রতিটি সময়ের WSS, working-set নীতিতে মোট fault (যে reference-এর page শেষ Δটির মধ্যে ছোঁয়া হয়নি) আর গড় WSS:

// Working set WS(t, D) = distinct pages among the last D references r(t-D+1) .. r(t).
const refs = [2,6,1,5,7,7,7,7,5,1, 6,2,3,4,1,2,3,4,4,4, 3,4,3,4,4,4];
const ws = (t, D) => [...new Set(refs.slice(Math.max(0, t - D), t))].sort((a, b) => a - b);

console.log("t   r(t)  WS(t, 10)          WSS");
for (const t of [10, 14, 18, 22, 26])
  console.log(String(t).padEnd(4) + String(refs[t - 1]).padEnd(6) +
              ("{" + ws(t, 10).join(",") + "}").padEnd(19) + ws(t, 10).length);

for (const D of [3, 5, 10]) {
  let faults = 0, sum = 0;
  const line = refs.map((p, i) => {
    if (!ws(i, D).includes(p)) faults++;          // not referenced in the last D -> fault
    const w = ws(i + 1, D).length; sum += w; return w;
  });
  console.log("D=" + String(D).padEnd(3) + "WSS: " + line.join(" ") +
              "  faults=" + faults + " avg WSS=" + (sum / refs.length).toFixed(2));
}

t   r(t)  WS(t, 10)          WSS
10  1     {1,2,5,6,7}        5
14  4     {1,2,3,4,5,6,7}    7
18  4     {1,2,3,4,5,6}      6
22  4     {1,2,3,4}          4
26  4     {3,4}              2
D=3  WSS: 1 2 3 3 3 2 1 1 2 3 3 3 3 3 3 3 3 3 2 1 2 2 2 2 2 1  faults=16 avg WSS=2.27
D=5  WSS: 1 2 3 4 5 4 3 2 2 3 4 5 5 5 5 4 4 4 4 3 2 2 2 2 2 2  faults=10 avg WSS=3.23
D=10 WSS: 1 2 3 4 5 5 5 5 5 5 4 5 6 7 7 7 7 6 5 5 4 4 4 4 3 2  faults=8 avg WSS=4.62

একটি ছোট প্রমাণ — Δ বাড়ালে fault কখনো বাড়ে না

পর্ব ৩৬-এ দেখেছেন FIFO-তে frame বাড়ালেও fault বাড়তে পারে (Belady's anomaly). Working-set নীতিতে এটি অসম্ভব। প্রমাণ:

1. সংজ্ঞা অনুযায়ী WS(t, Δ) ⊆ WS(t, Δ + 1), কারণ শেষ Δটি reference শেষ Δ + 1টির অংশ। তাই একই t-তে WSS Δ-এর সাথে কখনো কমে না।
2. Working-set নীতিতে reference r_t fault করে ঠিক তখনই, যখন r_t ∉ WS(t − 1, Δ) — অর্থাৎ ওই page-এর আগের ছোঁয়া Δটির বেশি reference আগে (বা কখনো নয়)।
3. Δ বাড়ালে (১) অনুযায়ী WS(t − 1, Δ) শুধু বড় হয়, তাই কোনো hit কখনো fault-এ বদলায় না; কিছু fault hit-এ বদলাতে পারে। অতএব মোট fault Δ-এর একটি অ-বর্ধমান (non-increasing) ফাংশন। ∎

উপরের আউটপুটে ১৬ ≥ ১০ ≥ ৮ ঠিক এটাই দেখায়। দাম দিতে হয় মেমরিতে: গড় WSS Δ-এর সাথে বাড়ে।

মোট চাহিদা আর thrashing-এর নিয়ম

প্রতিটি প্রসেস i-এর working-set size WSS_i জানা থাকলে সিস্টেমের মোট চাহিদা:

নিয়মটি সহজ। D ≤ m হলে প্রত্যেককে তার working set দেওয়া যায়, আর বাড়তি frame থাকলে নতুন প্রসেস আনা যায়। D > m হলে অন্তত একটি প্রসেস তার working set ধরে রাখতে পারবে না; সংজ্ঞা অনুযায়ী সে এমন page-এ fault করবে যা সে সাম্প্রতিক Δটির মধ্যে ছুঁয়েছে, অর্থাৎ বর্তমান locality-র page — এটাই thrashing-এর শুরু। তখন OS একটি প্রসেস suspend করে (সাধারণত সবচেয়ে কম priority-র, বা সবচেয়ে বড়টি, নীতিভেদে), তার frame বাকিদের দেয়, আর পরে D কমলে তাকে ফেরায়। অংশ ৪-এর stepper-এর ভাষায়: n = ৬-এ D = ১৮০ > ১২০, তাই নিয়মটি CPU পড়ে যাওয়ার আগেই সতর্ক করত। এভাবে working set একসাথে দুটি কাজ করে: thrashing ঠেকায়, আর নিরাপদ সীমার মধ্যে degree of multiprogramming যত বেশি সম্ভব রাখে।

৭ · Working set আন্দাজ করা, আর PFF

সংজ্ঞাটি সুন্দর, কিন্তু খরচ ভয়াবহ: প্রতিটি memory reference-এ জানালা সরানো আর সেট আপডেট করা মানে প্রতি কয়েক ন্যানোসেকেন্ডে হিসাব। কোনো hardware এটি করে না। তাই OS একটি আনুমানিক রূপ বানায় দুটি উপকরণ দিয়ে: পর্ব ৩৬-এর reference bit (page ছোঁয়া হলেই hardware যেটি ১ করে) আর একটি নিয়মিত timer interrupt.

পাঠ্যবইয়ের আনুমানিক কৌশল

ধরুন Δ = ১০,০০০ reference. Timer প্রতি ৫,০০০ reference-এ (সময় দিয়ে মাপা হয়, এখানে সহজ করে reference-এ বলা) একটি interrupt দেয়। প্রতিটি page-এর জন্য মেমরিতে রাখা হয় ২টি ইতিহাস-bit. প্রতিটি interrupt-এ OS:

1. প্রতিটি page-এর ইতিহাস-bit-গুলো এক ঘর সরায় (পুরোনোটি হারিয়ে যায়), আর এখনকার reference bit-টি নতুন ঘরে কপি করে;
2. সব reference bit শূন্য করে দেয়, যাতে পরের ৫,০০০ reference-এ কে ছোঁয়া হলো আবার দেখা যায়।

যেকোনো সময় একটি page-কে working set-এর অংশ ধরা হয়, যদি তার reference bit বা দুটি ইতিহাস-bit-এর অন্তত একটি ১ হয় — অর্থাৎ সেটি মোটামুটি শেষ ১০,০০০ থেকে ১৫,০০০ reference-এর মধ্যে ছোঁয়া হয়েছে।

Page-fault frequency (PFF) — ফলাফল দেখে নিয়ন্ত্রণ

Working set মাপার বদলে একটি সরাসরি পথ আছে: যা এড়াতে চাই, সেটিই মাপা। Thrashing মানে উঁচু fault rate. তাই page-fault frequency (PFF) কৌশলে OS প্রতিটি প্রসেসের fault rate মাপে আর দুটি সীমা বেঁধে দেয়:

(সংখ্যাগুলো শুধু উদাহরণ; বাস্তব সীমা মেশিন আর ডিস্কের গতির ওপর নির্ভর করে।) PFF আসলে একটি feedback controller — ঘরের এসির thermostat-এর মতো: বেশি গরম হলে ঠান্ডা বাড়ানো, বেশি ঠান্ডা হলে কমানো। Working set-এর সাথে এর সম্পর্কও ঘনিষ্ঠ: locality বদলের সময় working set ফুলে ওঠে, তখন fault rate-ও লাফ দেয়; নতুন locality-র page সব RAM-এ এসে গেলে fault rate আবার নামে। অর্থাৎ fault rate-এর লাফগুলোই working set-এর পরিবর্তনের ছায়া।

৮ · বাস্তবের OS — Linux আর Windows কী করে

এখানে পাঠ্যবই আর বাস্তবের মধ্যে একটি বড় ফাঁক আছে, যা ইন্টারভিউতে প্রায়ই ধরা হয়: Linux কোনো স্পষ্ট working-set scheduler চালায় না। সে D গোনে না, D > m হলে নিজে থেকে প্রসেস suspend করে না। তার বদলে কয়েকটি স্তরের ব্যবস্থা কাজ করে (বিস্তারিত পর্ব ৩৮-এ):

• Page reclaim আর kswapd: প্রতিটি NUMA node-এর জন্য একটি kernel thread, kswapd. খালি মেমরি একটি “low” watermark-এর নিচে নামলে সে জেগে ওঠে আর active/inactive LRU তালিকা থেকে কম ব্যবহৃত page মুক্ত করে — ডিস্কে লেখা আছে এমন file page সোজা ফেলে দেয়, পরিবর্তিত page আগে লিখে নেয়, আর anonymous page (heap, stack) swap-এ পাঠায়। চাপ আরও বাড়লে allocation-এর অনুরোধকারী প্রসেস নিজেই reclaim করতে বাধ্য হয় — direct reclaim, যা সেই প্রসেসকে ধীর করে।
• OOM killer: reclaim করেও মেমরি না পেলে kernel একটি প্রসেস বেছে বন্ধ করে দেয় — মূলত যে সবচেয়ে বেশি মেমরি ধরে আছে, oom_score_adj দিয়ে সমন্বয় করা। Denning-এর “suspend” যেখানে প্রসেসকে পরে ফেরত আনে, OOM killer সেখানে স্থায়ীভাবে মেরে ফেলে — নিষ্ঠুর, কিন্তু সিস্টেম বাঁচে।
• PSI (pressure stall information): Linux 4.20 (২০১৮) থেকে kernel মাপে, কাজগুলো মেমরির অপেক্ষায় কতটা সময় আটকে আছে। /proc/pressure/memory-তে দুটি লাইন: some — সময়ের কত শতাংশে অন্তত একটি কাজ মেমরির জন্য আটকে ছিল; full — কত শতাংশে সব সক্রিয় কাজ একসাথে আটকে ছিল। full-এর উঁচু মান thrashing-এর প্রায় সরাসরি মাপ। কিছু kernel-এ PSI বন্ধ থাকতে পারে (psi=1 boot option বা build config দিয়ে চালু হয়)।
• cgroup v2-এর memory.high আর memory.max: একটি cgroup memory.high ছাড়ালে kernel সেই দলকে ধীর করে আর জোর দিয়ে তারই page reclaim করে — দলের ভেতরে local replacement-এর মতো। memory.max হলো কঠিন সীমা; সেটি ছাড়ালে দলের ভেতরেই OOM. প্রতিটি cgroup-এর নিজস্ব memory.pressure ফাইলও থাকে। systemd-oomd বা Android-এর lmkd-এর মতো user-space টুল PSI দেখে আগেভাগেই কম গুরুত্বপূর্ণ প্রসেস বন্ধ করে — এটিকে বলা যায় Denning-এর নিয়মের আধুনিক, user-space রূপ।

নিচের bash কোড এই কন্টেইনারের kernel থেকে আসল সংখ্যাগুলো পড়ে। /proc/vmstat-এর pgfault হলো বুটের পর মোট page fault, pgmajfault হলো তাদের মধ্যে major fault (ডিস্ক থেকে পড়তে হয়েছে), বাকিগুলো minor fault (page RAM-এই ছিল, শুধু page table-এ বসাতে হয়েছে):

echo "--- /proc/pressure/memory (PSI) ---"
cat /proc/pressure/memory 2>/dev/null || echo "(not available on this kernel)"
echo "--- /proc/vmstat: since boot, whole machine ---"
grep -E '^(pgfault|pgmajfault|pswpin|pswpout|pgscan_kswapd|oom_kill) ' /proc/vmstat
echo "--- /proc/meminfo ---"
grep -E '^(MemTotal|MemAvailable|SwapTotal|SwapFree):' /proc/meminfo
echo "--- this container's cgroup limits ---"
for f in memory.max memory.high memory.current; do
    if [ -r "/sys/fs/cgroup/$f" ]; then echo "$f = $(cat /sys/fs/cgroup/$f)"; fi
done
read -r -a st < /proc/$$/stat        # fields 10 and 12: minflt, majflt
echo "this shell: minor faults ${st[9]}, major faults ${st[11]}"

--- /proc/pressure/memory (PSI) ---
some avg10=0.00 avg60=0.00 avg300=0.00 total=14801991025
full avg10=0.00 avg60=0.00 avg300=0.00 total=8254130176
--- /proc/vmstat: since boot, whole machine ---
pswpin 105618903
pswpout 135327574
pgfault 96629579710
pgmajfault 110950864
pgscan_kswapd 1654945654
oom_kill 12
--- /proc/meminfo ---
MemTotal:        2008912 kB
MemAvailable:    1352316 kB
SwapTotal:       6041596 kB
SwapFree:        5626488 kB
--- this container's cgroup limits ---
memory.max = max
memory.high = max
memory.current = 937984
this shell: minor faults 284, major faults 0

নিজের Linux মেশিনে চাপ চলাকালীন দেখতে চাইলে vmstat 1 চালান: si আর so কলাম প্রতি সেকেন্ডে swap-in আর swap-out, wa কলাম CPU-র I/O-অপেক্ষার শতাংশ। Thrashing-এর ছবি হলো — si/so টানা উঁচু, wa উঁচু, us (user কাজ) নিচু। (এটি একটি উদাহরণ-ধারণা; কলামের বিস্তারিত পর্ব ৫৭-এ।)

Windows — working set manager

Windows-এর memory manager সরাসরি “working set” শব্দটিই ব্যবহার করে: প্রতিটি প্রসেসের working set মানে তার যে page-গুলো এখন RAM-এ আছে (Task Manager-এর “Memory” কলামের পেছনে মূলত এটিই)। প্রতিটি প্রসেসের একটি ন্যূনতম আর সর্বোচ্চ working set-সীমা থাকে, আর replacement প্রধানত প্রসেসের নিজের working set-এর ভেতরে হয়। Kernel-এর working set manager (balance set manager নামের system thread-এর অংশ) নিয়মিত, আর খালি মেমরি কমে গেলে আরও ঘন ঘন, প্রসেসগুলোর working set ছাঁটে — বহুদিন না ছোঁয়া page আগে সরে। ছাঁটা page সঙ্গে সঙ্গে হারায় না; standby তালিকায় থাকে, আবার লাগলে soft fault-এ ফিরে আসে। এটি Denning-এর ধারণার কাছাকাছি, যদিও Δ-জানালা গুনে নয়, বয়স আর চাপ দেখে। (macOS-ও নিজের পথে চলে — মেমরির চাপে প্রথমে page compress করে, আর iOS-এ চাপ বেশি হলে পেছনের app বন্ধ করে দেয়।)

বাস্তবের পরামর্শ — ওষুধ আসলে দুটিই

সব কৌশলের শেষে সত্যটি সহজ: সক্রিয় চাহিদা D যদি সত্যিই RAM-এর চেয়ে বেশি হয়, তাহলে কোনো replacement algorithm বা tuning চক্র থেকে বাঁচাতে পারে না। ওষুধ দুটি — বেশি RAM, নয়তো একসাথে কম প্রসেস (বা প্রসেসগুলোর মেমরি চাহিদা কমানো)। বাস্তবে এর অর্থ:

• সার্ভারে swap-এর ব্যবহার আর PSI-র full মান নজরে রাখুন; টানা উঁচু হলে tuning নয়, ক্ষমতা পরিকল্পনা দরকার।
• Container-এ memory.high দিয়ে নরম সীমা আর memory.max দিয়ে কঠিন সীমা বসান, যাতে একটি সার্ভিস বাকিদের thrash না করায়।
• Worker-এর সংখ্যা (web server-এর process, database-এর connection) এমনভাবে বাঁধুন যাতে সবার working set মিলে RAM-এ আঁটে — “বেশি worker = বেশি গতি” সবসময় সত্য নয়, ঠিক অংশ ৪-এর বক্ররেখার মতো।
• ডেস্কটপে মেশিন হঠাৎ ধীর আর ডিস্ক-বাতি জ্বলে থাকলে আগে দেখুন কোন প্রোগ্রাম মেমরি খাচ্ছে (Task Manager বা top); প্রায়ই একটি ব্রাউজারের শত ট্যাবই দোষী।

৯ · AI-এর যুগে — মেমরির চাপ নিয়ে AI-কে প্রশ্ন

“আমার সার্ভার ধীর, মেমরি ভরা” — এমন প্রশ্নে AI দ্রুত পরামর্শ দেয়, কিন্তু এই বিষয়ে কয়েকটি ভুল বারবার দেখা যায়:

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

• Proportional allocation-এর ভাগ নিজে হিসাব করেছি, নিচে গোল করেছি, আর যোগফল m-এর বেশি নয় দেখেছি
• WS(t, Δ)-এর জানালায় ঠিক Δটি reference আছে কি না গুনেছি, আর উপরের calculator-এ মিলিয়েছি
• “Linux/Windows এটা করে” ধরনের দাবি kernel ডকুমেন্টেশন বা man page দিয়ে যাচাই করেছি, আর kernel version মিলিয়েছি
• পরামর্শ দেওয়া কমান্ড আমার distro আর OS-এর জন্যই কি না দেখেছি; পড়ার কাজে sudo বা chmod 777 মানিনি
• পরিবর্তনের আগে আর পরে PSI আর pgmajfault মেপে তুলনা করেছি — শুধু “এখন দ্রুত লাগছে” দেখে নয়, লোড দিয়ে পরীক্ষা করে