Priority scheduling আর Round Robin

১ · অগ্রাধিকার কেন — হাসপাতালের জরুরি বিভাগ

পর্ব ১৭-তে দেখেছেন FCFS, SJF, SRTF আর HRRN — সেখানে বাছাইয়ের ভিত্তি ছিল আসার সময় বা burst-এর দৈর্ঘ্য। কিন্তু বাস্তবে সব কাজ সমান জরুরি নয়। একটি সরকারি হাসপাতালের জরুরি বিভাগের কথা ভাবুন। সারিতে আগে এসেছেন জ্বরের এক রোগী, পরে এলেন সড়ক দুর্ঘটনায় আহত একজন। ডাক্তার আগে কাকে দেখবেন? আহতকে — কারণ তাঁর অগ্রাধিকার বেশি। এই বাছাইয়ের নাম triage. CPU-র ক্ষেত্রেও একই চিন্তা: মাউসের নড়াচড়ায় সাড়া দেওয়া, অডিও বাজানো বা নেটওয়ার্ক প্যাকেট সামলানো এমন কাজ, যা দেরি হলে ব্যবহারকারী সঙ্গে সঙ্গে টের পান; অথচ রাতের ব্যাকআপ কয়েক সেকেন্ড পিছিয়ে গেলে কারও ক্ষতি নেই।

Priority scheduling-এ প্রতিটি প্রসেসের সাথে একটি অগ্রাধিকার-সংখ্যা (priority) যুক্ত থাকে। Scheduler ready queue-এর প্রসেসদের মধ্যে যার অগ্রাধিকার সবচেয়ে বেশি, তাকে CPU দেয়। দুজনের অগ্রাধিকার সমান হলে এই পর্বে নিয়ম: যে আগে এসেছে, সে আগে (অর্থাৎ সমান স্তরে FCFS).

খেয়াল করুন, একই Linux-এর ভেতরেই দুই দিক আছে: user-কে দেখানো real-time priority-তে ৯৯ সবচেয়ে জরুরি, আর kernel-এর ভেতরের হিসাবে ০ সবচেয়ে জরুরি। তাই AI বা কোনো ব্লগ “priority বেশি” বললে আগে জিজ্ঞেস করুন — কোন সংখ্যার কথা হচ্ছে?

Static আর dynamic priority

অগ্রাধিকার আসে কোথা থেকে? ভেতরের (internal) মাপ থেকে — মেমরির চাহিদা, খোলা ফাইলের সংখ্যা, গড় CPU burst আর I/O burst-এর অনুপাত; অথবা বাইরের (external) সিদ্ধান্ত থেকে — কাজটি কতটা গুরুত্বপূর্ণ, কে টাকা দিচ্ছে, কোন বিভাগের কাজ। একটি সুন্দর সংযোগও আছে: SJF আসলে priority scheduling-এরই একটি বিশেষ রূপ, যেখানে priority = পরের CPU burst-এর অনুমিত দৈর্ঘ্য (ছোট burst = বেশি অগ্রাধিকার)। তাই SJF-এর starvation-সমস্যাও priority-র starvation-সমস্যার মতোই।

২ · Non-preemptive আর preemptive priority — পূর্ণ হিসাব

Priority scheduling দুইভাবে চলতে পারে। Non-preemptive হলে একবার CPU পাওয়া প্রসেস তার পুরো CPU burst শেষ (বা block) না হওয়া পর্যন্ত চলে; নতুন কেউ এলে সে সারিতে অপেক্ষা করে। Preemptive হলে নতুন আসা প্রসেসের অগ্রাধিকার চলতি প্রসেসের চেয়ে বেশি হওয়া মাত্র preemption হয় — চলতিটিকে থামিয়ে নতুনটিকে CPU দেওয়া হয়। মাপকাঠিগুলো পর্ব ১৬-এর: TAT = CT − AT, WT = TAT − BT, আর RT (response time) = প্রথমবার CPU পাওয়ার সময় − AT.

উদাহরণ ১: চারটি প্রসেস। ছোট সংখ্যা = বেশি অগ্রাধিকার।

Non-preemptive: t = 0-তে শুধু P1 আছে, সে চলে ০–৪, মাঝে P2, P3, P4 এলেও থামে না। t = ৪-এ ready: P2 (১), P3 (৪), P4 (২) → P2 চলে ৪–৭; তারপর P4 ৭–৯; শেষে P3 ৯–১৪.

│ P1 0-4 │ P2 4-7 │ P4 7-9 │ P3 9-14 │

Preemptive: এখানে প্রতিটি আগমন একটি সিদ্ধান্তের মুহূর্ত। নিচের stepper-এ ধাপে ধাপে দেখুন — বিশেষ করে t = ১-এ কী ঘটে।

1t=0  P1 arrives (pr 3), runs2t=1  P2 arrives (pr 1) -> preempts P13t=2  P3 arrives (pr 4), waits4t=3  P4 arrives (pr 2), waits5t=4  P2 done -> best is P4 (pr 2)6t=6  P4 done -> P1 (pr 3)7t=9  P1 done -> P3 (pr 4)8t=14 P3 done

