LEVEL 4লেসন ৮/২৯কঠিন১ ঘণ্টা ১৫ মিনিট

CPU Scheduling — কে চলবে, কতক্ষণ, আর কোন মূল্যে

CPU Scheduling

গত লেসনে দেখেছি switch করাটা ব্যয়বহুল — তবু scheduler ঘন ঘন switch করে, কারণ কখন আর কাকে CPU দেওয়া হবে সেই সিদ্ধান্তটাই ব্যবহারকারীর অভিজ্ঞতা নির্ধারণ করে। এই লেসনে classic scheduling policy — FIFO, SJF, Round Robin, priority — হাতে-কলমে তুলনা করব, দেখব turnaround আর response time কীভাবে একে অপরের বিরুদ্ধে টানাটানি করে, আর Mars Pathfinder-এর প্রায়-বিপর্যয় দিয়ে বুঝব কেন শুধু priority scheduling যথেষ্ট নয়।

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

Turnaround, response, throughput ও fairness — এই চারটা scheduling metric নির্ভুলভাবে সংজ্ঞায়িত করতে পারবেন, আর হাতে-কলমে দেখাতে পারবেন কেন একটা policy একসাথে সবগুলোতে জিততে পারে না
FIFO-র convoy effect, SJF/SRTF-এর optimality ও starvation, আর Round Robin-এর quantum trade-off — এই তিনটা classic policy একই workload-এ হাতে হিসাব করে সংখ্যাসহ তুলনা করতে পারবেন
Priority inversion কীভাবে ঘটে আর priority inheritance কীভাবে সেটা সমাধান করে তা Mars Pathfinder-এর প্রকৃত ঘটনা দিয়ে ব্যাখ্যা করতে পারবেন
Preemptive ও cooperative scheduling-এর পার্থক্য করতে পারবেন, আর কোথায় আজও cooperative model যুক্তিসঙ্গত তা চিহ্নিত করতে পারবেন
একটা mixed CPU-bound/I/O-bound workload-এ কেন কোনো একটা classic policy যথেষ্ট নয় তা যুক্তি দিয়ে ব্যাখ্যা করতে পারবেন — এটাই পরের লেসনের MLFQ/CFS-এর প্রেরণা
নিজের মেশিনে `nice` আর `chrt` দিয়ে scheduling priority বদলে CPU allocation-এ তার প্রকৃত প্রভাব পর্যবেক্ষণ করতে পারবেন

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

↑ Context Switching — যা সংরক্ষিত হয়, আর যার প্রকৃত দাম

আগে এটা বুঝি

আপনার ল্যাপটপে এই মুহূর্তে হয়তো একটা video call চলছে, একটা কোড compile হচ্ছে, আর background-এ গান বাজছে। CPU-র একটা core-এ, গত লেসনের ভাষায়, এক মুহূর্তে একটাই thread চলতে পারে। তাহলে কোনটা আগে চলবে?

এটা কোনো তুচ্ছ প্রশ্ন না। যদি scheduler ভুল সিদ্ধান্ত নেয় — compile job-কে ৫০ms-এর একটানা সুযোগ দিয়ে video call-এর audio thread-কে দেরি করায় — call-এ শব্দ কেটে কেটে আসবে, যদিও গড় CPU utilization হয়তো মাত্র ৩০%। উল্টোদিকে যদি scheduler প্রতি ১ms-এই সবকিছুর মধ্যে ঘুরতে থাকে “ন্যায্যতা” রক্ষা করতে, compile job শেষ হতে-হতে গত লেসনের switch-খরচ জমতে জমতে throughput নাটকীয়ভাবে কমে যাবে।

এই দুই চরমের মাঝে ভারসাম্য খোঁজাই CPU scheduling-এর কাজ — আর আজ আমরা দেখব এই ভারসাম্য একটা মতামতের প্রশ্ন না, একটা পরিমাপযোগ্য, প্রমাণযোগ্য trade-off। একই workload-এ কয়েকটা classic policy হাতে চালিয়ে দেখব ঠিক কোথায় প্রতিটা জেতে, কোথায় হারে — আর একটা বাস্তব মহাকাশযান কীভাবে প্রায় হারিয়ে গিয়েছিল শুধু scheduling priority-র একটা সূক্ষ্ম ভুলে।

মূল ধারণা

সমস্যাটা ঠিক কী

যেকোনো মুহূর্তে কিছু thread runnable — চলার জন্য প্রস্তুত, কিন্তু কোনো CPU core পায়নি এখনো। এদের রাখা হয় ready queue-তে (প্রতি core-এ একটা, লেসন ৯-এ বিস্তারিত)। একটা core যখনই ফাঁকা হয় — নতুন thread তৈরি হলে, একটা thread block করলে, বা quantum শেষ হলে — scheduler-কে দুইটা সিদ্ধান্ত নিতে হয়:

কাকে পরে চালাব? (কোন thread ready queue থেকে বাছব)
কতক্ষণ চালাব? (কখন তাকে আবার সরিয়ে অন্য কাউকে সুযোগ দেব)

এই দুই সিদ্ধান্তের নিয়মকেই বলে scheduling policy। আর প্রতিটা নিয়ম কিছু মেট্রিকে ভালো করে, কিছুতে খারাপ — এটাই এই লেসনের কেন্দ্রীয় বিষয়।

চারটা metric — যারা একে অপরের প্রতিদ্বন্দ্বী

Metric	সংজ্ঞা	কে চায়
Turnaround time	`finish − arrival`	Batch job — “কতক্ষণে পুরো কাজ শেষ হলো”
Response time	`first_run − arrival`	Interactive user — “কতক্ষণে প্রথম সাড়া পেলাম”
Waiting time	`turnaround − burst`	Fairness — “কতক্ষণ ready থেকেও বসে থাকতে হলো”
Throughput	সময়প্রতি সম্পন্ন job সংখ্যা	System operator — “সার্ভার কতটা কাজ হজম করছে”

লক্ষ্য করুন — একটা batch analytics job (রাতভর চলা রিপোর্ট জেনারেশন) turnaround নিয়ে ভাবে, response time নিয়ে না। একটা ইন্টার‌্যাক্টিভ শেল (আপনি keyboard-এ টাইপ করছেন) response time নিয়ে ভাবে, পুরো session কতক্ষণে “শেষ” হবে তা নিয়ে না — সেশন তো কখনো শেষই হয় না। একটা ওয়েব সার্ভার throughput নিয়ে ভাবে — একসাথে হাজার request হজম করতে পারা।

এই তিনজনের চাহিদা একসাথে পূরণ করা যায় না। নিচে দেখব কেন — প্রতিটা policy একটা metric-এ ভালো করতে গিয়ে অন্যটায় মূল্য দেয়।

FIFO — সরলতম, আর convoy effect

First-In-First-Out: যে আগে এসেছে, সে আগে চলে, শেষ পর্যন্ত (non-preemptive)। বাস্তবায়ন তুচ্ছ — একটা queue।

সমস্যা: ধরুন একটা ৫ মিনিটের ভারী job আগে এসেছে, তার পেছনে সারিবদ্ধ কয়েকটা ১০০ms-এর হালকা job। প্রতিটা হালকা job-কে প্রায় পুরো ৫ মিনিট অপেক্ষা করতে হবে, যদিও তাদের নিজেদের কাজ মুহূর্তেই শেষ হয়ে যেত। এটাই convoy effect — supermarket-এ একজন ভরা ট্রলি নিয়ে চেকআউটে দাঁড়ালে পেছনের সবার যা হয়, ঠিক সেটাই।

SJF/SRTF — প্রমাণযোগ্যভাবে optimal, কিন্তু ভবিষ্যৎ চায়

SJF (Shortest Job First): ready queue থেকে সবচেয়ে ছোট মোট-burst-ওয়ালা job বাছা হয়, non-preemptive। SRTF (Shortest Remaining Time First): preemptive সংস্করণ — নতুন কোনো job এলে, যদি তার burst বর্তমান চলমান job-এর অবশিষ্ট সময়ের চেয়ে ছোট হয়, তাহলে সাথে সাথে preempt করে সেই নতুনটা চালানো হয়।

