Linux Scheduler — MLFQ থেকে CFS হয়ে EEVDF পর্যন্ত

আগে এটা বুঝি

গত লেসনের শেষে একটা প্রশ্ন ঝুলিয়ে রেখেছিলাম — একটা video encoder (CPU-bound) আর একটা UI thread (I/O-bound) একসাথে চললে কোনো classic policy-ই দুইজনকে খুশি রাখতে পারে না। দরকার এমন একটা scheduler যেটা প্রতিটা thread-এর সাম্প্রতিক আচরণ পর্যবেক্ষণ করে নিজে থেকে adapt করে।

আজ আমরা দেখব ঠিক এই সমস্যার দুইটা বাস্তব সমাধান — একটা ঐতিহাসিক ধারণা (MLFQ) যা প্রশ্নটার উত্তর দেয় heuristic দিয়ে, আর Linux-এর প্রকৃত সমাধান যা প্রশ্নটাকে সম্পূর্ণ ভিন্নভাবে re-frame করে: “fairness” বলতে ঠিক কী বোঝায় তার একটা নির্ভুল গাণিতিক সংজ্ঞা দিয়ে (CFS), আর তারপর সেই সংজ্ঞাকেই আরও শক্তিশালী করে (EEVDF, ২০২৩-এ Linux 6.6-এ merge হওয়া)। শেষে দেখব ৮ বা ৬৪ core-এ এই পুরো ব্যবস্থা কীভাবে scale করে।

মূল ধারণা

MLFQ — ধারণাটা

Multi-Level Feedback Queue: একাধিক priority queue, প্রতিটার নিজস্ব priority আর quantum। নিয়ম কয়েকটা:

নতুন thread সর্বোচ্চ-priority queue-তে শুরু হয়
একটা thread যদি তার পুরো quantum ব্যবহার করে ফেলে (থামানোর আগে শেষ না করে), তাকে এক ধাপ নিচের queue-তে নামানো হয় — ধরে নেওয়া হয় সে CPU-bound
একটা thread যদি quantum শেষ হওয়ার আগেই নিজে থেকে CPU ছেড়ে দেয় (I/O-র জন্য), তার priority অপরিবর্তিত থাকে — ধরে নেওয়া হয় সে interactive
পর্যায়ক্রমে (কয়েকশ ms পর পর) সবাইকে সর্বোচ্চ-priority queue-তে ফিরিয়ে আনা হয় (boost)

নিয়ম ২-৩ মিলিয়ে MLFQ প্রায় SJF-এর মতো আচরণ করে — যে thread ছোট ছোট burst-এ কাজ করে (তাই কখনো পুরো quantum ব্যবহার করে না) সে উঁচু priority-তে থেকে যায়, দ্রুত সাড়া পায়। যে thread ক্রমাগত চলতেই থাকে সে ধীরে ধীরে নিচে নামে। আর এই সবটাই কোনো future knowledge ছাড়াই — গত লেসনের SJF-এর সবচেয়ে বড় সমস্যা (ভবিষ্যৎ burst জানা লাগে) এখানে নেই, কারণ MLFQ শুধু অতীত আচরণ দেখে সিদ্ধান্ত নেয়।

নিয়ম ৪ কেন লাগে — একটা “gaming” আক্রমণ। একটা malicious বা misbehaving thread একটা কৌশল খেলতে পারে: quantum শেষ হওয়ার ঠিক আগে একটা তুচ্ছ I/O করা (যেমন ১ বাইট পড়া, কিছুই না করে), তারপর আবার কাজে ফেরা। নিয়ম ৩ অনুযায়ী সে “I/O করেছে” ধরে নেওয়া হবে, priority কখনো কমবে না — অথচ বাস্তবে সে প্রায় ১০০% CPU-bound। এভাবে একটা thread চিরকাল সর্বোচ্চ priority ধরে রাখতে পারে, বাকিদের বঞ্চিত করে। Periodic boost এই আক্রমণ নিষ্ক্রিয় করে — যতই গেম খেলুক, একটা নির্দিষ্ট সময় পরপর সবাইকে আবার এক কাতারে আনা হবে, কেউ স্থায়ীভাবে সুবিধা নিতে পারবে না।

MLFQ-র সমস্যা — বড় সংখ্যক 'ম্যাজিক নাম্বার'

কয়টা queue? প্রতিটার quantum কত? Boost interval কত? এই প্রশ্নগুলোর কোনো একক “সঠিক” উত্তর নেই — শুধু experiment-based tuning। ভুল tuning-এ MLFQ-ও গেমযোগ্য বা অন্যায্য হয়ে যেতে পারে। এটাই মূল কারণ Linux ২০০৭-এ (কার্নেল ২.৬.২৩) MLFQ-জাতীয় O(1) scheduler ছেড়ে CFS-এ গিয়েছিল — এমন একটা মডেল খুঁজতে যেখানে “fairness” একটা heuristic না, একটা সংজ্ঞা।

CFS — fairness সংজ্ঞা দিয়ে, heuristic দিয়ে নয়

CFS (Completely Fair Scheduler)-এর কেন্দ্রীয় ধারণা: প্রতিটা priority “র‍্যাংক” রাখার বদলে, প্রতিটা thread-এর জন্য একটা সংখ্যা রাখা হয় — vruntime (virtual runtime) — যা মাপে সে কতটুকু CPU সময় ইতিমধ্যে খেয়েছে, তার নিজের weight দিয়ে normalize করে। নিয়ম একটাই: সবসময় সবচেয়ে কম vruntime-ওয়ালা thread চালাও।

vruntime += সময় চলেছে × (NICE_0_WEIGHT / নিজের weight)

যে thread কম চলেছে, তার vruntime কম, তাই সে আগে সুযোগ পায় — স্বয়ংক্রিয়ভাবে fair, কোনো “কে বেশি deserve করে” heuristic ছাড়াই।

Data structure: red-black tree। Ready thread-গুলো একটা self-balancing binary tree-তে রাখা হয়, vruntime দিয়ে key করে। সবচেয়ে ছোট vruntime-ওয়ালা thread সবসময় সবচেয়ে বাম node — kernel এই pointer cache করে রাখে, তাই পরবর্তী thread বাছা $O(1)$ ; নতুন thread যোগ বা vruntime আপডেটের পর পুনরায় জায়গা করা $O(\log n)$ । ৫০০০ thread-এও গভীরতা মাত্র ~১২, practically তাৎক্ষণিক।

Nice value → weight — সঠিক সংখ্যা

nice value ( $-20$ সবচেয়ে উঁচু priority থেকে $19$ সবচেয়ে নিচু) সরাসরি একটা weight-এ রূপান্তরিত হয়, kernel-এর sched_prio_to_weight[] টেবিল থেকে (kernel/sched/core.c):

nice	weight	nice	weight
-20	88761	1	820
-10	9548	5	335
-5	3121	10	110
-1	1277	15	36
0	1024	19	15

প্রতিটা ধাপে অনুপাত প্রায় $1.25$ । যাচাই করুন: $1277 / 1024 \approx 1.247$ , $88761 / 71755 \approx 1.237$ — টেবিলটা আসলে $1024 \times 1.25^{-\text{nice}}$ -এর একটা integer-রাউন্ড-করা সংস্করণ। এই $1.25$ -এর অর্থ: nice-এ ১ বাড়ালে CPU share প্রায় ২০% (কারণ $1/1.25 = 0.8$ ) কমে যায়।