৩ · Starvation আর aging

ব্যাংকের একটি কাউন্টারে নিয়ম: প্রবীণ নাগরিক আর প্রতিবন্ধী গ্রাহকেরা আগে সেবা পাবেন। ভালো নিয়ম। কিন্তু ধরুন সেদিন সকাল থেকে বিকেল পর্যন্ত একের পর এক প্রবীণ গ্রাহক আসতেই থাকলেন। সাধারণ টোকেন হাতে বসে থাকা ছাত্রটি সারা দিনেও ডাক পেলেন না। এটাই starvation (অনির্দিষ্ট অপেক্ষা) — প্রসেস প্রস্তুত, কিন্তু তার চেয়ে বেশি অগ্রাধিকারের কেউ না কেউ সবসময় থাকায় সে কখনো CPU পায় না। একটি বহুল-প্রচলিত গল্প আছে: ১৯৭৩ সালে MIT-র IBM 7094 কম্পিউটার বন্ধ করার সময় নাকি ১৯৬৭ সালে জমা দেওয়া একটি কম-অগ্রাধিকারের job পাওয়া গিয়েছিল, যা তখনো চলেনি। গল্পটির বিস্তারিত যাচাই করা কঠিন, কিন্তু শিক্ষাটি পরিষ্কার।

সমাধান aging: যে প্রসেস যত বেশি সময় ready queue-তে অপেক্ষা করে, তার অগ্রাধিকার ধীরে ধীরে তত বাড়ানো হয়। ব্যাংকের উদাহরণে — “যিনি এক ঘণ্টা বসে আছেন, তিনি প্রবীণদের সমান গণ্য হবেন।”

উদাহরণ ২ (aging): L প্রসেস আসে t = ০-তে, BT = ২, priority ৪. সাথে উঁচু অগ্রাধিকারের (priority ১) পাঁচটি H প্রসেস, প্রতিটির BT = ৩, আসে t = ০, ২, ৫, ৮, ১১-তে। Scheduling non-preemptive. Aging-এর নিয়ম: ready queue-তে প্রতি ৩ একক অপেক্ষার পর priority-সংখ্যা ১ কমে (সর্বনিম্ন ০)। সিদ্ধান্তের মুহূর্তে aging আগে হিসাব হয়, তারপর বাছাই; সমান হলে আগে আসা আগে।

Aging ছাড়া উত্তর সহজ: H1 ০–৩, H2 ৩–৬, H3 ৬–৯, H4 ৯–১২, H5 ১২–১৫, তারপর L ১৫–১৭. L-এর WT = ১৫. আর H আসা যদি থামতই না, L কখনো চলত না। এবার aging-সহ:

1t=0   L(4) vs H1(1)  -> H12t=3   L waited 3 -> pr 3; -> H23t=6   L waited 6 -> pr 2; -> H34t=9   L waited 9 -> pr 1 = H4(1); L came first -> L5t=11  L done; H4 waited 3 -> pr 0; -> H46t=14  H5 waited 3 -> pr 0; -> H57t=17  all done

প্রমাণ — aging কেন starvation দূর করে

দাবি: প্রতি k একক অপেক্ষায় priority-সংখ্যা ১ কমলে, সর্বনিম্ন সংখ্যা ০ হলে, আর সমান priority-তে আগে আসা প্রসেস আগে চললে, কোনো প্রসেস অনির্দিষ্টকাল অপেক্ষা করে না।

1. প্রসেস X t₀ সময়ে আসে, priority p₀. অপেক্ষায় থাকলে বড়জোর k·p₀ একক পরে তার priority ০, যা সর্বোচ্চ অগ্রাধিকার।
2. এরপর X-এর আগে চলতে পারে শুধু সেই প্রসেস, যার priority-ও ০ এবং যে X-এর আগে এসেছে। X-এর পরে আসা কেউ সমান priority-তে X-কে টপকাতে পারে না।
3. X-এর আগে আসা প্রসেস সসীম-সংখ্যক, আর প্রত্যেকের বাকি burst সসীম। (Non-preemptive হলে তখন চলতি প্রসেসের বাকি burst-ও যোগ হবে।)
4. তাই X-এর মোট অপেক্ষা ≤ k·p₀ + (আগে আসা সবার বাকি burst-এর যোগফল) — একটি সসীম সংখ্যা। অর্থাৎ starvation নেই। ∎

খেয়াল করুন, প্রমাণে tie-নিয়মটি জরুরি। সমান priority-তে যদি এলোমেলোভাবে বাছা হতো, তাহলে priority ০-তে নতুন আসা প্রসেসেরা X-কে অনির্দিষ্টকাল টপকে যেতে পারত।

নিচের simulator উদাহরণ ১ আর ২ দুটোই চালায়। preemptive আর AGE বদলে দেখুন — যেমন উদাহরণ ১-এ preemptive-এর সাথে aging দিলে কী হয়।

