Linux-এর scheduler — CFS, EEVDF, nice আর cgroup

১ · পাঠ্যবইয়ের নিয়ম থেকে আসল kernel — সমস্যাটা কোথায়

পর্ব ১৬ থেকে ২০ পর্যন্ত আপনি পাঠ্যবইয়ের scheduler-গুলো দেখেছেন: FCFS, SJF, SRTF (পর্ব ১৭), priority আর Round Robin (পর্ব ১৮), multilevel feedback queue (পর্ব ১৯), আর বহু-CPU ও real-time scheduling (পর্ব ২০)। প্রতিটির একটি পরিষ্কার নিয়ম আছে, আর Gantt chart এঁকে হিসাব মেলানো যায়। কিন্তু আপনার ফোন, ল্যাপটপ বা সার্ভারের Linux kernel-কে প্রতিদিন যা সামলাতে হয়, তা কোনো একটি পাঠ্যবইয়ের নিয়মে ধরে না।

একটি সাধারণ Linux ল্যাপটপে একই সময়ে কয়েকশো process আর হাজারখানেক thread থাকে: ব্রাউজার, যেখানে মাউস নাড়ালে সাথে সাথে সাড়া চাই; ভিডিও কল, যার প্রতিটি ফ্রেমের সময়সীমা আছে; পেছনে কোড compile — যে যত CPU পায় তত খুশি। সার্ভারে একই যন্ত্রে বিশটি container, প্রত্যেকে টাকা দিয়ে নির্দিষ্ট পরিমাণ CPU কিনেছেন। আর Android ফোনেও একই kernel, যেখানে ব্যাটারি প্রধান।

Scheduler-এর কাছে তাই চাওয়া অনেক, আর কিছু চাওয়া পরস্পরবিরোধী:

• ন্যায্যতা: একই গুরুত্বের কাজ সমান CPU পাবে; কেউ starvation-এ পড়বে না।
• সাড়া (latency): কিবোর্ড, অডিওর মতো ছোট কিন্তু জরুরি কাজ দ্রুত CPU পাবে।
• Throughput: বড় কাজ বারবার থামানো যাবে না — প্রতিটি context switch-এর দাম আছে (পর্ব ০৯)।
• নিয়ন্ত্রণ আর মাপযোগ্যতা: nice, real-time policy, cgroup দিয়ে ভাগ বদলানো যাবে; আর ২ থেকে কয়েকশো CPU-তে একই kernel চলবে।

এই পর্বে সেই খাতাটি খুলব: ইতিহাস, CFS-এর হিসাব, nice থেকে weight, ২০২৩ সালের EEVDF, তারপর scheduling class, cgroup আর container — প্রতিটি দাবি আসল Linux-এ চালিয়ে।

২ · তিন যুগের ইতিহাস — O(n), O(1), আর ন্যায্যতার বিতর্ক

প্রথম যুগ: O(n) scheduler (১৯৯১–২০০৩ মোটামুটি)

Linux ২.৪ পর্যন্ত সব runnable task ছিল একটি বৈশ্বিক তালিকায়; প্রতিবার schedule() পুরো তালিকা ঘুরে প্রত্যেকের একটি “goodness” নম্বর হিসাব করত। প্রতিটি task-এর counter-এ থাকত কত tick বাকি; সবার counter শূন্য হলে নতুন “epoch”, আর সবার — ঘুমন্তদেরও — counter হতো প্রায় counter/2 + priority. ঘুমন্তদের বাকি counter-ই ছিল ইন্টারঅ্যাকটিভ কাজের বাড়তি সুবিধা। সমস্যা: প্রতিটি সিদ্ধান্ত O(n), আর একটি lock-এর জন্য সব CPU-র কাড়াকাড়ি — বড় সার্ভারে গুরুতর বাধা।

দ্বিতীয় যুগ: Ingo Molnár-এর O(1) scheduler (২.৬.০, ২০০৩)

২০০২ সালের শুরুতে Ingo Molnár ২.৫ উন্নয়ন-শাখায় একটি নতুন scheduler আনেন, যা ডিসেম্বর ২০০৩-এ প্রকাশিত Linux ২.৬.০-এর অংশ হয়। নাম O(1) scheduler, কারণ task যতই থাকুক, পরের task বাছতে সময় স্থির। কৌশলটি সুন্দর:

• প্রতিটি CPU-র নিজের run queue — বৈশ্বিক lock-এর কাড়াকাড়ি শেষ।
• ১৪০টি priority স্তর — ০–৯৯ real-time, ১০০–১৩৯ সাধারণ task (nice −২০ থেকে ১৯). প্রতিটি স্তরের জন্য একটি আলাদা তালিকা, আর ১৪০-bit-এর একটি bitmap, যার bit বলে কোন স্তরে কেউ অপেক্ষায় আছে।
• দুটি array — active আর expired. কেউ নিজের timeslice শেষ করলে expired-এ যায়। Active খালি হলে দুটি pointer অদলবদল — পুরো epoch-এর পুনর্হিসাব এক নিমেষে।
• বাছাই: bitmap-এ প্রথম set bit খোঁজা (CPU-র bit-খোঁজার instruction দিয়ে কয়েক ধাপেই হয়), সেই স্তরের তালিকার প্রথম task — O(1).

