FCFS, SJF আর SRTF — Gantt chart দিয়ে হিসাব

১ · শুরুর আগে — মাপকাঠি আর Gantt chart এক নজরে

পর্ব ১৬-এ দেখেছেন, একটি প্রসেসের জীবন কাটে দুই রকম পালায়: CPU-তে টানা হিসাব (CPU burst) আর I/O-র অপেক্ষা। Short-term scheduler-এর কাজ একটাই — ready queue-এ যারা অপেক্ষা করছে, তাদের মধ্যে পরের CPU কে পাবে, তা ঠিক করা। কোন নিয়মে ঠিক করবে, সেটিই scheduling নীতি। এই পর্বে চারটি নীতি: FCFS, SJF, SRTF আর HRRN.

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

মাপার জন্য প্রতিটি প্রসেসের দুটি তথ্য লাগে: arrival time (AT, কখন ready queue-তে এল) আর burst time (BT, কতটুকু CPU-সময় লাগবে)। Scheduling শেষে Gantt chart থেকে পাওয়া যায় completion time (CT). বাকি তিনটি মাপ পর্ব ১৬-এর সংজ্ঞা অনুযায়ীই:

এখানে ধরে নেওয়া হয়েছে প্রতিটি প্রসেসের একটিই CPU burst আর কোনো I/O নেই, আর context switch-এর খরচ শূন্য — পরীক্ষার প্রায় সব অঙ্কে এটিই নিয়ম (প্রশ্নে অন্য কিছু বলা থাকলে সেটিই মানবেন; switch-এর খরচ ধরলে কী হয়, পর্ব ৯-এ দেখেছেন)। Non-preemptive নীতিতে একজন একবারেই পুরো burst চালায়, তাই সেখানে RT = WT. Preemptive নীতিতে একজন কয়েক টুকরোয় চলতে পারে, তখন RT ছোট হলেও WT বড় হতে পারে।

দুটি শব্দ মনে রাখুন। Non-preemptive নীতিতে একবার CPU পেলে প্রসেসটি নিজে শেষ না হওয়া পর্যন্ত (বা I/O-তে না যাওয়া পর্যন্ত) কেউ তাকে সরায় না — FCFS, SJF, HRRN এমন। Preemptive নীতিতে মাঝপথে থামানো যায় — SRTF এমন, আর পর্ব ১৮-এর Round Robin-ও। আরেকটি জিনিস: CPU যখন কারও কাজ পায় না — ready queue খালি — সেই idle সময় Gantt chart-এ আলাদা খোপে লিখতে হয়। পরীক্ষায় এই ফাঁক বাদ দেওয়া খুব প্রচলিত ভুল।

২ · FCFS — যে আগে আসে, সে আগে পায়

নিয়ম: ready queue একটি সাধারণ FIFO queue. নতুন প্রসেস এলে সারির পেছনে দাঁড়ায়; CPU খালি হলে সারির মাথার জন সেটি পায় আর পুরো burst শেষ করে তবেই ছাড়ে। সমান arrival time হলে প্রশ্নে দেওয়া ক্রম (P1 আগে, তারপর P2…) মানা হয়। বাস্তবায়ন সবচেয়ে সহজ: একটি linked list, যোগ করা আর বের করা দুটোই O(1). বোঝাও সহজ, আর এক অর্থে ন্যায্য — কেউ লাইন ভেঙে আগে যায় না।

কিন্তু “ন্যায্য” মানে “ভালো” নয়। পাঠ্যবইয়ের সবচেয়ে বিখ্যাত উদাহরণটি দেখুন: তিনটি প্রসেস একসাথে (t = 0) এসেছে, burst P1 = ২৪, P2 = ৩, P3 = ৩ ms. প্রথমে P1, P2, P3 ক্রমে, তারপর উল্টো করে P2, P3, P1 ক্রমে চালিয়ে দেখুন।

1order A: P1(24) P2(3) P3(3)2  24-27  P2 runs3  27-30  P3 runs  -> avg WT 174order B: P2(3) P3(3) P1(24)5   3-6   P3 runs6   6-30  P1 runs  -> avg WT 3

এই ঘটনার নাম convoy effect — মহাসড়কে একটি ধীর ট্রাকের পেছনে বাস, কার, মোটরসাইকেলের লম্বা সারি, ওভারটেকের উপায় নেই। আসল সিস্টেমে ক্ষতি আরও বড়, কারণ পুরো যন্ত্রের ব্যবহার খারাপ হয়। একটি CPU-bound প্রসেস CPU ধরে রাখার সময় অনেকগুলো I/O-bound প্রসেস নিজেদের I/O শেষ করে ready queue-তে জমে — ডিস্ক আর নেটওয়ার্ক তখন অলস। তারপর CPU-bound প্রসেসটি I/O-তে গেলে ছোটরা ঝটপট নিজেদের burst সেরে আবার I/O-তে যায় — এবার CPU অলস। দুই পক্ষ পালা করে অলস থাকে, অথচ একসাথে দুটোই ব্যস্ত থাকতে পারত।

৩ · SJF — সবচেয়ে ছোট কাজটি আগে