// Priority scheduling. SMALLER number = HIGHER priority. Tie: earlier arrival.
// Aging: after every AGE time units spent waiting, priority number drops by 1 (min 0).
function run(title, procs, preemptive, AGE = Infinity) {
  const ps = procs.map(([id, at, bt, pr]) => ({ id, at, bt, pr, left: bt, w: 0, start: -1, ct: 0 }));
  let t = 0, cur = null; const seg = [];
  while (ps.some(p => p.left > 0)) {
    const ready = ps.filter(p => p.at <= t && p.left > 0);
    if (!ready.length) { t++; continue; }                     // CPU idle
    if (!cur || preemptive) {                                  // decision point
      const best = [...ready].sort((a, b) => a.pr - b.pr || a.at - b.at)[0];
      if (best !== cur) seg.push({ id: best.id, from: t, pr: best.pr });
      cur = best;
      if (cur.start < 0) cur.start = t;
    }
    cur.left--;                                                // run 1 time unit
    for (const p of ready) if (p !== cur && ++p.w % AGE === 0 && p.pr > 0) p.pr--;
    t++;
    if (cur.left === 0) { cur.ct = t; cur = null; }
  }
  seg.forEach((s, k) => (s.to = k + 1 < seg.length ? seg[k + 1].from : t));
  console.log(title + "\n  " + seg.map(s => s.id + " " + s.from + "-" + s.to + " (pr " + s.pr + ")").join(" │ "));
  let tat = 0, wt = 0;
  for (const p of ps) {
    tat += p.ct - p.at; wt += p.ct - p.at - p.bt;
    console.log("  " + p.id + ": CT=" + p.ct + " TAT=" + (p.ct - p.at) + " WT=" + (p.ct - p.at - p.bt) + " RT=" + (p.start - p.at));
  }
  console.log("  avg TAT=" + (tat / ps.length).toFixed(2) + " avg WT=" + (wt / ps.length).toFixed(2));
}
const A = [["P1", 0, 4, 3], ["P2", 1, 3, 1], ["P3", 2, 5, 4], ["P4", 3, 2, 2]];
run("Non-preemptive", A, false);
run("Preemptive", A, true);
const B = [["L", 0, 2, 4], ["H1", 0, 3, 1], ["H2", 2, 3, 1], ["H3", 5, 3, 1], ["H4", 8, 3, 1], ["H5", 11, 3, 1]];
run("No aging", B, false);
run("Aging every 3 units", B, false, 3);

Non-preemptive
  P1 0-4 (pr 3) │ P2 4-7 (pr 1) │ P4 7-9 (pr 2) │ P3 9-14 (pr 4)
  P1: CT=4 TAT=4 WT=0 RT=0
  P2: CT=7 TAT=6 WT=3 RT=3
  P3: CT=14 TAT=12 WT=7 RT=7
  P4: CT=9 TAT=6 WT=4 RT=4
  avg TAT=7.00 avg WT=3.50
Preemptive
  P1 0-1 (pr 3) │ P2 1-4 (pr 1) │ P4 4-6 (pr 2) │ P1 6-9 (pr 3) │ P3 9-14 (pr 4)
  P1: CT=9 TAT=9 WT=5 RT=0
  P2: CT=4 TAT=3 WT=0 RT=0
  P3: CT=14 TAT=12 WT=7 RT=7
  P4: CT=6 TAT=3 WT=1 RT=1
  avg TAT=6.75 avg WT=3.25
No aging
  H1 0-3 (pr 1) │ H2 3-6 (pr 1) │ H3 6-9 (pr 1) │ H4 9-12 (pr 1) │ H5 12-15 (pr 1) │ L 15-17 (pr 4)
  L: CT=17 TAT=17 WT=15 RT=15
  ...
  avg TAT=6.00 avg WT=3.17
Aging every 3 units
  H1 0-3 (pr 1) │ H2 3-6 (pr 1) │ H3 6-9 (pr 1) │ L 9-11 (pr 1) │ H4 11-14 (pr 0) │ H5 14-17 (pr 0)
  L: CT=11 TAT=11 WT=9 RT=9
  ...
  H4: CT=14 TAT=6 WT=3 RT=3
  H5: CT=17 TAT=6 WT=3 RT=3
  avg TAT=5.67 avg WT=2.83

৪ · Priority inversion — যখন কম জরুরি কাজ বেশি জরুরিকে আটকে দেয়

Priority-র আরেকটি বিপদ আসে যখন প্রসেসেরা কোনো সম্পদ ভাগ করে — যেমন একটি mutex দিয়ে সুরক্ষিত ডেটা (মডিউল ৪-এ বিস্তারিত)। তিনটি task ধরুন: H (উচ্চ), M (মাঝারি), L (নিম্ন)। L একটি lock R নিয়ে কাজ করছে। H-এর ওই R দরকার। তাহলে H-কে অপেক্ষা করতে হবে L-এর জন্য — এটুকু স্বাভাবিক, কারণ L শিগগিরই R ছেড়ে দেবে। সমস্যা শুরু হয় যখন M এসে পড়ে।