Timeslice দেওয়া হতো static priority অনুযায়ী — nice 0-তে প্রায় ১০০ ms. আসল জটিলতা ছিল ইন্টারঅ্যাকটিভিটির অনুমান: প্রতিটি task-এর sleep_avg (কতটা ঘুমায়) দেখে বেশি ঘুমানো task-এর dynamic priority ৫ ধাপ পর্যন্ত বাড়ত, কম ঘুমানোর কমত; “ইন্টারঅ্যাকটিভ” task slice শেষেও আবার active-এ ঢুকতে পারত। এই heuristic গড়ে ভালো, কিন্তু ভিডিও প্লেয়ার বা গেমের মতো কাজে — যা অনেক CPU খায় আবার নিয়মিত ঘুমায় — অনুমান কখনো মিলত, কখনো না; কিছু প্রোগ্রাম কৌশলে বাড়তি priority আদায়ও করত। ভুল সারাতে heuristic-এর ওপর heuristic জমতে থাকে।

তৃতীয় যুগ: CFS (২.৬.২৩, অক্টোবর ২০০৭) — আর তার উত্তরসূরি EEVDF (৬.৬, ২০২৩)

CFS অক্টোবর ২০০৭-এ Linux ২.৬.২৩-এ আসে আর প্রায় ষোল বছর টিকে থাকে। ঘোষণা ছিল বৈপ্লবিক: timeslice নেই, sleep-অনুমান নেই, priority array নেই — শুধু একটি সংখ্যা, আদর্শ ন্যায্য CPU-র তুলনায় কে কতটা চলেছে। ২০২৩ সালের শেষে Linux ৬.৬-এ Peter Zijlstra CFS-এর বাছাইয়ের নিয়মটি EEVDF দিয়ে বদলে দেন; vruntime-এর হিসাব, weight, tree — বেশিরভাগ কাঠামো রয়ে গেছে (অংশ ৬)।

৩ · CFS-এর হৃদয় — virtual runtime

CFS প্রতিটি task-এর (kernel-এর ভাষায় scheduling entity) জন্য একটি সংখ্যা রাখে: vruntime, ন্যানোসেকেন্ডে। Task যখন CPU-তে চলে, তার vruntime বাড়ে:

এখানে 1024 হলো nice 0-এর weight (kernel-এ NICE_0_LOAD). তাই nice 0-এর task ১ ms চললে vruntime-ও ১ ms বাড়ে; বেশি weight-এর task-এর ধীরে, কম weight-এর দ্রুত। বাছাইয়ের নিয়ম: যে runnable task-এর vruntime সবচেয়ে কম, সে-ই পরের পালা পাবে।

যে task কম CPU পেয়েছে, তার vruntime পিছিয়ে, তাই সে আগে বাছাই হয়ে ধরে ফেলে। দীর্ঘ সময়ে সবার vruntime প্রায় সমান — মানে প্রত্যেকে weight-এর অনুপাতে আসল সময় পেয়েছে (অংশ ৪-এ প্রমাণ)। “ইন্টারঅ্যাকটিভ” অনুমানও লাগে না: টেক্সট এডিটর বেশিরভাগ সময় ঘুমায়, তাই জেগে উঠলেই সে সারির সামনে।

সবচেয়ে কম vruntime দ্রুত খুঁজতে CFS প্রতিটি CPU-র runnable task-গুলো একটি red-black tree-তে রাখে, vruntime-কে key করে। এটি স্ব-ভারসাম্য binary search tree (DSA-র red-black tree পর্ব): insert, delete O(log n), সবচেয়ে ছোট key বাঁয়ের node-এ, আর kernel সেই node-এর pointer আলাদা রাখে (rb_root_cached) — বাছাই O(1).

নিচের ডায়াগ্রামে একটি CPU-তে তিনটি সবসময়-ব্যস্ত task: A আর B nice 0 (weight 1024), C nice 5 (weight 335). সহজ করার জন্য scheduler প্রতি ১ ms tick-এ সিদ্ধান্ত নেয়, আর vruntime সমান হলে যে আগে সারিতে ঢুকেছে সে আগে। C ১ ms চললে তার vruntime বাড়ে 1024 ÷ 335 ≈ ৩.০৫৭ ms.

এবার একই নিয়ম অনেকক্ষণ চালিয়ে দেখি। নিচের JavaScript simulator প্রতি tick-এ সবচেয়ে কম vruntime-এর task বেছে নেয়, kernel-এর মতো পূর্ণসংখ্যায় (ন্যানোসেকেন্ডে) vruntime বাড়ায়, আর বিভিন্ন সময়ে কে কত শতাংশ CPU পেল ছাপায়:

// CFS in miniature: 1 CPU, 3 always-runnable tasks, the scheduler decides every 1 ms tick
const NICE_0_LOAD = 1024, TICK = 1000000;            // tick in nanoseconds
const tasks = [
  { name: "A", nice: 0, w: 1024 },
  { name: "B", nice: 0, w: 1024 },
  { name: "C", nice: 5, w: 335 },                    // sched_prio_to_weight[nice + 20]
].map(t => ({ ...t, vruntime: 0, ran: 0 }));
let picks = "", done = 0;
function tick() {
  let cur = tasks[0];                                // "leftmost": smallest vruntime wins
  for (const t of tasks) if (t.vruntime < cur.vruntime) cur = t;
  cur.ran++;
  cur.vruntime += Math.floor(TICK * NICE_0_LOAD / cur.w);   // calc_delta_fair()
  if (picks.length < 21) picks += cur.name;
  done++;
}
const W = tasks.reduce((s, t) => s + t.w, 0);
const pct = x => (100 * x).toFixed(2).padStart(6) + "%";
for (const upto of [21, 100, 1000, 10000]) {
  while (done < upto) tick();
  console.log(`after ${String(done).padStart(5)} ticks: ` +
    tasks.map(t => `${t.name} ${pct(t.ran / done)}`).join("  "));
}
console.log("theory  w / total     : " + tasks.map(t => `${t.name} ${pct(t.w / W)}`).join("  "));
console.log("first 21 picks        : " + picks);
console.log("vruntime now (ms)     : " +
  tasks.map(t => `${t.name} ${(t.vruntime / 1e6).toFixed(3)}`).join("  "));

after    21 ticks: A  42.86%  B  42.86%  C  14.29%
after   100 ticks: A  43.00%  B  43.00%  C  14.00%
after  1000 ticks: A  43.00%  B  42.90%  C  14.10%
after 10000 ticks: A  42.97%  B  42.97%  C  14.06%
theory  w / total     : A  42.97%  B  42.97%  C  14.06%
first 21 picks        : ABCABABABCABABABCABAB
vruntime now (ms)     : A 4297.000  B 4297.000  C 4297.743

৪ · nice থেকে weight — “এক ধাপে ১০%” নিয়ম

পর্ব ১১-এ nice আর renice চালিয়েছেন: −২০ থেকে ১৯, ডিফল্ট ০, বেশি মানে “ভদ্র”। কিন্তু nice 5 মানে ঠিক কতটা কম CPU? উত্তর kernel/sched/core.c-এর ৪০ ঘরের সারণি sched_prio_to_weight[]:

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

নিয়মটি হলো: nice 0 = 1024, আর প্রতি ধাপে weight প্রায় ১.২৫ গুণ বদলায় (1024 ÷ 820 ≈ ১.২৪৯, 820 ÷ 655 ≈ ১.২৫২…)। কেন ১.২৫? Kernel-এর মন্তব্যেই উদ্দেশ্য লেখা: একটি CPU-নির্ভর task nice 0 থেকে nice 1-এ গেলে, nice 0-তে থাকা আরেকটি CPU-নির্ভর task-এর তুলনায় সে মোটামুটি ১০% কম CPU পাবে। নিচের stepper-এ হিসাবটি দেখবেন। প্রভাবটি আপেক্ষিক ও গুণোত্তর: যেকোনো nice থেকে এক ধাপ সরলে একই প্রভাব, কারণ অনুপাত সব জায়গায় ১.২৫.

এবার পুরো হিসাব ধাপে ধাপে — পরীক্ষার ধাঁচের numerical: একটি CPU-তে A, B (nice 0) আর C (nice 5); শেষ দুই ধাপে দুটি বিখ্যাত তুলনা।

এবার আসল kernel-কে পরীক্ষা। প্রোগ্রামটি নিজেকে একটি CPU-তে বাঁধে (CPU affinity, পর্ব ২০), তারপর দুটি child বানায় — affinity উত্তরাধিকারে যায়, তাই দুজনে একই CPU-র জন্য লড়বে। Child ২ nice 10 ধাপ বাড়ায়। দুজনেই একই মুহূর্ত পর্যন্ত (প্রায় ১ সেকেন্ড) গণনা চালিয়ে pipe দিয়ে জানায় কত কাজ করল।

#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <sys/wait.h>
static const int weight[40] = {   /* sched_prio_to_weight[], nice -20 .. 19 */
 88761, 71755, 56483, 46273, 36291, 29154, 23254, 18705, 14949, 11916,
  9548,  7620,  6100,  4904,  3906,  3121,  2501,  1991,  1586,  1277,
  1024,   820,   655,   526,   423,   335,   272,   215,   172,   137,
   110,    87,    70,    56,    45,    36,    29,    23,    18,    15 };
static double now(void) {
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}
int main(void) {
    cpu_set_t one; CPU_ZERO(&one); CPU_SET(sched_getcpu(), &one);
    if (sched_setaffinity(0, sizeof one, &one) != 0) return 1;  /* children inherit */
    int fd[2]; long r[2][3], t[3]; if (pipe(fd) != 0) return 1;
    double end = now() + 1.0;                   /* both children stop at the same moment */
    for (long k = 0; k < 2; k++)
        if (fork() == 0) {
            long ni = nice(k == 0 ? 0 : 10);    /* child 1 keeps its nice, child 2: +10 */
            volatile unsigned long n = 0;
            while (now() < end) for (int i = 0; i < 100000; i++) n++;
            long rec[3] = { k, ni, (long)(n / 100000) };
            _exit(write(fd[1], rec, sizeof rec) == sizeof rec ? 0 : 1);
        }
    for (int k = 0; k < 2; k++) { wait(NULL); if (read(fd[0], t, sizeof t) == sizeof t) for (int j = 0; j < 3; j++) r[t[0]][j] = t[j]; }
    for (int k = 0; k < 2; k++)
        printf("child %d: nice %3ld  weight %5d  work %ld units\n", k + 1, r[k][1], weight[r[k][1] + 20], r[k][2]);
    printf("measured work ratio  : %.2f\n", (double)r[0][2] / r[1][2]);
    printf("weight ratio (theory): %.2f\n", (double)weight[r[0][1] + 20] / weight[r[1][1] + 20]);
    return 0;
}

