Context switch আর dispatcher — CPU কীভাবে প্রসেস বদলায়

১ · “Context” কী — CPU-র মনে রাখার খাতা

একটি ব্যাংকের শাখায় একজন কর্মকর্তা আছেন, কাউন্টার একটিই। সামনে তিনজন গ্রাহক — একজনের ঋণের ফাইল, একজনের নতুন অ্যাকাউন্ট, একজনের চেক। কর্মকর্তা প্রথম ফাইলে কাজ করতে করতে ম্যানেজারের ফোন পেলেন: “দ্বিতীয় গ্রাহককে আগে দেখুন।” তিনি কী করবেন? প্রথম ফাইলটি এলোমেলো রেখে উঠে গেলে পরে কিছুই মনে থাকবে না। তাই তিনি একটি চিরকুটে লেখেন — “পৃষ্ঠা ৭, তৃতীয় লাইন পর্যন্ত যাচাই শেষ, হিসাবে ৪২ হাজার টাকা পর্যন্ত মিলেছে, ক্যালকুলেটরে এখন ১২৫০ লেখা” — আর চিরকুটসহ ফাইলটি তাকে রাখেন। তারপর দ্বিতীয় গ্রাহকের ফাইল নামান, তার পুরোনো চিরকুট পড়েন, আর ঠিক যেখানে থেমেছিলেন সেখান থেকে শুরু করেন।

CPU-র ক্ষেত্রেও একই ব্যাপার। একটি CPU core একসময়ে একটিমাত্র নির্দেশ-ধারা চালায়, অথচ আপনার ফোনে বা ল্যাপটপে শত শত process আর thread “একসাথে” চলছে। এই ভ্রম তৈরি হয় দ্রুত পালাবদলে। আর পালাবদলের সময় চিরকুটে যা লিখতে হয়, সেটিই context — CPU-র ভেতরের সেই সব মান, যা ফিরিয়ে দিলে থেমে থাকা প্রোগ্রাম বুঝতেই পারে না যে সে থেমেছিল।

খেয়াল করুন, প্রসেসের খোলা ফাইলের তালিকা, তার মেমরির পাতাগুলো বা PID এই তালিকায় নেই। এগুলো আগে থেকেই মেমরিতে, প্রসেসের নিজস্ব কাঠামোয় রাখা থাকে; switch-এর সময় এগুলো কপি করতে হয় না, শুধু “এখন কোন প্রসেস চলছে” নির্দেশকটি বদলায়। Context switch-এ যা সত্যিই সরাতে হয়, তা হলো CPU-র ভেতরে থাকা অবস্থা — কারণ CPU-তে register-এর একটিই সেট, দুটো প্রসেস একসাথে সেখানে বসতে পারে না।

সংরক্ষিত context কোথায় যায়? পাঠ্যবইয়ের উত্তর: প্রসেসের PCB (process control block)-এ, যা পর্ব ৮-এ দেখেছেন — প্রসেসের PID, অবস্থা, অগ্রাধিকার, খোলা ফাইল আর সংরক্ষিত register রাখার kernel-এর কাঠামো। বাস্তব kernel-এ ব্যাপারটি একটু ভাগ করা। Linux-এ PCB-র নাম task_struct. User mode-এর register-গুলো kernel-এ ঢোকার মুহূর্তেই thread-এর নিজস্ব kernel stack-এর মাথায় একটি কাঠামোয় (pt_regs) জমা হয়; আর kernel-এর stack pointer-টি রাখা হয় task_struct-এর ভেতরে। Windows-এ scheduling-এর একক thread, তাই এই তথ্য থাকে প্রতিটি thread-এর কাঠামোয় (KTHREAD). Thread-এর এমন কাঠামোকে সাধারণভাবে বলে thread control block.

নিচের ডায়াগ্রামে দুটি প্রসেস P1 আর P2 দেখুন। মানগুলো ছোট করে বানানো, কিন্তু কোন মান কখন কোথায় যায়, তা বাস্তবের মতোই। ডান দিকে CPU-র register আর দুই প্রসেসের সংরক্ষণ-এলাকা (save area) পাশাপাশি রাখা হয়েছে।

1P1 (user): total = total + x2timer interrupt! CPU pushes RIP, RSP, RFLAGS3kernel entry: push RAX..R15 (pt_regs)4schedule(): P1 -> ready, pick P25switch_mm: CR3 = P2's page table6switch_to: RSP = P2's kernel stack, pop regs7iretq -> P2 (user) continues

২ · কখন context switch হয় — চারটি কারণ

