CPU scheduling-এর ভিত্তি — burst, criteria আর মাপকাঠি

১ · CPU–I/O burst চক্র — প্রসেস আসলে কীভাবে চলে

একটি ব্যাংকের শাখার কথা ভাবুন। টোকেন নিয়ে গ্রাহকেরা বসে আছেন, কাউন্টার একটি। কেউ এসেছেন শুধু একটি চেক জমা দিতে — কাউন্টারে দুই মিনিট, তারপর চলে যান বা পাশের ডেস্কে স্বাক্ষর যাচাইয়ের অপেক্ষায় বসেন। কেউ এসেছেন পুরো একটি ঋণের ফাইল নিয়ে — কাউন্টারে আধা ঘণ্টা। কাকে আগে ডাকবেন, তা ঠিক করতে আগে জানতে হবে গ্রাহকেরা সাধারণত কতক্ষণ কাউন্টার দখল করেন। CPU-র ক্ষেত্রেও প্রথম প্রশ্ন এটিই।

পর্ব ৮-এ দেখেছেন, একটি প্রসেস running, ready আর waiting অবস্থার মধ্যে ঘোরে। একটু দূর থেকে দেখলে প্রায় সব প্রসেসের জীবন একই ছন্দে চলে: কিছুক্ষণ CPU-তে হিসাব, তারপর কোনো I/O-র অপেক্ষা (ফাইল পড়া, নেটওয়ার্ক থেকে উত্তর, কিবোর্ডের চাপ), তারপর আবার হিসাব। হিসাবের একটানা অংশকে বলে CPU burst, অপেক্ষার একটানা অংশকে I/O burst. প্রসেস শুরু হয় একটি CPU burst দিয়ে, আর শেষও হয় একটি CPU burst দিয়ে — শেষটিতে সে exit() ডাকে। এই ছন্দের নাম CPU–I/O burst cycle.

Scheduler-এর কাছে এর গুরুত্ব সরাসরি: প্রসেস একটি I/O burst-এ ঢুকলেই CPU খালি হয়, আর তখন অন্য কাউকে দিতে হয়। আর একটি প্রসেস কতটা সময় একটানা CPU চাইবে — অর্থাৎ পরের CPU burst কত লম্বা — সেটি জানা থাকলে অনেক ভালো সিদ্ধান্ত নেওয়া যেত (পর্ব ১৭-এর SJF ঠিক এই ধারণা থেকে আসে)।

Burst-এর দৈর্ঘ্য — অনেক ছোট, অল্প কিছু লম্বা

বহু দশক ধরে নানা সিস্টেমে CPU burst-এর দৈর্ঘ্য মাপা হয়েছে। প্রোগ্রাম আর কম্পিউটার-ভেদে সংখ্যা বদলায়, কিন্তু বণ্টনের আকৃতি মোটামুটি একই থাকে: খুব বেশি সংখ্যক ছোট burst, আর খুব অল্প সংখ্যক লম্বা burst. পাঠ্যবইগুলো এই আকৃতিকে সাধারণত exponential বা hyperexponential ধাঁচের বলে বর্ণনা করে। নিচের ছবিটি শুধু আকৃতি বোঝানোর জন্য — এটি কোনো নির্দিষ্ট মাপা তথ্য নয়।

frequency
   │█
   │█ █
   │█ █ █
   │█ █ █ ▆
   │█ █ █ █ ▅ ▃
   │█ █ █ █ █ █ ▂ ▂ ▁ ▁   ▁         ▁
   └──────────────────────────────────────▶ burst length (ms)
     0   4   8   12  16  20  24  ...    40
     ↑ most bursts are short         ↑ a few are long

এই আকৃতির পেছনে দুই জাতের প্রসেস। I/O-bound প্রসেস — টেক্সট এডিটর, shell, ব্রাউজারের সাধারণ কাজ, ডেটাবেসের ছোট প্রশ্ন — অনেক বার অল্প সময়ের জন্য CPU চায়, তারপর অপেক্ষায় যায়। CPU-bound প্রসেস — ভিডিও এনকোড, বড় compile, মেশিন লার্নিং-এর প্রশিক্ষণ — অল্প কয়েকবার কিন্তু লম্বা সময়ের জন্য CPU চায়। সাধারণ কম্পিউটারে I/O-bound প্রসেসই বেশি, তাই ছোট burst-ও বেশি।

নিচের stepper-এ দুটি প্রসেসের জীবনের প্রথম কয়েকটি burst পাশাপাশি দেখুন — যেন প্রত্যেকে একাই একটি কম্পিউটারে চলছে। C মানে CPU burst, I মানে I/O burst, সংখ্যা মিলিসেকেন্ডে।

1CPU burst : editor 2 ms, encoder 90 ms2I/O burst : editor 50 (key), encoder 4 (disk)3CPU burst : editor 1 ms, encoder 110 ms4I/O burst : editor 120, encoder 35CPU burst : editor 3 ms, encoder 95 ms6summary   : share of time on the CPU