Weight কীভাবে CPU share ঠিক করে: যদি দুইটা thread A (weight $w_A$ ) আর B (weight $w_B$ ) একটানা runnable থাকে, CFS-এর “সবসময় সবচেয়ে কম vruntime চালাও” নিয়ম তাদের vruntime-কে কাছাকাছি রাখতে বাধ্য করে — আর যেহেতু $\text{vruntime} = \text{সময়} \times (1024/w)$ , vruntime সমান রাখতে হলে:

$n_A \times \frac{1024}{w_A} \approx n_B \times \frac{1024}{w_B} \quad\Rightarrow\quad \frac{n_A}{n_B} \approx \frac{w_A}{w_B}$

যেখানে $n_A, n_B$ হলো তারা কতটুকু প্রকৃত CPU সময় পেয়েছে। অর্থাৎ দীর্ঘমেয়াদে CPU share সরাসরি weight-এর অনুপাতে বণ্টিত হয় — নিচের example-এ এটা সংখ্যা দিয়ে দেখানো হবে।

sched_latency আর min_granularity

CFS-এর দুইটা tunable (pre-6.6 classic মডেল):

sched_latency_ns — একটা “target period” যার মধ্যে প্রতিটা runnable thread অন্তত একবার CPU পাবে বলে লক্ষ্য রাখা হয় (ঐতিহাসিকভাবে প্রায় ৬ms, kernel version-ভেদে বদলেছে)
sched_min_granularity_ns — একটা thread-কে ন্যূনতম কতক্ষণ চালানো হবে তার আগে আবার পুনর্বিবেচনা করা হবে (ঐতিহাসিকভাবে প্রায় ০.৭৫ms)

Runnable thread সংখ্যা কম হলে (ধরুন ≤৮টা), sched_latency_ns-কে সমান ভাগে ভাগ করে প্রতিটা thread তার share পায়। থ্রেড সংখ্যা বেশি হলে (২০টা, ১০০টা), প্রতিটার ভাগ min_granularity-র নিচে নামতে দেওয়া হয় না — তার বদলে period নিজেই বড় হয় (nr_running × min_granularity)। এটাই সেই একই U-curve trade-off যা গত লেসনে RR quantum নিয়ে দেখেছিলাম, শুধু এখানে quantum fixed না, adaptive।

EEVDF — CFS-কে প্রতিস্থাপনকারী (Linux 6.6, ২০২৩)

CFS-এর একটা সূক্ষ্ম দুর্বলতা আছে: নিয়ম শুধু “সবচেয়ে কম vruntime চালাও” — এটা গড়ে fair, কিন্তু কোনো thread-এর জন্য কতক্ষণের মধ্যে সে CPU পাবে তার কোনো bound দেয় না। একটা latency-sensitive thread (অডিও প্রসেসিং, ইন্টার্যাক্টিভ ইনপুট) যদি সবেমাত্র ঘুম থেকে জেগে ওঠে, তার vruntime হয়তো অন্য সবার চেয়ে বেশি (ঘুমিয়ে থাকার সময় সে “জমা” করেনি) — CFS তাকে বহুক্ষণ অপেক্ষা করাতে পারে, গড় fairness ঠিক থাকলেও তাৎক্ষণিক responsiveness নষ্ট হয়।

EEVDF (Earliest Eligible Virtual Deadline First) — মূলত Ion Stoica ও Hussein Abdel-Wahab-এর ১৯৯৫-এর একটা network fair queuing পেপার থেকে, Peter Zijlstra CPU scheduling-এ অভিযোজিত করেছেন — দুইটা ধারণা যোগ করে:

Eligibility (lag) — প্রতিটা thread-এর একটা “lag” মান আছে: সে তার ন্যায্য share-এর তুলনায় কম পেয়েছে (lag ≥ 0, “eligible”) না বেশি পেয়েছে (lag < 0, সাময়িকভাবে “ineligible”, তাকে না ডাকাই ভালো)।
Virtual deadline — eligible thread-গুলোর মধ্যে, প্রতিটার একটা virtual deadline হিসাব করা হয় (মোটাদাগে: vruntime + তার অনুরোধকৃত slice, weight দিয়ে normalize করে)। Scheduler eligible thread-গুলোর মধ্যে সবচেয়ে কাছের deadline-ওয়ালাটা বাছে।

ফলাফল: শুধু “কে কম পেয়েছে গড়ে” না, “কার এখনই পাওয়ার সবচেয়ে জরুরি দরকার” — দুইটা প্রশ্নের যৌথ উত্তর। একটা thread চাইলে sched_setattr()-এ একটা ছোট slice hint দিতে পারে (“আমাকে সংক্ষিপ্ত কিন্তু ঘন ঘন সুযোগ দাও”) — EEVDF সেটা সম্মান করে fairness নষ্ট না করেই, যেখানে CFS-এ এই ধরনের hint-এর কোনো প্রথম-শ্রেণীর জায়গা ছিল না।

Scheduling class — একটা কঠোর হায়ারার্কি

Linux-এ nice value শুধু একটা ক্লাসের (fair) ভেতরের একটা প্যারামিটার। পুরো সিস্টেমে ক্লাসের একটা কঠোর ক্রম আছে, উঁচু থেকে নিচু:

ক্লাস	Policy	কীভাবে schedule হয়
Deadline (সর্বোচ্চ)	`SCHED_DEADLINE`	runtime/deadline/period প্যারামিটার — EDF-ভিত্তিক, হার্ড গ্যারান্টি
Real-time	`SCHED_FIFO`, `SCHED_RR`	static priority ১-৯৯, block/yield না করা পর্যন্ত চলে (FIFO) বা RR quantum-এ ভাগ হয়
Fair	`SCHED_OTHER` (+ `SCHED_BATCH`)	CFS/EEVDF, nice ভিত্তিক weight
Idle (সর্বনিম্ন)	`SCHED_IDLE`	শুধু তখনই চলে যখন literally আর কিছু ready নেই

একটা উঁচু ক্লাসের thread সবসময় নিচু ক্লাসের thread-কে preempt করে, নিচু ক্লাসের priority/nice value যাই হোক না কেন। এটাই গত লেসনের experiment-এর ব্যাখ্যা — chrt -f দিয়ে SCHED_FIFO-তে দেওয়া একটা thread nice -20-এর SCHED_OTHER thread-কেও সম্পূর্ণ starve করতে পারে, কারণ class নিজেই আলাদা স্তরে, nice value তুলনাই অপ্রাসঙ্গিক।

Multi-core — per-CPU runqueue, load balancing, NUMA

এতক্ষণ যা আলোচনা করেছি তা একটা single core-এর ready queue-র জন্য। বাস্তবে প্রতিটা core-এর নিজস্ব runqueue আছে (নিজস্ব red-black tree সহ) — একটা একক গ্লোবাল queue হলে প্রতিটা scheduling decision-এ একটা lock-এর জন্য সব core-কে প্রতিযোগিতা করতে হতো, core সংখ্যা বাড়ার সাথে সাথে এই lock contention-ই bottleneck হয়ে যেত (Level 11-এ lock contention-এর পরিমাপ বিস্তারিত)।