child 1: nice  10  weight   110  work 8665 units
child 2: nice  19  weight    15  work 1238 units
measured work ratio  : 7.00
weight ratio (theory): 7.33

৫ · CFS-এর ভেতরের কলকবজা — slice, min_vruntime, ঘুম আর জন্ম

“সবচেয়ে কম vruntime চলবে” নিয়মটি একা চললে দুটি সমান task প্রতি মুহূর্তে অদলবদল করত, আর সব সময় যেত context switch-এ। আবার নতুন বা অনেকক্ষণ ঘুমিয়ে থাকা task-এর vruntime কত ধরা হবে? এই প্রশ্নগুলোর উত্তরই CFS-এর বাস্তব নকশা।

Targeted latency আর minimum granularity

ক্লাসিক CFS একটি targeted latency (sched_latency_ns) রাখত: এই সময়ের মধ্যে প্রতিটি runnable task অন্তত একবার চলবে। ভিত্তি-মান ৬ ms, আর CPU-র সংখ্যা অনুযায়ী বাড়ানো হতো (গুণক ১ + log₂(CPU-সংখ্যা), সর্বোচ্চ ৮ CPU পর্যন্ত গোনা — ৮ বা বেশি CPU-তে ২৪ ms). প্রতিটি task-এর slice = period × নিজের weight ÷ মোট weight — ঠিক আগের stepper-এর ধাপ ৪। কিন্তু task অনেক হলে slice অসম্ভব ছোট হয়ে যেত, তাই ছিল একটি তলা: minimum granularity (ভিত্তি ০.৭৫ ms). Runnable task ৮-এর বেশি হলে (৬ ÷ ০.৭৫ = ৮) period-ই বাড়ানো হতো: period = task-সংখ্যা × ০.৭৫ ms. — অনেক task-এ latency ছেড়ে throughput বাঁচানো। আর wakeup granularity (ভিত্তি ১ ms): জেগে ওঠা task চলমান task-কে সরাবে কেবল vruntime-এর পার্থক্য এর বেশি হলে।

মানগুলো পুরোনো kernel-এ /proc/sys/kernel/sched_latency_ns-এর মতো ফাইলে ছিল; Linux ৫.১৩ থেকে debugfs-এ (/sys/kernel/debug/sched/) সরানো হয়, কারণ অনেকে ইন্টারনেটের পরামর্শে অন্ধভাবে বদলাতেন। EEVDF-এ latency-র মানটিই নেই, আছে base_slice_ns. (সংখ্যাগুলো সংস্করণভেদে বদলেছে।)

min_vruntime — খাতার “আজকের তারিখ”

প্রতিটি CPU-র run queue (cfs_rq) একটি min_vruntime রাখে — মোটামুটি সবচেয়ে ছোট vruntime-এর মান, যা শুধু সামনে এগোয়, কখনো পেছায় না। নতুন বা জেগে ওঠা task-কে বসানোর সময় এটিই মাপকাঠি।

ঘুম থেকে ফেরা — sleeper fairness

এক ঘণ্টা ঘুমানো task পুরোনো vruntime নিয়ে জাগলে সবার চেয়ে এক ঘণ্টা “পিছিয়ে” — অনেকক্ষণ সে একাই CPU দখল করত! তাই CFS জেগে ওঠা task-এর vruntime বসাত প্রায় max(নিজের vruntime, min_vruntime − sched_latency/2)-এ: অর্ধেক latency period-এর বাড়তি সুবিধা, যাতে জেগেই দ্রুত চলতে পারে — কিন্তু অসীম ঋণ নয়। এই নীতির নাম sleeper fairness, আর “অর্ধেক” করার পতাকাটির নাম ছিল GENTLE_FAIR_SLEEPERS.

নতুন task — fork করে কৌশল ঠেকানো

নতুন task-এর vruntime 0 দিলে একটি প্রোগ্রাম বারবার fork করে CPU দখল করতে পারত। তাই CFS নতুন task-কে বসাত min_vruntime-এর মোটামুটি একটি slice পরে (START_DEBIT পতাকা)। আর child আর parent-এর কে আগে চলবে? CFS-যুগে sched_child_runs_first-এর ডিফল্ট ছিল 0, অর্থাৎ সাধারণত parent চলতে থাকে — পর্ব ১০-এর fork-এর আউটপুটের ক্রম কেন অনিশ্চিত, তার একটি কারণ এখানে।

নিচের কোড দুটি মূল ফাংশনের সরলীকৃত রূপ — নাম, ফিল্ড আর যুক্তি আসল kernel-এর, শুধু lock, পরিসংখ্যান, group scheduling আর বিশেষ ক্ষেত্র বাদ দেওয়া। প্রতিটি timer tick-এ, task ঘুমাতে গেলে বা জেগে উঠলে update_curr() ডাকা হয়।