নিজের প্রোগ্রামে মাপা — user time, system time আর switch

একটি প্রসেস কোন জাতের, তা Linux নিজেই হিসাব রাখে। getrusage() system call জানায় প্রসেস এখন পর্যন্ত user mode-এ কত সময় CPU পেয়েছে (ru_utime), kernel mode-এ তার হয়ে কত সময় কাজ হয়েছে (ru_stime), আর কতবার সে নিজে অপেক্ষায় গিয়ে CPU ছেড়েছে (voluntary switch, ru_nvcsw) বা জোর করে সরানো হয়েছে (involuntary, ru_nivcsw). নিচের প্রোগ্রাম তিনটি অংশ চালিয়ে প্রতিটির আগে-পরে এই সংখ্যাগুলো মাপে: টানা হিসাব, অনেকগুলো ছোট system call, আর অনেকগুলো ছোট অপেক্ষা।

#include <fcntl.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <sys/resource.h>

static struct rusage r0; static struct timespec w0;
static double ms(struct timeval t) { return t.tv_sec * 1e3 + t.tv_usec / 1e3; }
static void start(void) { getrusage(RUSAGE_SELF, &r0); clock_gettime(CLOCK_MONOTONIC, &w0); }
static void report(const char *name) {
    struct rusage r; struct timespec w;
    getrusage(RUSAGE_SELF, &r); clock_gettime(CLOCK_MONOTONIC, &w);
    double wall = (w.tv_sec - w0.tv_sec) * 1e3 + (w.tv_nsec - w0.tv_nsec) / 1e6;
    printf("%-8s wall %6.1f  user %6.1f  sys %6.1f ms  vol %3ld  invol %3ld\n", name, wall,
           ms(r.ru_utime) - ms(r0.ru_utime), ms(r.ru_stime) - ms(r0.ru_stime),
           r.ru_nvcsw - r0.ru_nvcsw, r.ru_nivcsw - r0.ru_nivcsw);
}
int main(void) {
    volatile unsigned long x = 0;
    start();                                   /* 1. CPU-bound: pure arithmetic */
    for (unsigned long i = 0; i < 100000000UL; i++) x += i % 7;
    report("compute"); (void)x;

    int fd = open("/dev/null", O_WRONLY);      /* 2. many tiny system calls */
    start();
    for (int i = 0; i < 300000; i++) if (write(fd, "x", 1) != 1) return 1;
    report("syscalls"); close(fd);

    struct timespec one_ms = {0, 1000000};     /* 3. I/O-bound-like: 200 short waits */
    start();
    for (int i = 0; i < 200; i++) nanosleep(&one_ms, NULL);
    report("waiting");
    return 0;
}

compute  wall  224.7  user  224.0  sys    0.0 ms  vol   0  invol  11
syscalls wall  249.1  user   64.6  sys  184.2 ms  vol   0  invol   5
waiting  wall  234.3  user    1.8  sys    5.3 ms  vol 200  invol   0

২ · কখন সিদ্ধান্ত নিতে হয় — চারটি মুহূর্ত, preemptive আর non-preemptive

CPU scheduling মানে ready অবস্থার প্রসেসগুলোর মধ্যে কে পরের বার CPU পাবে আর কতক্ষণ, তা ঠিক করা। কিন্তু scheduler সারাক্ষণ ভাবে না; নির্দিষ্ট কিছু ঘটনার পর তাকে ডাকা হয়। পর্ব ৮-এর প্রসেস-অবস্থার ছবিতে ফিরে গেলে এমন মুহূর্ত ঠিক চারটি:

১ আর ৪-এ বিকল্প নেই — চলতি প্রসেস নিজেই আর চলতে পারছে না, তাই অন্য কাউকে বাছতেই হবে (ready queue খালি থাকলে CPU idle থাকে)। ২ আর ৩-এ সিদ্ধান্ত ঐচ্ছিক। যে scheduler শুধু ১ আর ৪-এ সিদ্ধান্ত নেয়, সে non-preemptive (বা cooperative): একবার CPU পেলে প্রসেস নিজে না ছাড়া পর্যন্ত রাখে। যে scheduler ২ আর ৩-এও সিদ্ধান্ত নিতে পারে, সে preemptive: চলতি প্রসেসের কাছ থেকে CPU কেড়ে নিতে পারে (preemption). কেড়ে নেওয়ার যন্ত্রটি timer interrupt, যা পর্ব ৯-এ দেখেছেন; Windows 3.x বা Classic Mac OS-এর cooperative যুগের গল্পও সেখানে আছে।

নিচের stepper-এ তিনটি প্রসেস A, B, C নিয়ে চারটি মুহূর্ত একে একে দেখুন। ধরা হয়েছে সিস্টেমটি preemptive আর A একটি interactive প্রসেস, তাই তার অগ্রাধিকার বেশি; প্রতিটি ধাপে non-preemptive হলে কী হতো, সেটিও লেখা আছে।