উপরের উদাহরণের শিক্ষা পরিষ্কার: ছোট কাজ আগে গেলে গড় অপেক্ষা কমে। এই ধারণাকে নিয়ম বানালেই Shortest Job First (SJF). সঠিক নামটি আসলে “shortest-next-CPU-burst” — পুরো প্রসেসের দৈর্ঘ্য নয়, তার পরের CPU burst-এর দৈর্ঘ্য দেখা হয়। William Stallings-এর বইয়ে একই নীতির নাম SPN (Shortest Process Next).

সবচেয়ে প্রচলিত ভুল হলো এখনো না আসা প্রসেসকে বাছাইয়ে ধরা। SJF ভবিষ্যৎ দেখে না: t = 0-তে শুধু P1 থাকলে P1-ই চলবে, আর non-preemptive বলে পরে ছোট কেউ এলেও তাকে থামানো যাবে না। একটি উদাহরণ (সময় ms-এ):

SJF:  │ P1 0-7 │ P3 7-8 │ P2 8-12 │ P4 12-16 │

ধাপে ধাপে: t = 0-তে শুধু P1 এসেছে, তাই P1 চলে ০–৭. t = ৭-এ তিনজন অপেক্ষায়: P2 (৪), P3 (১), P4 (৪). সবচেয়ে ছোট P3 → ৭–৮. t = ৮-এ P2 আর P4 দুজনেরই burst ৪ — tie. নিয়ম অনুযায়ী আগে এসেছে P2 (AT ২), তাই P2 → ৮–১২, তারপর P4 → ১২–১৬. একই টেবিলে FCFS চালালে (P1, P2, P3, P4 ক্রমে) গড় WT হতো ৪.৭৫ — SJF বাঁচাল প্রতি প্রসেসে গড়ে পৌনে এক ms. পরে simulator দিয়ে দুটোই যাচাই করবেন।

SJF-এর ready queue সাধারণত একটি min-heap (key = burst), যোগ-বের করা O(log n) — বিস্তারিত DSA কোর্সের heap পর্বে. আসল কঠিন অংশ ডেটা স্ট্রাকচার নয়, burst-এর দৈর্ঘ্যটাই আগে জানা যায় না (অংশ ৬).

৪ · প্রমাণ — কেন SJF গড় অপেক্ষা সবচেয়ে কম রাখে

বিশ্ববিদ্যালয়ের পরীক্ষায় প্রায়ই আসে: “প্রমাণ করুন, SJF গড় waiting time সর্বনিম্ন করে।” দাবিটি সব অবস্থায় সত্য নয়, তাই আগে শর্তগুলো স্পষ্ট করে লিখতে হয়।

প্রমাণ (exchange argument): যেকোনো একটি ক্রম নিন। ধরুন সেখানে কোথাও পাশাপাশি দুটি কাজ X আর Y আছে — X আগে, Y ঠিক পরে — যেখানে X-এর burst a, Y-এর burst b, আর a > b. এমন জোড়াকে বলি “উল্টো জোড়া”। X শুরু হয় কোনো এক সময় s-এ।

1. বদলের আগে: X-এর অপেক্ষা s, Y-এর অপেক্ষা s + a. দুজনের যোগফল 2s + a.
2. X আর Y অদলবদল করলে: Y-এর অপেক্ষা s, X-এর অপেক্ষা s + b. যোগফল 2s + b.
3. বাকিদের কী হলো? X-Y-এর আগের কাজগুলো একই সময়ে শুরু হয়, কিছুই বদলায় না। পরের কাজগুলোও শুরু হয় s + a + b-তে — দুই ক্রমেই একই। তাই তাদের অপেক্ষাও অপরিবর্তিত।
4. ফল: মোট অপেক্ষার পরিবর্তন = (2s + b) − (2s + a) = b − a < 0. অর্থাৎ প্রতিটি উল্টো জোড়া সোজা করলে মোট অপেক্ষা ঠিক (a − b) কমে।
5. উপসংহার: যে ক্রমে একটিও উল্টো জোড়া আছে, তাকে কঠোরভাবে উন্নত করা যায় — তাই সেটি সর্বোত্তম হতে পারে না। পাশাপাশি উল্টো জোড়া একটিও না থাকা মানে ক্রমটি burst অনুযায়ী সাজানো, অর্থাৎ SJF. (সমান burst-এর কাজ অদলবদলে কিছু বদলায় না, তাই সমান burst থাকলে সব SJF-ক্রমই সমান ভালো।) আর প্রতিটি অদলবদল উল্টো জোড়ার সংখ্যা ঠিক একটি কমায় — bubble sort-এর মতো — তাই সসীম ধাপে যেকোনো ক্রম থেকে SJF-এ পৌঁছানো যায়, প্রতি ধাপে মোট অপেক্ষা বাড়ে না। ∎

একই কথা একটি সূত্র দিয়েও দেখা যায়। ক্রমের k-তম কাজটির burst যদি b₍ₖ₎ হয়, তবে সেটি তার পরের (n − k) টি কাজের প্রত্যেকের অপেক্ষায় একবার করে যোগ হয়:

গুণকগুলো (n − 1, n − 2, …, 0) কমতে থাকে, তাই মোট সবচেয়ে ছোট রাখতে সবচেয়ে বড় গুণকের সাথে সবচেয়ে ছোট burst জোড়া দিতে হয় (rearrangement inequality) — আবার SJF. নিচের diagram-এ চারটি কাজ (burst ৬, ৮, ৭, ৩) নিয়ে উল্টো জোড়া একে একে সোজা করে দেখুন — প্রতি ধাপে মোট অপেক্ষা ঠিক burst-এর পার্থক্যের সমান কমছে।

1start  : 6 8 7 3   (FCFS order P1..P4)2swap 7,3: 6 8 3 73swap 8,3: 6 3 8 74swap 6,3: 3 6 8 75swap 8,7: 3 6 7 86sorted -> no inversion left

প্রমাণ পড়ে বিশ্বাস হলো; এবার যন্ত্র দিয়ে যাচাই। চারটি কাজের 4! = ২৪টি সম্ভাব্য ক্রম আছে। নিচের C প্রোগ্রাম সবগুলো তৈরি করে (recursion দিয়ে), প্রতিটির গড় অপেক্ষা হিসাব করে, আর সবচেয়ে ভালো ও খারাপটি SJF-এর সাথে মেলায়।

#include <stdio.h>
#include <stdlib.h>
/* All jobs arrive at t=0. Try every order, report the average waiting time. */
#define N 4
static const int burst[N] = {6, 8, 7, 3};          /* P1..P4 */
static int order[N], used[N], count = 0;
static double best = 1e9, worst = 0;

static void try_all(int k) {
    if (k == N) {                                   /* one complete order */
        int clock = 0, total_wait = 0;
        for (int i = 0; i < N; i++) { total_wait += clock; clock += burst[order[i]]; }
        double avg = (double)total_wait / N;
        if (avg < best) best = avg;
        if (avg > worst) worst = avg;
        count++; return;
    }
    for (int j = 0; j < N; j++)
        if (!used[j]) { used[j] = 1; order[k] = j; try_all(k + 1); used[j] = 0; }
}

static int by_burst(const void *a, const void *b) {
    return burst[*(const int *)a] - burst[*(const int *)b];
}

int main(void) {
    try_all(0);
    int sjf[N] = {0, 1, 2, 3}, clock = 0, total = 0;
    qsort(sjf, N, sizeof sjf[0], by_burst);        /* shortest burst first */
    printf("SJF order:");
    for (int i = 0; i < N; i++) { printf(" P%d", sjf[i] + 1); total += clock; clock += burst[sjf[i]]; }
    printf("\norders tried = %d\n", count);
    printf("best avg WT = %.2f, worst avg WT = %.2f, SJF avg WT = %.2f\n", best, worst, (double)total / N);
    return 0;
}

SJF order: P4 P1 P3 P2
orders tried = 24
best avg WT = 7.00, worst avg WT = 11.00, SJF avg WT = 7.00

৫ · SRTF — ছোট কাজ এলে চলতি কাজ থামে

অংশ ৩-এর উদাহরণে P1 (burst ৭) t = 0-তে শুরু করল, আর t = ৪-এ এল মাত্র ১ ms-এর P3. Non-preemptive SJF-এ P3-কে ৭ পর্যন্ত বসে থাকতে হয়েছে। যদি P1-কে মাঝপথে থামানো যেত? সেটিই Shortest Remaining Time First (SRTF) — SJF-এর preemptive রূপ। তাত্ত্বিক বইয়ে এর নাম SRPT (shortest remaining processing time).

দুটি ঘটনার (আসা বা শেষ হওয়া) মাঝে কারও তুলনা বদলায় না, তাই সিদ্ধান্ত শুধু ঘটনার মুহূর্তে নিলেই চলে; তবু হাতে হিসাবের সময় এক ms করে এগোনো সবচেয়ে নিরাপদ। নিচের diagram অংশ ৩-এর চার প্রসেস (P1 0/7, P2 2/4, P3 4/1, P4 5/4 — AT/BT) নিয়ে প্রথম সাত ms এক এক করে দেখায়, তারপর শেষ দুটি লম্বা টুকরো একবারে, কারণ t = ৫-এর পরে আর কেউ আসে না।

1t=0  P1 arrives (7)       run P12t=1  nothing new          run P13t=2  P2 arrives (4 < 5)   PREEMPT -> P24t=3  nothing new          run P25t=4  P3 arrives (1 < 2)   PREEMPT -> P36t=5  P3 done, P4 arrives   pick P2 (2)7t=6  nothing new          run P28t=7  P2 done              pick P4 (4 < 5)9t=11 P4 done             pick P1 (5)10t=16 all done

SRTF-এর দুটি বড় সুবিধা: গড় waiting আর turnaround সর্বনিম্ন (সব burst জানা আর switch-এর খরচ শূন্য — এই শর্তে; ১৯৬০-এর দশকের শেষে Linus Schrage এর আনুষ্ঠানিক প্রমাণ দেন), আর ছোট কাজের response time প্রায় শূন্য। প্রমাণের মূল ধারণা অংশ ৪-এর অদলবদলের যুক্তিই, এবার চলার টুকরোগুলোর ওপর।

অসুবিধাও তিনটি: প্রতিটি preemption একটি context switch, যার খরচ বাস্তবে শূন্য নয় (পর্ব ৯); বাকি সময় জানতে মোট burst জানতে হয়; আর লম্বা কাজের প্রতি এটি SJF-এর চেয়েও নির্দয় — শুরু করেও ছোট কেউ এলেই থামতে হয়। উপরের উদাহরণে P1-এর অবস্থা দেখুন।

৬ · Starvation আর পরের burst-এর অনুমান

Starvation — লম্বা কাজ যখন কখনোই পালা পায় না

ধরুন একটি সার্ভারে প্রতি ২ ms-এ একটি ১ ms-এর ছোট অনুরোধ আসে, সঙ্গে একটি ৫০ ms-এর রিপোর্ট তৈরির কাজ। SJF বা SRTF-এ প্রতিটি সিদ্ধান্তে কোনো না কোনো ছোট অনুরোধ হাজির থাকলে রিপোর্টের পালা পিছোতেই থাকে — চলতে প্রস্তুত থেকেও এগোতে না পারা, এরই নাম starvation. Silberschatz-এর বইয়ে একটি জনশ্রুতি আছে: ১৯৭৩ সালে MIT-র IBM 7094 বন্ধ করার সময় ১৯৬৭ সালে জমা দেওয়া একটি নিম্ন-অগ্রাধিকারের job পাওয়া যায়, যেটি তখনো চলেনি — একে নথির বদলে শিক্ষণীয় কাহিনি হিসেবেই নিন।

প্রতিকারের সাধারণ নাম aging: যত বেশি অপেক্ষা, তত বেশি অগ্রাধিকার — অংশ ৭-এর HRRN এই ধারণাকে একটি সূত্রে বেঁধেছে। FCFS-এ starvation হয় না, সারি এগোয়ই। পার্থক্যটি মনে রাখুন: convoy-তে অপেক্ষা দীর্ঘ কিন্তু সীমিত; starvation-এ অপেক্ষার কোনো ঊর্ধ্বসীমা নেই।

Burst আগে থেকে জানা যায় না — তাহলে অনুমান

SJF আর SRTF দুটোই চায় পরের CPU burst-এর দৈর্ঘ্য, যা interactive সিস্টেমে কেউ আগে থেকে বলতে পারে না (batch যুগের সমাধান ভাবনার প্রশ্ন ১-এ)। একমাত্র পথ অতীত দেখে অনুমান: যে প্রসেস এতক্ষণ ছোট ছোট burst দিয়েছে, তার পরের burst-ও সম্ভবত ছোট।

সবচেয়ে প্রচলিত অনুমান-পদ্ধতি exponential averaging. ধরুন t(n) = n-তম burst-এর আসল (মাপা) দৈর্ঘ্য, আর τ(n) = সেই burst-এর জন্য আগে থেকে করা অনুমান। পরের burst-এর অনুমান:

অর্থাৎ নতুন অনুমান হলো “সর্বশেষ মাপ” আর “পুরোনো অনুমান”-এর একটি মিশ্রণ, আর α ঠিক করে কোনটির ওজন কত। সূত্রটি বারবার বসালে দেখা যায় কেন একে “exponential” বলে:

প্রতিটি পুরোনো মাপের ওজন (1 − α) গুণ করে করে কমে — জ্যামিতিক হারে। α = ০.৫ হলে সর্বশেষ মাপের ওজন ১/২, তার আগেরটির ১/৪, তার আগের ১/৮… আর সাতটি burst পরে প্রথম অনুমান τ(0)-এর ওজন মাত্র (১/২)⁷ = ১/১২৮. দুটি প্রান্তিক মান পরীক্ষায় প্রায়ই জিজ্ঞেস করা হয়:

সমাধান করা উদাহরণ — α = ০.৫, τ(0) = ১০

একটি প্রসেসের পরপর সাতটি burst মাপা হয়েছে: ৬, ৪, ৬, ৪, ১৩, ১৩, ১৩ ms. প্রথম অনুমান τ(0) = ১০ ms (যেমন সিস্টেমের গড়)। প্রতিটি ধাপ: নতুন অনুমান = (আসল + পুরোনো অনুমান) ÷ ২.

লক্ষ করুন, n = ৪ থেকে প্রসেসের আচরণ বদলেছে (burst ৪ থেকে ১৩), কিন্তু অনুমান ধীরে ধীরে উঠছে: ৫ → ৯ → ১১ → ১২. তিনটি ১৩-এর পরেও অনুমান ১৩-এ পৌঁছায়নি — প্রতিবার ফাঁকটি অর্ধেক হচ্ছে। নিচের কোড একই হিসাব α = ০.৫, ০, ১ আর ০.৮-এর জন্য পাশাপাশি দেখায়।

// Predict the next CPU burst: tau(n+1) = alpha * t(n) + (1 - alpha) * tau(n)
const actual = [6, 4, 6, 4, 13, 13, 13];   // measured bursts t(0), t(1), ...
const tau0 = 10;                            // initial guess (e.g. a system-wide average)

function predict(alpha) {
  const tau = [tau0];
  for (const t of actual) tau.push(alpha * t + (1 - alpha) * tau[tau.length - 1]);
  return tau;                               // tau[n] = prediction made before burst n
}

const cols = [0.5, 0, 1, 0.8].map(a => ({ a, tau: predict(a) }));
console.log(" n | actual t(n) | " + cols.map(c => ("tau a=" + c.a).padStart(9)).join(" | "));
for (let n = 0; n <= actual.length; n++) {
  const t = n < actual.length ? String(actual[n]) : "?";
  console.log(String(n).padStart(2) + " | " + t.padStart(11) + " | " +
    cols.map(c => c.tau[n].toFixed(2).padStart(9)).join(" | "));
}

// How much does the very first guess still matter after n bursts? weight = (1-a)^n
for (const a of [0.5, 0.8]) {
  console.log("alpha=" + a + ": weight of tau0 after 7 bursts = " + ((1 - a) ** 7).toFixed(6));
}

 n | actual t(n) | tau a=0.5 |   tau a=0 |   tau a=1 | tau a=0.8
 0 |           6 |     10.00 |     10.00 |     10.00 |     10.00
 1 |           4 |      8.00 |     10.00 |      6.00 |      6.80
 2 |           6 |      6.00 |     10.00 |      4.00 |      4.56
 3 |           4 |      6.00 |     10.00 |      6.00 |      5.71
 4 |          13 |      5.00 |     10.00 |      4.00 |      4.34
 5 |          13 |      9.00 |     10.00 |     13.00 |     11.27
 6 |          13 |     11.00 |     10.00 |     13.00 |     12.65
 7 |           ? |     12.00 |     10.00 |     13.00 |     12.93
alpha=0.5: weight of tau0 after 7 bursts = 0.007813
alpha=0.8: weight of tau0 after 7 bursts = 0.000013

৭ · HRRN — অপেক্ষারও মূল্য আছে

SJF ছোট কাজকে ভালোবাসে, FCFS অপেক্ষাকে সম্মান করে। দুটি মেলানো যায় কি? Highest Response Ratio Next (HRRN) ঠিক সেটি করে। একে সাধারণত Per Brinch Hansen-এর (১৯৭০-এর দশকের শুরু) প্রস্তাব বলে উল্লেখ করা হয়। এটি non-preemptive: CPU খালি হলে প্রতিটি অপেক্ষমাণ প্রসেসের জন্য একটি সংখ্যা হিসাব করা হয় —

— আর যার R সবচেয়ে বেশি, সে CPU পায় (সমান হলে আগে আসা জন, তারপর টেবিলের ক্রম)। S হরে থাকায় সমান অপেক্ষার পর ছোট কাজের R বেশি — SJF-এর মতো সুবিধা। W লবে থাকায় অপেক্ষার সাথে R বাড়তেই থাকে, ঊর্ধ্বসীমা নেই, আর নতুন আসা কাজের R শুরু হয় ১ থেকে — তাই দীর্ঘ অপেক্ষার কাজ একসময় সবাইকে ছাড়িয়ে যাবেই। Starvation অসম্ভব — aging-এর একটি সুন্দর গাণিতিক রূপ।

R-এর একটি সহজ মানে আছে: (W + S) হলো কাজটি শেষ হতে মোট যত সময় ব্যবস্থায় থাকবে (এখনই শুরু হলে), আর S তার নিজের দৈর্ঘ্য। R = ৩ মানে “নিজের দৈর্ঘ্যের তিন গুণ সময় লাইনে কাটাতে হচ্ছে।” HRRN প্রতিবার সবচেয়ে বেশি “অন্যায়ের শিকার” কাজটিকে আগে নেয়। তবে SJF-এর মতো এটিও burst-এর দৈর্ঘ্য জানতে বা অনুমান করতে চায়।

উদাহরণ (অংশ ৮-এর পূর্ণ সমস্যার টেবিল, AT/BT): P1 1/3, P2 3/6, P3 5/4, P4 7/5, P5 9/2, P6 23/3. নিচে প্রতিটি সিদ্ধান্তের মুহূর্তে R-এর হিসাব দেখুন।

1t=0   ready: none           -> idle 0-12t=1   ready: P1             -> P1 1-43t=4   ready: P2             -> P2 4-104t=10  ready: P3 P4 P5       -> P3 10-145t=14  ready: P4 P5          -> P5 14-166t=16  ready: P4             -> P4 16-217t=21  ready: none -> idle 21-23, P6 23-268done: avg TAT 7.17, avg WT 3.33

৮ · পরীক্ষার পূর্ণ সমস্যা — চার অ্যালগরিদম পাশাপাশি

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় scheduling-এর অঙ্ক সাধারণত এমন আসে: একটি process table দিয়ে কয়েকটি অ্যালগরিদমের Gantt chart, প্রতিটি প্রসেসের TAT/WT, গড়, আর কোনটি ভালো তার মন্তব্য চাওয়া হয়। নিচের সমস্যায় দুটি ফাঁদ ইচ্ছা করে রাখা হয়েছে: শুরুতে CPU idle (প্রথম প্রসেস t = ১-এ আসে), আর মাঝখানে আরেকটি idle ফাঁক (P6 আসে অনেক পরে)।

প্রশ্ন: ছয়টি প্রসেসের arrival আর burst time (ms) নিচে দেওয়া হলো। FCFS, SJF (non-preemptive), SRTF আর HRRN-এর Gantt chart আঁকুন; প্রতিটির গড় turnaround, waiting আর response time বের করুন; আর ফলাফল তুলনা করুন। Tie হলে আগে আসা প্রসেস আগে।