static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec = now - curr->exec_start;   /* শেষ হিসাবের পর কত ns চলল */

    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;      /* আসল সময়ের মোট */
    curr->vruntime += calc_delta_fair(delta_exec, curr);
                    /* = delta_exec * NICE_0_LOAD / curr->load.weight */
    update_min_vruntime(cfs_rq);               /* শুধু সামনে এগোয় */
}

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    /* rb_root_cached বাঁয়ের node মনে রাখে, তাই খোঁজা O(1) */
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);

    return rb_entry(left, struct sched_entity, run_node);
    /* আসল কোডে next/last/skip "buddy" নামের কিছু ব্যতিক্রম ছিল:
       যেমন সদ্য জাগানো task-কে cache গরম থাকতে আগে চালানো */
}

calc_delta_fair আসলে ভাগ করে না — আগে থেকে হিসাব করা উল্টো মান (sched_prio_to_wmult[]) দিয়ে গুণ আর bit-shift করে, কারণ ভাগ ধীর। আর tick-এ চলমান task slice পেরোলে তার ওপর need_resched পতাকা বসে, kernel থেকে ফেরার পথে schedule() নতুন বাছাই করে (পর্ব ০৯)।

৬ · EEVDF (Linux ৬.৬, ২০২৩) — lag, eligibility আর virtual deadline

CFS-এর কাছে একটি প্রশ্নের পরিষ্কার উত্তর ছিল না: দুটি task-এর ভাগ সমান, কিন্তু একজনের দরকার ঘন ঘন ছোট পালা (অডিও), অন্যজনের লম্বা পালা (compile) — কাকে কখন? nice শুধু ভাগ বদলায়, latency নয়; এর জন্য জমেছিল জোড়াতালি — wakeup granularity, sleeper-এর বাড়তি, buddy-নিয়ম। ২০১৯ থেকে প্রস্তাবিত “latency-nice” মানের অর্থও CFS-এর কাঠামোয় পরিষ্কার করা যাচ্ছিল না।

Peter Zijlstra ২০২৩ সালে একটি পুরোনো গবেষণাপত্রে ফিরে যান: Ion Stoica আর Hussein Abdel-Wahab-এর ১৯৯৫ সালের Earliest Eligible Virtual Deadline First. বাছাইয়ের অংশটি তিনি এর ওপর নতুন করে লেখেন, যা Linux ৬.৬-এ (অক্টোবর ২০২৩) আসে। Weight, vruntime, tree, SCHED_OTHER — সব একই; বদলেছে “কাকে বাছব” আর “কতক্ষণ চালাব”।

তিনটি ধারণা

• V — গড় vruntime: runnable task-দের vruntime-এর weight-ভারিত গড়, V = Σ w_i v_i ÷ Σ w_i. আদর্শ ন্যায্য CPU-তে এই মুহূর্তে সবার vruntime যা হওয়ার কথা, V তা-ই (kernel-এ avg_vruntime())।
• Lag: lag_i = w_i × (V − v_i) — আদর্শে task-টির যতটা পাওয়ার কথা, তার চেয়ে কত কম পেয়েছে। ধনাত্মক মানে পাওনা আছে, ঋণাত্মক মানে বেশি নিয়ে ফেলেছে। Eligible শুধু তারা, যাদের lag ≥ ০, অর্থাৎ v_i ≤ V.
• Virtual deadline: d_i = v_i + slice_i × 1024 ÷ w_i — task-টি নিজের চাওয়া slice পুরোটা পেলে খাতায় কোথায় পৌঁছাবে। ছোট slice চাওয়া task-এর deadline কাছে।

Eligibility ন্যায্যতা পাহারা দেয় — ভাগের বেশি নেওয়া task-কে অপেক্ষা করতে হয়, deadline যত কাছেই হোক; deadline latency ঠিক করে — সীমার মধ্যে যে ছোট পালা চায়, সে আগে পায়। CFS-এ দুটি একটি সংখ্যায় মেশানো ছিল।

একটি উদাহরণে তিন নিয়ম পাশাপাশি: CFS (সবচেয়ে কম vruntime), শুধু-deadline (eligibility ছাড়া) আর EEVDF. চারটি task, সবার weight 1024 (তাই virtual slice = আসল slice), একক ms; D একটি অডিও thread, slice ০.৫ ms.

Kernel-এ EEVDF কীভাবে লেখা

Tree এখনো red-black tree, তবে augmented: প্রতিটি node তার subtree-র একটি সারাংশ রাখে, তাই “eligible-দের মধ্যে আগের deadline” O(log n)-এ মেলে (প্রথম সংস্করণে tree vruntime-ক্রমে, পরে deadline-ক্রমে — বিস্তারিত সংস্করণভেদে বদলেছে)। V-এর জন্য kernel Σ w_i(v_i − min_vruntime) আর Σ w_i জমা রাখে।

/* eligible? v <= V, ভাগ না করে: (v - min_v) * Σw <= Σ w*(v_i - min_v) */
static int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    s64 avg  = cfs_rq->avg_vruntime;           /* Σ w_i * (v_i - min_vruntime) */
    long load = cfs_rq->avg_load;              /* Σ w_i */
    return avg >= (s64)(se->vruntime - cfs_rq->min_vruntime) * load;
}