একটা প্রমাণযোগ্য দাবি: একই arrival time-এর একগুচ্ছ job-এর মধ্যে, SJF non-preemptive policy-গুলোর মধ্যে গড় turnaround (বা সমতুল্যভাবে গড় waiting time) সর্বনিম্ন করে।

প্রমাণের ধারণা (exchange argument, Level 6-এ formal হবে): ধরুন একটা schedule-এ দুইটা পরপর job আছে, A (burst বড়) তারপর B (burst ছোট)। যদি A ও B-র জায়গা অদল-বদল করি (B আগে, A পরে):

B-র completion time কমে যায় (আগে চলছে)
A-র completion time বাড়ে, কিন্তু ঠিক ততটাই যতটা B-র কমেছে
কিন্তু A বড় বলে A যত বেশি সময় B-র পরে অপেক্ষা করাচ্ছিল, সেই সময়টা এখন B-কে আর সহ্য করতে হচ্ছে না

$\text{total completion time বদল} = (\text{burst}_A - \text{burst}_B) \times (-1) \times 1 < 0 \quad \text{(যখন burst}_A > \text{burst}_B\text{)}$

অর্থাৎ যেকোনো “বড় আগে, ছোট পরে” জোড়া উল্টে দিলে মোট completion time কমে (বা সমান থাকে) — কখনো বাড়ে না। যে schedule-এ আর কোনো এমন উল্টানো জোড়া নেই (অর্থাৎ burst-এর ঊর্ধ্বক্রম অনুযায়ী সাজানো) সেটাই সর্বনিম্ন। এই একই “adjacent swap কখনো ক্ষতি করে না, তাই sorted order optimal” যুক্তি Level 6-এ interval scheduling ও আরও অনেক greedy algorithm-এর optimality প্রমাণে ফিরে আসবে।

তাহলে সমস্যা কোথায়? দুইটা জায়গায়:

১. ভবিষ্যৎ জানা লাগে। Scheduler-এর কাছে একটা thread ঠিক কতক্ষণ CPU ব্যবহার করবে তা আগে থেকে জানার কোনো উপায় নেই — সে হয়তো ১ms পরেই I/O-তে block করবে, হয়তো ১ সেকেন্ড ধরে গণনা করবে। বাস্তব scheduler predict করার চেষ্টা করে — গত কয়েকটা burst-এর একটা exponential moving average দিয়ে:

$\tau_{n+1} = \alpha \cdot t_n + (1 - \alpha) \cdot \tau_n$

যেখানে $t_n$ শেষ প্রকৃত burst, $\tau_n$ আগের অনুমান। কিন্তু এটা একটা অনুমান, নিশ্চয়তা না — আর ভুল অনুমান হলে SJF-এর optimality প্রমাণটাই আর প্রযোজ্য থাকে না।

২. Starvation। যদি ছোট job-এর একটা অবিরাম স্রোত আসতে থাকে, একটা লম্বা job কখনো চলার সুযোগ পাবে না — প্রতিবার তার আগে কোনো না কোনো ছোট job এসে সামনে ঢুকে পড়বে। এটাই মূল কারণ কেন কোনো general-purpose OS বিশুদ্ধ SJF ব্যবহার করে না।

Round Robin — quantum-এর দাম

Round Robin (RR): প্রতিটা thread একটা fixed quantum পায়, তারপর জোর করে সরিয়ে queue-র পেছনে পাঠানো হয় (যদি এখনো শেষ না হয়ে থাকে), পরের thread-এর পালা।

Response time bounded — একটা thread সর্বোচ্চ (n-1) × quantum সময় অপেক্ষা করবে ( $n$ = ready thread সংখ্যা)। কিন্তু quantum ছোট করলে গত লেসনের সংখ্যাটা ফিরে আসে — প্রতিটা switch-এর একটা সরাসরি খরচ আছে (আমাদের মাপা ~৯ μs, cache warm-up ধরলে আরও বেশি)।

quantum খুব ছোট (≈ switch cost)  →  বেশিরভাগ সময় switching-এই যায়, throughput ধ্বংস
quantum খুব বড় (≫ সব burst)      →  RR কার্যত FIFO হয়ে যায়, response সুবিধা হারায়

এই কারণেই বাস্তব general-purpose OS-এর quantum μs নয়, বরং কয়েক millisecond — Linux-এ ডিফল্ট base slice প্রায় 0.75-3ms range-এ থাকে (sched_min_granularity_ns, লেসন ৯-এ বিস্তারিত) — সেই μs-স্কেলের switch cost-এর তুলনায় বহুগুণ বড়, তাই overhead ছোট একটা ভগ্নাংশ থাকে, কিন্তু interactive response-এর জন্য যথেষ্ট ছোটও।

Priority scheduling আর priority inversion — Mars Pathfinder-এর গল্প

Priority scheduling: প্রতিটা thread-এর একটা priority থাকে, সবসময় সর্বোচ্চ-priority ready thread চলে (preemptive) — নিম্ন-priority thread শুধু তখনই চলে যখন উচ্চতর priority-র কোনো thread ready নেই।

এটা শুনতে সহজ মনে হয়, কিন্তু এর একটা বিপজ্জনক ফাঁক আছে যখন priority-ওয়ালা thread-গুলো একটা shared lock ভাগ করে। ১৯৯৭-এর জুলাইয়ে, NASA-র Mars Pathfinder ল্যান্ডার মঙ্গলে অবতরণের কয়েকদিন পর বারবার সম্পূর্ণ system reset করতে শুরু করল — কোনো স্পষ্ট কারণ ছাড়াই। প্রতিটা reset মানে হারানো তথ্য, আর একটা মহাকাশযান কোটি মাইল দূরে যার সাথে সরাসরি hardware access নেই।

যা প্রকৃতপক্ষে ঘটছিল (VxWorks RTOS-এ, priority-based preemptive scheduling):

Mars Pathfinder priority inversion — ধাপে ধাপে

নিম্ন-priority: meteorological (ASI/MET) taskপর্যায়ক্রমে জেগে shared information bus-এ ডেটা লেখে, তার জন্য একটা mutex ধরে
mutex acquiredএখন এই নিম্ন-priority task-ই bus-এর তথ্যের একমাত্র মালিক, সাময়িকভাবে
মধ্যম-priority: communications task জেগে ওঠেmutex-এর সাথে সম্পর্কহীন কাজ, কিন্তু priority বেশি বলে নিম্ন-priority task-কে preempt করে
উচ্চ-priority: bus management task ready হয়তারও ওই mutex লাগবে — কিন্তু সেটা এখনো নিম্ন-priority task-এর হাতে
উচ্চ-priority task block করে mutex-এর জন্যযার মালিক (নিম্ন-priority) নিজেই CPU পাচ্ছে না, কারণ মধ্যম-priority task চলছে
ফলাফল: উচ্চ-priority কাজ deadline miss করেwatchdog টাইমার সন্দেহ করে সিস্টেম "hang" হয়েছে, পুরো reset করে

এখানে ভয়াবহ অংশটা লক্ষ্য করুন: মধ্যম-priority task-এর ওই mutex-এর সাথে কোনো সম্পর্কই নেই — সে শুধু নিজের priority বেশি বলে CPU দখল করে রেখেছে, আর তার ফলে পরোক্ষভাবে সর্বোচ্চ-priority task-কেও আটকে দিচ্ছে। এটাই priority inversion — কার্যকরভাবে একটা উচ্চ-priority thread একটা নিম্ন-priority thread-এর “অপেক্ষায়” থাকে, কিন্তু মাঝখানে একটা মধ্যম-priority thread সেই অপেক্ষাকে অনির্দিষ্টকাল দীর্ঘায়িত করে।

সমাধান কীভাবে এলো: JPL-এর ইঞ্জিনিয়ার Glenn Reeves আর দল মঙ্গলে থাকা সফটওয়্যারে সরাসরি নতুন কোড আপলোড না করে, VxWorks-এর একটা বিদ্যমান debug/trace সুবিধা remotely চালু করলেন, লক্ষণগুলো নিশ্চিত করলেন যে এটাই classic priority inversion, তারপর mutex তৈরির সময় একটা flag চালু করলেন যা priority inheritance সক্রিয় করে — কোনো নতুন বাইনারি আপলোড ছাড়াই, শুধু বিদ্যমান কনফিগারেশনের একটা flag flip করে।