1L runs, lock(R) succeeds2H wakes, preempts L; lock(R) -> BLOCKED3M wakes, preempts L (M > L)4M runs on and on ... H still waiting5FIX: L inherits H's priority, unlocks, H runs

৫ · Round Robin — বৃত্তাকার সারি আর tie-নিয়ম

পাড়ার চায়ের দোকানে একজন দোকানি, আর পাঁচজন অতিথি। কেউ চাইছেন শুধু এক কাপ চা, কেউ চা-বিস্কুট-কলা আর পান। দোকানি যদি একজনের সব কাজ শেষ করে তবে পরের জনের কাছে যান (FCFS), তাহলে শুধু চা চাওয়া মানুষটি অনেকক্ষণ দাঁড়িয়ে থাকেন। বুদ্ধিমান দোকানি তাই পালা করে প্রত্যেকের এক-একটি জিনিস দেন — এক চক্রে সবাই কিছু না কিছু পান, আর কারও কাজ শেষ না হলে তিনি আবার সারির পেছনে যান। এটাই Round Robin (RR), time-sharing সিস্টেমের মূল নীতি।

উদাহরণ ৩: পাঁচটি প্রসেস, q = ২. এই ডেটা ইচ্ছে করে এমনভাবে বাছা, যাতে tie-নিয়ম দুবার কাজে লাগে (t = ২ আর t = ৪)।

1t=0   queue [P1]          run P1 0-22t=2   P3 new, then P1     run P2 2-43t=4   P5 new, then P2     run P3 4-5 (done)4t=5                       run P1 5-75t=7   P1 to tail          run P4 7-9 (done)6t=9                       run P5 9-117t=11  P5 to tail          run P2 11-12 (done)8t=12                      run P1 12-13 (done)9t=13                      run P5 13-14 (done)10t=14  all done

একই ডেটা, q = ৪

P1 চলে ০–৪ (বাকি ১)। এর মধ্যে P2, P3, P4 এসে গেছে; t = ৪-এ P5 আসে আর P1-এর quantum ফুরায় — আগে P5, পরে P1: সারি [P2 P3 P4 P5 P1]. এরপর P2 ৪–৭, P3 ৭–৮, P4 ৮–১০, P5 ১০–১৩, P1 ১৩–১৪ — কেউই আর quantum ফুরিয়ে ফেরে না, শুধু P1 শেষে।

│ P1 0-4 │ P2 4-7 │ P3 7-8 │ P4 8-10 │ P5 10-13 │ P1 13-14 │

উল্টো প্রথা ধরলে কী বদলায়?

কিছু বই ও শিক্ষক উল্টো নিয়ম মানেন: সময়-ফুরানো প্রসেস আগে সারিতে ফেরে, একই মুহূর্তে আসা নতুন প্রসেস তার পরে। তাহলে q = ২-এ t = ২-এর সারি হয় [P2 P1 P3], আর পুরো চার্ট বদলে যায়:

│ P1 0-2 │ P2 2-4 │ P1 4-6 │ P3 6-7 │ P4 7-9 │ P2 9-10 │ P5 10-12 │ P1 12-13 │ P5 13-14 │

এখানে CT = ১৩, ১০, ৭, ৯, ১৪; গড় TAT আর গড় WT কাকতালীয়ভাবে একই (৮.৬ আর ৫.৮) থাকলেও প্রতিটি প্রসেসের আলাদা উত্তর বদলেছে, আর গড় RT ২.৪ থেকে বেড়ে ৩.০. q = ৪-এ গড় TAT ৮.৪ থেকে কমে ৮.০ হয়। তাই “আমার উত্তর বইয়ের সাথে মিলছে না” — এমন হলে প্রথম সন্দেহ এই tie-নিয়ম। দুটোই যুক্তিসঙ্গত; দরকার শুধু স্পষ্টভাবে লিখে দেওয়া।

৬ · RR simulator, response time আর একটি গ্যারান্টি

হাতে Gantt chart আঁকা শিখেছেন; এবার একই কাজ কোডে। নিচের simulator উপরের নিয়ম হুবহু মানে — admit() আগে, তারপর preempted প্রসেস সারিতে। প্রতিটি quantum-সীমায় সারির অবস্থা ছাপে, আর q = ১, ২, ৪, ৮-এর জন্য প্রতিটি প্রসেসের CT, TAT, WT, RT দেখায়। শেষ লাইনটি পরের অংশের জন্য।

// Round Robin. Tie rule: at the same instant a NEW arrival is enqueued
// BEFORE the process whose quantum just expired. Input sorted by arrival.
const jobs = [["P1", 0, 5], ["P2", 1, 3], ["P3", 2, 1], ["P4", 3, 2], ["P5", 4, 3]];