Load balancing পর্যায়ক্রমে (আর কোনো core idle হয়ে গেলে event-চালিত) প্রতিটা core-এর load তুলনা করে, প্রয়োজনে busiest থেকে idlest core-এ thread migrate করে। কিন্তু migration নিজেই বিনামূল্যে না — গত লেসনের context-switching-লেসনের same-core-বনাম-cross-core experiment মনে করুন: migration মানে ঠান্ডা cache-এ নতুন করে শুরু করা।

Scheduling domains — hardware topology-র একটা hierarchy (SMT sibling → একই physical core → একই L3/LLC group → একই NUMA node → পুরো মেশিন)। কাছের domain-এ (SMT sibling, একই cache) migration সস্তা, তাই আগ্রহের সাথে balance করা হয়; দূরের domain-এ (আলাদা NUMA node) migration ব্যয়বহুল, তাই আরও রক্ষণশীলভাবে, কম ঘনঘন।

NUMA awareness — একটা thread-এর memory সাধারণত একটা নির্দিষ্ট NUMA node-এ থাকে। সেই node থেকে দূরে migrate করলে প্রতিটা memory access ধীর হয়ে যায় (remote NUMA access, স্থানীয় access-এর চেয়ে কয়েকগুণ বেশি latency)। Automatic NUMA balancing (kernel-এর numa_balancing সুবিধা) periodic page fault sampling দিয়ে বুঝতে চেষ্টা করে thread কোন node-এর memory বেশি ব্যবহার করছে, তারপর হয় thread-কে সেই node-এর কাছে নেয়, নয়তো page-গুলোকে thread-এর কাছাকাছি নেয়।

ভেতরে কী ঘটছে

pick_next_task() ভেতরে কী ঘটে

গত লেসনের pick_next()-এর abstract স্বাক্ষরটা মনে করুন — এখন দেখি CFS/EEVDF-এ এর ভেতরটা ঠিক কেমন।

একটা scheduling tick-এ CFS/EEVDF-এর সিদ্ধান্ত

Timer tick → update_curr()বর্তমান thread যে সময় চলল, তার vruntime-এ যোগ হয় (weight দিয়ে normalize করে)
পুনর্বিবেচনার প্রয়োজন?min_granularity পার হয়েছে, আর অন্য কারো vruntime/deadline এখন এগিয়ে?
যদি হ্যাঁ: বর্তমান thread-কে tree-তে reinsertতার নতুন vruntime অনুযায়ী নতুন জায়গায় (O(log n))
pick_next: leftmost cache থেকে পড়া (CFS)অথবা eligible thread-দের মধ্যে earliest deadline (EEVDF)
সেই thread-কে tree থেকে সরানোএখন সে "current", আর তার জন্য tree-তে জায়গা নেই যতক্ষণ সে চলছে
switch_to() কলগত লেসনের mechanism — এখান থেকেই এগিয়ে যায়

Pseudocode হিসেবে:

NICE0_WEIGHT = 1024

def update_curr(task, delta_exec):
    task.vruntime += delta_exec * (NICE0_WEIGHT / task.weight)
    rbtree.reinsert(task)     # নতুন vruntime অনুযায়ী পুনরায় জায়গা

def pick_next_cfs():
    return rbtree.leftmost()   # cached — O(1)

def pick_next_eevdf(tasks):
    eligible = [t for t in tasks if t.lag >= 0]
    return min(eligible, key=lambda t: t.virtual_deadline)

লক্ষ্য করুন pick_next_eevdf-এ প্রথমে eligible দিয়ে filter করা হচ্ছে, তারপর তাদের মধ্যে deadline দিয়ে বাছা — এই দুই-ধাপের সিদ্ধান্তই CFS-এর এক-ধাপের (min(vruntime)) চেয়ে আলাদা।

উদাহরণ

দুইটা CPU-bound thread: A (nice 0, weight $1024$ ) আর B (nice 5, weight $335$ )। CFS-এর নিয়ম প্রয়োগ করে, প্রতিটা “tick” ( $1$ ms ধরে সরলীকরণের জন্য) সেই thread চালাই যার vruntime কম:

$\Delta v_A = 1 \times \frac{1024}{1024} = 1.000 \qquad \Delta v_B = 1 \times \frac{1024}{335} = 3.057$

Pick #	কে চলল	$v_A$	$v_B$
1	A	1.000	0.000
2	B	1.000	3.057
3	A	2.000	3.057
4	A	3.000	3.057
5	A	4.000	3.057
6	B	4.000	6.113
7	A	5.000	6.113
8	A	6.000	6.113
9	A	7.000	6.113
10	B	7.000	9.170

প্যাটার্ন স্পষ্ট: A B A A A B A A A B ... — প্রতি ৪টা pick-এ A প্রায় ৩ বার, B প্রায় ১ বার। এই ১০ pick-এ A=৭ বার, B=৩ বার (অনুপাত ২.৩৩) — এখনো ছোট নমুনা। একটা প্রোগ্রামে ২০০০ pick পর্যন্ত চালিয়ে দেখা যায়:

৪০ pick পরে:    A=30  B=10   অনুপাত = 3.000
২০০০ pick পরে:  A=1507 B=493  অনুপাত = 3.0568

আর তত্ত্ব যা predict করে:

$\frac{w_A}{w_B} = \frac{1024}{335} = 3.0567\ldots$

দীর্ঘমেয়াদে পরিমাপ আর তত্ত্ব ব্যবহারিকভাবে অভিন্ন (৩.০৫৬৮ বনাম ৩.০৫৬৭ — পার্থক্য rounding-এর মধ্যে)। আর $1.25^5 = 3.0518$ -ও প্রায় একই — সামান্য পার্থক্য কারণ kernel-এর weight table $1.25^{-\text{nice}}$ -এর একটা integer-এ রাউন্ড করা সংস্করণ, গাণিতিকভাবে নিখুঁত না।

নিজে চালিয়ে দেখুন

EXPERIMENT

/proc/sched_debug আর তাত্ত্বিক weight-ratio মেলানো

Linux· ১৫ মিনিট

sudo cat /proc/sched_debug | head -40

সাধারণ ফলাফল (অংশ, kernel version-ভেদে ফরম্যাট কিছুটা আলাদা হতে পারে):

cpu#0
  .nr_running                    : 2
  .clock                         : 8234891023.451234
cfs_rq[0]:/
  .exec_clock                    : 4123.556677
  .min_vruntime                  : 891234.567891
  .nr_running                    : 2
            task   PID         tree-key  switches  prio     wait-time
R           busyA  20142       891235.2       412   120      0.000000
            busyB  20143       891237.8        89   125      3.451234

tree-key কলামটাই vruntime — লক্ষ্য করুন দুইটা thread-এর vruntime একে অপরের কাছাকাছি থাকে (fairness-এর প্রমাণ, এলোমেলো দূরত্বে না)। switches কলাম বলছে nice কম (উঁচু priority) thread-টা বেশিবার schedule হয়েছে, প্রতিবার অল্প সময় (তার effective slice ছোট, কারণ বেশি thread ভাগ করে নিচ্ছে)।

এবার তাত্ত্বিক অনুপাতের সাথে বাস্তব মাপা মেলান:

taskset -c 0 nice -n 0  python3 -c "
while True: pass
" &
PID_A=$!
taskset -c 0 nice -n 5  python3 -c "
while True: pass
" &
PID_B=$!