Priority inheritance protocol (Sha, Rajkumar, Lehoczky, 1990): যখন একটা উচ্চ-priority thread একটা lock-এর জন্য block করে যেটা একটা নিম্ন-priority thread ধরে আছে, নিম্ন-priority thread-এর priority সাময়িকভাবে সেই উচ্চ-priority thread-এর স্তরে বাড়িয়ে দেওয়া হয় — যতক্ষণ না সে lock ছাড়ে। এর মানে এখন কোনো মধ্যম-priority thread আর তাকে preempt করতে পারবে না, কারণ সে (সাময়িকভাবে) নিজেই সর্বোচ্চ-priority।

Inheritance ছাড়া:  নিম্ন(lock ধরে) → মধ্যম প্রিয়েম্পট করে → উচ্চ অনির্দিষ্টকাল আটকে
Inheritance সহ:    নিম্ন(lock ধরে) → priority উচ্চ-তে বেড়ে যায় → মধ্যম আর প্রিয়েম্পট করতে পারে না → lock দ্রুত মুক্ত হয়

lock ছাড়ার সাথে সাথে priority আগের স্তরে ফিরে আসে। Blocking সম্পূর্ণ দূর হয় না (উচ্চ-priority thread-কে তবুও lock মুক্ত হওয়া পর্যন্ত অপেক্ষা করতে হয়), কিন্তু সেই অপেক্ষা এখন bounded — শুধু নিম্ন-priority thread-এর নিজের critical section-এর সময়টুকু, কোনো তৃতীয় পক্ষের অনির্দিষ্টকালীন হস্তক্ষেপ নয়। Sha et al.-এর পেপার এই bound formally প্রমাণ করে।

Preemptive বনাম cooperative scheduling

Preemptive: OS timer interrupt দিয়ে যেকোনো মুহূর্তে একটা thread-কে জোর করে সরাতে পারে, thread-এর সম্মতি ছাড়াই — আজকের প্রায় সব general-purpose OS (Linux, Windows, macOS) এটাই করে।

Cooperative: thread নিজে থেকে yield() না ডাকা পর্যন্ত, বা block না করা পর্যন্ত, কেউ তাকে সরাতে পারে না। একটা misbehaving বা infinite-loop-এ আটকে যাওয়া thread পুরো সিস্টেমকে জমিয়ে দিতে পারে — এটাই ছিল ক্লাসিক Windows 3.1 আর classic Mac OS-এর বাস্তবতা, যেখানে একটা খারাপ-লেখা অ্যাপ পুরো GUI freeze করে দিত।

আজও cooperative model বেঁচে আছে, কিন্তু ভিন্ন স্তরে: gত থ্রেড-লেসনের green thread/goroutine model user-level-এ cooperative — Go runtime নিজেই ঠিক করে কখন একটা goroutine অন্যটাকে সুযোগ দেবে (সাধারণত function call boundary-তে, বা explicit blocking operation-এ)। কিন্তু নিচে যে OS thread-গুলোর উপর এই runtime বসে আছে, সেগুলো OS kernel-এর কাছে সম্পূর্ণ preemptive। দুইটা স্তর, দুইটা ভিন্ন মডেল — এটাই এই বিষয়ের আধুনিক রূপ।

CPU-bound আর I/O-bound মেশানো — আসল কঠিন অংশ

এতক্ষণ আমরা ধরে নিয়েছি সব job শুধু CPU ব্যবহার করে, শেষ পর্যন্ত। বাস্তবে workload মিশ্রিত:

I/O-bound thread অল্প সময় চলে, তারপর I/O-তে block করে (disk read, network recv)। সে চায় দ্রুত সাড়া — যত তাড়াতাড়ি তার সামান্য CPU কাজ শেষ হবে, তত তাড়াতাড়ি সে পরের I/O request পাঠাতে পারবে, device-কে ব্যস্ত রাখতে পারবে।
CPU-bound thread দীর্ঘ, একটানা burst চায় — বারবার switch হলে শুধু overhead বাড়ে, throughput কমে।

একই quantum দুই ধরনের thread-কেই ভালোভাবে সেবা দিতে পারে না। ছোট quantum I/O-bound-এর জন্য ভালো কিন্তু CPU-bound-এর জন্য ব্যয়বহুল; বড় quantum উল্টো। আর একটা সিস্টেমে দুই ধরনের thread-ই একসাথে থাকে — একটা fixed quantum-ওয়ালা নীতি কাউকে না কাউকে বঞ্চিত করবেই।

ভেতরে কী ঘটছে

Timer interrupt থেকে scheduling decision পর্যন্ত

গত লেসনে switch_to()-এর mechanism দেখেছি — register save, CR3 বদল। কিন্তু একটা প্রশ্ন সেখানে উত্তরহীন রেখেছিলাম: কে ঠিক করে পরে কে চলবে? সেই সিদ্ধান্তটা switch_to()-এর আগে নেওয়া হয়, একটা policy-নির্ভর ফাংশনে।

Timer interrupt থেকে switch_to() কল পর্যন্ত

Timer interrupt আসেহার্ডওয়্যার, প্রতি কয়েক ms-এ একবার, লেসন ২২-এ বিস্তারিত
Interrupt handler → scheduler_tick()বর্তমান thread কতক্ষণ চলল তার হিসাব আপডেট হয়
Policy-নির্দিষ্ট প্রশ্ন"quantum শেষ?" (RR) / "ছোট burst-ওয়ালা কেউ ready হয়েছে?" (SRTF) / "উচ্চ-priority কেউ ready?" (priority)
যদি উত্তর হ্যাঁ: pick_next()ready queue থেকে পরবর্তী thread বাছাই — policy-নির্দিষ্ট নিয়মে
switch_to(current, next)গত লেসনের mechanism — register save/restore, দরকার হলে CR3

pick_next()-এর ভেতরটা policy-ভেদে সম্পূর্ণ ভিন্ন, কিন্তু স্বাক্ষর একই — ready queue দাও, একটা thread ফেরত নাও:

# Round Robin — সবচেয়ে সরল pick_next
def pick_next_rr(ready_queue):
    return ready_queue.pop(0)     # FIFO order-এই bhabe, শুধু quantum-এ কাটা

# Priority — সাথে inheritance-এর হিসাব
def pick_next_priority(ready_queue):
    # effective_priority = max(নিজের priority, যতগুলো thread
    # তার held lock-এর জন্য block করে আছে তাদের priority)
    return max(ready_queue, key=lambda t: t.effective_priority)

effective_priority-র এই max() ফাংশনটাই priority inheritance-এর মূল যন্ত্র — উপরে যে কথা বলা হয়েছিল তার বাস্তবায়ন এক লাইনে।

উদাহরণ

একটা সম্পূর্ণ তুলনা — একই workload, তিনটা policy

চারটা job, একই মেশিনে একই মুহূর্তে (সব সময় abstract একক, ধরুন millisecond):

Job	Arrival	Burst
J1	0	6
J2	1	2
J3	2	8
J4	3	3

FIFO (arrival order অনুযায়ী, শেষ পর্যন্ত চালানো):

Gantt:  J1(0-6) J2(6-8) J3(8-16) J4(16-19)

Job	Finish	Turnaround	Response
J1	6	6	0
J2	8	7	5
J3	16	14	6
J4	19	16	13

গড় turnaround = 10.75, গড় response = 6.00

SJF (non-preemptive, প্রতিবার সবচেয়ে ছোট burst-ওয়ালা ready job বাছা):

Gantt:  J1(0-6) J2(6-8) J4(8-11) J3(11-19)

J1 প্রথমে বাধ্যতামূলক (একমাত্র ready)। t=6-এ J2(2), J3(8), J4(3) ready — J2 জেতে। t=8-এ J3(8) বনাম J4(3) — J4 জেতে। শেষে J3।

Job	Finish	Turnaround	Response
J1	6	6	0
J2	8	7	5
J4	11	8	5
J3	19	17	9

গড় turnaround = 9.50, গড় response = 4.75 — turnaround-এ FIFO-র চেয়ে ভালো, ঠিক যেমন প্রমাণ বলে।

