Multilevel queue আর multilevel feedback queue

১ · এক লাইনের সমস্যা — সব কাজ একরকম নয়

পর্ব ১৭ আর ১৮-তে আপনি কয়েকটি scheduling নীতি দেখেছেন। প্রতিটির একটি করে দুর্বলতা আছে। FCFS-এ একটি লম্বা কাজ সামনে থাকলে পেছনের ছোট কাজগুলো আটকে থাকে। SJF আর SRTF গড় অপেক্ষা সবচেয়ে কম রাখে, কিন্তু তার জন্য আগে থেকেই জানতে হয় কোন কাজের CPU burst কত লম্বা — যা OS সাধারণত জানে না। Round Robin সবাইকে সমান ভাগ দেয় ঠিকই, কিন্তু টাইপ করা মানুষ আর ভিডিও রেন্ডার করা প্রোগ্রামকে একই চোখে দেখে।

আপনার ল্যাপটপে এই মুহূর্তে কী চলছে ভাবুন। একটি text editor, যে বেশিরভাগ সময় কিবোর্ডের অপেক্ষায় ঘুমিয়ে থাকে, আর একটি অক্ষর এলে কয়েক মাইক্রোসেকেন্ড কাজ করে আবার ঘুমায় — এটি I/O-bound. পটভূমিতে একটি বড় প্রজেক্ট compile হচ্ছে, যে সুযোগ পেলেই একটানা CPU খায় — এটি CPU-bound. Editor-এর কাছে দরকার কম response time; compile-এর কাছে দরকার মোট কাজ বা throughput. একটিমাত্র ready queue আর একটিমাত্র নিয়ম দিয়ে দুজনকে একসাথে খুশি রাখা কঠিন।

২ · Multilevel queue — স্থায়ী শ্রেণি, প্রতিটির নিজের নিয়ম

Multilevel queue scheduling-এ ready queue কয়েকটি আলাদা queue-তে ভাগ থাকে, আর প্রতিটি প্রসেস তার ধরন অনুযায়ী (মেমরির আকার, অগ্রাধিকার, প্রসেসের ধরন) একটি queue-তে স্থায়ীভাবে বসানো হয়। পাঠ্যবইয়ের একটি পরিচিত চিত্রে (Silberschatz-এর বইয়ের নতুন সংস্করণে) ওপর থেকে নিচে চারটি queue: real-time, system, interactive আর batch প্রসেস; পুরোনো সংস্করণে ছিল পাঁচটি — system, interactive, interactive editing, batch আর student প্রসেস।

এরপর দুটি সিদ্ধান্ত লাগে। প্রথমত, প্রতিটি queue-এর ভেতরে কোন algorithm চলবে — ওপরের টেবিলে তা আছে। দ্বিতীয়ত, queue-গুলোর মধ্যে CPU কীভাবে ভাগ হবে। এর দুটি প্রচলিত উপায়:

Time slicing-এর ছোট হিসাব: ধরুন foreground queue সারাক্ষণ ব্যস্ত, আর background-এ একটি ৬ ms-এর কাজ t = ০-তে এল। প্রতিটি ১০ ms চক্রের শেষ ২ ms background পায়: ৮–১০, ১৮–২০, ২৮–৩০. তিন চক্রে ৬ ms পূর্ণ হয়, কাজটি শেষ হয় t = ৩০-এ। Fixed priority হলে foreground যতক্ষণ ব্যস্ত, এই কাজ একটুও এগোত না।

সমাধান করা উদাহরণ — fixed priority, তিনটি queue

প্রশ্ন: তিনটি queue — Q0 = system (FCFS), Q1 = interactive (RR, q = ২), Q2 = batch (FCFS). Queue-গুলোর মধ্যে fixed priority, preemptive. পাঁচটি প্রসেস (ms-এ):

একটি নিয়ম ঠিক করে নিই, যা বেশিরভাগ বই মানে: নিচের queue-এর কেউ preempt হলে সে নিজের queue-এর সামনেই থাকে, আর RR-এর মাঝপথে থামলে বাকি quantum নিয়ে ফেরে। (প্রশ্নে অন্য নিয়ম দেওয়া থাকলে সেটিই মানবেন।) নিচে ধাপে ধাপে দেখুন।