Context switch নিজে থেকে হয় না; কোনো একটি ঘটনা kernel-কে নিয়ন্ত্রণ দেয়, আর kernel সিদ্ধান্ত নেয় এখন অন্য কাউকে CPU দেওয়া দরকার কি না। মনে রাখুন পর্ব ৫-এর কথা — kernel-এ ঢোকার পথ তিনটি: system call, interrupt আর exception. তাই switch-এর কারণগুলোও এই পথ দিয়েই আসে।

এখানে দুটি শব্দ খুব গুরুত্বপূর্ণ। Voluntary context switch মানে প্রসেস নিজেই এমন কিছু চেয়েছে যার জন্য অপেক্ষা করতে হবে, তাই সে blocked (waiting) অবস্থায় গিয়ে CPU ছেড়ে দিয়েছে। Involuntary context switch মানে প্রসেস চলতে প্রস্তুত ছিল, তবু kernel জোর করে তাকে সরিয়েছে — সময় শেষ বা অগ্রাধিকারের কারণে। প্রথমটি I/O-bound প্রোগ্রামের স্বভাব, দ্বিতীয়টি CPU-bound প্রোগ্রামের।

নিজের চোখে দেখা — Linux-এর দুটি গণক

Linux প্রতিটি প্রসেস (আসলে প্রতিটি thread)-এর জন্য দুটি সংখ্যা গুনে রাখে, আর /proc/<pid>/status ফাইলে দেখায়: voluntary_ctxt_switches আর nonvoluntary_ctxt_switches. নিচের script একটি bash shell-এর নিজের গণক তিনবার মাপে — অপেক্ষার কাজের আগে-পরে, হিসাব-ভারী লুপের আগে-পরে, আর একই CPU-তে একজন প্রতিদ্বন্দ্বী রেখে লুপের আগে-পরে। একটি সূক্ষ্ম বিষয়: /proc/self লিখলে “self” হতো grep প্রসেস নিজেই, তাই shell-এর নিজের PID $$ ব্যবহার করা হয়েছে।

snap() {   # this shell's own counters: /proc/$$ (not /proc/self, which is grep)
  v=$(grep '^voluntary_ctxt' /proc/$$/status | tr -dc 0-9)
  n=$(grep '^nonvoluntary_ctxt' /proc/$$/status | tr -dc 0-9)
}
echo "cpus: $(nproc)"

snap; v0=$v; n0=$n
for i in $(seq 20); do sleep 0.01; done          # 20 waits for a child
snap; echo "sleep x20 : voluntary +$((v - v0)), nonvoluntary +$((n - n0))"

snap; v0=$v; n0=$n
for ((i = 0; i < 200000; i++)); do :; done       # pure CPU, no waiting
snap; echo "busy loop : voluntary +$((v - v0)), nonvoluntary +$((n - n0))"

taskset -cp "$(taskset -cp $$ | grep -o '[0-9]*$')" $$ >/dev/null 2>&1
( while :; do :; done ) & hog=$!                  # a rival on the same CPU
snap; v0=$v; n0=$n
for ((i = 0; i < 200000; i++)); do :; done
snap; echo "busy+rival: voluntary +$((v - v0)), nonvoluntary +$((n - n0))"
kill $hog; wait $hog 2>/dev/null; echo "rival stopped"

cpus: 2
sleep x20 : voluntary +26, nonvoluntary +0
busy loop : voluntary +4, nonvoluntary +8
busy+rival: voluntary +3, nonvoluntary +416
rival stopped

৩ · Dispatcher — পালাবদলের কারিগর

দুটি শব্দ প্রায়ই গুলিয়ে যায়। Scheduler ঠিক করে কে পরের পালা পাবে — এটি নীতি (policy), যেমন FCFS, Round Robin বা Linux-এর EEVDF (মডিউল ৩-এ বিস্তারিত)। Dispatcher হলো সেই প্রক্রিয়া (mechanism), যা সিদ্ধান্তটি কাজে পরিণত করে — আসলেই CPU এক প্রসেসের হাত থেকে নিয়ে অন্যের হাতে তুলে দেয়। ট্রাফিক মোড়ের উপমায়: কোন রাস্তার গাড়ি এখন যাবে, সেই নিয়ম scheduler; আর সিগন্যালের বাতি বদলানো, পুলিশের হাত তোলা — dispatcher.

Dispatcher-এর কাজকে পাঠ্যবই তিন বাক্যে বলে: context switch করা, user mode-এ ফেরানো, আর নতুন প্রোগ্রামের সঠিক জায়গায় লাফ দেওয়া। আরেকটু ভেঙে দেখলে ধাপগুলো এমন:

1. পুরোনো প্রসেসের অবস্থা সংরক্ষণ — register, PC, SP, flags যায় PCB বা kernel stack-এ; প্রসেসের অবস্থা হয় ready বা blocked.
2. পরের জনকে বাছাই — scheduler-কে ডাকা; সে ready queue থেকে একজনকে দেয়।
3. Address space বদল — নতুনটি আলাদা প্রসেস হলে page table-এর ঠিকানা (CR3) বদল; একই প্রসেসের thread হলে এই ধাপ বাদ।
4. নতুনের অবস্থা ফিরিয়ে আনা — kernel stack বদল, register ফেরত, FPU/SIMD অবস্থা ফেরত।
5. User mode-এ ফেরা — বিশেষ return নির্দেশ দিয়ে mode নামিয়ে নতুন প্রসেসের সংরক্ষিত PC-তে লাফ।

এক প্রসেস থামানো থেকে আরেক প্রসেস চালু হওয়া পর্যন্ত সময়কে বলে dispatch latency. এই সময়ে কোনো user প্রোগ্রামের কাজ হয় না — CPU শুধু গোছগাছ করে। তাই dispatcher যত দ্রুত, তত ভালো; প্রতিটি সেকেন্ডে এটি শত থেকে হাজারবার চলতে পারে। Real-time সিস্টেমে (পর্ব ২০) dispatch latency-র ঊর্ধ্বসীমা জানা থাকা জরুরি, কারণ সেখানে “গড়ে দ্রুত” যথেষ্ট নয়, “কখনো দেরি নয়” দরকার।

এবার timer interrupt থেকে শুরু করে পুরো ঘটনাটি ধাপে ধাপে দেখুন। প্রতিটি ধাপে নিচের প্যানেলে ready queue আর ঘড়ির অবস্থা দেওয়া আছে।

running : P1  (quantum 4 ms, used 3.9 ms)
ready   : [P2, P3]
blocked : [P4 — waiting for disk]

CPU     : mode -> kernel, stack -> P1's kernel stack
pushed  : RIP, RSP, RFLAGS  (by hardware)
tick    : P1 used 4.0 of 4 ms -> need_resched = 1

pt_regs : RAX RBX RCX ... R15  (by entry code)
P1 state: running -> ready
ready   : [P2, P3, P1]

policy  : round robin -> take the head
picked  : P2
ready   : [P3, P1]

CR3     : P1's table -> P2's table
TLB     : old entries useless (flushed, or kept with a PCID tag)

save    : P1's kernel RSP -> P1's task_struct
load    : RSP <- P2's kernel stack
restore : P2's registers, FPU/SIMD state

iretq   : mode -> user, RIP = P2's saved PC
running : P2  (fresh quantum 4 ms)
ready   : [P3, P1]

৪ · Mode switch, context switch, process switch, thread switch

পরীক্ষায় আর ইন্টারভিউতে এই চারটি শব্দের পার্থক্য প্রায়ই জিজ্ঞেস করা হয়, আর অনেকে এগুলোকে এক মনে করেন। আসলে এরা একটি সিঁড়ির মতো — প্রতিটি ধাপে আগেরটির সব খরচ, সঙ্গে বাড়তি কিছু।

Mode switch আর context switch-এর পার্থক্য মনে রাখার সহজ উপায়: mode switch-এ অভিনেতা একই, মঞ্চ বদলায়; context switch-এ অভিনেতাই বদলায়। প্রতিটি context switch-এর আগে অন্তত একটি mode switch থাকে (kernel-এ না ঢুকে তো dispatcher চলতে পারে না), কিন্তু বেশিরভাগ mode switch কোনো context switch ঘটায় না।

Linux-এ একটি মজার মিল আছে: kernel-এর চোখে process আর thread দুটিই task_struct — একই প্রসেসের thread-গুলো শুধু একই মেমরি-কাঠামো (mm) ভাগ করে। তাই Linux-এ thread switch আর process switch-এর কোড একই; পার্থক্য হয় একটি তুলনায় — আগের আর পরের task-এর mm এক কি না। এক হলে page table বদলানোর কাজ বাদ পড়ে। Windows-এও scheduler process নয়, thread-কেই বেছে নেয়; প্রসেস সেখানে মূলত একটি ধারক (container) — address space, handle-এর তালিকা আর নিরাপত্তা-পরিচয় রাখার জায়গা। পরের thread অন্য প্রসেসের হলে তবেই address space বদলায়।

1A: getpid()        (Chrome tab, thread T1)2B: T1 -> T2        (same process: Chrome tab)3C: Chrome -> bash  (another process, no PCID)4D: Chrome -> bash  (another process, PCID on)5E: T2 -> kernel thread (e.g. kworker)