Round Robin, quantum=4 (নতুন arrival আগে queue-তে যোগ হয়, preempt-হওয়া job তারপর পেছনে যায়):

Gantt:  J1(0-4) J2(4-6) J3(6-10) J4(10-13) J1(13-15) J3(15-19)

Job	Finish	Turnaround	Response
J1	15	15	0
J2	6	5	3
J3	19	17	4
J4	13	10	7

গড় turnaround = 11.75, গড় response = 3.50

তিন নম্বরের গল্প — একনজরে

Policy	গড় turnaround	গড় response
FIFO	10.75	6.00
SJF	9.50 (সেরা)	4.75
RR(q=4)	11.75 (সবচেয়ে খারাপ)	3.50 (সেরা)

লক্ষ্য করুন — RR-এর turnaround FIFO-র চেয়েও খারাপ! কারণ RR বারবার বড় job-গুলোকে (J1, J3) মাঝপথে থামিয়ে ছোট job-দের সুযোগ দিচ্ছে, ফলে বড় job-দের completion পিছিয়ে যাচ্ছে। কিন্তু response time-এ RR স্পষ্টতই সেরা — প্রতিটা job দ্রুত প্রথম সাড়া পাচ্ছে।

এটাই সেই trade-off যা প্রমাণ ছাড়া বললে বিশ্বাসযোগ্য লাগত না, সংখ্যায় দেখলে অনস্বীকার্য। এই হিসাবে switch-এর প্রকৃত খরচ (গত লেসনের ~৯ μs) ধরা হয়নি — এই সময়ের একক যদি millisecond হয়, তাহলে ৬টা switch-এর মোট overhead ~৫৪ μs, যা ১৯ms-এর schedule-এ নগণ্য। এটাই আসল কারণ কেন quantum switch-cost-এর চেয়ে বহুগুণ বড় রাখা হয় — overhead কে হিসাবের বাইরে ঠেলে দেওয়ার জন্য।

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

EXPERIMENT

নিজের scheduler simulator চালান — একই workload, তিন policy

Python 3, যেকোনো OS· ১৫ মিনিট

from dataclasses import dataclass, field

@dataclass
class Job:
    jid: str
    arrival: int
    burst: int
    finish: int = None
    remaining: int = field(init=False)
    first_run: int = None
    def __post_init__(self):
        self.remaining = self.burst

def fifo(jobs):
    t, trace = 0, []
    for j in sorted(jobs, key=lambda j: j.arrival):
        t = max(t, j.arrival)
        j.first_run = t
        trace.append((j.jid, t, t + j.burst))
        t += j.burst
        j.finish = t
    return trace

def sjf(jobs):
    t, remaining, trace = 0, sorted(jobs, key=lambda j: j.arrival), []
    while remaining:
        ready = [j for j in remaining if j.arrival <= t]
        if not ready:
            t = min(j.arrival for j in remaining)
            continue
        j = min(ready, key=lambda j: j.burst)
        j.first_run = t
        trace.append((j.jid, t, t + j.burst))
        t += j.burst
        j.finish = t
        remaining.remove(j)
    return trace

def round_robin(jobs, quantum):
    t, queue, trace = 0, [], []
    arrivals = sorted(jobs, key=lambda j: j.arrival)
    i = 0
    def admit():
        nonlocal i
        while i < len(arrivals) and arrivals[i].arrival <= t:
            queue.append(arrivals[i]); i += 1
    admit()
    while queue:
        j = queue.pop(0)
        if j.first_run is None:
            j.first_run = t
        run = min(quantum, j.remaining)
        trace.append((j.jid, t, t + run))
        t += run
        j.remaining -= run
        admit()
        if j.remaining > 0:
            queue.append(j)
        else:
            j.finish = t
    return trace

def report(name, jobs, trace):
    print(f"--- {name} ---")
    print("Gantt:", " ".join(f"{jid}({s}-{e})" for jid, s, e in trace))
    turns = [j.finish - j.arrival for j in jobs]
    resps = [j.first_run - j.arrival for j in jobs]
    print(f"avg turnaround={sum(turns)/len(turns):.2f}  "
          f"avg response={sum(resps)/len(resps):.2f}\n")

def make_jobs():
    return [Job("J1", 0, 6), Job("J2", 1, 2), Job("J3", 2, 8), Job("J4", 3, 3)]

j = make_jobs(); report("FIFO", j, fifo(j))
j = make_jobs(); report("SJF", j, sjf(j))
j = make_jobs(); report("RR(q=4)", j, round_robin(j, 4))

python3 sched_sim.py

প্রকৃত ফলাফল (যাচাইকৃত — উপরের হাতে-করা হিসাবের সাথে নির্ভুল মিলবে):

--- FIFO ---
Gantt: J1(0-6) J2(6-8) J3(8-16) J4(16-19)
avg turnaround=10.75  avg response=6.00

--- SJF ---
Gantt: J1(0-6) J2(6-8) J4(8-11) J3(11-19)
avg turnaround=9.50  avg response=4.75

--- RR(q=4) ---
Gantt: J1(0-4) J2(4-6) J3(6-10) J4(10-13) J1(13-15) J3(15-19)
avg turnaround=11.75  avg response=3.50

নিজে চেষ্টা করুন: quantum ১, ২, ৮, ১৬ করে চালান — response time কীভাবে বদলায়, আর কোন বিন্দুতে RR কার্যত FIFO-র মতো আচরণ শুরু করে দেখুন।

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

উপরের হাতে-করা হিসাব একটা প্রোগ্রামেও একই সংখ্যা দেয় — scheduling metric একটা বিমূর্ত ধারণা নয়, নির্ভুলভাবে গণনাযোগ্য।

EXPERIMENT

`nice` দিয়ে CPU share বদলানো — প্রথম পর্যবেক্ষণ

Linux· ১০ মিনিট

দুইটা CPU-bound busy loop একই core-এ বেঁধে, ভিন্ন nice value দিয়ে চালান:

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

taskset -c 0 nice -n 19 python3 -c "
while True: pass
" &
PID_LOW=$!

sleep 10
ps -o pid,ni,pcpu,time -p $PID_NORMAL,$PID_LOW
kill $PID_NORMAL $PID_LOW

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

    PID  NI %CPU     TIME
  20142   0 91.2 00:00:09
  20143  19  8.6 00:00:00

nice 0 (স্বাভাবিক priority) প্রায় পুরো core দখল করছে, nice 19 (সর্বনিম্ন priority) সামান্য ভগ্নাংশ পাচ্ছে — কিন্তু শূন্য না। এই অনুপাতটা এলোমেলো নয়, একটা নির্দিষ্ট সূত্র মেনে চলে — পরের লেসনে ঠিক এই সংখ্যাটা তাত্ত্বিকভাবে predict করে মিলিয়ে দেখব।

এবার একটা real-time thread যোগ করুন (root/CAP_SYS_NICE লাগবে), সময়সীমাবদ্ধ করে (timeout দিয়ে, নাহলে সিস্টেম স্লো হয়ে যেতে পারে):

sudo timeout 3 chrt -f 10 taskset -c 0 python3 -c "
while True: pass
" &
taskset -c 0 nice -n 0 python3 -c "
while True: pass
" &
sleep 3
top -bn1 -p $(pgrep -f "while True" | tr '\n' ',' | sed 's/,$//')

SCHED_FIFO (real-time class) thread স্বাভাবিক SCHED_OTHER thread-এর চেয়ে সম্পূর্ণ ভিন্ন স্তরের priority-তে থাকে — এই ৩ সেকেন্ডে normal thread প্রায় কোনো CPU-ই পাবে না। কেন এতটা নাটকীয় পার্থক্য, আর SCHED_FIFO কীভাবে পুরো CPU “starve” করে দিতে পারে — সেটাই পরের লেসনের একটা experiment-এ পুরোপুরি পরিমাপ করা হবে।

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

Priority (এখানে nice value) সরাসরি CPU allocation-কে প্রভাবিত করে — এটা তত্ত্ব নয়, নিজের মেশিনে দেখা যায়।

নিজে বানান

BUILD IT