1A calls read() on the disk    (running -> waiting)2timer interrupt while B runs  (running -> ready)3disk interrupt: A's data ready (waiting -> ready)4A calls exit()                (running -> terminated)

Preemption-এর দাম

Preemptive scheduling ছাড়া আধুনিক interactive সিস্টেম কল্পনা করা যায় না — একটি অসীম লুপ পুরো কম্পিউটার জমিয়ে দিতে পারত। কিন্তু এর দামও আছে। প্রথমত, প্রতিটি অতিরিক্ত পালাবদল একটি context switch, যার খরচ পর্ব ৯-এ মেপেছেন। দ্বিতীয়ত, প্রসেস এখন যেকোনো দুই নির্দেশের মাঝখানে থামতে পারে। দুটি প্রসেস বা thread একই ডেটা ভাগ করলে, একজন অর্ধেক লেখা অবস্থায় থামলে অন্যজন ভুল মান পড়তে পারে — এটি race condition, যার সমাধান মডিউল ৪-এর বিষয়। তৃতীয়ত, kernel-এর নিজের ডেটা-কাঠামোও একই ঝুঁকিতে পড়ে; তাই আধুনিক kernel lock আর “preemption বন্ধ” অংশ দিয়ে নিজেকে রক্ষা করে।

৩ · Scheduler কোথায় চলে — স্তর, dispatcher আর dispatch latency

পর্ব ৮-এ তিন স্তরের scheduler দেখেছেন। সংক্ষেপে মনে করিয়ে দিই, কারণ “CPU scheduling” বলতে এই মডিউলে কেবল একটিকেই বোঝানো হবে:

Short-term scheduler সিদ্ধান্ত নেয় কে চলবে; সিদ্ধান্তটি কাজে পরিণত করে dispatcher — পুরোনোর অবস্থা রাখা, নতুনের অবস্থা ফেরানো, user mode-এ ফিরে তার সংরক্ষিত PC-তে লাফ। এক প্রসেস থামানো থেকে আরেকটি চালু পর্যন্ত সময় dispatch latency. এর খুঁটিনাটি পর্ব ৯-এ ধাপে ধাপে দেখেছেন; এখানে শুধু একটি কথা মনে রাখুন — Gantt chart-এর অঙ্কে সাধারণত dispatch latency শূন্য ধরা হয়। প্রশ্নে switch-এর খরচ দেওয়া থাকলে তা chart-এ আলাদা ঘর হিসেবে বসাতে হয়, যেমন পর্ব ৯-এর Round Robin উদাহরণে।

Scheduler কি আলাদা একটি প্রোগ্রাম?

অনেকে কল্পনা করেন, scheduler একটি আলাদা প্রসেস, যে পাশে বসে সবার দিকে নজর রাখে। বাস্তবে Linux-এ এমন কোনো প্রসেস নেই। Scheduler হলো kernel-এর কিছু ফাংশন (মূলটি schedule()), আর তা চলে সেই CPU-তেই, সেই মুহূর্তের প্রসেসের kernel-অংশ হিসেবে: প্রসেস block হতে গিয়ে নিজেই schedule() ডাকে (মুহূর্ত ১, ৪), অথবা interrupt বা system call থেকে ফেরার পথে kernel “reschedule দরকার” পতাকা দেখে ডাকে (মুহূর্ত ২, ৩)। প্রতিটি CPU-র নিজস্ব run queue থাকে — ready queue-র বাস্তব রূপ — আর প্রতিটি CPU নিজের জন্য নিজেই বাছাই করে; মাঝে মাঝে CPU-গুলোর মধ্যে কাজের ভার সমান করা হয় (পর্ব ২০)। Windows-এও আলাদা কোনো “scheduler thread” নেই — dispatcher-এর কোড প্রতিটি প্রসেসরে kernel-এর ভেতরেই চলে। শিক্ষণ-OS xv6 ব্যতিক্রম: সেখানে প্রতিটি CPU-র একটি নিজস্ব scheduler-লুপ আছে (পর্ব ৫৮)।

Linux প্রতিটি task-এর scheduling-এর হিসাবও রাখে, আর /proc-এ দেখায়। /proc/<pid>/schedstat ফাইলে তিনটি সংখ্যা: task মোট কত ন্যানোসেকেন্ড CPU-তে চলেছে, কত ন্যানোসেকেন্ড run queue-তে CPU-র অপেক্ষায় ছিল, আর কতগুলো আলাদা পালা (timeslice) পেয়েছে (schedstat). দ্বিতীয় সংখ্যাটিই আসলে এই পর্বের “waiting time”-এর বাস্তব রূপ। আর ps দিয়ে দেখা যায় প্রসেসের scheduling class, nice মান, অগ্রাধিকার আর সে শেষবার কোন CPU-তে চলেছে।