৫ · খরচ — প্রত্যক্ষ আর পরোক্ষ

Context switch-এর খরচকে দুই ভাগে ভাবুন। প্রত্যক্ষ খরচ হলো dispatcher-এর নিজের কাজ: kernel-এ ঢোকা, register রাখা ও ফেরানো, scheduler-এর বাছাই, CR3 লেখা, user mode-এ ফেরা। পরোক্ষ খরচ ধরা পড়ে switch শেষ হওয়ার পরে, নতুন প্রসেসের গতিতে — কারণ CPU-র সব “স্মৃতি” তখনো আগের প্রসেসের।

পরোক্ষ খরচ ১ — TLB

প্রতিটি মেমরি-ঠিকানা virtual থেকে physical-এ অনুবাদ করতে হয় (মডিউল ৫)। এই অনুবাদের ছোট, দ্রুত cache হলো TLB. পুরোনো x86-এ CR3-এ নতুন মান লিখলে TLB-র (global চিহ্ন ছাড়া) সব entry মুছে যায়। নতুন প্রসেসের প্রথম কয়েকশো মেমরি-ছোঁয়ার প্রতিটিতে তখন MMU-কে মেমরি থেকে page table পড়তে হয় — x86-64-এ চার স্তরের টেবিল। এই ক্ষতি কমাতে এসেছে address-space ট্যাগ: ARM-এর ASID বহু আগে থেকে, আর x86-এর PCID (Intel-এ প্রায় ২০১০ সালের প্রসেসর থেকে)। Linux ২০১৭-১৮ সাল থেকে PCID ব্যাপকভাবে ব্যবহার শুরু করে — বিশেষ করে Meltdown-এর পর KPTI চালু হওয়ায়, যেখানে প্রতিটি kernel-প্রবেশেই page table বদলায় (ভাবনার প্রশ্ন ৩)।

পরোক্ষ খরচ ২ — cache-এর দূষণ

P1 চলার সময় L1, L2 cache ভরে ছিল P1-এর ডেটা আর কোডে। P2 এসে নিজের ডেটা আনতে আনতে P1-এর অংশ সরিয়ে দেয় — একে বলে cache pollution. P1 পরে ফিরলে আবার cache miss, আবার মেমরি থেকে আনা। প্রসেসের working set (সক্রিয়ভাবে ব্যবহৃত মেমরি) যত বড়, ক্ষতি তত বেশি। এই খরচ মাপা কঠিন, কারণ এটি switch-এর মধ্যে নয়, পরের কয়েক মাইক্রো বা মিলিসেকেন্ডে ছড়িয়ে থাকে। Branch predictor-এর মতো CPU-র অন্য “শেখা” অবস্থাও একইভাবে আংশিক নষ্ট হয়, আর কিছু নিরাপত্তা-প্রতিরোধ (Spectre-এর পর) switch-এর সময় ইচ্ছা করেই এগুলো মুছে দেয়।

সংখ্যাগুলো ইচ্ছা করেই মোটা দাগের — CPU-র প্রজন্ম, kernel-এর সংস্করণ, নিরাপত্তা-সেটিং, virtual machine-এ চলছে কি না — সব কিছুতে এগুলো কয়েক গুণ বদলায়। মনে রাখার মতো বিষয় হলো অনুপাত: একটি switch-এর সময়ে CPU কয়েক হাজার সাধারণ নির্দেশ চালাতে পারত।

নিজের হাতে মাপা — দুই প্রসেসের ping-pong

Context switch-এর খরচ মাপার একটি পুরোনো, সরল কৌশল: দুটি প্রসেস, দুটি pipe. Parent এক বাইট পাঠায়, তারপর উত্তরের জন্য read()-এ block হয়। Child বাইটটি পড়ে ফেরত পাঠায়, আবার পরের বাইটের জন্য block হয়। দুটোই একই CPU-তে বাঁধা থাকলে (CPU affinity) প্রতিটি আসা-যাওয়ায় অন্তত দুটি context switch ঘটতেই হবে — কারণ একজন না ঘুমালে আরেকজন চলতে পারে না। fork-এর বিস্তারিত পর্ব ১০-এ, pipe-এর পর্ব ১২-এ; এখানে শুধু মাপার কাজ।

#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <sys/wait.h>
#define N 20000
static double now_us(void) {
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1e6 + t.tv_nsec / 1e3;
}