Pluggable-policy scheduler simulator, text Gantt chart সহ

Python · ●●●○○

Job dataclass আর একটা policy registry (নাম → function) বানান
FIFO, SJF, RR policy তিনটাই এক common ইন্টারফেসে লিখুন — জব লিস্ট নিয়ে একটা trace (jid, start, end) tuple-এর লিস্ট ফেরত দেয়
একটা text Gantt-chart renderer লিখুন যা যেকোনো policy-র trace থেকে একটা visual timeline আঁকে
একই workload সব policy দিয়ে চালিয়ে একটা তুলনামূলক metric টেবিল ছাপুন

উপরের experiment-এর কোডটাই ভিত্তি — এখানে সেটাকে একটা pluggable আর্কিটেকচারে সাজানো হচ্ছে, যাতে নতুন policy যোগ করা এক লাইনের কাজ হয়:

POLICIES = {}

def register(name):
    def deco(fn):
        POLICIES[name] = fn
        return fn
    return deco

@register("FIFO")
def fifo(jobs):
    ...  # আগের মতোই

@register("SJF")
def sjf(jobs):
    ...

@register("RR-4")
def rr4(jobs):
    return round_robin(jobs, quantum=4)

def draw_gantt(trace, width_per_unit=1):
    end = max(e for _, _, e in trace)
    row = [" "] * end
    for jid, s, e in trace:
        for t in range(s, e):
            row[t] = jid[-1]  # শুধু last char (J1 → '1')
    print("".join(row))
    print("".join(str(t % 10) for t in range(end)))

def compare(workload_factory):
    print(f"{'Policy':<10}{'avg_turn':>10}{'avg_resp':>10}{'switches':>10}")
    print("-" * 40)
    for name, policy in POLICIES.items():
        jobs = workload_factory()
        trace = policy(jobs)
        turns = [j.finish - j.arrival for j in jobs]
        resps = [j.first_run - j.arrival for j in jobs]
        print(f"{name:<10}{sum(turns)/len(turns):>10.2f}"
              f"{sum(resps)/len(resps):>10.2f}{len(trace):>10}")
        draw_gantt(trace)
        print()

compare(lambda: [Job("J1",0,6), Job("J2",1,2), Job("J3",2,8), Job("J4",3,3)])

প্রত্যাশিত আউটপুট (metric টেবিলের অংশ):

Policy      avg_turn  avg_resp  switches
----------------------------------------
FIFO           10.75      6.00         4
1111112233333333444
SJF             9.50      4.75         4
1111112244433333333
RR-4           11.75      3.50         6
1111222333344441113333

নিজে বাড়ান

একটা Priority policy যোগ করুন (static priority, ties arrival order দিয়ে ভাঙুন) — একটা লম্বা, নিম্ন-priority job দিয়ে starvation দেখান
switch_cost প্যারামিটার যোগ করুন — প্রতিটা preemption-এ কিছু সময় নষ্ট হয় ধরে নিয়ে RR-এর ছোট quantum-এ throughput কমতে দেখুন
Workload-এ I/O burst যোগ করুন (job মাঝপথে কিছুক্ষণের জন্য “block” হয়) — দেখুন FIFO/SJF/RR প্রতিটা কীভাবে এটা সামলায় (বা সামলাতে ব্যর্থ হয়)

সম্পূর্ণ, অনেক গভীর সংস্করণের জন্য — MLFQ, একটা সরলীকৃত CFS (vruntime-ভিত্তিক), multi-core load balancing, আর বাস্তব Linux-এর সাথে ফলাফল মিলিয়ে দেখা — কারিকুলামের Scheduler Simulator প্রজেক্ট দেখুন (/projects/scheduler-simulator)। এই BuildIt সেই প্রজেক্টের প্রথম ধাপ মাত্র; প্রজেক্টটা লেসন ৯-এর পরে শুরু করাই ভালো, কারণ সেখানে MLFQ আর CFS-এর তত্ত্ব লাগবে।

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

Scheduling নীতি যেখানে সরাসরি প্রভাব ফেলে

Linux scheduler-এর ইতিহাস। প্রথম দিকের Linux একটা সরল priority-ভিত্তিক O(n) scheduler ব্যবহার করত — প্রতিবার পরবর্তী thread বাছতে পুরো ready queue স্ক্যান করতে হতো। ২.৬ কার্নেলে এলো O(1) scheduler (প্রতিটা priority-র জন্য আলাদা bitmap-ইনডেক্সড queue)। ২০০৭-এ CFS (Completely Fair Scheduler) সম্পূর্ণ ভিন্ন মডেল নিয়ে এলো — আর ২০২৩-এ Linux 6.6-এ EEVDF CFS-কে প্রতিস্থাপন করেছে। পরের লেসনেই এই দুইটা বিস্তারিত।

Windows-এর dynamic priority boost। Windows scheduler-এর ৩২টা priority স্তর আছে, আর foreground GUI অ্যাপ্লিকেশন-এর thread-কে সাময়িকভাবে boost করে — যে window-তে আপনি এই মুহূর্তে কাজ করছেন, সেটার responsiveness অন্য background অ্যাপের চেয়ে বেশি গুরুত্ব পায়। I/O সম্পন্ন হওয়ার পরেও সাময়িক boost দেওয়া হয় (interactive thread-কে দ্রুত সাড়া দিতে)।

POSIX priority-inheritance mutex — সরাসরি ব্যবহারযোগ্য API। Mars Pathfinder-এর সমাধান আজ একটা standard library কল:

pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
pthread_mutex_t lock;
pthread_mutex_init(&lock, &attr);

এই flag ছাড়া তৈরি করা mutex-এ priority inversion-এর ঝুঁকি থেকেই যায়। Linux-এর PREEMPT_RT patch set (যা আজ mainline-এর অংশ) real-time workload-এর জন্য এই protocol ব্যাপকভাবে ব্যবহার করে।

Automotive ও avionics — rate-monotonic scheduling। AUTOSAR OS (গাড়ির ECU-তে ব্যবহৃত) আর অনেক avionics RTOS fixed-priority scheduling ব্যবহার করে, যেখানে ছোট period-ওয়ালা task-কে বেশি priority দেওয়া হয় (Liu-Layland-এর ১৯৭৩-এর ক্লাসিক ফলাফল) — deadline miss হবে না তার একটা গাণিতিক schedulability bound প্রমাণ করা যায়, যা এই ধরনের safety-critical সিস্টেমে আবশ্যক। VxWorks আজও অনেক মহাকাশযানে চলে — Curiosity ও Perseverance rover দুটোই।

Connection pooling-এর সাথে সংযোগ (গত লেসনের প্রসঙ্গ ফিরিয়ে আনা)। গত লেসনে দেখেছিলাম কেন thread pool-এর আকার সীমিত রাখা হয়। এখন কারণটা আরও স্পষ্ট — বেশি thread মানে scheduler-এর জন্য বেশি ready queue প্রতিদ্বন্দ্বিতা, বেশি quantum ভাগাভাগি, প্রতিটা thread-এর গড় response time বাড়া। Scheduling policy যতই ভালো হোক, thread সংখ্যা core সংখ্যার তুলনায় অতিরিক্ত বাড়ালে কোনো policy-ই সেটা পুরোপুরি ঢাকতে পারে না।

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

“SJF/SRTF প্রমাণযোগ্যভাবে optimal, তাই বাস্তব OS-এর সেটাই ব্যবহার করা উচিত।”

Optimality-র প্রমাণ একটা লুকানো শর্তের উপর দাঁড়িয়ে — প্রতিটা job-এর burst time আগে থেকে জানা। বাস্তব scheduler-এর কাছে এই তথ্য নেই; একটা thread কখন block করবে বা শেষ হবে তা তার নিজের কোড না দেখে বলার উপায় নেই।

Estimation (exponential moving average দিয়ে) আংশিক সমাধান দেয়, কিন্তু ভুল অনুমানে optimality গ্যারান্টিটাই ভেঙে যায়। তার উপর, বিশুদ্ধ SJF/SRTF একটা মৌলিক ন্যায্যতার সমস্যায় ভোগে — ক্রমাগত ছোট job এলে লম্বা job starve করে, যা একটা general-purpose সিস্টেমে অগ্রহণযোগ্য (একটা ভিডিও এনকোডিং job কখনো শেষ না হওয়া চলবে না শুধু ছোট শেল কমান্ড আসতে থাকার কারণে)।

বাস্তব সমাধান (পরের লেসনে বিস্তারিত): burst-length অনুমান ব্যবহার করা কিছু জায়গায় (যেমন interactive-detection heuristic), কিন্তু starvation-প্রতিরোধী গ্যারান্টি সহ — যেমন aging বা periodic priority boost।

“Round Robin-এ quantum যত ছোট, response time তত ভালো — তাই সবসময় ছোট quantum নেওয়া উচিত।”

এটা শুধু অর্ধেক সত্য — response time সত্যিই কমে, কিন্তু একটা সীমার পরে throughput ধ্বংস হতে শুরু করে, কারণ প্রতিটা quantum-এর শেষে গত লেসনের সেই context-switch খরচ (direct আর indirect দুটোই) বাস্তবায়িত হয়।

যদি quantum switch cost-এর কাছাকাছি নেমে আসে (ধরুন quantum ১০ μs, আর switch cost ৯ μs), তাহলে CPU-র প্রায় অর্ধেক সময় কাজে না লেগে switching-এই যাচ্ছে — কোনো thread-ই কার্যকর progress করছে না।

এটাই একটা U-আকৃতির curve তৈরি করে: quantum কমানোর সাথে সাথে প্রথমে response time দ্রুত ভালো হয় (উপকার বেশি, খরচ কম), কিন্তু একটা বিন্দুর পরে সামান্য response-উন্নতির জন্য বিশাল throughput-মূল্য দিতে হয়। বাস্তব OS-এর quantum (Linux-এ কয়েক ms) সেই curve-এর সর্বনিম্ন বিন্দুর কাছাকাছি বসানো, শূন্যের কাছাকাছি নয়।

“Priority inversion একটা বিরল, শুধু তাত্ত্বিক সমস্যা — বাস্তবে ঘটে না।”

Mars Pathfinder এই ধারণাটা সরাসরি খণ্ডন করে — একটা real, মহাব্যয়বহুল, উৎক্ষেপণ-পরবর্তী মহাকাশযানে এটা ঘটেছিল, আর প্রায় মিশন ব্যর্থ করে দিচ্ছিল। এই ধরনের bug বিশেষভাবে বিপজ্জনক কারণ এটা intermittent — শুধু একটা নির্দিষ্ট timing-এ তিনটা thread একসাথে সংঘর্ষে এলে প্রকাশ পায়, তাই সাধারণ টেস্টিং-এ প্রায়ই ধরা পড়ে না, উৎপাদনে গিয়ে হঠাৎ দেখা দেয়।

এটা এতটাই সাধারণ একটা সমস্যা যে আজ POSIX standard-এর নিজস্ব সমাধান আছে (PTHREAD_PRIO_INHERIT), প্রায় প্রতিটা real-time OS (VxWorks, QNX, Linux PREEMPT_RT) priority inheritance বা priority ceiling protocol বাস্তবায়ন করে। এই সমাধানগুলো এত ব্যাপকভাবে existing না হলে যুক্তি দেওয়া কঠিন হতো যে সমস্যাটা “বিরল” — বরং সমস্যাটা এত real যে পুরো industry standard সমাধান তৈরি করেছে।

ব্যবহারিক পরিণতি: যেকোনো priority-based real-time বা near-real-time সিস্টেমে shared lock ব্যবহার করলে priority inheritance (বা priority ceiling) protocol ছাড়া mutex ব্যবহার করা একটা সুপ্ত ঝুঁকি, শুধু “সম্ভাবনা কম” ভেবে উপেক্ষা করার মতো না।

“Preemptive scheduling সবসময় cooperative-এর চেয়ে ভালো, তাই cooperative model পুরনো, অপ্রাসঙ্গিক ধারণা।”

Preemptive OS scheduling নিঃসন্দেহে general-purpose সিস্টেমে জিতেছে — একটা misbehaving thread পুরো সিস্টেম জমিয়ে দিতে পারবে না, এটা একটা মৌলিক নির্ভরযোগ্যতার গ্যারান্টি। কিন্তু cooperative model আজও user-level এ ব্যাপকভাবে ব্যবহৃত, আর সেখানে এটা ত্রুটি না, বরং একটা সচেতন ডিজাইন পছন্দ।

Go-র goroutine scheduler, Python-এর asyncio, Node.js-এর event loop — এরা সবাই user-level-এ cooperative: কোড নিজে থেকে await/blocking call/explicit yield না করা পর্যন্ত control বদলায় না। এটা preemptive-এর চেয়ে কম নিরাপদ (একটা tight CPU loop পুরো event loop ব্লক করতে পারে), কিন্তু বিনিময়ে পাওয়া যায় ভয়ানক সস্তা “context switch” (শুধু একটা function call, কোনো kernel involvement নেই, কোনো register-save/CR3-বদলের খরচ নেই — গত লেসনের পুরো আলোচনাটাই user-level-এ প্রায় শূন্যে নেমে আসে)।

নিয়ম: যেখানে নির্ভরযোগ্যতা ও isolation মুখ্য (general-purpose OS kernel), preemptive অপরিহার্য। যেখানে predictable, disciplined code চলে আর switch-cost কমানোই মুখ্য লক্ষ্য (async runtime, green thread scheduler), cooperative একটা যুক্তিসঙ্গত, ব্যাপকভাবে প্রমাণিত পছন্দ — দুইটা মডেলই আজও সহাবস্থান করছে, ভিন্ন স্তরে।

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

Exchange-argument প্রমাণের ধারণাটা আবার লিখুন নিজের ভাষায় — কেন কোনো “বড় burst আগে, ছোট burst পরে” জোড়া schedule-এ থাকলে সেটা সবসময় উল্টে দিলে (বা সমান) গড় turnaround কমে (বা সমান থাকে), কখনো বাড়ে না?

যুক্তি

মূল পর্যবেক্ষণ: দুইটা পরপর জব উল্টালে শুধু তাদের নিজেদের আর “মাঝখানের” সময় বদলায়, বাকি সব job-এর completion time অপরিবর্তিত থাকে।

ধরুন schedule-এ পরপর দুইটা job আছে — $A$ (burst $b_A$ ) তারপর $B$ (burst $b_B$ ), আর $A$ শুরু হওয়ার ঠিক আগের সময় $t$ । এই দুইটা ছাড়া বাকি সব job-এর অবস্থান স্থির।

মূল ক্রমে (A আগে, B পরে):

$A$ শেষ হয় $t + b_A$ -তে
$B$ শেষ হয় $t + b_A + b_B$ -তে
দুইজনের সম্মিলিত completion time = $(t + b_A) + (t + b_A + b_B) = 2t + 2b_A + b_B$

উল্টানো ক্রমে (B আগে, A পরে):

$B$ শেষ হয় $t + b_B$ -তে
$A$ শেষ হয় $t + b_B + b_A$ -তে
সম্মিলিত completion time = $(t + b_B) + (t + b_B + b_A) = 2t + 2b_B + b_A$

পার্থক্য (মূল − উল্টানো):

$(2t + 2b_A + b_B) - (2t + 2b_B + b_A) = b_A - b_B$

যদি $b_A > b_B$ (অর্থাৎ বড়টা আগে ছিল), তাহলে এই পার্থক্য ধনাত্মক — মানে মূল ক্রমের সম্মিলিত completion time বেশি। উল্টে দিলে (ছোটটা আগে) সম্মিলিত completion time কমে, ঠিক $b_A - b_B$ পরিমাণ। বাকি সব job-এর completion time অপরিবর্তিত থাকে বলে মোট (সব job মিলিয়ে) completion time-ও একই পরিমাণে কমে।

উপসংহার: schedule-এ যদি এমন কোনো “বড় আগে, ছোট পরে” জোড়া থেকে যায়, সেটা উল্টে সবসময় উন্নতি করা যায় (বা কমপক্ষে সমান)। যে schedule-এ আর কোনো এমন জোড়া নেই — অর্থাৎ burst-এর অ-হ্রাসমান (non-decreasing) ক্রমে সাজানো — সেটাই local optimum, আর এই ধরনের adjacent-swap যুক্তিতে local optimum-ই global optimum (কারণ যেকোনো non-sorted ক্রম থেকে সসীম সংখ্যক swap দিয়ে sorted ক্রমে পৌঁছানো যায়, প্রতিটা swap-ই উন্নতি করে বা সমান রাখে)।