show() {   # three numbers: ns on CPU, ns waiting in the run queue, timeslices
  read run wait slices < /proc/$$/schedstat
  echo "$1 on-CPU $((run / 1000000)) ms, waited $((wait / 1000000)) ms, slices $slices"
}
show "start      :"
for ((i = 0; i < 300000; i++)); do :; done      # a CPU burst
show "after loop :"
sleep 0.2                                        # an I/O-like wait
show "after sleep:"
echo
ps -o pid,cls,ni,pri,psr,comm -p $$                      # this shell
nice -n 10 sh -c 'ps -o pid,cls,ni,pri,psr,comm -p $$'   # a "nicer" child

start      : on-CPU 3 ms, waited 1 ms, slices 7
after loop : on-CPU 752 ms, waited 49 ms, slices 424
after sleep: on-CPU 754 ms, waited 49 ms, slices 427

    PID CLS  NI PRI PSR COMMAND
      2  TS  10   9   0 bash
    PID CLS  NI PRI PSR COMMAND
      5  TS  19   0   1 sh

৪ · মাপকাঠি — কোন সংখ্যা দিয়ে scheduler-কে বিচার করবেন

“কোন scheduling algorithm ভালো?” — এই প্রশ্নের উত্তর দিতে আগে ঠিক করতে হয় ভালো মানে কী। পাঠ্যবইগুলো কয়েকটি scheduling criteria ব্যবহার করে। প্রথমে প্রতিটি প্রসেসের জন্য চারটি মৌলিক সময় লিখে নিন:

• Arrival time (AT): প্রসেস কখন ready queue-তে পৌঁছাল।
• Burst time (BT): তার মোট কতটুকু CPU সময় দরকার।
• Completion time (CT): কখন তার কাজ পুরো শেষ হলো (কিছু বইয়ে finish বা exit time).
• প্রথম CPU পাওয়ার সময়: সে প্রথমবার কখন CPU-তে উঠল (কিছু বইয়ে start time).

এই চারটি থেকেই সব প্রসেস-ভিত্তিক মাপকাঠি আসে:

সূত্রগুলোর পেছনের যুক্তি

কেন WT = TAT − BT? একটি প্রসেস আসার পর থেকে শেষ হওয়া পর্যন্ত (TAT) প্রতিটি মুহূর্তে সে দুটির একটি করছে: CPU-তে চলছে, অথবা ready queue-তে অপেক্ষা করছে — যদি তার একটিই CPU burst থাকে, অর্থাৎ মাঝে কোনো I/O নেই। চলার মোট সময় ঠিক BT. তাই বাকিটা অপেক্ষা: WT = TAT − BT. প্রসেসের মাঝে I/O burst থাকলে TAT-এর মধ্যে তৃতীয় একটি অংশ ঢোকে — I/O-তে কাটানো সময় — তখন সঠিক সূত্র: WT = TAT − (মোট CPU burst) − (মোট I/O সময়)। পরীক্ষার বেশিরভাগ অঙ্কে একটিই CPU burst থাকে, তাই প্রথম সূত্রটিই চলে; কিন্তু অনুশীলন ২-এ দেখবেন I/O থাকলে সেটি কীভাবে ভুল উত্তর দেয়।

Response time আর waiting time কবে সমান? Non-preemptive scheduling-এ প্রসেস একবার CPU পেলে শেষ না হওয়া পর্যন্ত নামে না, তাই তার সব অপেক্ষা প্রথম CPU পাওয়ার আগেই — RT = WT. Preemptive scheduling-এ প্রসেস মাঝপথে নামলে আবার অপেক্ষা করে, তাই WT ≥ RT. খেয়াল করুন, পাঠ্যবইয়ের সংজ্ঞায় response time হলো “প্রথম সাড়া শুরু হওয়া পর্যন্ত সময়”, প্রোগ্রামের পুরো উত্তর ছাপা শেষ হওয়া পর্যন্ত নয়। Gantt chart-এর অঙ্কে একে প্রথমবার CPU পাওয়া হিসেবেই মাপা হয়।

Throughput আর utilisation কোন সময়-সীমায়? সাধারণত পুরো chart-এর সময়-সীমায় — t = 0 থেকে শেষ প্রসেসের CT পর্যন্ত। কিছু বই প্রথম প্রসেস আসার মুহূর্ত থেকে গোনে। প্রথম প্রসেস t = 0-তে এলে দুটি একই; না এলে প্রশ্নের নিয়ম দেখে নিন, আর উত্তরে কোন সীমা নিয়েছেন তা লিখে দিন।

৫ · লক্ষ্যের টানাপোড়েন — সবকিছু একসাথে ভালো করা যায় না

সব মাপকাঠি একসাথে সর্বোত্তম করা সম্ভব হলে একটিই “সেরা” algorithm থাকত। বাস্তবে এগুলো একে অপরের বিরুদ্ধে টানে। তিনটি গুরুত্বপূর্ণ সংঘাত:

• Throughput বনাম response time: Response কমাতে ঘন ঘন পালাবদল দরকার — প্রত্যেকে দ্রুত একটু CPU পাক। কিন্তু প্রতিটি পালাবদল একটি context switch, আর cache-TLB আবার ভরার খরচ; ফলে উপকারী কাজ কমে, throughput পড়ে। উল্টো দিকে, প্রত্যেককে লম্বা সময় দিলে throughput বাড়ে, কিন্তু অন্যেরা অপেক্ষায় থাকে।
• গড় waiting বনাম fairness: সবচেয়ে ছোট কাজ আগে চালালে গড় waiting time সবচেয়ে কম হয় (পর্ব ১৭-এ এর প্রমাণ), কিন্তু ছোট কাজের স্রোত চলতে থাকলে লম্বা কাজটি হয়তো কখনোই সুযোগ পায় না — starvation.
• Utilisation বনাম predictability: CPU-কে সবসময় ১০০% ব্যস্ত রাখলে নতুন কাজ এসে লম্বা সারিতে পড়ে; অপেক্ষার সময় খুব অনিশ্চিত হয়ে যায় (অংশ ৭-এর queueing তত্ত্ব দেখাবে, utilisation ১০০%-এর কাছে গেলে অপেক্ষা হঠাৎ লাফিয়ে বাড়ে)। Real-time সিস্টেম তাই ইচ্ছা করে কিছু CPU খালি রাখে।

তাই কোন মাপকাঠি সবচেয়ে জরুরি, তা সিস্টেমের ধরন ঠিক করে:

৬ · Gantt chart পড়া ও আঁকা — একটি পূর্ণ সমাধান

Scheduling-এর অঙ্কের প্রধান যন্ত্র Gantt chart — একটি সময়রেখা, যেখানে প্রতিটি ঘরে লেখা থাকে কোন সময় থেকে কোন সময় পর্যন্ত CPU-তে কে ছিল। নামটি এসেছে Henry Gantt থেকে, যিনি বিংশ শতকের শুরুতে প্রকল্পের কাজ সাজাতে এমন চার্ট জনপ্রিয় করেন। ঠিকভাবে আঁকার নিয়ম:

1. সময়রেখা শুরু হয় t = 0 থেকে, আর প্রতিটি ঘরের দুই প্রান্তে সময় লেখা থাকে। পাশাপাশি দুটি ঘরের মাঝের সংখ্যাটি একটির শেষ আর অন্যটির শুরু।
2. কোনো প্রসেস তার arrival time-এর আগে CPU পেতে পারে না। Scheduler কেবল সেই মুহূর্তে ready queue-তে যারা আছে, তাদের মধ্য থেকেই বাছে।
3. CPU খালি থাকলে তা দেখাতে হবে। Ready queue খালি আর পরের প্রসেস তখনো আসেনি — এমন সময় chart-এ একটি “idle” ঘর বসে। এই ঘর ভুলে গেলে পরের প্রত্যেকের CT আর সব গড় ভুল হয়।
4. প্রতিটি ঘরের দৈর্ঘ্য যোগ করে মেলান: প্রতিটি প্রসেসের ঘরগুলোর মোট দৈর্ঘ্য তার burst time-এর সমান হতে হবে, আর chart-এর মোট দৈর্ঘ্য = সব burst-এর যোগফল + সব idle ঘর।
5. সমান অবস্থায় নিয়ম আগে ঠিক করুন — যেমন দুজন একই সময়ে এলে ছোট নম্বরের প্রসেস আগে। প্রশ্নে বলা না থাকলে এই সাধারণ নিয়মটি লিখে দিন।

উদাহরণ হিসেবে সবচেয়ে সরল নীতিটি নেওয়া হলো — FCFS (first-come, first-served): যে আগে এসেছে, সে আগে পাবে, আর একবার পেলে শেষ না হওয়া পর্যন্ত রাখবে। নীতিটির বিশ্লেষণ পর্ব ১৭-এ; এখানে লক্ষ্য শুধু chart আঁকা আর মাপা। প্রসেসের টেবিল (সময় ms-এ):

1t=0 : P1 arrives, CPU free -> P1 runs2t=1 : P2 arrives -> ready queue3t=2 : P3 arrives -> ready queue4t=5 : P1 done -> P2 runs5t=8 : P2 done -> P3 runs6t=10: P3 done, queue empty -> idle7t=12: P4 arrives -> P4 runs8t=16: P4 done -> chart complete

এবার এই chart থেকে প্রতিটি প্রসেসের মাপকাঠি বের করুন। কৌশলটি সবসময় একই: প্রথমে টেবিলে AT, BT আর chart থেকে CT লিখুন, তারপর একে একে সূত্র বসান।

1table : AT, BT given; CT and first-run from the chart2P1    : TAT = 5-0, WT = TAT-5, RT = 0-03P2    : TAT = 8-1, WT = TAT-3, RT = 5-14P3    : TAT = 10-2, WT = TAT-2, RT = 8-25P4    : TAT = 16-12, WT = TAT-4, RT = 12-126totals: averages, throughput, utilisation