sleep 20
awk '{print $14, $15}' /proc/$PID_A/stat   # utime stime (ticks)
awk '{print $14, $15}' /proc/$PID_B/stat
kill $PID_A $PID_B

সাধারণ ফলাফল (utime টিক-এ, SC_CLK_TCK সাধারণত ১০০/সেকেন্ড):

A (nice 0): 1490 12
B (nice 5): 487  9
অনুপাত (utime): 1490/487 = 3.06
তাত্ত্বিক (weight): 1024/335 = 3.057

২০ সেকেন্ডের real measurement আর তত্ত্ব ১%-এর কম পার্থক্যে মিলছে — এটাই এই লেসনের কেন্দ্রীয় দাবির সরাসরি প্রমাণ।

এটা কী প্রমাণ করে

উপরের হাতে-করা vruntime trace বাস্তব kernel-এও একই আচরণ দেখায় — এটা তত্ত্ব না, প্রতিটা মেশিনে যাচাইযোগ্য।

EXPERIMENT

chrt দিয়ে SCHED_FIFO-র SCHED_OTHER-কে সম্পূর্ণ starve করা

Linux· ১০ মিনিট

# nice -20 (সর্বোচ্চ nice-priority) SCHED_OTHER thread
taskset -c 0 nice -n -20 python3 -c "
import time
count = 0
start = time.time()
while time.time() - start < 5:
    count += 1
print('SCHED_OTHER iterations:', count)
" &

sleep 0.5

# SCHED_FIFO priority মাত্র ১০ — কিন্তু আলাদা, উঁচু ক্লাস
sudo timeout 5 chrt -f 10 taskset -c 0 python3 -c "
import time
count = 0
start = time.time()
while time.time() - start < 4:
    count += 1
print('SCHED_FIFO iterations:', count)
"

wait

সাধারণ ফলাফল:

SCHED_FIFO iterations: 48213891
SCHED_OTHER iterations: 312

nice -20 (সর্বোচ্চ সম্ভাব্য SCHED_OTHER priority) তারপরও প্রায় কিছুই পায়নি — কারণ SCHED_FIFO সম্পূর্ণ ভিন্ন, উঁচু ক্লাসে বসে। SCHED_FIFO priority 10 বনাম SCHED_OTHER nice -20 — এই তুলনাটাই অর্থহীন, দুইজন ভিন্ন খেলার মাঠে। এটাই এই লেসনের scheduling-class hierarchy অংশের সরাসরি বাস্তব প্রমাণ।

এটা কী প্রমাণ করে

Scheduling class হায়ারার্কি nice value-কে সম্পূর্ণ irrelevant করে দেয় — এটা তাত্ত্বিক দাবি না, নিজের চোখে দেখা যায় (সতর্কতার সাথে)।

নিজে বানান

BUILD IT

Nice level জুড়ে achieved CPU share মাপা — তাত্ত্বিক weight-এর বিপরীতে

Python · ●●●●○

N টা child process spawn করুন, প্রতিটা ভিন্ন nice value-তে (-10, -5, 0, 5, 10), সবাইকে একই core-এ taskset দিয়ে বাঁধুন
একটা fixed সময় (২০-৩০ সেকেন্ড) সবাইকে একসাথে busy-loop চালান
/proc/[pid]/stat থেকে utime+stime পড়ে প্রতিটার প্রকৃত CPU সময় বের করুন
sched_prio_to_weight টেবিল থেকে প্রতিটার তাত্ত্বিক share হিসাব করুন, আর বাস্তবের সাথে একটা টেবিলে তুলনা করুন

#!/usr/bin/env python3
import os, sys, time, signal

WEIGHT = {
    -10: 9548, -5: 3121, 0: 1024, 5: 335, 10: 110,
}
DURATION = 20  # সেকেন্ড

def child(nice_val):
    os.nice(nice_val)
    os.sched_setaffinity(0, {0})       # সবাইকে core 0-তে বাঁধা
    end = time.time() + DURATION
    while time.time() < end:
        pass
    os._exit(0)

def read_cpu_ticks(pid):
    with open(f"/proc/{pid}/stat") as f:
        fields = f.read().split()
    utime, stime = int(fields[13]), int(fields[14])
    return utime + stime

def main():
    nice_values = [-10, -5, 0, 5, 10]
    pids = []
    for nv in nice_values:
        pid = os.fork()
        if pid == 0:
            child(nv)
        pids.append(pid)

    time.sleep(DURATION + 1)
    ticks = {}
    for nv, pid in zip(nice_values, pids):
        try:
            ticks[nv] = read_cpu_ticks(pid)
        except FileNotFoundError:
            ticks[nv] = 0
        os.waitpid(pid, 0)

    total_ticks = sum(ticks.values())
    total_weight = sum(WEIGHT[nv] for nv in nice_values)

    print(f"{'nice':>6}{'weight':>10}{'তাত্ত্বিক %':>14}{'measured %':>14}")
    for nv in nice_values:
        theoretical_pct = 100 * WEIGHT[nv] / total_weight
        measured_pct = 100 * ticks[nv] / total_ticks if total_ticks else 0
        print(f"{nv:>6}{WEIGHT[nv]:>10}{theoretical_pct:>13.2f}%{measured_pct:>13.2f}%")

if __name__ == "__main__":
    main()

sudo python3 nice_share.py    # os.sched_setaffinity-এ কিছু সিস্টেমে root লাগতে পারে

প্রত্যাশিত আউটপুট (weight-অনুপাত অনুযায়ী):

  nice    weight   তাত্ত্বিক %   measured %
   -10      9548        67.34%       66.91%
    -5      3121        22.02%       22.58%
     0      1024         7.23%        7.19%
     5       335         2.36%        2.31%
    10       110         0.78%        0.81%

তাত্ত্বিক আর measured column প্রায় হুবহু মিলবে — কিছু শতাংশ-বিন্দু পার্থক্য থাকতে পারে scheduling noise, migration, আর অন্য system process-এর কারণে।

নিজে বাড়ান

Core সংখ্যা ২, ৪-এ বাড়িয়ে দেখুন — multi-core-এ load balancing কীভাবে এই অনুপাতকে প্রভাবিত করে (বা করে না) তুলনা করুন
একটা SCHED_FIFO thread যোগ করুন মাঝপথে ৫ সেকেন্ডের জন্য — বাকি সবার measured % কীভাবে সাময়িকভাবে শূন্যের কাছে নেমে যায় দেখান
EEVDF-এর slice hint ব্যবহার করুন (sched_setattr দিয়ে, python3-perf/ctypes লাগবে raw syscall-এর জন্য) — একটা ছোট slice-request thread-এর response latency কীভাবে কমে তা মাপুন

সম্পূর্ণ, আরও গভীর সংস্করণের জন্য (multi-core simulation, MLFQ-র সরলীকৃত মডেল, real Linux ফলাফলের সাথে হুবহু মেলানো) — Level 4-এর Scheduler Simulator প্রজেক্ট দেখুন (/projects/scheduler-simulator), যার একটা milestone সরাসরি এই CFS/vruntime পরীক্ষাটাই বলে।

বাস্তব সিস্টেমে

Fairness model যেখানে সরাসরি প্রভাব ফেলে