int main(void) {
    int to_child[2], to_parent[2]; char b = 'x';
    cpu_set_t one;                 /* keep both processes on ONE cpu */
    CPU_ZERO(&one); CPU_SET(sched_getcpu(), &one);
    int pinned = sched_setaffinity(0, sizeof one, &one) == 0;
    if (pipe(to_child) < 0 || pipe(to_parent) < 0) { perror("pipe"); return 1; }
    fflush(stdout);
    pid_t pid = fork();
    if (pid == 0) {                /* child: echo every byte back */
        for (int i = 0; i < N; i++)
            if (read(to_child[0], &b, 1) != 1 || write(to_parent[1], &b, 1) != 1) _exit(1);
        _exit(0);
    }
    double t0 = now_us();
    for (int i = 0; i < N; i++)    /* parent: send, then wait for the echo */
        if (write(to_child[1], &b, 1) != 1 || read(to_parent[0], &b, 1) != 1) return 1;
    double us = (now_us() - t0) / N;
    waitpid(pid, NULL, 0);
    printf("pinned to one CPU: %s, round trips: %d\n", pinned ? "yes" : "no", N);
    printf("avg round trip   : %.2f us\n", us);
    printf("per switch (~1/2): %.2f us\n", us / 2);
    return 0;
}

pinned to one CPU: yes, round trips: 20000
avg round trip   : 18.12 us
per switch (~1/2): 9.06 us

$ perf bench sched pipe            # the same ping-pong, built into perf
# Running 'sched/pipe' benchmark:
# Executed 1000000 pipe operations between two processes

     Total time: 4.871 [sec]

       4.871203 usecs/op
         205287 ops/sec

$ vmstat 1 3                       # "cs" column = context switches per second (whole system)
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 1  0      0 812340  90412 2412220    0    0     3    11  402  911  3  1 96  0  0
 2  0      0 812100  90412 2412236    0    0     0     0  618 1430  4  1 95  0  0

৬ · হিসাব — overhead আর CPU efficiency

এবার পরীক্ষার সবচেয়ে প্রিয় অংশ। ধরুন time-sharing সিস্টেমে প্রতিটি প্রসেস একবারে q সময় পায় (time quantum), আর প্রতিটি context switch-এ s সময় লাগে, যখন কোনো উপকারী কাজ হয় না। প্রতিটি প্রসেস যদি পুরো quantum ব্যবহার করে (অর্থাৎ CPU-bound), তাহলে প্রতিটি চক্র দেখতে এমন: q সময় কাজ, s সময় switch, আবার q, আবার s…

সূত্রটি থেকে দুটি সীমা পরিষ্কার: q → ∞ হলে efficiency → ১০০% (কিন্তু তখন Round Robin আসলে FCFS হয়ে যায়, ছোট কাজও দীর্ঘ অপেক্ষা করে); q → 0 হলে efficiency → 0 (CPU-র প্রায় সব সময় যায় পালাবদলে, আসল কাজ হয় না)। আর q = s হলে ঠিক অর্ধেক, ৫০%. তাই quantum বাছাই একটি দর-কষাকষি — response time বনাম efficiency (বিস্তারিত পর্ব ১৮-এ)।

সমাধান করা উদাহরণ ১ — সরাসরি সূত্র

প্রশ্ন: q = ১০ ms, s = ০.১ ms. (ক) CPU efficiency কত? (খ) q কমিয়ে ১ ms করলে? (গ) Efficiency অন্তত ৯৫% রাখতে q কমপক্ষে কত হতে হবে?

সমাধান: (ক) ১০ ÷ (১০ + ০.১) = ১০ ÷ ১০.১ ≈ ৯৯.০%. (খ) ১ ÷ ১.১ ≈ ৯০.৯% — quantum দশ ভাগের এক ভাগ করায় overhead প্রায় ১% থেকে ৯%-এ উঠল। (গ) q ÷ (q + ০.১) ≥ ০.৯৫ ⇒ q ≥ ০.৯৫q + ০.০৯৫ ⇒ ০.০৫q ≥ ০.০৯৫ ⇒ q ≥ ১.৯ ms.

সমাধান করা উদাহরণ ২ — প্রসেস quantum-এর আগেই block হলে

বাস্তবে অনেক প্রসেস পুরো quantum ব্যবহার করে না — I/O-র জন্য আগেই block হয়। ধরুন গড়ে একটি প্রসেস T সময় চলে তারপর block হয়, switch-এর খরচ s, আর quantum q. পাঠ্যবইগুলোর একটি পরিচিত অনুশীলন:

খেয়াল করুন, q যখন T-এর চেয়ে বড়, তখন quantum আরও বাড়িয়ে লাভ নেই — efficiency আটকে থাকে T/(T+s)-এ, কারণ switch-টা হচ্ছে block হওয়ার কারণে, quantum-এর কারণে নয়। সংখ্যায়: T = ২০ ms, s = ১ ms হলে q = ১০০ ms-এ efficiency = ২০/২১ ≈ ৯৫.২%; q = ৫ ms-এ ৫/৬ ≈ ৮৩.৩%; q = ১ ms-এ ৫০%.

সমাধান করা উদাহরণ ৩ — Gantt chart-এ overhead ধরা

তিনটি প্রসেস একসাথে (t = 0) আসে: burst time P1 = ৭, P2 = ৪, P3 = ৫ ms. Round Robin, q = ৪ ms, আর ভিন্ন প্রসেসে যেতে প্রতিবার s = ১ ms. (একই প্রসেস পরপর চললে switch নেই; প্রথম প্রসেস চালু করার খরচ ধরা হয়নি — প্রশ্নে অন্য নিয়ম বলা থাকলে সেটিই মানবেন।) নিচে ধাপে ধাপে দেখুন।

1 0- 4  P1 runs 42 4- 5  switch P1 -> P23 5- 9  P2 runs 4 (done)4 9-10  switch P2 -> P3510-14  P3 runs 4614-15  switch P3 -> P1715-18  P1 runs 3 (done)818-19  switch P1 -> P3919-20  P3 runs 1 (done)

সূত্র আর আসল চার্ট কি সবসময় মেলে? নিচের simulator একই তিনটি প্রসেস বিভিন্ন quantum-এ চালিয়ে দুটো পাশাপাশি দেখায়। burst, s বা quantum-এর তালিকা বদলে আবার চালিয়ে দেখুন।

// Round Robin, all arrive at t=0. A switch to a DIFFERENT process costs s ms.
const burst = { P1: 7, P2: 4, P3: 5 };   // CPU time each process needs (ms)
const s = 1;                              // fixed switch overhead (ms)

function rr(q) {
  const left = { ...burst }, queue = Object.keys(burst), line = [];
  let useful = 0, overhead = 0, switches = 0, last = null;
  while (queue.length) {
    const p = queue.shift();
    if (last !== null && last !== p) { overhead += s; switches++; line.push("|cs|"); }
    const run = Math.min(q, left[p]);
    useful += run; left[p] -= run; line.push(p + ":" + run);
    if (left[p] > 0) queue.push(p);
    last = p;
  }
  return { q, useful, overhead, switches, line: line.join(" ") };
}

console.log("timeline q=4: " + rr(4).line);
console.log(" q | switches | useful | overhead | efficiency | q/(q+s)");
for (const q of [1, 2, 4, 8, 16]) {
  const r = rr(q), eff = (100 * r.useful) / (r.useful + r.overhead);
  console.log(String(q).padStart(2) + " | " + String(r.switches).padStart(8) + " | " +
    String(r.useful).padStart(6) + " | " + String(r.overhead).padStart(8) + " | " +
    (eff.toFixed(1) + "%").padStart(10) + " | " + ((100 * q) / (q + s)).toFixed(1) + "%");
}

timeline q=4: P1:4 |cs| P2:4 |cs| P3:4 |cs| P1:3 |cs| P3:1
 q | switches | useful | overhead | efficiency | q/(q+s)
 1 |       14 |     16 |       14 |      53.3% | 50.0%
 2 |        8 |     16 |        8 |      66.7% | 66.7%
 4 |        4 |     16 |        4 |      80.0% | 80.0%
 8 |        2 |     16 |        2 |      88.9% | 88.9%
16 |        2 |     16 |        2 |      88.9% | 94.1%

সমাধান করা উদাহরণ ৪ — সবচেয়ে বেশি অপেক্ষা আর প্রতি সেকেন্ডের খরচ

প্রশ্ন: ৫টি CPU-bound প্রসেস Round Robin-এ, q = ২০ ms, s = ২ ms. (ক) একটি প্রসেস তার এক পালা শেষে আবার CPU পাওয়ার আগে সর্বোচ্চ কত অপেক্ষা করে? (খ) প্রতি সেকেন্ডে কতগুলো switch হয়, আর কত সময় overhead-এ যায়?

সমাধান: (ক) বাকি (n − 1) = ৪টি প্রসেসের প্রত্যেকে q চলে, আর প্রতিবার একটি করে switch — নিজের কাছে ফেরার switch-সহ মোট ৫টি: ৪ × ২০ + ৫ × ২ = ৯০ ms. (সাধারণ সূত্র: (n − 1)·q + n·s; অনেক বই সরলভাবে (n − 1)(q + s) লেখে, যেখানে শেষ switch-টি বাদ পড়ে = ৮৮ ms — প্রশ্নে কোনটি চাওয়া হয়েছে তা দেখুন।) (খ) একটি চক্র q + s = ২২ ms, তাই প্রতি সেকেন্ডে ১০০০ ÷ ২২ ≈ ৪৫টি switch; overhead = s/(q+s) = ২/২২ ≈ ৯.১%, অর্থাৎ প্রতি সেকেন্ডে প্রায় ৯১ ms.