/* update_curr()-এর শেষে ডাকা হয়: slice শেষ হলে নতুন deadline */
static void update_deadline(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    if ((s64)(se->vruntime - se->deadline) < 0)
        return;                                 /* এখনো slice বাকি */
    se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
    resched_curr(rq_of(cfs_rq));                /* আবার বাছাই */
}

/* pick_eevdf(): eligible entity-দের মধ্যে সবচেয়ে আগের deadline —
   augmented rbtree-তে O(log n) খোঁজা; কেউ না মিললে বাঁয়ের node */

EEVDF-এ “কতক্ষণ চালাব”-ও বদলেছে: period ভাগ করে slice নয়, প্রতিটি task-এর নিজের slice (ডিফল্ট base_slice_ns; অংশ ৭-এর রানে se.slice 1400000, অর্থাৎ ১.৪ ms), deadline পেরোলেই আবার বাছাই। Task-প্রতি আলাদা slice চাওয়া এসেছে পরে — যতদূর জানা যায়, প্রায় ৬.১২ থেকে sched_setattr()-এর sched_runtime দিয়ে, একটি সীমার মধ্যে। “latency-nice” মানটি এই লেখা পর্যন্ত মূলধারায় আসেনি — নিজের kernel-এর Documentation/scheduler/sched-eevdf.rst দেখে নিশ্চিত হোন।

৭ · Scheduling class আর policy — ps আর top-এর সংখ্যা পড়া

এ পর্যন্ত যা দেখলেন — CFS বা EEVDF — তা Linux-এর একমাত্র scheduler নয়, শুধু সাধারণ task-এর। Kernel-এ কয়েকটি scheduling class আছে — প্রত্যেকে struct sched_class-এ ফাংশন pointer-এর একটি টেবিল — কঠোর ক্রমে সাজানো। schedule() ওপরের class থেকে খোঁজে: এই class-এ কেউ runnable আছে কি না; প্রথম যেখানে পায়, সেই task চলে।

ক্রমটির মানে কঠোর: একটি runnable SCHED_FIFO task থাকলে fair class-এর কেউ সেই CPU পায় না — nice −২০-ও না। (তবে ডিফল্টভাবে real-time task-রা প্রতি ১ সেকেন্ডে সর্বোচ্চ ০.৯৫ সেকেন্ড পায়, sched_rt_runtime_us; বাকি ৫% সাধারণ task-এর জন্য — ভুল real-time কোড পুরো যন্ত্র আটকে ফেলবে না।) Fair class-এর ভেতরের তিনটি policy:

• SCHED_OTHER — ডিফল্ট; nice অনুযায়ী weight.
• SCHED_BATCH — একই weight, কিন্তু scheduler ধরে নেয় task-টি CPU-নির্ভর আর latency-তে উদাসীন: জেগে উঠে সে চলমান task-কে সরায় না, তাই context switch কম, cache ভালো থাকে। রাতের ব্যাকআপ, ডেটা প্রক্রিয়াকরণের জন্য।
• SCHED_IDLE — weight মাত্র ৩, nice 19-এর (15) চেয়েও অনেক কম। প্রায় শুধু তখনই চলে, যখন আর কেউ নেই।

PR, NI, PRI — তিনটি সংখ্যা, তিন রকম নিয়ম

পর্ব ১১-এ top-এর PR = ২০ + NI দেখেছেন। পুরো ছবিটা এই: kernel-এর ভেতরে প্রতিটি task-এর একটি prio, ০–১৩৯, যেখানে ছোট সংখ্যা = বেশি গুরুত্ব। ০–৯৯ real-time (prio = ৯৯ − rt_priority), ১০০–১৩৯ সাধারণ (prio = ১২০ + nice). বিভিন্ন টুল এটি বিভিন্নভাবে দেখায়:

ps-এর pri উল্টো দিকে চলে, আর ps -l-এর PRI আরেক নিয়মে — তাই আগে জানুন কোন টুলের কোন কলাম। আসল যন্ত্রে মিলিয়ে দেখি:

ps -o pid,ni,pri,cls,comm               # NI = nice, PRI = ps-style priority, CLS = policy
nice -n 10 sh -c 'ps -o ni= -p $$'      # ask for +10 more
chrt -p $$                              # policy of this bash
for n in 0 4 9; do                      # nice -> weight, read from the kernel itself
  nice -n $n sh -c 'printf "NI %s -> se.load.weight %s\n" "$(ps -o ni= -p $$)" \
    "$(awk "/se.load.weight/{print \$3}" /proc/$$/sched)"'
done
echo "autogroup: $(cat /proc/self/autogroup)"
echo "cgroup cpu.max: $(cat /sys/fs/cgroup/cpu.max), cpu.weight: $(cat /sys/fs/cgroup/cpu.weight)"
if [ -r /proc/$$/sched ]; then
  grep -E '^(se\.vruntime|se\.sum_exec_runtime|nr_switches|policy|prio|se\.slice) ' /proc/$$/sched
else
  echo "/proc/PID/sched is not available (kernel built without SCHED_DEBUG)"
fi

    PID  NI PRI CLS COMMAND
      1  10   9  TS podman-init
      2  10   9  TS bash
      3  10   9  TS ps
 19