macOS/XNU-র QoS class। Apple-এর scheduler nice value-র বদলে Quality-of-Service tier ব্যবহার করে — User Interactive, User Initiated, Utility, Background — প্রতিটা আলাদা scheduling আচরণ পায় (thread priority range, throttling)। Concept একই (কে বেশি জরুরি তার হিসাব রাখা), বাস্তবায়ন আলাদা।

Android-এর Energy Aware Scheduling (EAS)। Linux CFS-এর উপর ভিত্তি করে, কিন্তু মোবাইলের জন্য একটা বাড়তি মাত্রা যোগ করে — কোন core-এ (big বা LITTLE, ARM big.LITTLE architecture-এ) একটা thread চালালে battery সবচেয়ে কম খরচ হবে সেটাও বিবেচনা করে load balancing decision-এ, শুধু fairness না, energy efficiency-ও।

cgroups CPU controller — containers-এর ভিত্তি। Docker/Kubernetes-এর cpu.weight (cgroup v2) বা cpu.shares (v1) সরাসরি একই underlying mechanism ব্যবহার করে — প্রতিটা cgroup নিজেই একটা “nested” scheduling entity, তার নিজস্ব vruntime নিয়ে একটা group-level red-black tree-তে প্রতিদ্বন্দ্বিতা করে। একটা Kubernetes pod-এর resources.requests.cpu শেষ পর্যন্ত এই একই weight-ভিত্তিক ব্যবস্থায় রূপান্তরিত হয় (Level 12-এ বিস্তারিত)। Hard limit-এর জন্য আলাদা mechanism আছে — cpu.max/cfs_quota_us — যা একটা group-কে একটা period-এ নির্দিষ্ট সময়ের বেশি চলতেই দেয় না, weight-based fairness-এর বাইরে একটা সম্পূর্ণ আলাদা, hard ceiling।

Pro-audio-তে SCHED_FIFO-র বাস্তব ব্যবহার। JACK আর PipeWire-এর মতো real-time audio server তাদের প্রসেসিং thread-কে SCHED_FIFO priority দেয় (সাধারণত chrt -f দিয়ে বা সরাসরি pthread_setschedparam()), কারণ একটা audio buffer underrun (কয়েক ms দেরি) সরাসরি শ্রুতিগোচর glitch তৈরি করে — এখানে “গড়ে fair” যথেষ্ট না, hard deterministic priority দরকার, ঠিক এই লেসনের class-hierarchy অংশের বাস্তব প্রয়োগ।

Real-time embedded-এ SCHED_DEADLINE। অটোমোটিভ ও robotics কন্ট্রোল লুপ (নির্দিষ্ট period-এ চালানো লাগবে, কখনো miss করা যাবে না) SCHED_DEADLINE ব্যবহার করে — runtime/deadline/period তিনটা প্যারামিটার দিয়ে kernel-কে সরাসরি বলে দেওয়া হয় ঠিক কতটুকু CPU, কত ঘনঘন লাগবে, আর kernel admission-control করে নিশ্চিত করে সব deadline-thread একসাথে মিলিয়ে schedulable কি না — এই লেসনের class hierarchy-তে সবচেয়ে উঁচুতে থাকার কারণ এটাই।

যে ভুলগুলো সবাই করে

“CFS/EEVDF সম্পূর্ণ heuristic-মুক্ত — pure গণিত, কোনো tuning লাগে না।”

আংশিক সত্য। vruntime-এর সংজ্ঞা আর “কম vruntime আগে” নিয়মটা গাণিতিকভাবে নির্ভুল, ঠিক। কিন্তু sched_latency_ns, min_granularity_ns, আর নিজেই সেই weight table ( $1.25$ -এর অনুপাত) — এগুলো সবই ডিজাইন সিদ্ধান্ত, empirically tune করা। $1.25$ কেন, $1.3$ বা $1.2$ কেন না? উত্তর: kernel developer-রা পরীক্ষা করে দেখেছেন $1.25$ nice value-র “অনুভূতিগত” পার্থক্য (প্রতিটা ধাপ স্পষ্ট প্রভাব ফেলে, কিন্তু চরম না) আর ব্যবহারিক CPU-allocation দুইটাতেই ভালো ভারসাম্য দেয়।

EEVDF-ও তাই — eligibility ও deadline-এর সংজ্ঞা গাণিতিকভাবে নিখুঁত হলেও, “slice length” hint কতটা বিশ্বাস করা হবে, কত ঘনঘন eligibility পুনর্গণনা হবে — এসবই বাস্তবায়ন-নির্ভর tuning। “গাণিতিক ভিত্তি” আর “tuning-মুক্ত” এক জিনিস না।

“Nice value সরাসরি একটা 'শতাংশ' CPU বরাদ্দ করে (nice -10 মানে ৫০%)।”

Nice value একটা relative weight, কোনো absolute শতাংশ না। Example-এ দেখেছি nice 0 বনাম nice 5-এ অনুপাত ~3.06 — কিন্তু এই অনুপাত থেকে “কে কত শতাংশ পাবে” নির্ভর করে আর কে কে একই সময়ে runnable তার উপর।

যদি একটা মেশিনে শুধু একটা nice 10 thread একা চলে (আর কেউ competing না), সে ১০০% CPU পাবে, নিজের nice value যাই হোক না কেন — কারণ CFS শুধু runnable thread-দের মধ্যে আপেক্ষিক ভাগ করে, absolute allocation না। উপরের build-এর টেবিলে “measured %” প্রতিটা thread-এর নিজস্ব শতাংশ না — এটা সেই মুহূর্তে প্রতিদ্বন্দ্বী সবার মধ্যে আপেক্ষিক ভাগ, যা অন্য process যোগ/বিয়োগ হলেই বদলে যাবে।

Absolute upper bound চাইলে nice যথেষ্ট না — cpu.max (cgroup) বা SCHED_DEADLINE-এর মতো hard-limiting mechanism লাগবে।

“SCHED_FIFO priority আসলে nice-এর মতোই, শুধু একটু বেশি জোরালো।”

সম্পূর্ণ ভুল একটা মানসিক মডেল। SCHED_FIFO/SCHED_RR-এর priority (১-৯৯) আর SCHED_OTHER-এর nice value সম্পূর্ণ আলাদা স্কেলে, তুলনাই অর্থহীন — এরা ভিন্ন class-এ বাস করে, আর class hierarchy nice value-কে সম্পূর্ণ irrelevant করে দেয়।

SCHED_FIFO priority 1 (real-time class-এর সবচেয়ে নিচু) এখনও SCHED_OTHER nice -20-কে (fair class-এর সবচেয়ে উঁচু) preempt করবে, প্রতিবার, নিঃশর্তে। এই লেসনের chrt experiment এটা সরাসরি দেখিয়েছে — nice -20 thread ৩১২টা iteration পেয়েছে, SCHED_FIFO priority 10 পেয়েছে ৪৮ মিলিয়নের বেশি।

ব্যবহারিক পরিণতি: SCHED_FIFO/SCHED_RR ব্যবহার একটা গুরুতর সিদ্ধান্ত — ভুলভাবে লেখা একটা real-time thread (যেমন একটা bug-এ আটকে যাওয়া infinite loop) আক্ষরিক অর্থে পুরো CPU-কে বাকি সবার কাছ থেকে অনির্দিষ্টকাল কেড়ে নিতে পারে, এমনকি root-এর ssh session-ও অসাড় করে দিতে পারে single-core সিস্টেমে।