সমাধানের পদ্ধতি — প্রতিটি অ্যালগরিদমে একই

1. সময় t = ০ থেকে শুরু করুন। CPU খালি হলে দেখুন কারা এসে গেছে (AT ≤ t); কেউ না এলে পরের arrival পর্যন্ত idle লিখুন।
2. নিয়ম অনুযায়ী একজনকে বাছুন (FCFS: আগে আসা; SJF: ছোট burst; HRRN: বড় R; SRTF: ছোট বাকি সময় — আর SRTF-এ প্রতিটি arrival-এ আবার তুলনা)।
3. Gantt chart-এ খোপ আঁকুন, শুরু আর শেষের সময় নিচে লিখুন। শেষে মোট দৈর্ঘ্য যাচাই: মোট burst (২৩) + মোট idle = শেষ সময়।
4. প্রতিটি প্রসেসের CT চার্ট থেকে পড়ুন; TAT = CT − AT, WT = TAT − BT, RT = প্রথম শুরু − AT. একটি যাচাই: সব WT-এর যোগফল = সব TAT-এর যোগফল − ২৩.

চারটি Gantt chart

FCFS │idle│P1 │P2    │P3  │P4   │P5 │idle│P6 │
     0    1   4      10   14    19  21   23  26

SJF  │idle│P1 │P2    │P5 │P3  │P4   │idle│P6 │
     0    1   4      10  12   16    21   23  26

SRTF │idle│P1 │P2│P3  │P5 │P2   │P4   │idle│P6 │
     0    1   4  5    9   11    16    21   23  26

HRRN │idle│P1 │P2    │P3  │P5 │P4   │idle│P6 │
     0    1   4      10   14  16    21   23  26

যেখানে নীতিগুলো আলাদা হয়: t = ৪ পর্যন্ত সবাই একই — শুধু P1 থাকে, আর SRTF-এ t = ৩-এ P2 এলেও P1-এর বাকি ১ < ৬, তাই preemption নেই। SRTF t = ৫-এ P3 (৪) দিয়ে P2-কে (বাকি ৫) থামায়; t = ৭-এ P4 (৫) আসে, কিন্তু P3-এর বাকি ২, তাই কিছু হয় না; t = ৯-এ P3 শেষ, P5 (২) আসে — প্রার্থী P2 (৫), P4 (৫), P5 (২) → P5; t = ১১-এ P2 আর P4-এর বাকি সমান (৫) — tie-নিয়মে আগে আসা P2. SJF t = ১০-এ সবচেয়ে ছোট P5 নেয়, HRRN নেয় সবচেয়ে বেশিক্ষণ বসে থাকা P3 (অংশ ৭). FCFS শুধু আসার ক্রম মানে, তাই সবচেয়ে ছোট P5 সবার শেষে — অপেক্ষা ১০.

মন্তব্য (খাতায় যেমন লিখবেন): গড়ে SRTF সেরা, তারপর SJF, HRRN, আর FCFS সবচেয়ে খারাপ — অংশ ৪ আর ৫-এর তত্ত্বের সাথে মেলে। SRTF-এর দাম একটি বাড়তি context switch (t = ৫-এ P2-কে থামানো; ৬-এর বদলে ৭ বার dispatch) আর P2-এর বড় অপেক্ষা (৭), যদিও তার RT মাত্র ১. HRRN গড়ে SJF-এর চেয়ে সামান্য পিছিয়ে, কিন্তু অপেক্ষা বেশি সমানভাবে ভাগ করে (P3 আর P5 দুজনেরই ৫) আর starvation-মুক্ত। CPU utilisation সবার একই: ২৬ ms-এ ২৩ ms ব্যস্ত, ≈ ৮৮.৫% — idle ফাঁক নীতির দোষ নয়, কাজই ছিল না। Throughput-ও সমান: ২৬ ms-এ ৬টি প্রসেস।

Simulator দিয়ে যাচাই

হাতে করা উত্তর যন্ত্র দিয়ে মেলানো সবচেয়ে ভালো অভ্যাস। নিচের simulator সময়কে ১ ms করে এগোয়; প্রতিটি নীতির একটি “key” ফাংশন বলে দেয় কে আগে (ছোট key জেতে — তাই HRRN-এর key-তে বিয়োগ চিহ্ন)। Non-preemptive নীতিতে শুধু CPU খালি হলে বাছাই হয়, SRTF-এ প্রতি ms-এ। Tie-নিয়ম কোডেই লেখা: SRTF-এ চলতিটি থাকে, তারপর আগে আসা, তারপর টেবিলের ক্রম।

// FCFS, SJF, SRTF, HRRN on one table. Time moves 1 ms at a time.
// Ties: SRTF keeps the running process; then earlier arrival, then table order.
const table = [["P1", 1, 3], ["P2", 3, 6], ["P3", 5, 4],   // [name, arrival, burst]
               ["P4", 7, 5], ["P5", 9, 2], ["P6", 23, 3]];