1 0- 1  P1 (Q2 batch)2 1- 3  P2 (Q1), P1 preempted3 3- 5  P3 (Q1)4 5- 7  P5 (Q0 system)5 7-10  P2, P3 (Q1) done610-18  P1, P4 (Q2 FCFS)

নিচের simulator একই হিসাব করে। কোনো প্রসেসের cls বা arrive বদলে আবার চালিয়ে দেখুন — যেমন P5-কে batch-এ নিলে কী হয়।

// Multilevel queue: every process is fixed to one class (queue) for life.
// Queue 0 = system (FCFS), 1 = interactive (RR, q = 2), 2 = batch (FCFS).
// Between queues: fixed priority, preemptive (a lower queue runs only if all higher are empty).
const quantum = [Infinity, 2, Infinity];
const procs = [
  { name: "P1", cls: 2, arrive: 0, burst: 6 },
  { name: "P2", cls: 1, arrive: 1, burst: 4 },
  { name: "P3", cls: 1, arrive: 2, burst: 3 },
  { name: "P4", cls: 2, arrive: 3, burst: 3 },
  { name: "P5", cls: 0, arrive: 5, burst: 2 },
];
const Q = [[], [], []], ps = procs.map(p => ({ ...p, left: p.burst, used: 0 }));
let t = 0, gantt = [];
while (ps.some(p => p.left > 0)) {
  ps.forEach(p => { if (p.arrive === t) Q[p.cls].push(p); });
  const lv = Q.findIndex(q => q.length);
  const p = lv < 0 ? null : Q[lv][0];
  const name = p ? p.name : "idle", last = gantt[gantt.length - 1];
  if (last && last.name === name) last.end = t + 1; else gantt.push({ name, start: t, end: t + 1 });
  t++;
  if (!p) continue;
  p.left--; p.used++;
  if (p.left === 0) { p.fin = t; Q[lv].shift(); }
  else if (p.used === quantum[lv]) { p.used = 0; Q[lv].push(Q[lv].shift()); } // RR: to the tail
}
console.log(gantt.map(g => g.start + "-" + g.end + " " + g.name).join(" | "));
let tat = 0, wt = 0;
for (const p of [...ps].sort((a, b) => a.name.localeCompare(b.name))) {
  tat += p.fin - p.arrive; wt += p.fin - p.arrive - p.burst;
  console.log(p.name + " queue " + p.cls + ": finish " + p.fin + ", TAT " + (p.fin - p.arrive) + ", WT " + (p.fin - p.arrive - p.burst));
}
console.log("average TAT = " + tat / ps.length + ", average WT = " + wt / ps.length);

0-1 P1 | 1-3 P2 | 3-5 P3 | 5-7 P5 | 7-9 P2 | 9-10 P3 | 10-15 P1 | 15-18 P4
P1 queue 2: finish 15, TAT 15, WT 9
P2 queue 1: finish 9, TAT 8, WT 4
P3 queue 1: finish 10, TAT 8, WT 5
P4 queue 2: finish 18, TAT 15, WT 12
P5 queue 0: finish 7, TAT 2, WT 0
average TAT = 9.6, average WT = 6

৩ · Multilevel feedback queue — ইতিহাস আর পাঁচটি প্যারামিটার

MLFQ-তে প্রসেস স্তর বদলায়, তাই একে বর্ণনা করতে পাঠ্যবইয়ে সাধারণত পাঁচটি প্যারামিটার বলা হয়। পরীক্ষায় “MLFQ define করুন” প্রশ্নে এই তালিকাটিই উত্তরের কাঠামো:

সংজ্ঞাটি তাই এক বাক্যে বলা যায়: MLFQ হলো কয়েকটি priority-স্তরের queue, যেখানে প্রসেসের সাম্প্রতিক CPU-ব্যবহার দেখে তার স্তর বদলানো হয়, আর সবসময় সবচেয়ে উঁচু অ-খালি স্তরের প্রসেস চলে। এই পাঁচটি প্যারামিটার বদলে প্রায় যেকোনো scheduler-এর মতো আচরণ পাওয়া যায় — একটিমাত্র স্তর আর বড় quantum দিলে সেটি FCFS, একটিমাত্র স্তর আর ছোট quantum দিলে Round Robin. এই নমনীয়তাই MLFQ-এর শক্তি, আবার tuning-এর মাথাব্যথাও (অংশ ৮)।

৪ · পাঠ্যবইয়ের ৩-স্তরের উদাহরণ — q = ৮, q = ১৬, FCFS

বিশ্ববিদ্যালয় আর চাকরির পরীক্ষায় সবচেয়ে বেশি আসা MLFQ-এর রূপটি এই:

অর্থাৎ যে কাজের burst ৮ ms বা কম, সে সবচেয়ে বেশি অগ্রাধিকার পায় আর দ্রুত শেষ হয়। ৮ থেকে ২৪ ms-এর কাজ Q1 থেকে বাকি সময় পায়। এর চেয়ে লম্বা কাজ Q2-তে নেমে যায়, আর ওপরের দুই queue খালি থাকলে তবেই চলে। এবার একটি পূর্ণ উদাহরণ।

প্রশ্ন: চারটি প্রসেস — P1 (arrival ০, burst ৪০), P2 (২, ৬), P3 (৪, ১০), P4 (৪৪, ৫). প্রতিটির completion, turnaround time (TAT) আর waiting time (WT) বের করুন। নিয়ম: preempt হওয়া প্রসেস নিজের স্তরেই থাকে আর সেই queue-এর সামনে থেকে আবার চলে।

1 0- 8  P1@Q0 (uses all 8)2 8-14  P2@Q0 (done in 6)314-22  P3@Q0 (uses all 8)422-38  P1@Q1 (uses all 16)538-40  P3@Q1 (done)640-44  P1@Q2 (FCFS)744-49  P4@Q0 preempts P1849-61  P1@Q2 (done)

একই প্রশ্ন simulator দিয়ে মিলিয়ে নিন। প্রসেসের তালিকা বদলে নিজের বইয়ের অনুশীলনীও যাচাই করতে পারবেন — কিন্তু আগে হাতে করুন, তারপর মেলান।

// Textbook MLFQ: Q0 = RR q 8, Q1 = RR q 16, Q2 = FCFS. Every new process enters Q0.
// Uses the full quantum -> moves one level down. A higher queue preempts a lower one;
// the preempted process stays at the head of its own queue.
const quantum = [8, 16, Infinity];
const procs = [
  { name: "P1", arrive: 0, burst: 40 },
  { name: "P2", arrive: 2, burst: 6 },
  { name: "P3", arrive: 4, burst: 10 },
  { name: "P4", arrive: 44, burst: 5 },
];
const Q = [[], [], []], ps = procs.map(p => ({ ...p, left: p.burst, used: 0 }));
let t = 0, gantt = [];
while (ps.some(p => p.left > 0)) {
  ps.forEach(p => { if (p.arrive === t) Q[0].push(p); });
  const lv = Q.findIndex(q => q.length);
  const p = lv < 0 ? null : Q[lv][0];
  const name = p ? p.name + "@Q" + lv : "idle", last = gantt[gantt.length - 1];
  if (last && last.name === name) last.end = t + 1; else gantt.push({ name, start: t, end: t + 1 });
  t++;
  if (!p) continue;
  p.left--; p.used++;
  if (p.left === 0) { p.fin = t; Q[lv].shift(); }
  else if (p.used === quantum[lv]) { p.used = 0; Q[lv].shift(); Q[lv + 1].push(p); } // demote
}
gantt.forEach(g => console.log(String(g.start).padStart(2) + "-" + String(g.end).padEnd(3) + g.name));
let tat = 0, wt = 0;
for (const p of ps) {
  tat += p.fin - p.arrive; wt += p.fin - p.arrive - p.burst;
  console.log(p.name + ": finish " + p.fin + ", TAT " + (p.fin - p.arrive) + ", WT " + (p.fin - p.arrive - p.burst));
}
console.log("average TAT = " + tat / ps.length + ", average WT = " + wt / ps.length);

 0-8  P1@Q0
 8-14 P2@Q0
14-22 P3@Q0
22-38 P1@Q1
38-40 P3@Q1
40-44 P1@Q2
44-49 P4@Q0
49-61 P1@Q2
P1: finish 61, TAT 61, WT 21
P2: finish 14, TAT 12, WT 6
P3: finish 40, TAT 36, WT 26
P4: finish 49, TAT 5, WT 0
average TAT = 28.5, average WT = 13.25

অন্য নীতির সাথে তুলনা

একই চারটি প্রসেস FCFS আর SRTF-এ (পর্ব ১৭) হাতে হিসাব করলে:

SRTF সবচেয়ে ভালো, কারণ সে প্রতিটি burst আগে থেকে “জানে”। FCFS সবচেয়ে খারাপ, কারণ ৪০ ms-এর P1 সামনে থাকায় সবাই আটকে থাকে। MLFQ কিছুই না জেনে মাঝামাঝি — FCFS-এর চেয়ে গড় অপেক্ষা প্রায় অর্ধেক। ছোট P2 আর P4 MLFQ-তে প্রায় SRTF-এর মতোই দ্রুত সাড়া পেয়েছে (P2-এর প্রথম সাড়া t = ৮-এ, P4-এর সঙ্গে সঙ্গে)। এই “না জেনেও কাছাকাছি” কেন হয়, তা অংশ ৭-এ দেখব।

৫ · নিয়মগুলো এক এক করে — Rule 1 থেকে Rule 4

পাঠ্যবইয়ের উদাহরণে I/O ছিল না — সব প্রসেস টানা CPU চেয়েছে। বাস্তবে interactive প্রসেস একটু চলে, তারপর I/O-র জন্য ঘুমায়। এই অবস্থায় MLFQ কীভাবে আচরণ করবে, তা পরিষ্কার নিয়মে লিখেছেন Remzi ও Andrea Arpaci-Dusseau তাঁদের বিনামূল্যের বই Operating Systems: Three Easy Pieces (OSTEP)-এ। নিয়মগুলো ধাপে ধাপে গড়ে উঠেছে — প্রতিটি নতুন নিয়ম আগেরটির একটি সমস্যা সারায়।

Rule 3 আর পুরোনো Rule 4-এর জুটি দেখতে কেমন? ধরুন quantum Q0 = ৪, Q1 = ৮, Q2 = ১৬ ms. A একটি দীর্ঘ CPU-bound কাজ (৪০ ms), t = ০-তে আসে। B একটি interactive কাজ — t = ১২-তে আসে, প্রতিবার ১ ms চলে, তারপর ৩ ms I/O-তে ঘুমায়; মোট ৬ বার। নিচে দেখুন B কীভাবে ওপরে থেকে যায়।

1 0-12  A sinks: Q0 (4) -> Q1 (8) -> Q2212-13  B@Q0 runs 1, starts I/O313-16  A@Q2 runs while B waits for I/O416-17  B back: preempts A, runs 1517-46  same rhythm; B done 33, A done 46

নিয়মের ফাঁক — quantum শেষের ঠিক আগে CPU ছেড়ে দেওয়া

পুরোনো Rule ৪খ একটি ন্যায্যতার ফাঁক রেখে দেয়, যাকে OSTEP বলে “gaming the scheduler”. একটি প্রোগ্রাম যদি প্রতিবার quantum-এর ৯৯% ব্যবহার করে তারপর একটি তুচ্ছ I/O (যেমন একটি ছোট ফাইল-লেখা) করে, তাহলে নিয়ম অনুযায়ী সে কখনোই “পুরো slice” খায়নি — তাই চিরকাল সবার ওপরের স্তরে থাকে, আর বাকি সবার চেয়ে অনেক বেশি CPU পায়। এটি কোনো ভাঙন নয়, নিয়মটিরই দুর্বলতা; একটি প্রোগ্রাম ইচ্ছা করে না করেও (যেমন অনেক ছোট লেখা করে এমন সার্ভার) এই আচরণে পড়তে পারে। আর shared সার্ভারে এক ব্যবহারকারীর এমন প্রোগ্রাম অন্যদের ধীর করে দেয়। তাই scheduler-এর নকশাকারীরা প্রশ্নটিকে হিসাব রাখার (accounting) সমস্যা হিসেবে দেখেন: একটি স্তরে প্রসেস মোট কত CPU পেল, সেটিই গুনতে হবে।

নতুন Rule 4 ঠিক তাই করে — প্রতিটি স্তরে একটি time allotment থাকে, আর CPU ছেড়ে দিলেও ব্যবহৃত সময় মুছে যায় না। নিচের ছোট পরীক্ষায় A একটি সাধারণ CPU-bound কাজ, আর G প্রতিবার ৯ ms চলে ১ ms-এর I/O করে (quantum ১০)। দুই ধরনের হিসাবে ৫০০ ms-এ কে কত CPU পেল:

// Fairness check: job G gives up the CPU just before its slice ends (runs 9 ms, 1 ms I/O).
// Compare per-slice accounting (old rule) with allotment accounting (new Rule 4).
function share(keepUsage, horizon) {
  const quanta = [10, 20, 40], Q = [[], [], []];
  const js = [{ name: "A", run: 0 }, { name: "G", run: 9, io: 1 }]
    .map(j => ({ ...j, lvl: 0, used: 0, burst: 0, readyAt: 0, got: 0 }));
  for (let t = 0; t < horizon; t++) {
    js.forEach(j => { if (j.readyAt === t) Q[j.lvl].push(j); });
    const lv = Q.findIndex(q => q.length);
    if (lv < 0) continue;
    const j = Q[lv][0];
    j.got++; j.used++; j.burst++;
    const io = j.run && j.burst === j.run;
    if (io) { Q[lv].shift(); j.readyAt = t + 1 + j.io; j.burst = 0; if (!keepUsage) j.used = 0; }
    if (j.used >= quanta[lv]) {
      if (!io) Q[lv].shift();
      j.used = 0; j.lvl = Math.min(lv + 1, 2);
      if (!io) Q[j.lvl].push(j);
    }
  }
  return js.map(j => j.name + " got " + j.got + " ms (" + (100 * j.got / horizon).toFixed(0) + "%), now at Q" + j.lvl).join(", ");
}
console.log("per-slice accounting:  " + share(false, 500));
console.log("allotment accounting:  " + share(true, 500));

per-slice accounting:  A got 59 ms (12%), now at Q2, G got 441 ms (88%), now at Q0
allotment accounting:  A got 401 ms (80%), now at Q2, G got 99 ms (20%), now at Q2

৬ · Rule 5 — priority boost, starvation-এর ওষুধ

Rule 1–4 মিলে আরেকটি সমস্যা থেকে যায়। ধরুন সিস্টেমে কয়েকটি interactive কাজ আছে, যারা পালা করে CPU চায় — একজন ঘুমালে আরেকজন জাগে। ওপরের স্তর কখনো খালি হয় না, তাই নিচের স্তরের দীর্ঘ কাজ একটুও CPU পায় না: starvation. আরেকটি সমস্যা হলো আচরণ-বদল: একটি প্রোগ্রাম শুরুতে টানা হিসাব করে নিচে নেমে গেল, পরে সে interactive হয়ে উঠল (যেমন একটি ছবি-সম্পাদক ফাইল খোলা শেষে ব্যবহারকারীর ক্লিকের অপেক্ষায়)। Rule 1–4-এ সে আর কখনো ওপরে উঠতে পারে না।

OSTEP-এর সমাধান সরল: Rule 5 — প্রতি S সময় পরপর সব কাজকে সবার ওপরের স্তরে তোলা। এতে দুটি সমস্যাই মেটে: নিচের কাজ অন্তত প্রতি S সময়ে একবার ওপরে উঠে CPU পায়, আর আচরণ বদলানো কাজ নতুন করে নিজের জায়গা খুঁজে নেয়। পাঠ্যবইয়ে একই চিন্তাকে বলা হয় aging — যে যত বেশি অপেক্ষা করেছে, তার অগ্রাধিকার তত বাড়ানো (পর্ব ১৮)।

নিচের simulator তিনটি স্তর (quantum ২, ৪, ৮ ms) নিয়ে চলে। A একটি দীর্ঘ CPU-bound কাজ (২০ ms), t = ০-তে আসে। B আর C দুটি interactive কাজ, t = ৬-এ আসে; প্রত্যেকে ১ ms চলে, ১ ms I/O করে, মোট ২০ ms CPU চায়। যেহেতু তারা পালা করে চলে, Q0 কখনো খালি হয় না। একবার boost ছাড়া, একবার প্রতি ১০ ms-এ boost দিয়ে চালানো হলো। আউটপুটে প্রতিটি লাইন একটি স্তর; অক্ষর মানে সেই ms-এ সেই স্তরে কে চলেছে, আর longest wait মানে প্রস্তুত থেকেও টানা কত ms CPU পায়নি।

// MLFQ simulator, 1 tick = 1 ms. quanta[i] = time slice (and allotment) of level i.
// keepUsage = false: usage resets when a job gives up the CPU (old per-slice rule).
function mlfq(jobs, quanta, S, keepUsage) {
  const Q = quanta.map(() => []), rows = quanta.map(() => "");
  const js = jobs.map(j => ({ ...j, left: j.cpu, lvl: 0, used: 0, burst: 0,
                              readyAt: j.arrive, fin: 0, gap: 0, maxGap: 0 }));
  for (let t = 0; js.some(j => !j.fin); t++) {
    if (S && t && t % S === 0) {                         // Rule 5: priority boost
      Q[0] = [].concat(...Q); for (let i = 1; i < Q.length; i++) Q[i] = [];
      js.forEach(j => { j.lvl = 0; j.used = 0; });
    }
    js.forEach(j => { if (!j.fin && j.readyAt === t) Q[j.lvl].push(j); });
    const lv = Q.findIndex(q => q.length), j = lv < 0 ? null : Q[lv][0];
    rows.forEach((r, i) => rows[i] += (i === lv ? j.name : "."));
    js.forEach(o => { if (o !== j && !o.fin && o.readyAt <= t) o.maxGap = Math.max(o.maxGap, ++o.gap); });
    if (!j) continue;
    j.gap = 0; j.left--; j.used++; j.burst++;
    if (!j.left) { j.fin = t + 1; Q[lv].shift(); continue; }
    const io = j.run && j.burst === j.run;               // job releases the CPU for I/O
    if (io) { Q[lv].shift(); j.readyAt = t + 1 + j.io; j.burst = 0; if (!keepUsage) j.used = 0; }
    if (j.used >= quanta[lv]) {                          // Rule 4: demote one level
      if (!io) Q[lv].shift();
      j.used = 0; j.lvl = Math.min(lv + 1, quanta.length - 1);
      if (!io) Q[j.lvl].push(j);
    }
  }
  for (let c = 0; c < rows[0].length; c += 30)
    rows.forEach((r, i) => console.log("Q" + i + " t=" + String(c).padStart(2) + " " + r.slice(c, c + 30)));
  js.forEach(j => console.log(j.name + ": finish " + j.fin + ", turnaround " + (j.fin - j.arrive) + ", longest wait " + j.maxGap));
}
const jobs = [{ name: "A", arrive: 0, cpu: 20 },                 // long, CPU-bound
              { name: "B", arrive: 6, cpu: 20, run: 1, io: 1 },  // interactive
              { name: "C", arrive: 6, cpu: 20, run: 1, io: 1 }]; // interactive
console.log("--- no boost");          mlfq(jobs, [2, 4, 8], 0, false);
console.log("--- boost every 10 ms"); mlfq(jobs, [2, 4, 8], 10, false);

--- no boost
Q0 t= 0 AA....BCBCBCBCBCBCBCBCBCBCBCBC
Q1 t= 0 ..AAAA........................
Q2 t= 0 ..............................
Q0 t=30 BCBCBCBCBCBCBCBC..............
Q1 t=30 ..............................
Q2 t=30 ................AAAAAAAAAAAAAA
A: finish 60, turnaround 60, longest wait 40
B: finish 45, turnaround 39, longest wait 0
C: finish 46, turnaround 40, longest wait 1
--- boost every 10 ms
Q0 t= 0 AA....BCBCAABCBCBCBCAABCBCBCBC
Q1 t= 0 ..AAAA........................
Q2 t= 0 ..............................
Q0 t=30 AABCBCBCBCAABCBCBCBCAABCBC....
Q1 t=30 ..........................AAAA
Q2 t=30 ..............................
A: finish 60, turnaround 60, longest wait 8
B: finish 55, turnaround 49, longest wait 2
C: finish 56, turnaround 50, longest wait 2

1 0- 6  A alone: Q0 (2) -> Q1 (4) -> Q22 6-10  B, C alternate at Q0; A starves310-12  BOOST: all to Q0; A runs 2412-20  A back at Q1, waits 8520-52  boost at 20, 30, 40, 50652-60  B, C finish; A finishes

৭ · না জেনেও SJF-এর কাছাকাছি — MLFQ কেন কাজ করে

পর্ব ১৭-এ দেখেছেন, সব কাজ একসাথে এলে SJF গড় waiting time-কে সর্বনিম্ন রাখে, আর preemptive রূপ SRTF-ও তার অনুরূপ। সমস্যা হলো burst জানা লাগে। পাঠ্যবইয়ের সমাধান ছিল আগের burst-গুলোর exponential average দিয়ে অনুমান। MLFQ আরেকটি চতুর পথ নেয়: অনুমান না করে, পর্যবেক্ষণ করে।

• শুরুতে সবাইকে ছোট ধরা: নতুন কাজ ওপরে ঢোকে (Rule 3), তাই কাজটি সত্যিই ছোট হলে সে প্রায় SJF-এর মতোই দ্রুত শেষ হয় — উদাহরণের P2 আর P4 যেমন।
• যত চলে, তত নামে: কেউ q₀ খেয়ে ফেললে আমরা জানি তার burst অন্তত q₀. q₀ + q₁ খেলে জানি অন্তত তত। অর্থাৎ স্তরটিই হলো “এ পর্যন্ত কত CPU পেয়েছে”-এর মোটা দাগের মাপ, আর ওপরের স্তর মানে কম পেয়েছে।
• সবচেয়ে কম পাওয়াকে আগে চালানো: তাই MLFQ মোটামুটি এই নিয়মে চলে — “যে এ পর্যন্ত সবচেয়ে কম CPU পেয়েছে, সে আগে।” এই নীতির নাম least attained service (LAS) বা foreground-background scheduling; MLFQ এর ধাপে-ধাপে (quantum-এর মাপে) রূপ।

কখন এটি SJF-এর মতো ভালো হয়? একটি যুক্তি দেখুন। ধরুন সব কাজ t = ০-তে এল, I/O নেই। MLFQ-তে ওপরের স্তরের সবাই একবার করে q₀ পর্যন্ত চলে। যে কাজের burst ≤ q₀, সে প্রথম চক্রেই শেষ — কোনো দীর্ঘ কাজ q₀-এর বেশি পাওয়ার আগেই। অর্থাৎ প্রতিটি ছোট কাজ প্রতিটি বড় কাজের আগে শেষ হয়, ঠিক SJF-এর মতো; পার্থক্য শুধু এটুকু যে বড় কাজগুলোও প্রথম চক্রে q₀ করে পায়, যা ছোটদের অপেক্ষা সামান্য বাড়ায়। স্তর যত বেশি আর quantum-এর ধাপ যত সূক্ষ্ম, ক্রম তত SJF-এর কাছাকাছি। উল্টো দিকে, burst যদি কাছাকাছি হয় (যেমন সবার ১০ ms), MLFQ সবাইকে টুকরো টুকরো করে Round Robin-এর মতো আচরণ করে — তখন FCFS-ই বরং ভালো।

বাস্তবে এটি কেন ভালো কাজ করে, তার একটি পর্যবেক্ষণভিত্তিক কারণ আছে: অনেক সিস্টেমে কাজের দৈর্ঘ্যের বণ্টন “ভারী লেজওয়ালা” — বেশিরভাগ কাজ খুব ছোট, অল্প কয়েকটি বিশাল। এমন বণ্টনে “যে অনেকক্ষণ চলেছে, সে সম্ভবত আরও অনেকক্ষণ চলবে” — তাই যে কম পেয়েছে তাকে আগে চালানো প্রায়ই সঠিক বাজি। অবশ্য সব workload-এ এটি খাটে না।

৮ · Tuning-এর মাথাব্যথা আর বাস্তব OS