“Load balancing সবসময় সব core-এর load তাৎক্ষণিক ও নিখুঁতভাবে সমান করে দেয়।”

Load balancing ইচ্ছাকৃতভাবে তাৎক্ষণিক নয়, আর নিখুঁতও না — এটা একটা সচেতন trade-off।

Migration-এর নিজস্ব খরচ আছে (context-switching লেসনের same-core বনাম cross-core experiment মনে করুন — cache locality হারানো)। তাই kernel migration-কে ঘন ঘন trigger করে না; সাধারণত periodic (প্রতি কয়েক ms) আর event-driven (core idle হলে) চেক করে, আর migration তখনই করে যখন imbalance একটা threshold ছাড়ায় (তুচ্ছ imbalance উপেক্ষা করা হয়, কারণ ঠিক করার খরচ লাভের চেয়ে বেশি হতে পারে)।

NUMA-তে এই রক্ষণশীলতা আরও প্রকট — একটা thread-কে দূরের NUMA node-এ সরানো মানে সম্ভবত তার memory access latency বহুগুণ বাড়া, তাই সেখানে balance-এর বার সহনশীলতা আরও বেশি রাখা হয়। ফলে /proc/sched_debug-এ প্রতিটা core-এর nr_running কখনো সম্পূর্ণ সমান দেখাবে না — সামান্য অসাম্যই স্বাভাবিক, বাগ না।

বুঝেছেন কি না দেখুন

EEVDF কেন শুধু “সবচেয়ে কাছের virtual deadline” দিয়ে thread বাছে না — কেন প্রথমে “eligibility” (lag ≥ 0) দিয়ে ফিল্টার করা আবশ্যক?

যুক্তি

কারণ শুধু deadline দিয়ে বাছলে সিস্টেমটা “গেমযোগ্য” হয়ে যায় — একটা thread ক্রমাগত ছোট deadline-request পাঠিয়ে তার ন্যায্য share-এর চেয়ে বেশি CPU দখল করতে পারবে।

কল্পনা করুন eligibility ছাড়া শুধু “earliest deadline first” নিয়ম। একটা thread যদি প্রতিবার খুব ছোট একটা slice request করে (virtual deadline সবসময় কাছেই থাকবে), সে বারবার scheduler-এর পছন্দের তালিকায় সবার আগে থাকবে — এমনকি সে ইতিমধ্যে তার fair share-এর চেয়ে অনেক বেশি CPU খেয়ে ফেললেও। এটা ঠিক গত লেসনের MLFQ-র “gaming” আক্রমণের মতোই একটা দুর্বলতা, শুধু ভিন্ন প্রক্রিয়ায়।

Eligibility এই দুর্বলতা বন্ধ করে। lag মান ট্র্যাক করে — একটা thread তার আদর্শ (ideal, weight-অনুপাতে) share-এর তুলনায় কতটা কম বা বেশি পেয়েছে। যদি একটা thread ইতিমধ্যে বেশি পেয়ে থাকে (lag < 0), সে ineligible — যতই কাছের deadline request করুক, scheduler তাকে বিবেচনাই করবে না যতক্ষণ না তার lag আবার non-negative হয়।

ফলাফল — দুইটা ভিন্ন গ্যারান্টির সংযুক্তি:

শুধু deadline (EDF-এর মতো)	শুধু fairness (CFS-এর মতো)	EEVDF (দুটোই)
Latency bound দেয়, কিন্তু গেমযোগ্য	দীর্ঘমেয়াদে fair, কিন্তু tail-latency bound নেই	Fair এবং bounded latency

এই “দুই ধাপের ফিল্টার” (প্রথমে যোগ্যতা যাচাই, তারপর সেই যোগ্যদের মধ্যে জরুরি-তার ক্রম) একটা সাধারণ প্যাটার্ন — Level 6 (Algorithms)-এ scheduling ও resource-allocation প্রমাণে বারবার দেখবেন: single-criterion greedy প্রায়ই গেমযোগ্য বা suboptimal, দুই-ধাপের constraint-then-optimize প্রায়ই মজবুত গ্যারান্টি দেয়।

তিনটা thread একসাথে runnable: nice -5, nice 0, nice 10। weight table থেকে প্রতিটার CPU share (শতাংশে) হিসাব করুন।

প্রয়োগ

weight table থেকে মান নেওয়া:

nice	weight
-5	3121
0	1024
10	110

মোট weight:

$w_{total} = 3121 + 1024 + 110 = 4255$

প্রতিটার শতাংশ ভাগ:

$\text{nice}{-5}: \frac{3121}{4255} \times 100 \approx 73.37\%$

$\text{nice}\ 0: \frac{1024}{4255} \times 100 \approx 24.07\%$

$\text{nice}\ 10: \frac{110}{4255} \times 100 \approx 2.59\%$

যাচাই: $73.37 + 24.07 + 2.59 = 100.03\%$ (rounding-এর কারণে সামান্য পার্থক্য, প্রত্যাশিত)।

পর্যবেক্ষণ: nice -5 thread একাই CPU-র প্রায় তিন-চতুর্থাংশ পাচ্ছে, যদিও তার nice value শুধু ৫ ধাপ কম বাকি দুইজনের তুলনায়। এটাই সেই exponential ( $1.25^{\Delta}$ ) প্রকৃতির প্রভাব — nice value-র ছোট পার্থক্যও দ্রুত বড় CPU-share পার্থক্যে রূপান্তরিত হয়। এই কারণেই প্রায় সব ব্যবহারিক ক্ষেত্রে nice value $-5$ থেকে $+5$ -এর বাইরে খুব কমই ব্যবহৃত হয় — চরম মান দ্রুত এক thread-এর কার্যত পুরো CPU দখল করার মতো পরিস্থিতি তৈরি করে, ঠিক গত অনুচ্ছেদের misconception-এ যেমন দেখানো হয়েছে।

Level 11-এ (Performance Engineering) আমরা perf sched দিয়ে এই ধরনের CPU-share বণ্টন বাস্তব production workload-এ সরাসরি পরিমাপ করব, শুধু hand-calculation না।

একটা media-processing অ্যাপ্লিকেশনে একটা অডিও thread (latency-sensitive, প্রতি ১০ms-এ অন্তত একবার অল্প সময়ের জন্য চলা লাগবে, নাহলে শ্রুতিগোচর glitch) আর একটা ভিডিও এনকোডিং thread (throughput-মুখ্য, দীর্ঘ burst) একসাথে চলছে। CFS-এ মাঝেমধ্যে অডিও glitch দেখা যাচ্ছিল। আপনি কী পরিবর্তন বিবেচনা করবেন — EEVDF-এর slice hint, নাকি SCHED_FIFO? দুটোর trade-off কী?

ডিজাইন

দুইটাই সম্ভাব্য সমাধান, কিন্তু ঝুঁকি ও গ্যারান্টির মাত্রা সম্পূর্ণ ভিন্ন — সিদ্ধান্তটা নির্ভর করে কতটা “hard” গ্যারান্টি দরকার তার উপর।

বিকল্প ১ — EEVDF slice hint (একই fair class-এ থেকে)।