৭ · Cooperative বনাম preemptive multitasking

এ পর্যন্ত আমরা ধরে নিয়েছি, kernel timer interrupt দিয়ে যেকোনো সময় CPU কেড়ে নিতে পারে। এটিই preemptive multitasking. কিন্তু আরেকটি পথ আছে, যা ইতিহাসে বহু বছর চলেছে: cooperative multitasking — প্রতিটি প্রোগ্রাম নিজে থেকে মাঝে মাঝে CPU ছেড়ে দেবে (yield), এই ভরসায়। Switch হয় শুধু voluntary পথে।

Cooperative ধারণা কিন্তু হারিয়ে যায়নি — জায়গা বদলেছে। আজ এটি থাকে প্রোগ্রামের ভেতরে: JavaScript-এর event loop, Python-এর asyncio, Kotlin-এর coroutine — এরা একটি thread-এর ভেতরে কাজ ভাগ করে, আর await-এ পৌঁছালে তবেই পালা বদলায়। ব্রাউজারের একটি tab-এ কেউ অসীম লুপ লিখলে সেই tab জমে যায় — ঠিক Windows 3.x-এর মতো — কিন্তু OS preemptive বলে বাকি কম্পিউটার চলতে থাকে। আধুনিক ব্যবস্থা তাই দুই স্তরের: বাইরে preemptive kernel, ভেতরে চাইলে সস্তা cooperative switch (ভাবনার প্রশ্ন ৪)।

Kernel নিজে কি preemptive? এটি আলাদা প্রশ্ন। পুরোনো Linux-এ (২.৪ পর্যন্ত) kernel কোড চলার সময় অন্য কেউ CPU নিতে পারত না, শুধু user mode-এ ফেরার সময় switch হতো। Linux ২.৬ থেকে kernel preemption বিকল্প হিসেবে এসেছে (CONFIG_PREEMPT); নতুন সংস্করণে (৬.x) কোন মাত্রার preemption চলবে তা বুট-সময়েও বেছে নেওয়া যায়, আর real-time-এর PREEMPT_RT অংশ মূল kernel-এ যুক্ত হয়েছে ২০২৪ সালে (Linux 6.12).

৮ · বাস্তব kernel-এ — Linux, Windows, macOS

Linux: schedule() → context_switch() → switch_to

Linux-এ পালাবদলের কেন্দ্র kernel/sched/core.c ফাইলের __schedule() ফাংশন। দুইভাবে এটি ডাকা হয়: কোনো task নিজে block হতে গিয়ে (voluntary), অথবা interrupt বা system call থেকে ফেরার পথে need_resched পতাকা ওঠা দেখে (involuntary). নিচের অংশটি বহু লাইন বাদ দিয়ে সরল করা — শুধু কাঠামো দেখানোর জন্য, চালানোর জন্য নয়।

static void __schedule(...)
{
    struct rq *rq = this_rq();                 /* this CPU's run queue */
    struct task_struct *prev = rq->curr, *next;

    if (prev is going to sleep)                /* e.g. blocked in read() */
        deactivate_task(rq, prev);             /* take it off the run queue */

    next = pick_next_task(rq, prev);           /* POLICY: fair, RT, deadline... */
    clear_tsk_need_resched(prev);

    if (prev != next) {
        rq->nr_switches++;
        rq = context_switch(rq, prev, next);   /* MECHANISM */
    }
}

static struct rq *context_switch(struct rq *rq,
        struct task_struct *prev, struct task_struct *next)
{
    if (!next->mm)                             /* kernel thread: no user memory */
        enter_lazy_tlb(prev->active_mm, next); /* keep the old page table */
    else
        switch_mm_irqs_off(prev->active_mm, next->mm, next);  /* CR3; skipped if same mm */

    switch_to(prev, next, prev);               /* kernel stack + registers */
    return finish_task_switch(prev);           /* runs in NEXT's context */
}

switch_to একটি macro, যা x86-64-এ assembly-র __switch_to_asm ডাকে (arch/x86/entry/entry_64.S). এর মূল অংশ কয়েক লাইনের:

__switch_to_asm:                 ; rdi = prev, rsi = next
    push rbp, rbx, r12, r13, r14, r15        ; callee-saved regs onto PREV's kernel stack
    mov  [rdi + thread.sp], rsp              ; remember where prev's stack is
    mov  rsp, [rsi + thread.sp]              ; ---- from here we are on NEXT's stack ----
    pop  r15, r14, r13, r12, rbx, rbp        ; next's callee-saved regs
    jmp  __switch_to                         ; C part: FPU state, FS/GS base, per-CPU stack top

লক্ষ করুন, এখানে মাত্র ছয়টি register রাখা হয়। কারণ এটি একটি সাধারণ C ফাংশন-কলের মতো: বাকি register রাখার দায় C-এর নিয়মে ডাকার পক্ষের, আর user mode-এর সব register তো kernel-এ ঢোকার মুহূর্তেই pt_regs-এ রাখা হয়ে গেছে (অংশ ১-এর stepper). __switch_to() C ফাংশন বাকি কাজ করে: FPU/SIMD অবস্থার ব্যবস্থা (আধুনিক x86 Linux-এ এটি XSAVE দিয়ে রাখা হয়, আর নতুন thread-এর অবস্থা user mode-এ ফেরার আগে ফিরিয়ে আনা হয়), thread-local storage-এর FS/GS base, আর পরের interrupt-এ কোন kernel stack ব্যবহার হবে তা CPU-কে জানানো।

Windows: thread-ই scheduling-এর একক

Windows NT পরিবার (আজকের Windows 10/11-সহ) শুরু থেকেই thread ধরে schedule করে; process সেখানে address space, handle table আর নিরাপত্তা-token-এর ধারক। Kernel-এর যে অংশ thread বাছাই আর পালাবদল করে, Microsoft-এর নথি ও Windows Internals বইয়ে তাকে বলা হয় dispatcher — এখান থেকেই পাঠ্যবইয়ের শব্দটি পরিচিত। প্রতিটি thread-এর context থাকে তার KTHREAD কাঠামো আর kernel stack-এ; Windows-এ ৩২টি অগ্রাধিকার-স্তর (০–৩১) আছে, আর সবচেয়ে উঁচু অগ্রাধিকারের ready thread-ই চলে (পর্ব ৫৬-এ বিস্তারিত)। পুরো সিস্টেমে প্রতি সেকেন্ডে কতগুলো switch হচ্ছে, দেখা যায় Performance Monitor-এর একটি counter দিয়ে:

PS> Get-Counter '\System\Context Switches/sec' -SampleInterval 1 -MaxSamples 2

Timestamp                 CounterSamples
---------                 --------------
25-10-2026 10:15:01       \\mypc\system\context switches/sec :
                          8412.37
25-10-2026 10:15:02       \\mypc\system\context switches/sec :
                          9105.88

macOS/iOS-এর kernel XNU-এর scheduling অংশ এসেছে Mach থেকে; সেখানেও scheduling-এর একক Mach thread, আর প্রসেস (BSD-র দিক থেকে proc, Mach-এর দিক থেকে task) মূলত ধারক। তিনটি বড় OS তাই একই জায়গায় মিলেছে: CPU পায় thread, address space-এর মালিক process.

৯ · AI-এর যুগে context switch

“আমার সার্ভার ধীর, context switch অনেক বেশি — কী করব?” — AI-কে জিজ্ঞেস করলে লম্বা তালিকা পাবেন। কিছু পরামর্শ কাজের, কিছু ভুল OS-এর, কিছু পুরোনো, আর কিছু ক্ষতিকর। এই পর্বের ধারণাগুলো দিয়ে সেগুলো যাচাই করুন:

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

• উত্তরটি আমার OS আর kernel সংস্করণের জন্য কি না মিলিয়েছি (Linux বনাম Windows, পুরোনো বনাম নতুন scheduler)
• খরচের সংখ্যা (µs বনাম ms) নিজের মেশিনে একটি ছোট পরীক্ষা চালিয়ে যাচাই করেছি
• voluntary আর involuntary গণক আলাদা করে দেখে কারণ বুঝেছি — অপেক্ষা, নাকি CPU-র জন্য কাড়াকাড়ি
• যেকোনো পরিবর্তনের আগে-পরে একই লোডে মেপেছি; “আমার মেশিনে চলে” যথেষ্ট মনে করিনি
• Efficiency বা overhead-এর অঙ্ক Gantt chart এঁকে হাতে মিলিয়েছি
• sudo দিয়ে kernel সেটিং বদলানো বা নিরাপত্তা-প্রতিরোধ বন্ধ করার পরামর্শ মানিনি; man page আর kernel-এর ডকুমেন্টেশন দেখেছি