pid 2's current scheduling policy: SCHED_OTHER
pid 2's current scheduling priority: 0
NI  10 -> se.load.weight 112640
NI  14 -> se.load.weight 46080
NI  19 -> se.load.weight 15360
autogroup: /autogroup-8473039 nice 0
cgroup cpu.max: max 100000, cpu.weight: 100
se.vruntime                                  :           933.944650
se.sum_exec_runtime                          :            10.423888
nr_switches                                  :                   21
policy                                       :                    0
prio                                         :                  130
se.slice                                     :              1400000

নিজের যন্ত্রে policy বদলানোর কয়েকটি কমান্ড (উদাহরণ; real-time policy-তে সাধারণত root বা CAP_SYS_NICE লাগে, তাই অনলাইন ব্লকে চালানো হয়নি):

$ chrt -b 0 ./nightly-report.sh        # SCHED_BATCH-এ চালানো
$ chrt -i 0 ./index-photos             # SCHED_IDLE: শুধু অলস সময়ে
$ sudo chrt -f 50 ./audio-engine       # SCHED_FIFO, priority 50 — সাবধানে!
$ chrt -p 4242
pid 4242's current scheduling policy: SCHED_BATCH
pid 4242's current scheduling priority: 0
$ ps -eo pid,cls,rtprio,ni,pri,comm | head -4
    PID CLS RTPRIO  NI PRI COMMAND
      1  TS      -   0  19 systemd
     17  FF     99   -  139 migration/0
     23  TS      -   0  19 kthreadd

৮ · Task-এর ওপরে দল — autogroup, cgroup v2 আর container-এর CPU limit

এক terminal-এ make -j16 (১৬টি compiler) আর অন্য জানালায় এক-thread-এর ব্রাউজার: task-ভিত্তিক ন্যায্যতায় ব্রাউজার পায় ১/১৭ ভাগ, অথচ ব্যবহারকারীর চোখে দুটি “কাজ”। সমাধান group scheduling (২.৬.২৪ থেকে): একটি দল fair class-এর কাছে একটি entity — নিজের weight, নিজের vruntime — আর দলের ভেতরে আরেকটি cfs_rq. অর্থাৎ tree-র ভেতরে tree.

Autogroup — terminal ধরে স্বয়ংক্রিয় দল

Linux ২.৬.৩৮-এ (২০১১) Mike Galbraith-এর autogroup আসে: প্রতিটি session (পর্ব ১১; সাধারণত একটি terminal বা SSH সংযোগ) আপনা-আপনি একটি দল — ১৬টি compiler এক দল, ব্রাউজার আরেক, প্রত্যেকে প্রায় অর্ধেক। উপরের রানের autogroup: /autogroup-8473039 nice 0 এই script-এর session-এর দল।

cgroup v2-এর cpu controller

cgroup process-দের একটি গাছে দল বাঁধে আর প্রতিটি দলের CPU, মেমরি, I/O নিয়ন্ত্রণ করে (পুরো গল্প পর্ব ৫১-এ)। CPU-র দুটি ফাইল, cgroup v2-এ:

• cpu.weight (১–১০০০০, ডিফল্ট ১০০) — দলের আপেক্ষিক ভাগ, task-এর weight-এর মতো; শুধু প্রতিযোগিতায় কার্যকর, অলস যন্ত্রে weight ১-এর দলও পুরো CPU পায়। (cgroup v1-এ এর নাম ছিল cpu.shares, ডিফল্ট ১০২৪।)
• cpu.max — কড়া সীমা: “quota period” মাইক্রোসেকেন্ডে। 50000 100000 = প্রতি ১০০ ms-এ সব CPU মিলিয়ে সর্বোচ্চ ৫০ ms, অর্থাৎ অর্ধেক CPU — যন্ত্র অলস থাকলেও। উপরের রানের max 100000 মানে কোনো সীমা নেই।

cpu.max-এর পেছনের যন্ত্রটির নাম CFS bandwidth control, Linux ৩.২-এ (২০১২) যুক্ত — মূলত Google আর IBM-এর প্রকৌশলীদের কাজ। প্রতি period-এ দল একটি কোটা পায় (প্রতিটি CPU ছোট টুকরো ধার নেয়); কোটা শেষ হলে দলের সব task throttle হয় — period-এর বাকি সময় চলতে পারে না, CPU অলস থাকলেও।

Kubernetes-এর CPU request আর limit — আর throttling-এর ফাঁদ

Container-এর টুলগুলো সরাসরি এই ফাইল লেখে: Docker-এ --cpus=1.5 মানে cpu.max = 150000 100000; Kubernetes-এ requests.cpu হয় weight (ভিড়ে আনুপাতিক ভাগ), আর limits.cpu হয় cpu.max (কড়া সীমা)। সমস্যা আসে বহু-thread প্রোগ্রামে:

$ cat /sys/fs/cgroup/kubepods.slice/.../cpu.max
200000 100000
$ cat /sys/fs/cgroup/kubepods.slice/.../cpu.stat
usage_usec 118204331
user_usec 101330120
system_usec 16874211
nr_periods 600
nr_throttled 600
throttled_usec 360102874