অডিও thread-কে sched_setattr()-এ একটা ছোট sched_runtime (slice length) request দিতে বলা — এটা তাকে বলছে “আমার ঘন ঘন, কিন্তু সংক্ষিপ্ত সুযোগ দরকার”। EEVDF-এর eligibility + deadline মডেল এই request-কে সম্মান করবে fairness নষ্ট না করেই — অডিও thread তার ন্যায্য share-এর বেশি নেবে না, কিন্তু সেই share-টা ঘন ঘন ছোট ছোট টুকরায় পাবে, যা তার latency-প্রয়োজনের সাথে মেলে।

সুবিধা: কোনো hard গ্যারান্টি ভাঙে না, বাকি সিস্টেমের fairness অক্ষত, ভুল হলে (bug থাকলে) worst-case এখনও bounded
সীমাবদ্ধতা: এটা এখনও একটা best-effort hint, একটা নিশ্চয়তা না — চরম system load-এ (অনেক অন্য high-priority process) তবুও দেরি হতে পারে

বিকল্প ২ — SCHED_FIFO/SCHED_RR (real-time class-এ তুলে নেওয়া)।

অডিও thread-কে chrt-এর মতো real-time priority দেওয়া — এখন সে fair class-এর উপরে, CFS/EEVDF-এর কোনো fairness হিসাবই তাকে প্রভাবিত করে না, ভিডিও এনকোডার (fair class) তাকে কখনোই preempt করতে পারবে না।

সুবিধা: সবচেয়ে শক্তিশালী গ্যারান্টি — deterministic, latency bound প্রায় নিশ্চিত (যদি thread নিজে ভালোভাবে লেখা হয়)
ঝুঁকি: যদি অডিও thread-এ কোনো bug থাকে (infinite loop, বা লক নিয়ে বসে থাকা), সে পুরো CPU-কে অনির্দিষ্টকাল আটকে রাখতে পারে, এই লেসনের chrt experiment-এ যেমন দেখানো হয়েছে — একটা misbehaving real-time thread পুরো সিস্টেমকে অসাড় করে দিতে পারে

সুপারিশ: প্রথমে EEVDF slice hint চেষ্টা করা — এটা কম ঝুঁকির, আর বাস্তবে বেশিরভাগ audio glitch সমস্যার জন্য যথেষ্ট (glitch সাধারণত occasional scheduling delay-র জন্য হয়, পুরোপুরি অভাবের জন্য না)। যদি এরপরও glitch থেকে যায় (মানে সমস্যাটা fairness-এর না, সত্যিকারের hard real-time প্রয়োজনীয়তার), তবেই SCHED_FIFO-তে যাওয়া — সাথে খুব সতর্কভাবে code review করে নিশ্চিত করা thread-টা কখনো unbounded loop-এ পড়বে না, আর সম্ভব হলে একটা watchdog রাখা (Mars Pathfinder-এর মতোই, যদি কখনো hang হয়ে যায়)।

Level 9 (Distributed Systems)-এ আমরা এই একই “best-effort বনাম hard-guarantee” প্রশ্ন আরও বড় স্কেলে দেখব — একটা distributed media-streaming pipeline-এ কোন কম্পোনেন্টকে কতটা resource isolation দেওয়া উচিত, একই মৌলিক trade-off, ভিন্ন স্তরে।

আপনার build (nice-share পরিমাপক)-এ ২০ সেকেন্ড চালিয়ে দেখলেন nice 0 thread ১৪২০ tick, আর nice 5 thread ৫২০ tick পেয়েছে (মোট ২০০০ tick-এর মধ্যে অন্য কিছু process-ও কিছু নিয়েছে)। তাত্ত্বিক অনুপাত ৩.০৫৭ প্রত্যাশিত ছিল, কিন্তু পরিমাপ দেখাচ্ছে $1420/520 = 2.73$ । এই বিচ্যুতির সম্ভাব্য কারণ কী, আর কীভাবে যাচাই করবেন?

প্রয়োগ

বিচ্যুতির তিনটা প্রধান সম্ভাব্য উৎস:

১. তৃতীয় কোনো process প্রতিযোগিতায় ছিল। যদি core 0-এ শুধু এই দুইটা thread না থেকে অন্য কোনো system process (এমনকি একটা সংক্ষিপ্ত cron job, বা measurement script নিজেই) মাঝেমধ্যে CPU নিয়ে থাকে, দুই thread-এর আপেক্ষিক অনুপাত বিকৃত হবে না (কারণ CFS আপেক্ষিক ভাগ করে) — কিন্তু যদি তৃতীয় process-টা শুধু একজনের সাথে বেশি সময় সহাবস্থান করে (যেমন timing-এর কাকতালে), তাহলে অনুপাত সাময়িকভাবে বিকৃত হতে পারে।

# পরীক্ষা: measurement windowe আর কেউ core 0-এ ছিল কিনা
taskset -c 0 ps -eLo pid,psr,comm | grep -v grep

২. Measurement window খুব ছোট। Example section-এ দেখেছি — ১০ pick-এ অনুপাত ছিল ২.৩৩, ৪০ pick-এ ৩.০০, ২০০০ pick-এ ৩.০৫৬৮। ছোট window-এ শুরু আর শেষের “warm-up” transient (কে প্রথমে চলে, tie-breaking) সামগ্রিক অনুপাতকে টেনে ধরে। ২০ সেকেন্ড আসলে হাজার হাজার scheduling decision ধরে রাখা উচিত, তাই এটা একা সম্পূর্ণ ব্যাখ্যা না, তবে অবদান রাখতে পারে যদি thread দুটো বারবার block/wake হয়ে থাকে (pure busy-loop না হয়ে)।

৩. Migration ঘটে থাকতে পারে, taskset সত্ত্বেও। যদি sched_setaffinity/taskset সঠিকভাবে প্রয়োগ না হয় (কোনো syscall ব্যর্থ হয়ে চুপচাপ উপেক্ষা করে থাকতে পারে), thread দুটো আলাদা core-এ চলে যেতে পারে, যেখানে তারা আর সরাসরি প্রতিদ্বন্দ্বী না — প্রতিটাই প্রায় একা একটা core পাবে, অনুপাত ১-এর কাছাকাছি টানবে, ৩.০৫৭-এর চেয়ে অনেক কম।

# পরীক্ষা: থ্রেড দুটো সত্যিই একই core-এ ছিল কিনা
grep Cpus_allowed_list /proc/$PID_A/status /proc/$PID_B/status
ps -o pid,psr -p $PID_A,$PID_B    # PSR কলাম = প্রকৃত core

নির্ণয়ের ক্রম: প্রথমে PSR (processor) কলাম চেক করে নিশ্চিত করুন দুইজনেই core 0-এ ছিল সারাক্ষণ (কারণ ৩ সবচেয়ে মৌলিক ভুল)। তারপর top -H-এ measurement window-এ core 0-এ আর কে ছিল দেখুন। যদি দুটোই পরিষ্কার আসে, তাহলে window দীর্ঘ করে (৬০+ সেকেন্ড) পুনরায় মাপুন — transient effect দীর্ঘ window-এ গড়ে মিলিয়ে যাওয়া উচিত, আর অনুপাত ৩.০৫৭-এর কাছাকাছি চলে আসা উচিত।

কেন per-CPU runqueue + scheduling domain-ভিত্তিক load balancing একটা একক global runqueue-র চেয়ে বেশি core-এ ভালো scale করে?