function rr(list, q, show) {
  const ps = list.map(([id, at, bt]) => ({ id, at, bt, left: bt, start: -1, ct: 0 }));
  let t = 0, next = 0; const queue = [], gantt = [], qlog = [];
  const admit = () => { while (next < ps.length && ps[next].at <= t) queue.push(ps[next++]); };
  admit();
  while (queue.length || next < ps.length) {
    if (!queue.length) { t = ps[next].at; admit(); }       // CPU idle until next arrival
    const p = queue.shift();
    if (p.start < 0) p.start = t;
    const run = Math.min(q, p.left);
    gantt.push(p.id + " " + t + "-" + (t + run));
    t += run; p.left -= run;
    admit();                                              // 1) new arrivals first
    if (p.left > 0) queue.push(p); else p.ct = t;         // 2) then the preempted one
    qlog.push(t + ":[" + queue.map(x => x.id).join(" ") + "]");
  }
  let tat = 0, wt = 0, rt = 0;
  if (show) console.log("q = " + q + "\n Gantt: " + gantt.join(" │ ") + "\n queue: " + qlog.join(" "));
  for (const p of ps) {
    tat += p.ct - p.at; wt += p.ct - p.at - p.bt; rt += p.start - p.at;
    if (show) console.log("  " + p.id + " CT=" + p.ct + " TAT=" + (p.ct - p.at) +
      " WT=" + (p.ct - p.at - p.bt) + " RT=" + (p.start - p.at));
  }
  const n = ps.length;
  if (show) console.log("  avg TAT=" + tat / n + " WT=" + wt / n + " RT=" + rt / n);
  return tat / n;
}
for (const q of [1, 2, 4, 8]) rr(jobs, q, true);
const four = [["P1", 0, 6], ["P2", 0, 3], ["P3", 0, 1], ["P4", 0, 7]];
console.log("avg TAT for bursts 6,3,1,7: " +
  [1, 2, 3, 4, 5, 6, 7].map(q => "q" + q + "=" + rr(four, q, false)).join(" "));

q = 1
 Gantt: P1 0-1 │ P2 1-2 │ P1 2-3 │ P3 3-4 │ P2 4-5 │ P4 5-6 │ P1 6-7 │ P5 7-8 │ P2 8-9 │ P4 9-10 │ P1 10-11 │ P5 11-12 │ P1 12-13 │ P5 13-14
 queue: 1:[P2 P1] 2:[P1 P3 P2] 3:[P3 P2 P4 P1] 4:[P2 P4 P1 P5] ... 13:[P5] 14:[]
  ...
  avg TAT=8 WT=5.2 RT=1.2
q = 2
 Gantt: P1 0-2 │ P2 2-4 │ P3 4-5 │ P1 5-7 │ P4 7-9 │ P5 9-11 │ P2 11-12 │ P1 12-13 │ P5 13-14
 queue: 2:[P2 P3 P1] 4:[P3 P1 P4 P5 P2] 5:[P1 P4 P5 P2] 7:[P4 P5 P2 P1] 9:[P5 P2 P1] 11:[P2 P1 P5] 12:[P1 P5] 13:[P5] 14:[]
  P1 CT=13 TAT=13 WT=8 RT=0
  P2 CT=12 TAT=11 WT=8 RT=1
  P3 CT=5 TAT=3 WT=2 RT=2
  P4 CT=9 TAT=6 WT=4 RT=4
  P5 CT=14 TAT=10 WT=7 RT=5
  avg TAT=8.6 WT=5.8 RT=2.4
q = 4
 Gantt: P1 0-4 │ P2 4-7 │ P3 7-8 │ P4 8-10 │ P5 10-13 │ P1 13-14
 queue: 4:[P2 P3 P4 P5 P1] 7:[P3 P4 P5 P1] 8:[P4 P5 P1] 10:[P5 P1] 13:[P1] 14:[]
  ...
  avg TAT=8.4 WT=5.6 RT=3.8
q = 8
 Gantt: P1 0-5 │ P2 5-8 │ P3 8-9 │ P4 9-11 │ P5 11-14
 queue: 5:[P2 P3 P4 P5] 8:[P3 P4 P5] 9:[P4 P5] 11:[P5] 14:[]
  ...
  avg TAT=7.4 WT=4.6 RT=4.6
avg TAT for bursts 6,3,1,7: q1=11 q2=11.5 q3=10.75 q4=11.5 q5=12.25 q6=10.5 q7=10.5

RR-এর গ্যারান্টি — প্রমাণসহ

RR-এর আসল শক্তি গড় নয়, নিশ্চয়তা। দাবি: ready queue-তে মোট n টি প্রসেস থাকলে (context switch-এর খরচ বাদে) কোনো প্রসেস পরপর দুই পালার মাঝে (n − 1)·q-এর বেশি অপেক্ষা করে না।

যুক্তি: প্রসেস X যখন সারির পেছনে ঢোকে, তার সামনে আছে বড়জোর n − 1 টি প্রসেস। সারি FIFO, তাই পরে যারা আসবে তারা X-এর পেছনে বসবে — X-এর অবস্থান কেবল সামনে এগোয়। সামনের প্রত্যেকে একবারে সর্বোচ্চ q চলে (তার আগে শেষ বা block হলে আরও কম)। তাই X-এর অপেক্ষা ≤ (n − 1)·q. ∎ উদাহরণ: ৫টি প্রসেস, q = ২০ ms হলে কেউ ৮০ ms-এর বেশি সাড়াহীন থাকে না। Context switch-এর খরচ s যোগ করলে হিসাব ও CPU efficiency q/(q + s) পর্ব ৯-এর Context switch আর dispatcher-এ পূর্ণভাবে করা আছে — এখানে পুনরাবৃত্তি করছি না।

এজন্যই interactive সিস্টেমে RR জনপ্রিয়: টাইপ করা অক্ষরটি পর্দায় আসতে কতক্ষণ লাগবে, তার একটি ঊর্ধ্বসীমা জানা। Priority বা SJF-এ এমন সীমা নেই — বড় কাজ বা কম অগ্রাধিকারের কাজ যেকোনো দৈর্ঘ্যে পিছিয়ে যেতে পারে।

৭ · Quantum কত বড় হবে?

পুরো RR-এর আচরণ একটি সংখ্যায় বাঁধা — q. দুই প্রান্ত থেকে ভাবুন।

তাহলে মাঝামাঝি কোথায়? পাঠ্যবইয়ের (যেমন Silberschatz) একটি মোটা দাগের নিয়ম: quantum এমন হোক যাতে মোটামুটি ৮০% CPU burst q-এর চেয়ে ছোট হয়। তাহলে বেশিরভাগ প্রসেস এক quantum-এর মধ্যেই কাজ শেষ করে নিজে থেকে block হয় — preemption আর বাড়তি switch কমে, অথচ লম্বা CPU-bound কাজও কাউকে দীর্ঘক্ষণ আটকে রাখতে পারে না। এটি একটি নির্দেশিকা, প্রমাণিত সূত্র নয়; burst-এর বণ্টন কাজের ধরন অনুযায়ী বদলায়। পাঠ্যবইয়ে আধুনিক সিস্টেমের quantum সাধারণত ১০–১০০ ms ধরা হয়, আর context switch-এর সময় তার তুলনায় অনেক ছোট (মাইক্রোসেকেন্ডের ঘরে)।

Turnaround q-এর সাথে সরলভাবে কমে না

অনেকে ভাবেন quantum বাড়ালে গড় turnaround নিশ্চয়ই কমবে, কারণ switch কমে। কিন্তু উপরের simulator-এর শেষ লাইনটি দেখুন — চারটি প্রসেস, সবাই t = ০-তে, burst ৬, ৩, ১, ৭ (switch-এর খরচ শূন্য ধরে):

সংখ্যাগুলো ওঠানামা করছে! কারণটি বুঝতে q = ৩ আর q = ৫ পাশাপাশি রাখুন। q = ৩-এ P2 (৩) প্রথম চক্রেই ঠিক শেষ হয়, P3 (১)-ও; ফলে দুটি ছোট কাজ দ্রুত বিদায় নেয় (CT = ৬ আর ৭)। q = ৫-এ P1 প্রথমেই ৫ একক নিয়ে নেয়, P2 আর P3 সেই সময় অপেক্ষা করে (CT = ৮ আর ৯) — একটি বড় quantum ছোট কাজদের পিছিয়ে দিল, অথচ P1 নিজেও শেষ হলো না। শিক্ষা: গড় turnaround কমে তখন, যখন বেশিরভাগ প্রসেস একটি quantum-এর মধ্যেই শেষ হয়; q-এর সাথে এর সম্পর্ক monotonic নয়। পরীক্ষায় “q বাড়ালে TAT কমে” — এমন সাধারণ দাবি তাই ভুল।

৮ · দুটো মেলানো, আর অনুপাতে ভাগ — lottery থেকে CFS-এর পথে

Priority + Round Robin

বাস্তবের অনেক scheduler দুটো নীতি একসাথে ব্যবহার করে: সবচেয়ে উঁচু অগ্রাধিকার-স্তরে যারা আছে শুধু তারাই চলে, আর সেই স্তরের ভেতরে Round Robin. ট্রাফিক মোড়ে অ্যাম্বুলেন্স সবার আগে যায়; কিন্তু দুটি অ্যাম্বুলেন্স একসাথে এলে পুলিশ পালা করে ছাড়ে।

উদাহরণ ৪: সবাই t = ০-তে, q = ২. P1 (BT ৪, pr ১), P2 (BT ৩, pr ১), P3 (BT ৫, pr ২), P4 (BT ২, pr ২)। প্রথমে স্তর ১-এ P1 আর P2 RR-এ চলে; তারা শেষ হলে স্তর ২-এ P3 আর P4.

│ P1 0-2 │ P2 2-4 │ P1 4-6 │ P2 6-7 │ P3 7-9 │ P4 9-11 │ P3 11-13 │ P3 13-14 │

CT = ৬, ৭, ১৪, ১১. শেষে P3 একা থাকায় পরপর দুটি quantum পায় (১১–১৩, ১৩–১৪) — সারিতে আর কেউ নেই, তাই কোনো context switch-ও হয় না। Linux-এর SCHED_RR নীতি ঠিক এই নকশা: real-time priority ১–৯৯-এর প্রতিটি স্তরে আলাদা সারি, সবচেয়ে উঁচু অ-খালি স্তর চলে, আর একই স্তরের task-গুলো time slice ভাগ করে। (একই স্তরে SCHED_FIFO হলে task নিজে ছাড়া পর্যন্ত চলে।) স্তরগুলোর মধ্যে প্রসেস ওঠানামা করতে পারলে সেটি হয় multilevel feedback queue — পরের পর্বের বিষয়।

অনুপাতে ভাগ — proportional share

Priority বলে “কে আগে”; কিন্তু অনেক সময় প্রশ্নটা হলো “কে কত ভাগ”। একটি সার্ভারে দুটি বিভাগের কাজ চলছে, চুক্তি: হিসাব বিভাগ পাবে CPU-র ৬০%, মানবসম্পদ ৪০%. কঠোর priority দিয়ে এটা হয় না — উঁচু যে, সে সব নিয়ে নেয়। দরকার proportional-share scheduling.

• Lottery scheduling (Carl Waldspurger ও William Weihl, ১৯৯৪): প্রতিটি প্রসেস কিছু টিকিট পায়। প্রতিটি time slice-এর শুরুতে একটি এলোমেলো টিকিট টানা হয়; যার টিকিট, সে চলে। t টিকিটের মালিক মোট T টিকিটের মধ্যে প্রতিবার জেতার সম্ভাবনা t/T, তাই দীর্ঘমেয়াদে তার গড় ভাগ t/T. Starvation নেই — যার একটি টিকিটও আছে, তার জেতার সম্ভাবনা শূন্য নয়। দুর্বলতা: অল্প সময়ের হিসাবে ভাগ এলোমেলো।
• Stride scheduling (একই গবেষকদের, ১৯৯৫): এলোমেলোতার বদলে নির্ধারিত হিসাব। প্রত্যেকের stride = একটি বড় সংখ্যা ÷ টিকিট, আর একটি “pass” গণক। প্রতিবার যার pass সবচেয়ে ছোট সে চলে, তারপর তার pass-এ stride যোগ হয়। কম stride (বেশি টিকিট) মানে pass ধীরে বাড়ে, তাই বেশি পালা।
• Weighted fair queueing (Demers, Keshav ও Shenker, ১৯৮৯) মূলত নেটওয়ার্ক রাউটারে প্যাকেট পাঠানোর জন্য তৈরি — প্রতিটি প্রবাহ তার weight অনুপাতে লিংকের ভাগ পায়। Stride-এর pass আর WFQ-এর “virtual finish time” একই ধারণার দুই রূপ।

// Proportional share: lottery (random) vs stride (deterministic).
const tickets = { A: 50, B: 30, C: 20 };          // A should get 50% of the CPU
let seed = 12345;                                  // fixed seed -> same output every run
const rand = () => (seed = (seed * 48271) % 2147483647) / 2147483647;  // exact MINSTD generator

function lottery(slices) {
  const total = Object.values(tickets).reduce((a, b) => a + b, 0), won = { A: 0, B: 0, C: 0 };
  for (let i = 0; i < slices; i++) {
    let r = Math.floor(rand() * total);            // winning ticket number 0..total-1
    for (const p in tickets) { if (r < tickets[p]) { won[p]++; break; } r -= tickets[p]; }
  }
  return won;
}
for (const n of [10, 100, 10000]) {
  const w = lottery(n);
  console.log("lottery " + String(n).padStart(5) + " slices: A=" + w.A + " B=" + w.B + " C=" + w.C +
    "  (A share " + (100 * w.A / n).toFixed(1) + "%)");
}

// Stride: stride = BIG / tickets; always run the smallest "pass", then pass += stride.
const BIG = 600, pass = {}, stride = {}, won = { A: 0, B: 0, C: 0 }, order = [];
for (const p in tickets) { stride[p] = BIG / tickets[p]; pass[p] = 0; }
for (let i = 0; i < 20; i++) {
  const p = Object.keys(pass).sort((x, y) => pass[x] - pass[y] || (x < y ? -1 : 1))[0];
  order.push(p); won[p]++; pass[p] += stride[p];
}
console.log("stride strides: A=" + stride.A + " B=" + stride.B + " C=" + stride.C);
console.log("stride order:   " + order.join(""));
console.log("stride 20 slices: A=" + won.A + " B=" + won.B + " C=" + won.C);

lottery    10 slices: A=4 B=5 C=1  (A share 40.0%)
lottery   100 slices: A=50 B=27 C=23  (A share 50.0%)
lottery 10000 slices: A=4954 B=3011 C=2035  (A share 49.5%)
stride strides: A=12 B=20 C=30
stride order:   ABCABACABAABCABACABA
stride 20 slices: A=10 B=6 C=4

CFS-এর সেতু: Linux-এর Completely Fair Scheduler (CFS, ২০০৭ সালে Linux 2.6.23) stride-এর মতোই চিন্তা করে: প্রতিটি task-এর একটি “virtual runtime” — তার আসল চলার সময়কে weight দিয়ে ভাগ করে বাড়ে — আর সবসময় সবচেয়ে কম virtual runtime-এর task চলে। weight আসে nice থেকে: nice 0-এ 1024, আর nice-এর প্রতি এক ধাপে weight প্রায় ১.২৫ গুণ বদলায় (মোটামুটি ১০% CPU-র পার্থক্য)। Linux 6.6 (২০২৩) থেকে মূল নীতি EEVDF. এগুলোর পুরো ভেতরের কথা পর্ব ২১-এ।

নিজের চোখে দেখুন — Linux-এ একটি প্রসেসের nice আর kernel-এর চোখে তার priority. /proc/<pid>/stat-এর ১৮ আর ১৯ নম্বর ঘর যথাক্রমে priority আর nice; সাধারণ (non-real-time) প্রসেসে priority = nice + 20. awk এখানে /proc/self/stat পড়ছে, অর্থাৎ নিজের তথ্য।

# Fields 18 (priority) and 19 (nice) of /proc/self/stat, as seen by the kernel
awk '{print "default     : priority=" $18 " nice=" $19}' /proc/self/stat
nice -n 7 awk '{print "nice -n 7   : priority=" $18 " nice=" $19}' /proc/self/stat
nice -n 7 nice -n 5 awk '{print "7 then +5   : priority=" $18 " nice=" $19}' /proc/self/stat
nice -n 50 awk '{print "nice -n 50  : priority=" $18 " nice=" $19}' /proc/self/stat
{ nice -n -5 awk '{print "nice -n -5  : priority=" $18 " nice=" $19}' /proc/self/stat; } 2>&1
ps -o pid,ni,cls,comm -p $$
echo "SCHED_RR timeslice (ms): $(cat /proc/sys/kernel/sched_rr_timeslice_ms 2>/dev/null || echo n/a)"

default     : priority=30 nice=10
nice -n 7   : priority=37 nice=17
7 then +5   : priority=39 nice=19
nice -n 50  : priority=39 nice=19
nice: cannot set niceness: Permission denied
nice -n -5  : priority=30 nice=10
    PID  NI CLS COMMAND
      2  10  TS bash
SCHED_RR timeslice (ms): 100

Windows-এ ৩২টি স্তর (০–৩১, বড় সংখ্যা বেশি জরুরি): ১৬–৩১ real-time স্তর, ১–১৫ সাধারণ (variable) স্তর, আর ০ সংরক্ষিত একটি বিশেষ system thread-এর জন্য। সাধারণ স্তরে Windows dynamic priority ব্যবহার করে — I/O শেষ হলে বা জানালা সামনে এলে thread সাময়িক “boost” পায়। Windows Internals বইয়ের বর্ণনা অনুযায়ী একটি kernel thread (balance set manager) নিয়মিত খোঁজে কোন thread প্রায় ৪ সেকেন্ড ধরে ready থেকেও চলতে পারেনি, আর তাকে সাময়িকভাবে priority ১৫-তে তুলে দেয় — একেবারে বাস্তব aging, priority inversion কমানোর একটি মোটা দাগের উপায়ও।

৯ · AI-এর যুগে priority আর Round Robin

Scheduling-এর numerical-এ AI খুব আত্মবিশ্বাসী উত্তর দেয় — আর প্রায়ই নিঃশব্দে একটি নিয়ম ধরে নেয়, যা আপনার প্রশ্নের নিয়মের সাথে মেলে না। বাস্তব সিস্টেমে আরও বিপজ্জনক পরামর্শও আসে। নিচের টেবিলে সাধারণ ভুলগুলো:

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

• Priority-র দিক (ছোট না বড় সংখ্যা বেশি জরুরি) আর tie-নিয়ম উত্তরে স্পষ্ট লেখা আছে
• প্রতিটি arrival-এর মুহূর্তে preemption হওয়ার কথা কি না, নিজে একবার যাচাই করেছি
• অন্তত দুটি প্রসেসের CT, TAT, WT, RT হাতে কষে মিলিয়েছি; সব প্রসেসের burst-এর যোগফল = শেষ CT (CPU কখনো ফাঁকা না থাকলে)
• সংখ্যাগুলো এই পর্বের simulator-এ ডেটা বসিয়ে মিলিয়েছি
• বাস্তব সিস্টেমে sudo দিয়ে real-time priority বা negative nice দেওয়ার পরামর্শ মানার আগে মেপেছি, আর man 7 sched পড়েছি
• কমান্ডটি আমার OS-এর জন্য কি না দেখেছি (Linux-এর nice/chrt, Windows-এ Task Manager বা PowerShell-এর PriorityClass)