হিসাবটি কোড দিয়ে মেলান

নিচের ছোট calculator একটি প্রসেস টেবিল আর একটি নির্দিষ্ট Gantt ক্রম নেয় — কোন প্রসেস কত ms চলবে, পরপর — আর arrival দেখে দরকার হলে idle ঘর বসায়। এটি কোনো algorithm নয়; ক্রমটি আপনি দেন, সে শুধু মাপে। একটি প্রসেসকে কয়েক টুকরোয় ভাগ করেও দিতে পারেন (preemptive chart), যেমন ["P1", 2], ["P2", 3], ["P1", 3]. দুটি ক্রম চালানো হয়েছে: FCFS-এর ক্রম, আর P2-P3 অদলবদল করা আরেকটি ক্রম।

// Scheduling metrics from a process table and a GIVEN Gantt order (deterministic).
const procs = { P1: [0, 5], P2: [1, 3], P3: [2, 2], P4: [12, 4] };  // name: [arrival, burst] in ms

function evaluate(label, order) {           // order: [process, run length] slices, in time order
  let t = 0, busy = 0;
  const gantt = [], ct = {}, first = {}, ran = {};
  for (const [p, len] of order) {
    const at = procs[p][0];
    if (t < at) { gantt.push(`idle ${t}-${at}`); t = at; }   // CPU must wait for the arrival
    if (!(p in first)) first[p] = t;                          // first time on the CPU
    gantt.push(`${p} ${t}-${t + len}`);
    t += len; busy += len; ran[p] = (ran[p] || 0) + len; ct[p] = t;
  }
  console.log(`--- ${label}\nGantt: |${gantt.join("|")}|`);
  const row = (cells) => console.log(cells.map((v) => String(v).padStart(4)).join(""));
  row(["P", "AT", "BT", "CT", "TAT", "WT", "RT"]);
  const names = Object.keys(procs), sum = { tat: 0, wt: 0, rt: 0 };
  for (const p of names) {
    const [at, bt] = procs[p];
    if (ran[p] !== bt) throw new Error(`${p}: slices add up to ${ran[p]}, burst is ${bt}`);
    const tat = ct[p] - at, wt = tat - bt, rt = first[p] - at;
    sum.tat += tat; sum.wt += wt; sum.rt += rt;
    row([p, at, bt, ct[p], tat, wt, rt]);
  }
  const n = names.length, span = t - Math.min(...names.map((p) => procs[p][0]));
  console.log(`avg TAT ${sum.tat / n}, avg WT ${sum.wt / n}, avg RT ${sum.rt / n}`);
  console.log(`throughput ${n}/${span} = ${(n / span).toFixed(3)} per ms, ` +
              `CPU busy ${busy}/${span} = ${((100 * busy) / span).toFixed(1)}%`);
}

evaluate("FCFS order", [["P1", 5], ["P2", 3], ["P3", 2], ["P4", 4]]);
evaluate("another order", [["P1", 5], ["P3", 2], ["P2", 3], ["P4", 4]]);

--- FCFS order
Gantt: |P1 0-5|P2 5-8|P3 8-10|idle 10-12|P4 12-16|
   P  AT  BT  CT TAT  WT  RT
  P1   0   5   5   5   0   0
  P2   1   3   8   7   4   4
  P3   2   2  10   8   6   6
  P4  12   4  16   4   0   0
avg TAT 6, avg WT 2.5, avg RT 2.5
throughput 4/16 = 0.250 per ms, CPU busy 14/16 = 87.5%
--- another order
Gantt: |P1 0-5|P3 5-7|P2 7-10|idle 10-12|P4 12-16|
   P  AT  BT  CT TAT  WT  RT
  P1   0   5   5   5   0   0
  P2   1   3  10   9   6   6
  P3   2   2   7   5   3   3
  P4  12   4  16   4   0   0
avg TAT 5.75, avg WT 2.25, avg RT 2.25
throughput 4/16 = 0.250 per ms, CPU busy 14/16 = 87.5%

৭ · Algorithm বিচারের চার পদ্ধতি

নতুন কোনো scheduling algorithm প্রস্তাব করলে প্রশ্ন ওঠে: সে কি আগেরটির চেয়ে ভালো? উত্তর খোঁজার চারটি পথ আছে, প্রতিটি আগেরটির চেয়ে বাস্তবের কাছাকাছি — আর বেশি খরচের।

১. Deterministic modelling — একটি নির্দিষ্ট উদাহরণে হাতে হিসাব

একটি নির্দিষ্ট প্রসেস টেবিল নিয়ে প্রতিটি algorithm-এর Gantt chart আঁকা আর গড় waiting বা turnaround তুলনা করা — ঠিক যা অংশ ৬-এ করলেন। এটিই deterministic modelling. সুবিধা: সরল, দ্রুত, সংখ্যাগুলো নিখুঁত, আর ধারণা তৈরিতে দারুণ — পরীক্ষার প্রায় সব scheduling-অঙ্ক এই ধরনের। দুর্বলতা: উত্তর শুধু সেই টেবিলের জন্য সত্য। অন্য burst বা arrival-এ ফল উল্টে যেতে পারে। তবে অনেক উদাহরণে একই প্রবণতা দেখলে সাধারণ সূত্রের ইঙ্গিত মেলে, যা পরে প্রমাণ করা যায় (যেমন SJF-এর সর্বোত্তমতা, পর্ব ১৭)।

২. Queueing model — গড় আচরণের গণিত

বাস্তব সিস্টেমে প্রসেস আসে এলোমেলোভাবে, burst-ও এলোমেলো। কিন্তু তাদের বণ্টন মাপা যায় — গড়ে প্রতি সেকেন্ডে কতগুলো আসে (arrival rate λ), গড় burst কত। কম্পিউটারকে তখন কয়েকটি “সার্ভার” (CPU, ডিস্ক) আর তাদের সামনের সারির একটি জাল হিসেবে দেখা যায়, আর queueing তত্ত্ব দিয়ে গড় সারির দৈর্ঘ্য, গড় অপেক্ষা, utilisation হিসাব করা যায় — এটিই queueing model. এর সবচেয়ে সাধারণ আর সবচেয়ে কাজের ফলটি Little-এর সূত্র:

সূত্রটি অবাক করার মতো সাধারণ: আগমনের বণ্টন যা-ই হোক, সারির নিয়ম (FCFS, priority, যেকোনো) যা-ই হোক, সিস্টেম দীর্ঘ সময়ে স্থিতিশীল থাকলেই (যত আসে, গড়ে তত বেরোয়) এটি সত্য। “সারি” যেকোনো সীমানা দিয়ে আঁকা যায় — শুধু ready queue, শুধু ডিস্কের সারি, বা পুরো সিস্টেম; তিনটি রাশি একই সীমানার জন্য মাপলেই হলো।

কেন সত্য — একটি সরল যুক্তি: লম্বা একটি সময় T ধরে প্রতিটি মুহূর্তে সারিতে কতজন আছে, তা একটি লেখচিত্রে আঁকুন (n(t)). লেখচিত্রের নিচের ক্ষেত্রফলকে দুইভাবে গোনা যায়। এক, প্রতিটি মুহূর্তের n(t) যোগ করে: ক্ষেত্রফল = (গড় n) × T. দুই, প্রতিটি প্রসেস সারিতে যতক্ষণ ছিল, ততক্ষণ সে লেখচিত্রে এক একক উচ্চতা যোগ করেছে; তাই ক্ষেত্রফল = সব প্রসেসের অপেক্ষার যোগফল = (আসা প্রসেসের সংখ্যা) × (গড় W). আসা প্রসেসের সংখ্যা ≈ λ × T. দুই হিসাব সমান করে: (গড় n) × T = λ × T × W, অর্থাৎ n = λW. (শুরু আর শেষে আংশিক থাকা প্রসেসগুলোর জন্য সামান্য ভুল থাকে, যা T লম্বা হলে নগণ্য হয়ে যায়; John D. C. Little ১৯৬১ সালে এর কঠোর প্রমাণ প্রকাশ করেন।)

সমাধান করা উদাহরণ: একটি সার্ভারে গড়ে প্রতি সেকেন্ডে ৭টি প্রসেস ready queue-তে আসে, আর প্রতিটি সেখানে গড়ে ২ সেকেন্ড অপেক্ষা করে। গড়ে queue-তে কতজন থাকে? n = ৭ × ২ = ১৪টি প্রসেস. উল্টো দিক থেকে: একটি ওয়েব সার্ভার প্রতি সেকেন্ডে ৫০টি অনুরোধ নেয়, আর যেকোনো মুহূর্তে গড়ে ১০টি অনুরোধ ভেতরে থাকে (মাপা যায়)। একটি অনুরোধ গড়ে কতক্ষণ থাকে? W = n ÷ λ = ১০ ÷ ৫০ = ০.২ সেকেন্ড = ২০০ ms. খেয়াল করুন, এখানে কোনো scheduling algorithm জানতে হয়নি।

আরও গভীর queueing মডেল (যেমন আগমন Poisson আর সেবা-সময় exponential ধরলে, যাকে M/M/1 বলে) একটি গুরুত্বপূর্ণ সত্য দেখায়: utilisation ρ যত ১-এর কাছে যায়, গড় অপেক্ষা তত দ্রুত বাড়ে — ঐ মডেলে সিস্টেমে গড় সময় সেবা-সময়ের ১/(১ − ρ) গুণ। ৫০% ব্যস্ত CPU-তে তা ২ গুণ, ৯০%-এ ১০ গুণ, ৯৯%-এ ১০০ গুণ। অংশ ৫-এর “utilisation বনাম predictability” টানাপোড়েনের গাণিতিক রূপ এটিই। দুর্বলতা: মডেলগুলো বাস্তবের তুলনায় অনেক সরল অনুমান করে, আর জটিল algorithm-এর জন্য গণিত দ্রুত কঠিন হয়ে যায়।

