CPU শিডিউলিং বেসিকস ও শিডিউলিং ক্রাইটেরিয়া

CPU scheduling basics & criteria

৮ মিনিট পড়া শুরু · Beginner Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

CPU শিডিউলার ঠিক করে কোন READY প্রসেস পরবর্তী CPU পাবে — একটি প্রসেস waiting-এ যাওয়া, টার্মিনেট হওয়া, বা time quantum শেষ হওয়ার মুহূর্তে সিদ্ধান্ত নেওয়া হয়।
পাঁচটি মূল মেট্রিক — CPU utilization, throughput, turnaround time, waiting time, response time — যেগুলো এই মডিউলের প্রতিটি অ্যালগরিদম মূল্যায়নে ব্যবহৃত হবে।
Preemptive শিডিউলিং-এ scheduler জোরপূর্বক একটি চলমান প্রসেস থেকে CPU নিতে পারে; non-preemptive-এ একটি প্রসেস স্বেচ্ছায় না ছাড়া পর্যন্ত CPU ধরে রাখে।

এই পাঠে যা শিখবেন

CPU শিডিউলার কখন এবং কেন কাজ করে
পাঁচটি মূল শিডিউলিং মেট্রিক এবং প্রতিটি কী পরিমাপ করে
Waiting time ও turnaround time-এর মধ্যে পার্থক্য, এবং response time কেন আলাদা
Preemptive বনাম non-preemptive শিডিউলিং
Python দিয়ে একটি রেফারেন্স টেবিল — এই মডিউলের বাকি পাঠগুলো এই একই মেট্রিকগুলো বারবার ব্যবহার করবে

১ · CPU শিডিউলার কী করে

CPU শিডিউলারCPU schedulerOS-এর সেই অংশ যা ঠিক করে কোন READY প্রসেস পরবর্তীতে CPU-তে চলবে। ঠিক করে কোন READY প্রসেস (L05-এর প্রসেস স্টেট মনে করুন) পরবর্তীতে CPU পাবে। এটি চারটি মুহূর্তে সক্রিয় হয়: (১) একটি চলমান প্রসেস I/O-এর জন্য waiting-এ যায়, (২) একটি প্রসেস টার্মিনেট হয়, (৩) একটি প্রসেসের time quantum শেষ হয় (preemptive সিস্টেমে), অথবা (৪) CPU অন্যথায় idle থাকতো। শিডিউলার একটি ভুল সিদ্ধান্ত নিলে পুরো সিস্টেমের পারফরম্যান্স ধীর হয়ে যেতে পারে — তাই "সঠিক" প্রসেস বেছে নেওয়ার সঠিক মাপকাঠি (criteria) প্রয়োজন, যা এই পাঠের মূল বিষয়।

২ · পাঁচটি মূল শিডিউলিং মেট্রিক

CPU Utilization
CPU যত সময় ব্যস্ত থাকে তার শতাংশ — বেশি ভালো।

Throughput
প্রতি একক সময়ে সম্পন্ন হওয়া প্রসেসের সংখ্যা — বেশি ভালো।

Turnaround TimeTurnaround timeপ্রসেস আসা (arrival) থেকে সম্পূর্ণ হওয়া পর্যন্ত মোট সময় — waiting + execution + I/O সময় সব মিলিয়ে।
আসা থেকে সম্পূর্ণ হওয়া পর্যন্ত মোট সময় — কম ভালো।

Waiting TimeWaiting timeREADY কিউতে (না চলা, না I/O করা) কাটানো সময় — শিডিউলার সবচেয়ে সরাসরি এটিই নিয়ন্ত্রণ করে।
শুধু READY কিউতে কাটানো সময় — কম ভালো। শিডিউলার সরাসরি এটিই প্রভাবিত করে।

Response TimeResponse timeরিকোয়েস্ট থেকে প্রথম রেসপন্সের সময় -- সম্পূর্ণ হওয়া পর্যন্ত নয়, ইন্টারঅ্যাক্টিভ সিস্টেমে গুরুত্বপূর্ণ।
রিকোয়েস্ট থেকে প্রথম রেসপন্স পর্যন্ত সময় — কম ভালো। ইন্টারঅ্যাক্টিভ সিস্টেমে গুরুত্বপূর্ণ, turnaround-এর থেকে ভিন্ন।

Turnaround time বনাম Response time — পার্থক্য কেন গুরুত্বপূর্ণ

একটি প্রসেস সম্পূর্ণ শেষ হতে অনেকক্ষণ লাগতে পারে (উচ্চ turnaround time), কিন্তু যদি এটি প্রথম আউটপুট খুব দ্রুত দেখায় (কম response time), একজন ইন্টারঅ্যাক্টিভ ব্যবহারকারীর কাছে সিস্টেমটি "দ্রুত" মনে হবে। এই কারণেই Round Robin-এর মতো (L11) time-sharing শিডিউলার turnaround time কিছুটা বাড়িয়ে হলেও response time কমানোকে প্রাধান্য দেয়।

৩ · Preemptive বনাম Non-preemptive শিডিউলিং

Non-preemptive শিডিউলিং-এ একটি প্রসেস CPU পাওয়ার পর তা স্বেচ্ছায় না ছাড়া (terminate হওয়া বা I/O-এর জন্য waiting-এ যাওয়া) পর্যন্ত ধরে রাখে — scheduler কখনো জোর করে তা কেড়ে নেয় না (L10-এর FCFS ও SJF এই ধরনের)। Preemptive শিডিউলিং-এ scheduler প্রয়োজনে একটি চলমান প্রসেস থেকে জোরপূর্বক CPU কেড়ে নিতে পারে — উদাহরণস্বরূপ একটি উচ্চ-প্রায়োরিটি প্রসেস এসে পড়লে, বা time quantum শেষ হলে (L11-এর Round Robin এই ধরনের)। এই পার্থক্য এই পুরো মডিউলে বারবার আসবে।

৪ · রেফারেন্স টেবিল — Python দিয়ে

নিচের কোড সেলে এই পাঠের পাঁচটি মেট্রিক একটি dict-এ সাজিয়ে একটি রেফারেন্স টেবিল প্রিন্ট করা হয়েছে — এই মডিউলের প্রতিটি পরবর্তী পাঠ (L10-L13) এই একই মেট্রিকগুলো তাদের ওয়ার্কড উদাহরণে ব্যবহার করবে।

Python

# শিডিউলিং মেট্রিক রেফারেন্স টেবিল -- এই মডিউলের বাকি পাঠগুলো এই একই মেট্রিক ব্যবহার করবে
metrics = {
    "CPU utilization": {
        "definition": "CPU যত সময় ব্যস্ত থাকে তার শতাংশ",
        "lower_is_better": False,
    },
    "Throughput": {
        "definition": "প্রতি একক সময়ে সম্পন্ন হওয়া প্রসেসের সংখ্যা",
        "lower_is_better": False,
    },
    "Turnaround time": {
        "definition": "প্রসেস আসা থেকে সম্পূর্ণ হওয়া পর্যন্ত মোট সময় (waiting+execution+I/O)",
        "lower_is_better": True,
    },
    "Waiting time": {
        "definition": "শুধু READY কিউতে কাটানো সময় (না চলা, না I/O)",
        "lower_is_better": True,
    },
    "Response time": {
        "definition": "রিকোয়েস্ট থেকে প্রথম রেসপন্স পর্যন্ত সময়",
        "lower_is_better": True,
    },
}

print("=== শিডিউলিং ক্রাইটেরিয়া রেফারেন্স টেবিল ===\n")
for name, info in metrics.items():
    lower = "হ্যাঁ (কম ভালো)" if info["lower_is_better"] else "না (বেশি ভালো)"
    print(f"* {name}")
    print(f"    সংজ্ঞা      : {info['definition']}")
    print(f"    কম ভালো?   : {lower}")

better_when_low = [name for name, info in metrics.items() if info["lower_is_better"]]
print(f"\nযে {len(better_when_low)}টি মেট্রিকে কম মান ভালো:", better_when_low)

লক্ষ্য করুন — পাঁচটি মেট্রিকের মধ্যে তিনটিতে (turnaround, waiting, response) কম মান ভালো, আর দুটিতে (utilization, throughput) বেশি মান ভালো। L10-এর FCFS ও SJF উদাহরণে আমরা সরাসরি waiting time ও turnaround time গণনা করে দেখবো কীভাবে অ্যালগরিদম বদলালে এই সংখ্যাগুলো বদলে যায়।

মূল কথা · Key takeaway

কোনো একটি "সেরা" শিডিউলিং অ্যালগরিদম নেই — প্রতিটি অ্যালগরিদম এই পাঁচটি মেট্রিকের মধ্যে একটি ভিন্ন trade-off বেছে নেয় (যেমন কম waiting time বনাম কম response time)। L10-L13 জুড়ে আমরা দেখবো প্রতিটি অ্যালগরিদম ঠিক কোন trade-off বেছে নেয় এবং কেন।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ একটি সিস্টেমের CPU utilization ৯৯% হলেও ব্যবহারকারীরা অভিযোগ করছে সিস্টেম "স্লো" মনে হচ্ছে — এটা কীভাবে সম্ভব?

CPU utilization শুধু বলে CPU কতটা ব্যস্ত ছিল, প্রতিটি কাজ কতটা দ্রুত শেষ হলো তা নয়। উচ্চ utilization সত্ত্বেও যদি প্রতিটি ইন্টারঅ্যাক্টিভ প্রসেস দীর্ঘ waiting time বা response time অনুভব করে (উদাহরণস্বরূপ, কিছু দীর্ঘ ব্যাচ জব CPU দখল করে রেখেছে), ব্যবহারকারীরা সিস্টেমকে ধীর মনে করবে যদিও CPU একেবারেই idle নয়। এটিই দেখায় কেন একটি একক মেট্রিক (utilization) দিয়ে পুরো সিস্টেমের পারফরম্যান্স বিচার করা যথেষ্ট নয়।

প্র ০২ কেন waiting time-কে turnaround time-এর চেয়ে "শিডিউলার সরাসরি নিয়ন্ত্রণ করে" বলা হয়?

Turnaround time = waiting time + execution time + I/O time। execution time (প্রসেসের প্রকৃত CPU burst) এবং I/O time মূলত প্রোগ্রামের নিজস্ব বৈশিষ্ট্য, শিডিউলার এগুলো বদলাতে পারে না। কিন্তু READY কিউতে কতক্ষণ অপেক্ষা করতে হবে (waiting time) — সেটাই শিডিউলার সরাসরি সিদ্ধান্ত নেয়, কোন প্রসেসকে কখন CPU দেওয়া হবে তার মাধ্যমে। তাই বিভিন্ন শিডিউলিং অ্যালগরিদম তুলনা করার সবচেয়ে সরাসরি উপায় হলো তাদের গড় waiting time তুলনা করা (L10-এ ঠিক এটিই হবে)।

প্র ০৩ Non-preemptive শিডিউলিং-এ কি কখনো "খারাপ" প্রসেস অন্যদের CPU থেকে বঞ্চিত করতে পারে? কীভাবে?

হ্যাঁ — যেহেতু non-preemptive-এ চলমান একটি প্রসেসকে জোর করে থামানো যায় না, একটি খুব দীর্ঘ CPU-বাউন্ড প্রসেস (যেমন কোনো ভারী গণনা) CPU ধরে রাখলে তার পেছনে থাকা সব প্রসেসকে দীর্ঘ সময় অপেক্ষা করতে হবে — এটিই L10-এর "convoy effect"-এর মূল কারণ। preemptive শিডিউলিং (যেমন Round Robin, L11) এই সমস্যার সমাধান করে নিয়মিত বিরতিতে জোরপূর্বক CPU ভাগ করে দিয়ে।

অনুশীলন

চিন্তা করুন: ভিডিও গেম খেলার সময় (ইন্টারঅ্যাক্টিভ, response time গুরুত্বপূর্ণ) বনাম একটি বড় ভিডিও ফাইল এনকোড করার সময় (ব্যাচ, throughput গুরুত্বপূর্ণ) — এই দুই পরিস্থিতিতে কোন মেট্রিক বেশি গুরুত্বপূর্ণ এবং কেন?

গেমিং-এ response time সবচেয়ে গুরুত্বপূর্ণ — ইনপুট দেওয়ার পর সাথে সাথে প্রতিক্রিয়া না পেলে অভিজ্ঞতা খারাপ হয়ে যায়, ভিডিও এনকোডিং কতক্ষণে সম্পূর্ণ হলো তা এখানে গৌণ। ভিডিও এনকোডিং-এ throughput ও turnaround time বেশি গুরুত্বপূর্ণ — কাজটি কত দ্রুত পুরোপুরি শেষ হলো তা-ই মুখ্য, মাঝপথে "প্রথম রেসপন্স" নিয়ে কেউ চিন্তিত নয়।
পরীক্ষা করুন: উপরের কোড সেলে একটি নতুন মেট্রিক "Fairness" যোগ করুন (definition: "সব প্রসেস আনুপাতিকভাবে CPU সময় পাচ্ছে কিনা", lower_is_better: False) এবং টেবিলটি পুনরায় প্রিন্ট করে দেখুন এটি ঠিকমতো যোগ হয়েছে কিনা।

metrics dict-এ নতুন কী "Fairness" যোগ করলে লুপ স্বয়ংক্রিয়ভাবে এটিকেও টেবিলে প্রিন্ট করবে (dict-টি ইটারেট করার সময় যেকোনো নতুন এন্ট্রি একই ফরম্যাটে দেখাবে), এবং যেহেতু lower_is_better = False, এটি better_when_low তালিকায় যুক্ত হবে না। এটি দেখায় কোড এমনভাবে লেখা হয়েছে যে নতুন মেট্রিক যোগ করা সহজ — কোনো হার্ডকোডেড তালিকা পরিবর্তনের দরকার নেই।