MLFQ-এর প্রশ্নগুলোর কোনো একক সঠিক উত্তর নেই: কয়টি স্তর? প্রতিটির quantum কত? Allotment কত? S কত ঘন ঘন? অনুশীলনীতে দেখবেন, S = ৫ করলে দীর্ঘ কাজ খুব ভালো পায়, কিন্তু interactive কাজ অনেক পিছিয়ে যায়; S = ১০০ হলে উল্টো। OSTEP জানায়, বিখ্যাত systems গবেষক John Ousterhout এমন মানগুলোকে বলতেন “voo-doo constants” — যেন ঠিক করতে কালো জাদু লাগে। OSTEP সেখান থেকে একটি পরামর্শও দেয়, যাকে বইটি “Ousterhout's Law” বলে: সম্ভব হলে এমন জাদুর সংখ্যা এড়িয়ে চলুন।

এবার দেখা যাক বাস্তব OS এই ধারণা কোথায় কীভাবে ব্যবহার করেছে। মনে রাখবেন, প্রতিটি সিস্টেমের খুঁটিনাটি সংস্করণভেদে বদলেছে; নিচে মূল চিন্তাটুকু দেওয়া হলো।

Linux? Linux 2.6-এর প্রথম দিকের “O(1)” scheduler-এ ১৪০টি priority স্তর আর ঘুমের ইতিহাস থেকে interactivity-র অনুমান ছিল — MLFQ-এর ঘনিষ্ঠ আত্মীয়। কিন্তু সেই অনুমানের নিয়মগুলো জটিল আর কখনো কখনো ভুল হতো; ২০০৭ সালে Linux 2.6.23-এ CFS এসে স্তরের বদলে “কে কত কম CPU পেয়েছে” সরাসরি মাপা শুরু করে, আর Linux 6.6 (২০২৩) থেকে EEVDF. সেই গল্প পর্ব ২১-এ। Linux-এ আজও “শ্রেণি” আছে — real-time (SCHED_FIFO, SCHED_RR) শ্রেণি সবসময় সাধারণ শ্রেণির ওপরে — যা আসলে একটি multilevel queue. মজার ব্যাপার, ডিফল্ট সেটিংয়ে real-time শ্রেণি প্রতি সেকেন্ডে CPU-র সর্বোচ্চ প্রায় ৯৫% পায় (sched_rt_runtime_us সীমা), যাতে একটি ভুল real-time লুপ পুরো সিস্টেম জমিয়ে না দেয় — অর্থাৎ fixed priority-র সাথে এক টুকরো time slicing.

$ ps -eo pid,cls,rtprio,ni,comm | head -5
    PID CLS RTPRIO  NI COMMAND
      1  TS      -   0 systemd
      2  TS      -   0 kthreadd
     19  FF     99   - migration/0
    812  TS      -   0 sshd

এখানে TS মানে সাধারণ time-sharing শ্রেণি, FF মানে SCHED_FIFO real-time শ্রেণি, যা সবসময় TS-এর আগে চলে — একটি দুই-স্তরের multilevel queue চোখের সামনে। আপনার মেশিনে PID আর নাম আলাদা হবে।

৯ · AI-এর যুগে MLFQ

MLFQ-এর অঙ্ক বা ধারণা নিয়ে AI-কে জিজ্ঞেস করলে উত্তর সাধারণত আত্মবিশ্বাসী শোনায়, কিন্তু এই বিষয়ে কয়েকটি নির্দিষ্ট ভুল বারবার দেখা যায়:

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

• প্রশ্নের নিয়ম (preempted প্রসেস কোথায় যায়, বাকি quantum না নতুন quantum) AI-এর উত্তরে মানা হয়েছে কি না দেখেছি
• প্রতিটি arrival-এর মুহূর্তে preemption হওয়ার কথা কি না হাতে মিলিয়েছি
• সব প্রসেসের burst-এর যোগফল আর idle সময় মিলিয়ে শেষ সময়টি ঠিক কি না যাচাই করেছি (এখানে ৪০ + ৬ + ১০ + ৫ = ৬১)
• WT = TAT − burst সূত্রে প্রতিটি সংখ্যা আবার হিসাব করেছি, আর উপরের simulator-এ চালিয়ে মিলিয়েছি
• বাস্তব OS-এর তথ্য (Linux, Windows, macOS) কোন সংস্করণের, তা জেনেছি, আর kernel ডকুমেন্টেশন বা man page (man sched) দেখেছি
• sudo দিয়ে real-time priority বা negative nice দেওয়ার পরামর্শ মানার আগে লোড দিয়ে পরীক্ষা করেছি