এই একই কৌশল কোথায় আবার দেখবেন: Level 6 (Algorithms)-এ interval scheduling maximization, Huffman coding-এর optimality, আর greedy algorithm-এর সাধারণ “exchange argument” প্রমাণ-পদ্ধতির ভিত্তি এই একই ধারণা — একটা প্রস্তাবিত সমাধান optimal সমাধানের থেকে আলাদা হলে, একটা local swap দিয়ে দেখানো যে সেটা কখনো খারাপ করে না, এবং যথেষ্ট swap-এ optimal-এ পৌঁছানো যায়।

তিনটা job: J1 (arrival 0, burst 4), J2 (arrival 2, burst 4), J3 (arrival 4, burst 4)। FIFO আর RR(quantum=2)-এ হাতে হিসাব করুন — Gantt chart, প্রতিটা job-এর turnaround ও response, আর গড়। একটা interactive shell-এর জন্য কোনটা বেছে নেবেন, আর কেন?

প্রয়োগ

FIFO:

Gantt: J1(0-4) J2(4-8) J3(8-12)

Job	Finish	Turnaround	Response
J1	4	4	0
J2	8	6	2
J3	12	8	4

গড় turnaround = (4+6+8)/3 = 6.00, গড় response = (0+2+4)/3 = 2.00

RR(quantum=2):

t=0: queue=[J1]. J1 চলে 0-2 (remaining4-2=2)। t=2-এ J2 আসে, queue=[J2, J1(rem2)]। t=2: J2 চলে 2-4 (remaining4-2=2)। queue=[J1(rem2), J2(rem2)]। t=4: J1 চলে 4-6, শেষ (remaining0)। এই সময়ে t=4-এ J3 আসে, কিন্তু J1 আগেই pop হয়ে গেছে চলার জন্য — J3 queue-তে যোগ হয় J1 শেষ হওয়ার পর: queue=[J2(rem2), J3]। t=6: J2 চলে 6-8, শেষ। queue=[J3]। t=8: J3 চলে 8-12 (পুরো burst বাকি, single run-এ শেষ কারণ আর কেউ নেই preempt করার)।

Gantt: J1(0-2) J2(2-4) J1(4-6) J2(6-8) J3(8-12)

Job	Finish	Turnaround	Response
J1	6	6	0
J2	8	6	0
J3	12	8	4

গড় turnaround = (6+6+8)/3 = 6.67, গড় response = (0+0+4)/3 = 1.33

তুলনা:

Policy	গড় turnaround	গড় response
FIFO	6.00	2.00
RR(q=2)	6.67	1.33

Interactive shell-এর জন্য RR(q=2) ভালো পছন্দ। একটা শেলে আপনি একটা কমান্ড টাইপ করলে তাৎক্ষণিক সাড়া চান — সেই কমান্ড কখন “সম্পূর্ণভাবে” শেষ হলো তা নিয়ে আপনি খুব একটা ভাবেন না (বেশিরভাগ শেল কমান্ড এমনিতেই কয়েক ms-এর মধ্যে শেষ হয়ে যায়)। Response time-ই এখানে user-experience নির্ধারণ করে, turnaround না — আর এই ছোট উদাহরণেই RR-এর response 33% ভালো, turnaround মাত্র 11% খারাপ। বিনিময়টা এখানে স্পষ্টভাবে RR-এর পক্ষে।

এর উল্টো ক্ষেত্র হবে batch job queue (রাতভর ব্যাচ প্রসেসিং) — সেখানে turnaround-ই মুখ্য, FIFO (বা SJF) ভালো পছন্দ। Level 11-এ perf/tracing tool দিয়ে বাস্তব সিস্টেমে এই response-time সংখ্যাগুলো সরাসরি মাপা শেখানো হবে, শুধু হাতে-হিসাব না।

আপনি একটা সিস্টেম ডিজাইন করছেন যেখানে একসাথে চলছে একটা video encoder (দীর্ঘ, একটানা CPU burst, throughput মুখ্য) আর একটা UI thread (ঘন ঘন সামান্য কাজ করে, তারপর ইনপুটের জন্য অপেক্ষা করে, response মুখ্য)। এই লেসনের classic policy-গুলোর মধ্যে কোনোটা একা ব্যবহার করলে কী সমস্যা হবে? আপনি কীভাবে এই দুই বিপরীতমুখী চাহিদা মেটাবেন?

ডিজাইন

একটা single classic policy দিয়ে দুইটা চাহিদাই মেটানো সম্ভব না — প্রতিটাই একটাকে জেতাতে গিয়ে অন্যটাকে বলি দেয়।

FIFO ব্যবহার করলে: যদি encoder আগে arrival হয়, UI thread-এর প্রতিটা ইনপুট ইভেন্ট encoder শেষ না হওয়া পর্যন্ত অপেক্ষা করবে — convoy effect, UI সম্পূর্ণ অসাড়। ব্যবহারকারীর কাছে “সিস্টেম freeze” মনে হবে।

SJF/SRTF ব্যবহার করলে: UI thread-এর burst ছোট বলে সে প্রায় সবসময় জিতবে, encoder প্রায় না চলার মতো — encoding কখনো এগোবে না যদি UI thread ঘন ঘন সামান্য কাজ পাঠাতে থাকে। এটাও আরেক ধরনের starvation।

RR ব্যবহার করলে (fixed quantum): কাজ করবে, কিন্তু quantum নির্বাচনে সমস্যা — যদি quantum encoder-এর জন্য বড় করা হয় (throughput ভালো), UI response খারাপ হবে (একটা ইনপুট ইভেন্টের জন্য পুরো quantum অপেক্ষা করতে হতে পারে)। যদি quantum ছোট করা হয় (UI-এর জন্য ভালো), encoder ঘন ঘন preempt হয়ে overhead-এ ভুগবে।

সমাধানের দিক নির্দেশনা (যা পরের লেসনের বিষয়):

একটা adaptive policy দরকার যেটা প্রতিটা thread-এর সাম্প্রতিক আচরণ পর্যবেক্ষণ করে নিজে থেকে সিদ্ধান্ত বদলায়:

UI thread যেহেতু বারবার নিজে থেকে block করে (voluntary switch, গত লেসনের পরিভাষায়) — তাকে সাময়িকভাবে উচ্চ priority দেওয়া যায়, কারণ সে যাই হোক অল্প সময়ের মধ্যেই আবার নিজে থেকে CPU ছেড়ে দেবে (তার নিজের interest-এই)
Encoder যেহেতু কখনো নিজে থেকে ছাড়ে না (involuntary switch বেশি) — তাকে নিম্ন priority-তে রাখা যায়, কারণ তার fairness আক্রান্ত হবে না উল্লেখযোগ্যভাবে (সে এমনিতেই long-running, কিছু ms দেরি তার overall progress-এ নগণ্য)

এটাই Multi-Level Feedback Queue (MLFQ)-এর মূল ধারণা — একটা thread কতটা “interactive” (ঘন ঘন voluntary block করে) তার পর্যবেক্ষিত ইতিহাস অনুযায়ী priority স্বয়ংক্রিয়ভাবে সমন্বয় করা, কোনো programmer-নির্ধারিত static priority ছাড়াই। Linux-এর CFS/EEVDF একটা ভিন্ন গাণিতিক মডেল (vruntime, fairness-ভিত্তিক) দিয়ে একই সমস্যার সমাধান করে — দুটোই পরের লেসনের বিষয়, আর এই প্রশ্নের উত্তরটাই সেই লেসনের প্রেরণা।

একটা production সিস্টেমে একটা high-priority monitoring thread মাঝেমধ্যে (প্রতি কয়েক ঘণ্টায় একবার) তার deadline miss করছে, যদিও গড় CPU utilization মাত্র ৪০%। আপনি সন্দেহ করছেন এটা priority inversion। কীভাবে নিশ্চিত করবেন, আর কীভাবে ঠিক করবেন?

প্রয়োগ

নিশ্চিত করার ধাপ:

১. লক্ষণ মেলানো। Priority inversion-এর signature হলো intermittent, low-utilization সত্ত্বেও deadline miss — ঠিক এই বর্ণনার সাথে মেলে। যদি miss গুলো সবসময় নির্দিষ্ট timing-এ (একটা নির্দিষ্ট মধ্যম-priority thread সক্রিয় থাকার সময়) হয়, সেটা আরও শক্তিশালী ইঙ্গিত।

২. কোন lock-এ block হচ্ছে খুঁজে বের করা। High-priority thread যখন miss করে, সেই মুহূর্তে সে কী করছিল — strace (কোন syscall-এ block) বা kernel-এর scheduling tracer (trace-cmd/ftrace with sched_switch events) দিয়ে দেখুন সে কোনো mutex/semaphore-এর জন্য অপেক্ষা করছিল কি না।

৩. Lock-এর মালিক কে ছিল, আর সেই মালিক কেন CPU পাচ্ছিল না। যদি lock-এর মালিক একটা নিম্ন-priority thread হয়, আর ঠিক সেই সময় একটা মধ্যম-priority thread চলছিল (যার lock-টার সাথে কোনো সম্পর্কই নেই) — এটাই classic priority inversion-এর নিশ্চিত প্রমাণ, Mars Pathfinder-এর হুবহু প্যাটার্ন।

# Linux-এ ftrace দিয়ে sched_switch trace করা
echo sched_switch > /sys/kernel/debug/tracing/set_event
cat /sys/kernel/debug/tracing/trace_pipe

সমাধান:

১. Priority-inheritance mutex ব্যবহার করা। যদি এখনো PTHREAD_PRIO_INHERIT ছাড়া সাধারণ mutex ব্যবহার হচ্ছে, সেটাকে pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT) দিয়ে পুনর্গঠন করুন — lock-holder সাময়িকভাবে উচ্চ-priority পাবে, মধ্যম-priority thread আর তাকে preempt করতে পারবে না।

২. Priority ceiling protocol (বিকল্প)। প্রতিটা lock-এর সাথে একটা static “ceiling priority” (তাকে ব্যবহারকারী সর্বোচ্চ priority thread-এর সমান) বেঁধে দেওয়া — lock নেওয়ার সাথে সাথে priority সেই ceiling-এ বেড়ে যায়, ধরে রাখার সময়ও, শুধু inheritance-এর মতো “প্রয়োজনে” না। Bounded blocking-এর একটা শক্তিশালী গ্যারান্টি দেয়, কিন্তু বেশি রক্ষণশীল (lock না নিলেও কখনো কখনো priority বেশি থাকে)।

৩. Critical section সংক্ষিপ্ত করা। সাধারণ নিয়ম — একটা lock যত কম সময় ধরে রাখা হয়, inversion-এর “জানালা” তত ছোট, আর inheritance protocol চালু না থাকলেও ক্ষতি সীমিত থাকে।

যাচাই: fix apply করার পর একই কয়েক-ঘণ্টার production load-এ trace আবার নিয়ে দেখুন miss বন্ধ হয়েছে কি না। এই ধরনের timing-নির্ভর bug-এর জন্য একবার fix করেই নিশ্চিত হওয়া ঠিক না — কয়েকদিনের পর্যবেক্ষণ লাগে, কারণ trigger করা condition নিজেই বিরল।

একটা modern preemptive OS-এও কিছু জায়গায় “cooperative” আচরণ থেকে যায় — যেমন একটা kernel spinlock ধরে থাকা অবস্থায় preemption সাময়িকভাবে বন্ধ রাখা হয়। কেন একটা পুরোপুরি preemptive সিস্টেমেও এই ধরনের ছোট “non-preemptible window” দরকার হয়?

যুক্তি

কারণ preemption নিজেই বিপজ্জনক হতে পারে যদি সেটা এমন একটা মুহূর্তে ঘটে যখন কোনো shared data structure একটা অসম্পূর্ণ, অস্থায়ী অবস্থায় আছে।

ধরুন kernel-এর একটা code path একটা linked list-এ নতুন node যোগ করছে — এই কাজটা কয়েকটা ধাপে হয় (নতুন node-এর pointer সেট করা, তারপর পুরনো tail-এর next pointer বদলানো)। যদি ঠিক এই দুই ধাপের মাঝখানে একটা preemption ঘটে, আর নতুন যে thread schedule হলো সে একই list-এ অন্য একটা অপারেশন করতে চায় — সে একটা অর্ধেক-আপডেট-হওয়া, ভুল list দেখবে। ফলাফল data corruption, বা crash।

এটাই সেই সমস্যা যা Level 4-এর synchronization লেসনে বিস্তারিত আলোচিত হবে — critical section-কে atomic দেখানোর দরকার, আর তার একটা (সরল, ব্যয়বহুল-কিন্তু-নির্ভরযোগ্য) সমাধান হলো সেই সংক্ষিপ্ত সময়ের জন্য preemption বন্ধ রাখা:

preempt_disable();
/* খুবই সংক্ষিপ্ত critical section — কয়েক instruction */
list_add(&new_node, &shared_list);
preempt_enable();

সঙ্গে দুইটা কড়া নিয়ম: এই window অবশ্যই সংক্ষিপ্ত হতে হবে (কয়েক microsecond-এর মধ্যে) — নাহলে সেই সময়টুকুতে সিস্টেম কার্যকরভাবে non-preemptive হয়ে যায়, আর latency-sensitive thread-এর জন্য এটা ঠিক সেই সমস্যা যা priority inversion তৈরি করে (একটা নিম্ন-priority thread preemption বন্ধ রেখে একটা উচ্চ-priority thread-কে অপেক্ষা করাচ্ছে)। আর এই window-এ কোনো blocking operation (sleep, I/O wait) করা যাবে না — preemption বন্ধ থাকা অবস্থায় block করলে পুরো সিস্টেম আটকে যাবে, কেউ আর CPU-ই পাবে না।

**এই একই মৌলিক টেনশন — “কতটুকু সময় uninterrupted থাকা দরকার নিরাপত্তার জন্য, বনাম কতটুকু preemption দরকার responsiveness-এর জন্য” — Level 9 (Distributed Systems)-এ বহুগুণ বড় স্কেলে ফিরে আসবে, যখন distributed lock/consensus protocol-এ “কতক্ষণ একটা নোড critical section-এ থাকতে পারে অন্য নোডদের অপেক্ষা করিয়ে” প্রশ্নটা নেটওয়ার্ক latency-র সাথে জড়িয়ে আরও জটিল হয়ে ওঠে।

এরপর কী

পরের লেসন — Linux Schedulers

আজ আমরা classic policy-গুলো দেখলাম আর একটা প্রশ্ন খোলা রেখে এসেছি: কীভাবে একটা scheduler thread-এর সাম্প্রতিক আচরণ পর্যবেক্ষণ করে নিজে থেকে adapt করবে, কোনো programmer-নির্ধারিত static priority ছাড়াই?

পরের লেসনে দুইটা বাস্তব উত্তর দেখব — প্রথমে MLFQ-র ধারণা (একাধিক priority queue, আচরণ দেখে thread-কে queue-র মধ্যে সরানো), তারপর Linux-এর প্রকৃত সমাধান CFS (Completely Fair Scheduler) — যেখানে “fairness” একটা নির্ভুল গাণিতিক সংজ্ঞা পায় (vruntime), আর সেই সংজ্ঞা একটা red-black tree-তে বাস্তবায়িত হয়। শেষে দেখব ২০২৩-এ Linux 6.6-এ CFS-কে প্রতিস্থাপন করা EEVDF, আর কেন সেই বদল দরকার হলো।

আজকের nice experiment-এর সেই অসম্পূর্ণ সংখ্যাটাও (nice 0 বনাম nice 19-এর অনুপাত) পরের লেসনে একটা নির্ভুল সূত্র পাবে — $1.25^{\Delta \text{nice}}$ — আর আমরা সেটা নিজের মেশিনে মিলিয়ে দেখব।