তাই দেরি-সংবেদনশীল সার্ভিসে CPU limit নিয়ে বিতর্ক আছে — অনেকে শুধু request রাখেন, অন্যরা বলেন limit ছাড়া একটি ভুল pod পুরো node অনিশ্চিত করে (ভাবনার প্রশ্ন ৪)। সাহায্য এসেছে cpu.max.burst-এ (৫.১৪ থেকে, অব্যবহৃত কোটার কিছুটা পরে খরচ), আর ২০১৯ নাগাদ ধরা পড়া একটি অপ্রয়োজনীয়-throttling বাগের সংশোধন এসেছে Linux ৫.৪-এ। Runtime-কেও (JVM, Go) জানতে হয় সে কত CPU-র কোটা পেয়েছে; না জানলে বেশি thread বানিয়ে ঠিক এই ফাঁদে পড়ে।

৯ · sched_ext, আর Windows ও macOS-এর scheduler

sched_ext — scheduler-ও এখন প্রোগ্রাম করা যায় (Linux ৬.১২)

বহু বছর Linux-এর নীতি ছিল একটিই সাধারণ scheduler; কিন্তু Meta, Google-এর মতো প্রতিষ্ঠান নিজস্ব scheduler নিয়ে রিবুট ছাড়া পরীক্ষা চালাতে চাইছিল। Tejun Heo আর David Vernet (Meta)-এর নেতৃত্বে তৈরি sched_ext একটি নতুন scheduling class দেয়, যার নিয়ম লেখা হয় eBPF প্রোগ্রামে (পর্ব ৫৫) — চলমান kernel-এ লোড করা যায়, রিবুট ছাড়াই বদলানো যায়। দীর্ঘ বিতর্কের পর এটি Linux ৬.১২-এ (নভেম্বর ২০২৪) মূলধারায় আসে।

নিরাপত্তা-জাল আছে: BPF verifier প্রোগ্রাম লোডের আগে যাচাই করে; আর BPF scheduler ভুল করলে — যেমন একটি runnable task-কে একটি সময়সীমার মধ্যে না চালালে (ডিফল্ট সর্বোচ্চ প্রায় ৩০ সেকেন্ড; BPF scheduler নিজে আরও কম ঠিক করতে পারে) — kernel তাকে সরিয়ে দিয়ে সব task fair class-এ ফিরিয়ে আনে। উদাহরণ: scx_rustland (নিয়ম user space-এ Rust-এ) আর গেমিংয়ের জন্য scx_lavd (Steam Deck-এর জন্য Igalia-র কাজ বলে পরিচিত)। সাধারণ ব্যবহারে ডিফল্ট fair class-ই থাকছে।

অন্য OS কী করে

দর্শনের পার্থক্য লক্ষ করুন: Windows আর macOS মূলত priority আর ইঙ্গিত-নির্ভর — Windows নিজে boost দেয়, macOS অ্যাপকে QoS জানাতে বলে; Linux-এর fair class দাঁড়িয়ে আনুপাতিক ভাগের গণিতে, যেখানে nice আসলে একটি অনুপাত। কোনোটি সার্বিকভাবে “সেরা” নয়। (ভেতরের সংখ্যা ও নাম সংস্করণভেদে বদলায়; Windows আরও দেখবেন পর্ব ৫৬-এ।)

১০ · AI-এর যুগে scheduler-এর প্রশ্ন — উত্তর যাচাই

“আমার সার্ভারে latency বেশি, scheduler tune করব কীভাবে?” — AI সাথে সাথে sched_latency_ns আর sched_min_granularity_ns-এর মান বলে দেবে, প্রায়ই sysctl -w দিয়ে। সমস্যা: এই ফাইলগুলো ৫.১৩ থেকে /proc/sys-এ নেই, আর EEVDF-যুগের kernel-এ latency-র মানটিই নেই। AI-এর জানা তথ্যের বড় অংশ পুরোনো kernel-এর। সাধারণ ভুলগুলো:

AI-এর দেওয়া scheduler-পরামর্শ ব্যবহারের আগে — চেকলিস্ট

• uname -r দেখে নিশ্চিত হয়েছি পরামর্শটি আমার kernel-এর (CFS না EEVDF) জন্য, আর ফাইল বা sysctl-টি আসলেই আছে
• nice, weight বা CPU-ভাগের যেকোনো সংখ্যা আসল sched_prio_to_weight সারণি থেকে হাতে হিসাব করে মিলিয়েছি
• কোনো পরিবর্তনের আগে-পরে মেপেছি — /proc/PID/sched, cpu.stat, বা নিজের ছোট benchmark — শুধু “ভালো লাগছে” দেখে নয়
• real-time policy (SCHED_FIFO, SCHED_RR) বা sudo শুধু তখনই, যখন প্রয়োজন প্রমাণিত, আর ভুল লুপে কী হবে তা ভেবেছি
• container-এ CPU limit-এর প্রভাব চাপের (load test) মধ্যে দেখেছি, শুধু অলস অবস্থায় নয়; runtime (JVM, Go) কতগুলো CPU দেখছে যাচাই করেছি
• পরামর্শটি Linux-এর না Windows/macOS-এর — নিশ্চিত হয়েছি, আর ডকুমেন্টেশনের সাথে মিলিয়েছি