CPU Scheduling অ্যালগরিদম ও Deadlock প্রতিকার

CPU Scheduling-এর মৌলিক সূত্র

যেকোনো শিডিউলিং অংকে এই দুটি সূত্র সরাসরি ব্যবহৃত হয়:

• Turnaround Time (TAT) = Completion Time (CT) − Arrival Time (AT)
• Waiting Time (WT) = Turnaround Time (TAT) − Burst Time (BT)

প্রধান Scheduling অ্যালগরিদমসমূহ

• FCFS (First-Come, First-Served): Non-preemptive। বড় প্রসেস আগে এলে ছোট প্রসেসগুলো আটকে থাকে, যাকে Convoy Effect বলে।
• SJF (Shortest Job First) / SRTF (Preemptive SJF): সর্বনিম্ন গড় Waiting Time দেয় (Optimal)। কিন্তু বড় প্রসেসগুলোর Starvation হতে পারে।
• Priority Scheduling: অগ্রাধিকার অনুযায়ী চলে। Starvation সমস্যা হয়, যার সমাধান হলো Aging (অপেক্ষমাণ প্রসেসের অগ্রাধিকার ধীরে ধীরে বাড়ানো)।
• Round Robin (RR): Preemptive; নির্দিষ্ট Time Quantum (q) পরপর প্রসেস সুইচ হয়। Time-sharing সিস্টেমের জন্য আদর্শ (No starvation)। q খুব ছোট হলে Context Switch overhead বেড়ে যায়, আর খুব বড় হলে FCFS-এর মতো আচরণ করে।

উদাহরণ: ৩টি প্রসেস P1(BT=5), P2(BT=2), P3(BT=4) সবাই AT=0 সময়ে এলে SJF ক্রম হবে:
P2 (0..2) -> P3 (2..6) -> P1 (6..11)
Waiting Time: P2 = 0, P3 = 2, P1 = 6; Average WT = (0 + 2 + 6) / 3 = 2.67

Deadlock ও Coffman-এর ৪টি আবশ্যিক শর্ত

একসাথে নিচের ৪টি শর্ত পূরণ হলে তবেই কেবল Deadlock হতে পারে:

1. Mutual Exclusion: রিসোর্স একসাথে কেবল একটি প্রসেসই ব্যবহার করতে পারবে (non-shareable)।
2. Hold and Wait: প্রসেস অন্তত একটি রিসোর্স ধরে রেখে অন্য রিসোর্সের জন্য অপেক্ষা করবে।
3. No Preemption: প্রসেস স্বেচ্ছায় না ছাড়া পর্যন্ত রিসোর্স জোর করে ছিনিয়ে নেওয়া যাবে না।
4. Circular Wait: প্রসেসগুলোর মধ্যে বৃত্তাকার অপেক্ষার চেইন তৈরি হবে (P0 → P1 → ... → P0)।

Deadlock মোকাবিলার উপায়

• Prevention: উপরের ৪টি শর্তের যেকোনো একটি ভেঙে দেওয়া (যেমন রিসোর্সগুলোর ক্রমিক নম্বর নির্ধারণ করে Circular Wait বন্ধ করা)।
• Avoidance: Banker's Algorithm ব্যবহার করে সিস্টেম Safe State-এ থাকবে কি না তা আগে থেকেই পরীক্ষা করে রিসোর্স বরাদ্দ দেওয়া।