৩. Simulation — কম্পিউটারে কম্পিউটার

একটি প্রোগ্রাম বানানো হয়, যেখানে একটি ঘড়ি, ready queue আর scheduler-এর নিয়ম আছে; ঘড়ি এগোয়, প্রসেস আসে, চলে, শেষ হয়, আর প্রোগ্রাম সব মাপকাঠি গোনে — এটি simulation. প্রসেসের ধারা আসতে পারে random-সংখ্যা থেকে (মাপা বণ্টন অনুযায়ী), অথবা আরও নির্ভরযোগ্যভাবে একটি আসল সিস্টেমের রেকর্ড করা ঘটনার তালিকা (trace) থেকে — তখন একই বাস্তব কাজের ধারা দিয়ে একাধিক algorithm-কে হুবহু একই পরীক্ষায় ফেলা যায়। দুর্বলতা: ভালো simulator বানাতে সময় লাগে, আর তার সরলীকরণ (যেমন context switch-এর খরচ শূন্য ধরা) ফল বাঁকাতে পারে।

৪. Implementation — আসল OS-এ বসিয়ে মাপা

শেষ পরীক্ষা: algorithm-টি আসল kernel-এ লিখে, আসল কাজ চালিয়ে মাপা। এটিই সবচেয়ে নির্ভুল — হার্ডওয়্যার, cache, interrupt, সব বাস্তব। কিন্তু খরচ বেশি: kernel কোড লেখা আর পরীক্ষা কঠিন, ভুল হলে পুরো সিস্টেম অস্থির হয়। আরেকটি সূক্ষ্ম সমস্যা: প্রোগ্রামাররা নিয়ম শিখে আচরণ বদলান — scheduler ছোট burst-কে অগ্রাধিকার দিলে কেউ লম্বা হিসাবের মাঝে অপ্রয়োজনীয় ছোট I/O বসিয়ে নিজেকে “interactive” দেখাতে পারেন। Linux-এ নতুন scheduler বা বড় পরিবর্তন ঢোকার আগে বহু benchmark আর বাস্তব কাজের ফল দেখানো হয়; আর ২০২৪ সালে Linux 6.12-এ যুক্ত হওয়া sched_ext scheduling নীতিকে BPF প্রোগ্রাম হিসেবে লিখে চলন্ত kernel-এ পরীক্ষা করার সুযোগ দিয়েছে (পর্ব ২১, ৫৫)।

৮ · সামনে কী — algorithm-গুলোর মানচিত্র

এই পর্বের মাপকাঠি আর Gantt chart নিয়ে এবার আপনি পরের পাঁচটি পর্বের জন্য প্রস্তুত। প্রতিটি পর্ব একটি প্রশ্নের উত্তর খোঁজে:

আর পর্ব ২১-এ সব মিলবে একটি আসল scheduler-এ — Linux-এর CFS, তার উত্তরসূরি EEVDF, nice আর cgroup.

৯ · AI-এর যুগে scheduling-এর হিসাব

Scheduling-এর অঙ্ক AI-কে দিলে উত্তর দ্রুত আসে, আর দেখতে নিখুঁত টেবিলের মতো লাগে। কিন্তু এখানে ছোট একটি ভুল — একটি idle ফাঁক বাদ পড়া, বা arrival বিয়োগ না করা — পুরো উত্তর নষ্ট করে, আর টেবিল দেখে তা ধরা যায় না। এই পর্বের নিয়মগুলো দিয়ে যাচাই করুন:

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

• Gantt chart নিজে এঁকে প্রতিটি ঘরের শুরু arrival-এর পরে কি না, আর idle ফাঁক আছে কি না দেখেছি
• প্রতিটি প্রসেসের ঘরগুলোর মোট দৈর্ঘ্য তার burst-এর সমান কি না মিলিয়েছি
• সূত্রগুলো (TAT = CT − AT, WT = TAT − BT, RT = প্রথম CPU − AT) হাতে বসিয়ে অন্তত একটি প্রসেস যাচাই করেছি, আর calculator-এ পুরোটা মিলিয়েছি
• Throughput আর utilisation কোন সময়-সীমায় (t = 0 থেকে, নাকি প্রথম arrival থেকে) মাপা হয়েছে, তা স্পষ্ট করেছি
• Linux-এর কমান্ড আমার নিজের OS আর kernel-এ চালিয়ে দেখেছি, man page (man getrusage, man ps) আর kernel-এর নথি মিলিয়েছি
• sudo দিয়ে অগ্রাধিকার বা real-time class বদলানোর পরামর্শ মাপা কারণ ছাড়া মানিনি