const key = {                                // smaller key is chosen first
  FCFS: (p, t) => p.at,   SJF: (p, t) => p.bt,
  SRTF: (p, t) => p.left,
  HRRN: (p, t) => -((t - p.at) + p.bt) / p.bt,   // -(W + S) / S
};
function run(alg) {
  const ps = table.map(([n, at, bt], i) => ({ n, at, bt, i, left: bt, start: -1 }));
  const g = []; let t = 0, cur = null, done = 0;
  while (done < ps.length) {
    if (!cur || alg === "SRTF") {            // non-preemptive: decide only when CPU is free
      const k = p => key[alg](p, t), diff = (a, b) => Math.abs(k(a) - k(b)) < 1e-9 ? 0 : k(a) - k(b);
      const ready = ps.filter(p => p.at <= t && p.left > 0);
      ready.sort((a, b) => diff(a, b) || (b === cur) - (a === cur) || a.at - b.at || a.i - b.i);
      cur = ready[0] || null;
    }
    const lab = cur ? cur.n : "idle", last = g[g.length - 1];
    if (last && last.lab === lab) last.end++; else g.push({ lab, s: t, end: t + 1 });
    if (cur && cur.start < 0) cur.start = t;
    if (cur && --cur.left === 0) { cur.ct = t + 1; done++; cur = null; }
    t++;
  }
  console.log(alg + ": " + g.map(x => x.s + "-" + x.end + " " + x.lab).join(" | "));
  const sum = [0, 0, 0];
  for (const p of ps) {
    const v = [p.ct - p.at, p.ct - p.at - p.bt, p.start - p.at];   // TAT, WT, RT
    v.forEach((x, j) => sum[j] += x);
    console.log(`  ${p.n} CT=${p.ct} TAT=${v[0]} WT=${v[1]} RT=${v[2]}`);
  }
  const [a, w, r] = sum.map(x => (x / ps.length).toFixed(2));
  console.log(`  avg TAT=${a} WT=${w} RT=${r}`);
}
["FCFS", "SJF", "SRTF", "HRRN"].forEach(run);

FCFS: 0-1 idle | 1-4 P1 | 4-10 P2 | 10-14 P3 | 14-19 P4 | 19-21 P5 | 21-23 idle | 23-26 P6
  P1 CT=4 TAT=3 WT=0 RT=0
  P2 CT=10 TAT=7 WT=1 RT=1
  P3 CT=14 TAT=9 WT=5 RT=5
  P4 CT=19 TAT=12 WT=7 RT=7
  P5 CT=21 TAT=12 WT=10 RT=10
  P6 CT=26 TAT=3 WT=0 RT=0
  avg TAT=7.67 WT=3.83 RT=3.83
SJF: 0-1 idle | 1-4 P1 | 4-10 P2 | 10-12 P5 | 12-16 P3 | 16-21 P4 | 21-23 idle | 23-26 P6
  P1 CT=4 TAT=3 WT=0 RT=0
  P2 CT=10 TAT=7 WT=1 RT=1
  P3 CT=16 TAT=11 WT=7 RT=7
  P4 CT=21 TAT=14 WT=9 RT=9
  P5 CT=12 TAT=3 WT=1 RT=1
  P6 CT=26 TAT=3 WT=0 RT=0
  avg TAT=6.83 WT=3.00 RT=3.00
SRTF: 0-1 idle | 1-4 P1 | 4-5 P2 | 5-9 P3 | 9-11 P5 | 11-16 P2 | 16-21 P4 | 21-23 idle | 23-26 P6
  P1 CT=4 TAT=3 WT=0 RT=0
  P2 CT=16 TAT=13 WT=7 RT=1
  P3 CT=9 TAT=4 WT=0 RT=0
  P4 CT=21 TAT=14 WT=9 RT=9
  P5 CT=11 TAT=2 WT=0 RT=0
  P6 CT=26 TAT=3 WT=0 RT=0
  avg TAT=6.50 WT=2.67 RT=1.67
HRRN: 0-1 idle | 1-4 P1 | 4-10 P2 | 10-14 P3 | 14-16 P5 | 16-21 P4 | 21-23 idle | 23-26 P6
  P1 CT=4 TAT=3 WT=0 RT=0
  P2 CT=10 TAT=7 WT=1 RT=1
  P3 CT=14 TAT=9 WT=5 RT=5
  P4 CT=21 TAT=14 WT=9 RT=9
  P5 CT=16 TAT=7 WT=5 RT=5
  P6 CT=26 TAT=3 WT=0 RT=0
  avg TAT=7.17 WT=3.33 RT=3.33

৯ · বাস্তব OS-এ এই নীতিগুলো

খাঁটি SJF বা SRTF কোনো সাধারণ-ব্যবহারের OS-এর প্রধান scheduler নয় — burst জানা যায় না, আর লম্বা কাজের starvation গ্রহণযোগ্য নয়। কিন্তু এদের ধারণা সবখানে ছড়িয়ে আছে:

• Linux-এর SCHED_FIFO: real-time thread-এর জন্য একটি নীতি — প্রতিটি অগ্রাধিকার-স্তরের ভেতরে খাঁটি FCFS. Task নিজে block বা yield না করলে, বা বেশি অগ্রাধিকারের কেউ না এলে, CPU ছাড়ে না। পাশেই SCHED_RR, যা একই জিনিস কিন্তু time quantum-সহ। সাধারণ প্রসেস চলে SCHED_OTHER নীতিতে (Linux 6.6 থেকে EEVDF, তার আগে CFS — পর্ব ২১). Windows-এও real-time অগ্রাধিকার শ্রেণি আছে, তবে সেখানে একই অগ্রাধিকারের thread-রা quantum ধরে পালা করে।
• “কম চলেছে, তাকে আগে”: Interactive প্রসেস (editor, shell) সাধারণত ছোট burst দিয়েই ঘুমিয়ে পড়ে; আধুনিক scheduler জেগে ওঠা এমন প্রসেসকে দ্রুত CPU দেয় — পরোক্ষভাবে “ছোট burst আগে” (পর্ব ১৯-এর MLFQ).
• Batch আর HPC cluster: Slurm-এর মতো job scheduler-এ ব্যবহারকারী প্রতিটি job-এর সর্বোচ্চ সময় ঘোষণা করেন, আর scheduler সেটি দিয়ে “backfill” করে — বড় job-এর অপেক্ষার ফাঁকে ছোট job ঢোকায়, যদি তাতে বড়টির শুরু না পিছোয়।

Linux kernel প্রতিটি task-এর “কতক্ষণ CPU-তে চলেছে” আর “কতক্ষণ run queue-তে অপেক্ষা করেছে” — অর্থাৎ ঠিক এই পর্বের BT আর WT — ন্যানোসেকেন্ডে গুনে রাখে, আর /proc/<pid>/schedstat ফাইলে দেখায় (তিনটি সংখ্যা: CPU-তে সময়, অপেক্ষার সময়, কতগুলো timeslice). নিচের script দুটি অসীম লুপকে taskset দিয়ে একই CPU-তে বেঁধে এক সেকেন্ড চালায়, তারপর kernel-এর হিসাব পড়ে।

# Two CPU-hungry loops share ONE CPU for about 1 second.
# /proc/PID/schedstat = ns on the CPU, ns waiting in the run queue, timeslices
cpu=$(taskset -cp $$ | sed 's/.*: //; s/[-,].*//')     # first CPU this shell may use
echo "policy of this shell: $(chrt -p $$ | head -1 | sed 's/.*: //')"
pids=""
for i in 1 2; do
  taskset -c "$cpu" sh -c 'while :; do :; done' &
  pids="$pids $!"
done
sleep 1
i=0
for p in $pids; do
  i=$((i + 1))
  read -r run wait slices < "/proc/$p/schedstat"
  echo "loop $i: on-cpu $((run / 1000000)) ms, waiting $((wait / 1000000)) ms, slices $slices"
done
{ kill $pids; wait $pids; } 2>/dev/null
echo "both loops stopped"

policy of this shell: SCHED_OTHER
loop 1: on-cpu 464 ms, waiting 542 ms, slices 435
loop 2: on-cpu 464 ms, waiting 544 ms, slices 486
both loops stopped

নীতি দেখতে বা বদলাতে Linux-এ chrt কমান্ড আছে। Real-time নীতি দিতে সাধারণত বিশেষ অনুমতি (root বা CAP_SYS_NICE) লাগে, কারণ একটি real-time অসীম লুপ পুরো CPU দখল করতে পারে; সুরক্ষা হিসেবে ডিফল্টে real-time task-রা প্রতি সেকেন্ডে সর্বোচ্চ ০.৯৫ সেকেন্ড পায়। উদাহরণ (চালানোর কোড নয়):

$ chrt -p $$                       # current policy of this shell
pid 4120's current scheduling policy: SCHED_OTHER
pid 4120's current scheduling priority: 0
$ cat /proc/sys/kernel/sched_rt_runtime_us
950000
$ sudo chrt -f 10 ./sensor_logger   # run with SCHED_FIFO, priority 10 (needs privilege)

১০ · AI-এর যুগে scheduling-এর অঙ্ক

“এই টেবিলের SRTF Gantt chart আর গড় waiting time চাই” — AI-কে এমন বললে আত্মবিশ্বাসী উত্তর পাবেন, কিন্তু scheduling-এর অঙ্কে AI-এর ভুল খুব চেনা ধরনের। উত্তর নেওয়ার আগে এগুলো খুঁজুন:

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

• চার্ট t = ০ থেকে শুরু হয়েছে, আর প্রতিটি idle ফাঁক আলাদা খোপে আছে
• প্রতিটি সিদ্ধান্তে শুধু এসে যাওয়া প্রসেসই প্রার্থী ছিল, আর tie-নিয়ম আমার দেওয়া নিয়মের সাথে মেলে
• শেষ সময় = মোট burst + মোট idle, আর ΣWT = ΣTAT − ΣBT মিলিয়েছি
• অন্তত একটি অ্যালগরিদম হাতে করে, বা উপরের simulator-এ টেবিল বসিয়ে, সংখ্যা মিলিয়েছি
• “সর্বোত্তম” বা “Linux/Windows এটি ব্যবহার করে” জাতীয় দাবির শর্ত আর সংস্করণ যাচাই করেছি; real-time নীতি দিতে অকারণে sudo চালাইনি