যুক্তি

মূল কারণ: একক global runqueue মানে প্রতিটা scheduling decision-এই একটা shared lock-এর জন্য প্রতিযোগিতা, যা core সংখ্যা বাড়ার সাথে সাথে exponentially খারাপ হয়।

কল্পনা করুন একটা single global runqueue, একটা lock দিয়ে সুরক্ষিত। প্রতিটা core-এর প্রতিটা scheduling tick-এ (প্রতি কয়েক ms-এ, প্রতিটা core-এই আলাদাভাবে) সেই একই lock নিতে হবে — thread বাছতে, আপডেট করতে, ছাড়তে। ৪ core-এ এটা হয়তো সহনীয়, কিন্তু ৬৪ বা ২৫৬ core-এর একটা server-এ সব core একই cache line-এর (lock variable) জন্য ক্রমাগত প্রতিদ্বন্দ্বিতা করবে — এই ধরনের contention-এ প্রতিটা lock acquire cache-coherence traffic তৈরি করে (Level 11-এ বিস্তারিত), আর scheduling নিজেই সিস্টেমের bottleneck হয়ে যায়, যেই কাজের জন্য scheduling করা হচ্ছিল সেটার বদলে।

Per-CPU runqueue এই contention সম্পূর্ণ দূর করে সাধারণ ক্ষেত্রে। প্রতিটা core নিজের runqueue-তে lock ছাড়াই (বা শুধু নিজের সাথে প্রতিদ্বন্দ্বিতা করে এমন একটা lock দিয়ে) কাজ করে — অন্য core-এর সাথে কোনো লেনদেন লাগে না normal scheduling-এ। শুধু load balancing-এর সময় দুইটা core-এর runqueue একসাথে touch করা লাগে, আর সেটাও ইচ্ছাকৃতভাবে বিরল (periodic, threshold-ভিত্তিক, উপরে misconception-এ আলোচিত)।

Scheduling domains এই ধারণাকে hardware topology-র সাথে মেলায়। কাছের core-দের (SMT sibling, শেয়ার্ড cache) মধ্যে ঘন ঘন, সস্তা balance করা যায় (migration cost কম, cache এমনিতেই কাছাকাছি)। দূরের core-দের (আলাদা NUMA node) মধ্যে কম ঘন ঘন, রক্ষণশীল balance — কারণ migration cost বেশি (memory access latency, আজকের আলোচনার শেষ অংশ)। এই hierarchical কাঠামো global lock-contention আর perfect-instant-fairness — দুইটা চরমের মাঝে একটা practical মধ্যপন্থা।

Level 9 (Distributed Systems)-এ এই একই টেনশন আরও বড় স্কেলে ফিরে আসবে — একটা কেন্দ্রীয় scheduler/load-balancer (single point of coordination, কিন্তু bottleneck-প্রবণ) বনাম বিকেন্দ্রীভূত, gossip-based বা eventually-consistent load-তথ্য শেয়ারিং (কম সমন্বয়-খরচ, কিন্তু কখনো সম্পূর্ণ নিখুঁত জ্ঞান থাকে না)। মূল নীতি অভিন্ন — যত বেশি “নোড” (এখানে core, সেখানে সার্ভার), তত বেশি কেন্দ্রীভূত সমন্বয়ের খরচ বাড়ে, তাই বিকেন্দ্রীকরণ, hierarchy, আর approximate (perfect না) balance-ই বাস্তবসম্মত পথ হয়ে দাঁড়ায়।

এরপর কী

পরের লেসন — Virtual Memory Intro

আজ পর্যন্ত আমরা ধরে নিয়েছি প্রতিটা thread/process-এর জন্য একটা “address space” আছে — কিন্তু কখনো প্রশ্ন করিনি সেই address space কীভাবে তৈরি হয়, বা কেন প্রতিটা process ভাবে সে পুরো memory-র একমাত্র মালিক, অথচ বাস্তবে সবাই একই সীমিত RAM ভাগ করে নেয়।

পরের লেসনে virtual memory-র মূল প্রতিশ্রুতি তিনটা — isolation (একটা process অন্যটার memory ছুঁতে পারবে না), relocation (প্রতিটা process ঠিকানা 0 থেকে শুরু করে ভাবতে পারবে, আসলে RAM-এ যেখানেই থাকুক), আর সীমার বাইরে যাওয়া (physical RAM-এর চেয়ে বেশি memory ব্যবহারের বিভ্রম, swap আর overcommit দিয়ে)। এই তিনটা সমস্যা কীভাবে একটা হার্ডওয়্যার ইউনিট (MMU) সমাধান করে, প্রতিটা memory access-এ, অদৃশ্যভাবে — সেটাই পরের কয়েকটা লেসনের কেন্দ্রীয় বিষয়, আর এখান থেকেই paging আর page table-এর দিকে এগিয়ে যাব।

Linux Scheduler — MLFQ থেকে CFS হয়ে EEVDF পর্যন্ত

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

MLFQ — ধারণাটা

CFS — fairness সংজ্ঞা দিয়ে, heuristic দিয়ে নয়

Nice value → weight — সঠিক সংখ্যা

sched_latency আর min_granularity

EEVDF — CFS-কে প্রতিস্থাপনকারী (Linux 6.6, ২০২৩)

Scheduling class — একটা কঠোর হায়ারার্কি

Multi-core — per-CPU runqueue, load balancing, NUMA

ভেতরে কী ঘটছে

pick_next_task() ভেতরে কী ঘটে

উদাহরণ

নিজে চালিয়ে দেখুন

/proc/sched_debug আর তাত্ত্বিক weight-ratio মেলানো

chrt দিয়ে SCHED_FIFO-র SCHED_OTHER-কে সম্পূর্ণ starve করা

নিজে বানান

Nice level জুড়ে achieved CPU share মাপা — তাত্ত্বিক weight-এর বিপরীতে

বাস্তব সিস্টেমে

Fairness model যেখানে সরাসরি প্রভাব ফেলে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

পরের লেসন — Virtual Memory Intro

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

MLFQ — ধারণাটা

CFS — fairness সংজ্ঞা দিয়ে, heuristic দিয়ে নয়

Nice value → weight — সঠিক সংখ্যা

sched_latency আর min_granularity

EEVDF — CFS-কে প্রতিস্থাপনকারী (Linux 6.6, ২০২৩)

Scheduling class — একটা কঠোর হায়ারার্কি

Multi-core — per-CPU runqueue, load balancing, NUMA

⚙ভেতরে কী ঘটছেUnder the hood

pick_next_task() ভেতরে কী ঘটে

▶উদাহরণExample

CPU share vruntime থেকে বের করা — একটা সম্পূর্ণ trace

⌘নিজে চালিয়ে দেখুনExperiment

/proc/sched_debug আর তাত্ত্বিক weight-ratio মেলানো

chrt দিয়ে SCHED_FIFO-র SCHED_OTHER-কে সম্পূর্ণ starve করা

⚒নিজে বানানBuild it yourself

Nice level জুড়ে achieved CPU share মাপা — তাত্ত্বিক weight-এর বিপরীতে

◉বাস্তব সিস্টেমেReal-world usage

Fairness model যেখানে সরাসরি প্রভাব ফেলে

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

পরের লেসন — Virtual Memory Intro

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী