CPU Scheduling

 

আগের যুগের কম্পিউটার গুলাতে একটা একটা করে প্রসেস রান করা যেত, একটা প্রসেসের কাজ শেষ হবে তারপরই আরেকটা প্রসেস শুরু করা সম্ভব, এর আগে না ।

কিন্তু এখন যেহেতু multiprogramming system চলে এসেছে তাই কাহিনী ও কিছুটা পালটে গেছে ।

 

CPU Scheduling হইতেসে অনেকগুলা প্রসেস Ready queue তে থাকলে CPU কোন প্রসেসের কাজ আগে করবে কোনটা পরে করতে এটা ঠিক করে যে প্রক্রিয়ায়।

 

CPU Scheduling ২ প্রকার। যথাঃ

1. Preemptive (RR, SRTF, Priority Scheduling preemptive version)

2. Non Preemptive (SJF, Priority Scheduling non preemptive version)

 

Preemptive: যে প্রসেসগুলা Preemptive Scheduling follow করে  তারা কিছুক্ষণ CPU ইউজ করবে আবার ছেড়ে অন্য প্রসেসকে সুযোগ দিবে , আবার ইউজ করবে আবার ছেড়ে দিবে, মানে কোনো একটা প্রসেসের নিজের কাজ পুরাপুরি(100%) শেষ হউয়ার আগেই সে CPU নিজ থেকে ছেড়ে দিবে অথবা OS তাকে ছাড়াইতে পারবে এই টাইপগুলা Preemptive।  কিন্তু

 

Non preemptive: যে প্রসেসগুলা Non Preemptive scheduling follow করে তারা কোনো একটা প্রসেসের কাজ সম্পূর্ন না হউয়া পর্যন্ত CPU দখল করে রাখবে, অন্য কেউ সুযোগ পাবে না । একজনের কাজ শেষ হবে তারপর আরেকটা প্রসেস শুরু করবে আবার তার কাজ সম্পূর্ণ না হউয়া পর্যন্ত CPU ছাড়বে না। এর মাঝে সে waiting এ যাক, ready তে যাক, ভাত খাইতে যাক যেখানেই যাক কাজ শেষ না হউয়া পর্যন্ত  CPU ঐ একটা প্রসেসের দখলে ।

 

courtesy: studytonight

Convoy effect: আমাদের কিছু কিছু প্রসেস থাকে যেগুলা এক্সিকিউট করতে বেশি সময় লাগে, আবার কিছু কিছু ছোট প্রসেস থাকে যেগুলা এক্সিকিউট করতে খুব কম সময় লাগে, তো যাদের কম সময় লাগে তারা যদি আগে CPU ইউজ করে তাদের কাজটা আগে শেষ করে নিত তাহলে তাদের আর বেশিক্ষন অপেক্ষা করা লাগতো না, কিন্তু যদি এমন হয় কোনো একটা বড় প্রসেসের কাজ আগে শুরু হয়েছে এজন্য ছোট প্রসেস যাদের কাজ হয়তো কয়েক মিলি সেকেন্ডেই শেষ হয়ে যেত কিন্তু তাদের ঐ বড় প্রসেসের কাজ শেষ হউয়ার জন্য ২/১ ঘন্টা অপেক্ষা করা লাগতেছে, এইরকম বিরিখিটি অবস্থাকে Convoy Effect বলে ।

 

Courtesy: javatpoint

 

CPU Scheduling কেন করে ?

ধরেন পদ্মা ,মেঘনা ,যমুনা কোনো একটা ব্রিজ বানানোর জন্য চায়না থেকে মেশিন আর ইঞ্জিনিয়ার নিয়ে আসা হয়েছে ১ মাসের জন্য । ১মাসের ভাড়া আমরা দিয়ে দিয়েছি, এখন এই ১মাসে ঐ মেশিন দিয়ে আমরা যতবেশি কাজ করাই নিতে পারব আমাদের তত লাভ, মেশিন যদি খালি বসে থাকে তাহলে তো আমাদের ই লস তাই না ?

 

একই ব্যাপারটা সিপিইউ এর ক্ষেত্রেও চিন্তা করা হয় ,আমাদের কম্পিউটারের যে সিপিইউ আছে সেটা যদি কোনো কাজ না করে হাত, পা ছেড়ে বসে থাকে তাহলে এটাকে বলে CPU utilization হইতেসে না , মানে CPU অনেক কাজ করতে সক্ষম কিন্তু আমরা তাকে দিয়ে কাজ করাইতে পারতেসি না ।

 

আমরা যাতে CPU এর বেস্ট ইউজ করতে পারি এইজন্য CPU Scheduling apply করি ।

আরোও কিছু কাহিনী আছে CPU Scheduling করার পেছনে , এইখানে আমরা কিছু জিনিসকে maximize আর কিছু জিনিস minimize করতে Scheduling Algorithm ইউজ করি

১। waiting time কমানো , ধরেন দুইটা প্রসেস আছে একজনের কাজ ৫ সেকেন্ডের আরেকজনের কাজ করতে ২ঘন্টা লাগবে, তাহলে ৫ সেকেন্ড যার তাকে যদি আগে CPU দেয় তাহলে তাকে wait করতে হচ্ছে না, ৫ সেকেন্ড এর কাজ শেষ পরে এই CPU ২ ঘন্টা লাগবে যার তাকে দিয়ে দিবে , নাহলে ৫ সেকেন্ডের কাজ করার জন্য তাকে ২ ঘন্টা wait করা লাগতো এভাবে waiting time কমানো।

২। Maximize Throughput: Throughput হইতেসে কোনো একক সময়ে কতগুলা কাজ হইতেছে এই নাম্বারটা বাড়ানো।ঐযে বলে না ঘন্টায় ৫ কিলোমিটার, ঘন্টায় ১০ কিলোমিটার তো এইভাবে নাম্বারটা যত বাড়বে স্পিড ততবেশি, ঐরকমভাবেই কোনো একক সময়ে CPU যতগুলা কাজ করে তাকে throughput বলতেসে, এটা maximize করা মানে একক সময়ে বেশি কাজ শেষ করার চেষ্টা করা আর কি।

৩। CPU utilization: এটাতো বলসি উপরে, যাতে CPU হাত পা ছেড়ে খালি বসে না থাকে সেদিকে খেয়াল রাখা।

৪। Maximize response time: ধরেন একসাথে ৩টা প্রসেসের কাজ চলতেছে তো CPU দুইটা প্রসেসের মধ্যেই লেনদেন চলতেছে ৩ নাম্বার প্রসেসকে দিচ্ছেই না একবারও তাহলেও তো সমস্যা “Google Chrome” ওপেন করতে বলসেন ২দিন পর ওপেন হইতেসে, তাহলে চলবে? এমন যাতে না হয় এইজন্য response time maximize করতেও CPU Scheduling দরকার লাগে।

 

উপরের সবগুলা চাহিদা কোনো একটা algorithm দিয়ে fulfill করতে পারবো না , আলাদা আলদা Algorithm আলাদা আলাদা সুযোগ সুবিধা দিয়ে থাকে । এখন আমাদের অবস্থা বুঝে ব্যবস্থা নিতে হবে আর কি যখন যেই সুবিধা বেশি দরকার ঐ সুবিধা যেই Algorithm দেয় ঐটা ঐখানে ইউজ করবো ।

 

কয়েক প্রকার CPU Scheduling Algorithm হলোঃ

1.   First Come First Serve (FCFS) (আগে আসলে আগে পাবেন)

2.   Shortest Job First (SJF) (যার কাজ ছোট , সে আগে সুযোগ পাবে)

3.   Round Robin (RR)

4.   Priority Scheduling (যার ক্ষমতা বেশি,তার কাজ আগে করব)

5.     Shortest Remaining Time First (যার সময় কম লাগবে তাকে আগে সুযোগ দিব)

Algorithm গুলা কোনটা কিভাবে কাজ করে সেটা তো জানবই ইনশাআল্লাহ , কিন্তু তার আগে কিছু ভাঙ্গচুর শব্দের মানে জানা দরকার

 

 

Scheduling Criteria:

Courtesy: GFG

Arrival Time: একটা প্রসেস প্রথমবার যেই সময়ে RAM এ আসে । (ধরলাম ৭টা ৫মিনিট ৫ সেকেন্ড)

Completion Time: প্রসেসটার সব কাজ(১০০%) শেষ হইলো এই অবস্থায় যয়টা বাজতেছে । (ধরলাম ৭ টা ৪৫ মিনিট ৩৯ সেকেন্ড )

Brust Time: এটা একটা time duration , কোনো একটা প্রসেস CPU কে যতক্ষণ ব্যবহার করেছে অথবা আসলেই যতক্ষণ তার কাজ চলেছে waiting, block ইত্যাদি state গুলার হিসাব বাদে শুধু Runing state এর হিসাব করে। (ধরলাম ১০ সেকেন্ড, মানে বাকি সময় সে waiting, ready অথবা অন্য যেকোনো অবস্থায় ছিল)

Turn Around Time: ধরেন আপনি ট্রেনের টিকেট কাটতে স্টেশনে গেছেন বিকাল ৫ টায়, টিকেট পেয়ে বাইর হইতে হইতে ৭টা বেজে গেছে, তাহলে আপনার Turn Around Time হইলো দুই ঘন্টা, মানে একটা প্রসেসের কাজ শুরু থেকে একদম শেষ হইতে যত টাইম লাগে আর কি, এর মাঝে অনেক state এ যাইতে পারে , কিন্তু আমরা শুরুর সময় আর শেষের সময় ধরে Turn Around হিসাব করবো । কাজটা শুরু করেছে কখন, শেষ করেছে কখন এই সময় পার্থক্য ।

Turn Around Time = Completion Time – Arrival Time

 

Waiting Time: = Turn Around Time – Brust Time

Waiting time=সবমোট যতক্ষণ লেগেছে – আসলেই যতক্ষণ কাজ করেছে

ট্রেনের টিকেট কেটে স্টেশন থেকে বাইর হইতে আপনার দুই ঘন্টা লেগেছে, তার মানে কি এই যে টিকেট যে কেটে দিচ্ছে ঐ লোক দুই ঘন্টা ধরে শুধু আপনার একার ই টিকেট কেটেছে ? নাহ আপনাকে লাইনে দাড়াইতে হইসে wait করতে হইসে ,অনেক লোকের পরে আপনি সুযোগ পাইসেন , আপনার টিকেট কেটে লেনদেন করতে হইতো ২মিনিট লেগেছে মাত্র, তাহলে আপনার দুইঘন্টা লাগলো শেষ হইতে, কিন্তু আপনার কাজ চলেছে ২মিনিট, তাহলে waiting time কতক্ষণ আপনার ?

২ঘন্টা – ২ মিনিট = ১ ঘন্টা ৫৮ মিনিট

Turn around – Brust time = waiting time

 

First Come First Serve:  sorts based on Arrival Time

 

নামে দেখেই বুঝা যাইতেছে যে প্রসেস আগে Ready Queue তে আসবে তার কাজ আগে শুরু করবে Brust time, waiting time, completion time এগুলা কোনো বেল নাই এইখানে, আগে আসবেন আগে সার্ভিস পাবেন । আর এই Algorithm, Non preemptive মানে যেই প্রসেসের কাজ শুরু করবে তার কাজ একদম শেষ করেই অন্য প্রসেসের কাজ শুরু করবে । এই Algo বানাইতে Queue data structure ইউজ করা হয় । এই algorithm এ Convoy Effect  হয়ে যাওয়ার সম্ভাবনা বেশি কারণ আগে যে আসবে CPU সে আগে পাবে, এখন যদি বড় প্রসেস আগে চলে আসে তাহলেই তো Convoy Effect হয়ে যাইতেছে, মানে waiting time বেড়ে যাচ্ছে । যদি Arrival Time same হয় তখন কি করবে? তখন Randomly pick করবে ।

Wait time of each process is as follows −

Process	Wait Time : Service Time - Arrival Time
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	8 - 2 = 6
P3	16 - 3 = 13

Average Wait Time: (0+4+6+13) / 4 = 5.75

Courtesy: tutorialspoint.com

 

Shortest Job First:  sorts based on CPU time/Brust Time

Ready queue তে যেসব প্রসেস উপস্থিত তাদের মধ্যে যার Brust time কম তাকে আগে CPU দেয়া হবে ।

এটারও নাম দেখেই বুঝা যাইতেছে যার CPU time কম লাগবে তাকে আগে CPU দিব, তাহলে ছোট গুলার কাজ আগে আগে শেষ হয়ে যাবে আর বড়গুলা পরে সময় নিয়ে কাজ শেষ করবে, এভাবে কাজ করলে waiting time কমানো যাবে। এই Algorithm Preemtive ও হয়, আবার Non Preemtive ও হইতে পারে । Preemtive হইলেতো একবার P1, একবার P2 একবার P3 এভাবে একেকবার একেকজনের কাজ করবে কিন্তু শুরুটা হবে সবসময় shortest CPU time যেই প্রসেসের তাকে দিয়ে , আর Non preemptive হইলে একজনের কাজ ১০০% শেষ করে আরেকজনের কাজ শুরু করবে , এইখানেও যার CPU time সব থেকে কম তাকে দিয়েই কাজ শুরু করবে।

 

আপনি কতদিন বাচবেন? বলা তো যায় না, একটা প্রসেস কতক্ষন কাজ করবে এটাও বলা যায়না সবসময়, কতক্ষন কাজ করবে না জানতে পারলে sort করবেন কিভাবে যে কার কাজ কম লাগতেছে , বেশি লাগতেছে বের করবেন কিভাবে? সেটাই, এইরকম CPU time জানা না থাকলে এই Algorithm কাজ করতে পারবে না ।

 

PID	Arrival Time	Burst Time	Completion Time	Turn Around Time	Waiting Time
1	1	7	8	7	0
2	3	3	13	10	7
3	6	2	10	4	2
4	7	10	31	24	14
5	9	8	21	12	4

Since, No Process arrives at time 0 hence; there will be an empty slot in the Gantt chart from time 0 to 1 (the time at which the first process arrives).

 Avg Waiting Time = 27/5

Round Robin: time sharing OS এ ব্যবহারের জন্য এই algorithm বেশি ব্যবহার হয়। আর এই algorithm Preemptive Scheduling follow করে, মানে একবার P1 CPU use করবে , একবার P2 এভাবে চেঞ্জ হইতারবে। মানে পুরাটা time sharing Operating System পড়েছি ঐটাই এখন নাম পাল্টাইয়া Round Robin নামে  আবার পড়তেছি ।

 

Time sharing Os এর মতো এই Round Robin algorithm এর ও একটা

 নির্দিষ্ট time quantum/time slice থাকে ঐ টাইম স্লাইস শেষ হইলে আরেকটা প্রসেসকে CPU তে দেয়া হবে আবার টাইম স্লাইস শেষ হইলে আরেকটা প্রসেস CPU তে যাবে এভাবে চলতে থাকে , 

time slice = 5

In the above diagram, arrival time is not mentioned so it is taken as 0 for all processes.

Let us now calculate the Turn around time and waiting time for the above example :

Processes	Burst Time	Turn Around Time Turn Around Time = Completion Time – Arrival Time	Waiting Time Waiting Time = Turn Around Time – Burst Time
P1	21	32-0=32	32-21=11
P2	3	8-0=8	8-3=5
P3	6	21-0=21	21-6=15
P4	2	15-0=15	15-2=13

Average waiting time is calculated by adding the waiting time of all processes and then dividing them by no.of processes.

average waiting time = waiting time of all processes/ no.of processes

average waiting time=11+5+15+13/4 = 44/4= 11ms

courtesy: studytonight

Priority Scheduling:  এই algorithm এর Preemptive ভার্সন ও পাওয়া যায়, আবার Non Preemptive ভার্সনও পাওয়া যায়, যখন যেরকম দরকার আর কি বানানো যায় ।

Preemptive Priority Scheduling: একটা প্রসেস রানিং অবস্থায় যদি Ready queue তে আরেকটা নতুন প্রসেস আসে যেটার Priority running process এর থেকে Higher তখন CPU Preempt করবে । মানে নতুন যে বেশি priority এর প্রসেস এলো তার কাজ শুরু করবে ।

Non Preemptive Priority Scheduling: এক্ষেত্রে যতই Higher priority এর process আসুক না কেন CPU যার কাজ করছিল তার কাজ ই করতে থাকবে , তার কাজ শেষ হলে তখন Ready queue তে যে প্রসেসগুলা থাকবে তাদের মধ্যে যার Priority বেশি হবে তাকে নিয়ে কাজ শুরু করবে ।

Problem in Priority Scheduling: Priority এর উপর ভিত্তি করে যদি CPU দিতে থাকে তাহলে যে প্রসেসের Priority সব থেকে কম এমনও হতে পারে যে সে কোনোদিন CPU পাইলো ই না, কারণ তার থেকে বেশি Priority এর প্রসেসগুলা রে CPU দিতে না দিতেই আরো High Priority এর প্রসেস এসে হাজির , তখন কোনো কোনো প্রসেসের একদম Block হয়ে যাওয়ার মত অবস্থা হইতে পারে, মানে Exist করবে কিন্ত বুঝতে পারবেন না ।

 

Using Aging technic: উপরের সমস্যা দূর করার জন্য এই টেকনিক ব্যবহার করা হয়, টেকনিক হইতেসে একটা নির্দিষ্ট waiting time পার হউয়ার পর পর আমরা lowest priority প্রসেসের priority বাড়াইতে থাকব । কতখানি করে বাড়াবো এটা বলা থাকবে ।

Shortest Remaining Time:  হইতেসে SJF এর Preemptive version।

এইখানে অনেক প্রসেস দেখা গেল আগে থেকে চলতেছে আর একটু টাইম হইলেই শেষ হয়ে যাবে এদের বেশি Priority দেয়া হয় এইখানে ।