CPU Scheduling Algorithm & Its type
CPU Scheduling
CPU Scheduling एक ऐसी Process है जो एक Process को CPU का प्रयोग करने का Permission देता है | जबकि दूसरी Process का Execution Resource की Unavailability के कारण hold होता है | जिससे CPU को Utilize किया जा सके | CPU Scheduling का Aim (उद्देश्य) System को Efficient, Fast, and Fair बनाना है |
जब भी CPU Idle हो जाता है, तो Operating System Ready Queue में Wait कर Process को Execute करने के लिए Select करता है | Selection Process Short-term Schedular के द्वारा Complete किया जाता है | Schedular Memory में से उन Process को Select करता है जो Execution के लिए तैयार है और उन्हें CPU Allocate करता है |
Type of CPU Scheduling
(i) Non-Preemptive Scheduling
Non-Preemptive Scheduling के अनुसार यदि एक बार CPU को एक Process को Allocate कर दिया गया है, तो वह Process CPU को अपने पास तब तक Hold करके रखती है जब तक उसका Execution Complete नहीं हो जाता है | यह एकमात्र Method है जिसका उपयोग कुछ Hardware Platform पर किया जाता है क्योंकि इसमें Preemptive Scheduling के लिए आवश्यक Special Hardware की आवश्यकता नहीं होती है |
Non-Preemptive Scheduling में CPU Currently Running Process को Disturb नहीं करता है | जबकि यह तब तक Wait करता है जब उस Process का Burst time Complete नहीं हो जाता है उसके बाद ही CPU को अन्य Process को Allocate किया जाता है |
Non-Preemptive Scheduling Algorithm Are – FCFS Scheduling, SJF Scheduling (Shortest Job First), and Priority Scheduling (Non-preemptive version).
(ii) Preemptive Scheduling
इस प्रकार के Scheduling मे Process को CPU Priority के आधार पर Assign किया जाता है | कभी-कभी ऐसे Process को Execute करने की आवश्यकता होती है जोकि Currently Running Process से Higher priority की होती है जिसके लिए पहले से Run हो रही process के Execution को कुछ देर के लिए Block कर दिया जाता है | तथा Higher Priority के Process के Complete Execute हो जाने के बाद उस process को पुनः Execute किया जाता है |
इस प्रकार के Scheduling का उपयोग मुख्यः रूप से तब किया जाता है जब कोई Process या तो Running State से Ready State में या Waiting State से Ready State में बदल जाती है | इसमें Resources limited time के लिए Process को Allocate किया जाता है और फिर वापस ले लिया जाता है और उसके बाद Process को फिर से Ready Queue में रखा जाता है यदि उस Process का Burst Time अभी Execute होना बाकी हो तो | वह Process Ready Queue में तब रहती है जब तक उसे दोबारा Execute होने के लिए CPU Availble न हो |
Preemptive Scheduling Algorithm Are – Round Robin Scheduling, Shortest remaining time First, Priority Scheduling (preemptive version).
Scheduling Algorithm
Decide करने के लिए की CPU को Maximum Utilize करने के लिए किस Process को पहले Execute किया जाये और कौन सी process को last में execute किया जाए | Scheduling Algorithm का प्रयोग किया जाता है जो निम्नलिखित है –
- First Come First Serve Scheduling Algorithm (FCFS)
- Shortest Job First Scheduling Algorithm (SJF)
- Round Robin Scheduling Algorithm (RR)
First Come First Serve Scheduling Algorithm (FCFS)
First Come First Serve Scheduling के अनुसार जो Process पहले आती है उसे पहले Execute किया जाता है | या जो Process CPU के लिए पहले Request करता है उसे CPU पहले Allocate किया जाता है | FIFO Scheduling Queue Data Structure के Rule को Follow करती है जिसके अनुसार जो Process Queue में पहले Add होती वो Process पहले Queue से Remove होती है | इसका प्रयोग Batch Operating System में किया जाता है |
Queue Data Structure का Use करके इसे Programmatically Implement करना आसान है, जहां नए Process को Tail Side से Add करते है और Schedular Head Side के द्वारा Prpocess को Execute करने के लिए Select करता है | FCFS का Perfect Real Time Example Ticket Counter से Ticket खरीदना है |
Important Formula
Turn Around Time = Completion Time – Arrival Time Waiting Time = Turn Around Time – Burst Time
Example
| Process | Burst Time | Order | Arrival Time |
| P1 | 24 | 1 | 0 |
| P2 | 3 | 2 | 0 |
| P3 | 4 | 3 | 0 |
Gantt Chart
Program for FCFS
// C program for implementation of FCFS
// scheduling
#include<stdio.h>
// Function to find the waiting time for all
// processes
void findWaitingTime(int processes[], int n,
int bt[], int wt[])
{
// waiting time for first process is 0
wt[0] = 0;
// calculating waiting time
for (int i = 1; i < n ; i++ )
wt[i] = bt[i-1] + wt[i-1] ;
}
// Function to calculate turn around time
void findTurnAroundTime( int processes[], int n,
int bt[], int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];
}
//Function to calculate average time
void findavgTime( int processes[], int n, int bt[])
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
//Function to find waiting time of all processes
findWaitingTime(processes, n, bt, wt);
//Function to find turn around time for all processes
findTurnAroundTime(processes, n, bt, wt, tat);
//Display processes along with all details
printf("Processes Burst time Waiting time Turn around time\n");
// Calculate total waiting time and total turn
// around time
for (int i=0; i<n; i++)
{
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
printf(" %d ",(i+1));
printf(" %d ", bt[i] );
printf(" %d",wt[i] );
printf(" %d\n",tat[i] );
}
int s=(float)total_wt / (float)n;
int t=(float)total_tat / (float)n;
printf("Average waiting time = %d",s);
printf("\n");
printf("Average turn around time = %d ",t);
}
// Driver code
int main()
{
//process id's
int processes[] = { 1, 2, 3};
int n = sizeof processes / sizeof processes[0];
//Burst time of all processes
int burst_time[] = {10, 5, 8};
findavgTime(processes, n, burst_time);
return 0;
}
// This code is contributed by Shivi_Aggarwal
Output
Processes Burst time Waiting time Turn around time 1 10 0 10 2 5 10 15 3 8 15 23 Average waiting time = 8.33333 Average turn around time = 16
Shortest Job First Scheduling Algorithm (SJF)
SJF Scheduling में Ready Queue में Available Process की List में से सबसे कम Burst Time वाले Process को Execution के लिए आगे Schedule किया जाता है | हालांकि, किसी Process के लिए आवश्यक Burst Time Predict करना मुश्किल है इसीलिए इस Algorithm को System में Implement करना Difficult होता है | Waiting Time को Minimize करने का यह Best Approach है | इसका प्रयोग Mostly Batch Systems में किया जाता है | यह Preemptive and Non-Preemptive दोनों प्रकार का होता है |
(i) Non-Preemptive SJF
| Process | Burst Time | Arrival Time |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Gantt Chart
Program
// C++ program to implement Shortest Job first with Arrival
// Time
#include <iostream>
using namespace std;
int mat[10][6];
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void arrangeArrival(int num, int mat[][6])
{
for (int i = 0; i < num; i++) {
for (int j = 0; j < num - i - 1; j++) {
if (mat[j][1] > mat[j + 1][1]) {
for (int k = 0; k < 5; k++) {
swap(mat[j][k], mat[j + 1][k]);
}
}
}
}
}
void completionTime(int num, int mat[][6])
{
int temp, val;
mat[0][3] = mat[0][1] + mat[0][2];
mat[0][5] = mat[0][3] - mat[0][1];
mat[0][4] = mat[0][5] - mat[0][2];
for (int i = 1; i < num; i++) {
temp = mat[i - 1][3];
int low = mat[i][2];
for (int j = i; j < num; j++) {
if (temp >= mat[j][1] && low >= mat[j][2]) {
low = mat[j][2];
val = j;
}
}
mat[val][3] = temp + mat[val][2];
mat[val][5] = mat[val][3] - mat[val][1];
mat[val][4] = mat[val][5] - mat[val][2];
for (int k = 0; k < 6; k++) {
swap(mat[val][k], mat[i][k]);
}
}
}
int main()
{
int num, temp;
cout << "Enter number of Process: ";
cin >> num;
cout << "...Enter the process ID...\n";
for (int i = 0; i < num; i++) {
cout << "...Process " << i + 1 << "...\n";
cout << "Enter Process Id: ";
cin >> mat[i][0];
cout << "Enter Arrival Time: ";
cin >> mat[i][1];
cout << "Enter Burst Time: ";
cin >> mat[i][2];
}
cout << "Before Arrange...\n";
cout << "Process ID\tArrival Time\tBurst Time\n";
for (int i = 0; i < num; i++) {
cout << mat[i][0] << "\t\t" << mat[i][1] << "\t\t"
<< mat[i][2] << "\n";
}
arrangeArrival(num, mat);
completionTime(num, mat);
cout << "Final Result...\n";
cout << "Process ID\tArrival Time\tBurst Time\tWaiting "
"Time\tTurnaround Time\n";
for (int i = 0; i < num; i++) {
cout << mat[i][0] << "\t\t" << mat[i][1] << "\t\t"
<< mat[i][2] << "\t\t" << mat[i][4] << "\t\t"
<< mat[i][5] << "\n";
}
}
(ii) Preemptive SJF
| Process | Burst Time | Arrival Time |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Gantt Chart
Program
// C++ program to implement Shortest Remaining Time First
// Shortest Remaining Time First (SRTF)
#include <bits/stdc++.h>
using namespace std;
struct Process {
int pid; // Process ID
int bt; // Burst Time
int art; // Arrival Time
};
// Function to find the waiting time for all
// processes
void findWaitingTime(Process proc[], int n,
int wt[])
{
int rt[n];
// Copy the burst time into rt[]
for (int i = 0; i < n; i++)
rt[i] = proc[i].bt;
int complete = 0, t = 0, minm = INT_MAX;
int shortest = 0, finish_time;
bool check = false;
// Process until all processes gets
// completed
while (complete != n) {
// Find process with minimum
// remaining time among the
// processes that arrives till the
// current time`
for (int j = 0; j < n; j++) {
if ((proc[j].art <= t) &&
(rt[j] < minm) && rt[j] > 0) {
minm = rt[j];
shortest = j;
check = true;
}
}
if (check == false) {
t++;
continue;
}
// Reduce remaining time by one
rt[shortest]--;
// Update minimum
minm = rt[shortest];
if (minm == 0)
minm = INT_MAX;
// If a process gets completely
// executed
if (rt[shortest] == 0) {
// Increment complete
complete++;
check = false;
// Find finish time of current
// process
finish_time = t + 1;
// Calculate waiting time
wt[shortest] = finish_time -
proc[shortest].bt -
proc[shortest].art;
if (wt[shortest] < 0)
wt[shortest] = 0;
}
// Increment time
t++;
}
}
// Function to calculate turn around time
void findTurnAroundTime(Process proc[], int n,
int wt[], int tat[])
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n; i++)
tat[i] = proc[i].bt + wt[i];
}
// Function to calculate average time
void findavgTime(Process proc[], int n)
{
int wt[n], tat[n], total_wt = 0,
total_tat = 0;
// Function to find waiting time of all
// processes
findWaitingTime(proc, n, wt);
// Function to find turn around time for
// all processes
findTurnAroundTime(proc, n, wt, tat);
// Display processes along with all
// details
cout << "Processes "
<< " Burst time "
<< " Waiting time "
<< " Turn around time\n";
// Calculate total waiting time and
// total turnaround time
for (int i = 0; i < n; i++) {
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << proc[i].pid << "\t\t"
<< proc[i].bt << "\t\t " << wt[i]
<< "\t\t " << tat[i] << endl;
}
cout << "\nAverage waiting time = "
<< (float)total_wt / (float)n;
cout << "\nAverage turn around time = "
<< (float)total_tat / (float)n;
}
// Driver code
int main()
{
Process proc[] = { { 1, 6, 1 }, { 2, 8, 1 },
{ 3, 7, 2 }, { 4, 3, 3 } };
int n = sizeof(proc) / sizeof(proc[0]);
findavgTime(proc, n);
return 0;
}
Round Robin Scheduling Algorithm (RR)
Round Robin (RR) Scheduling algorithm mainly Time-sharing System के लिए Design किया गया है | यह Algorithm FCFS के समान ही है लेकिन Round Robin में Preemption Allowed होता है | जो System को Process के बीच में Switch करने में सक्षम बनाता है | इसमें प्रत्येक को Execution के लिए Fixed Time Allot किया जाता है जिसे Time-Quantum कहते है |
एक बार दी गयी Time-Quantum के लिए Execute होने के बाद उस process Preempt करके System अन्य Process को Execute करना Start कर देता है | Preempted Processes की States को Save करने के लिए Context Switch का Use किया जाता है | यह Algorithm Simple एवं Easy to Implement है | यह Algorithm Starvation-free क्योंकि सभी Process को CPU का उचित हिस्सा Fixed Time के लिए उपयोग करने के लिए मिलता है | Time Quantum की Length 10 से 100 Millisecond तक होती है |
Example
| Process | Burst Time |
| P1 | 21 |
| P2 | 3 |
| P3 | 6 |
| P4 | 2 |
Gantt Chart
Program
// Program implementation in C++ for Round Robin scheduling
#include<iostream>
using namespace std;
//The Function to find the waiting time for all processes
void fWaitingTime(int processes[], int n,
int bt[], int wt[], int quantum)
{
// Let us Make a copy of burst times bt[] to store remaining burst times
int rem_bt[n];
for (int i = 0 ; i < n ; i++)
rem_bt[i] = bt[i];
int t = 0; // for Current time
// Let us keep traverse the processes in the round robin manner until all of them are not done.
while (1)
{
bool done = true;
//let us Traverse all processes one by one repeatedly
for (int i = 0 ; i < n; i++)
{
// If burst time of a process is greater than 0 then there is a need to process further
if (rem_bt[i] > 0)
{
done = false; // indicates there is a pending process
if (rem_bt[i] > quantum)
{
// By Increasing the value of t it shows how much time a process has been processed
t += quantum;
// Decreasing the burst_time of current process by the quantum
rem_bt[i] -= quantum;
}
// If burst time is smaller than or equal to the quantum then it is Last cycle for this process
else
{
// Increase the value of t to show how much time a process has been processed
t = t + rem_bt[i];
// Waiting time is current time minus time used by this process.
wt[i] = t - bt[i];
// As the process gets fully executed thus remaining burst time becomes 0.
rem_bt[i] = 0;
}
}
}
// If all the processes are done
if (done == true)
break;
}
}
// Function used to calculate the turn around time
void fTurnAroundTime(int processes[], int n,
int bt[], int wt[], int tat[])
{
// calculating turnaround time by adding bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];
}
// Function to calculate the average time
void findavgTime(int processes[], int n, int bt[],
int quantum)
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Function to find waiting time of all processes
fWaitingTime(processes, n, bt, wt, quantum);
// Function to find turn around time for all processes
fTurnAroundTime(processes, n, bt, wt, tat);
// Display processes along with all details
cout << "Processes "<< " Burst time "
<< " Waiting time " << " Turn around time\n";
// Calculate the total waiting time and total turn
// around time
for (int i=0; i<n; i++)
{
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << i+1 << "\t\t" << bt[i] <<"\t "
<< wt[i] <<"\t\t " << tat[i] <<endl;
}
cout << "Average waiting time = "
<< (float)total_wt / (float)n;
cout << "\nAverage turn around time = "
<< (float)total_tat / (float)n;
}
//Given below is the Driver Code
int main()
{
// process id's
int processes[] = { 1, 2, 3,4};
int x = sizeof processes / sizeof processes[0];
// Burst time of all processes
int burst_time[] = {21, 13, 6,12};
// Time quantum
int quantum = 2;
findavgTime(processes, x, burst_time, quantum);
return 0;
}
Output:
Processes Burst time Waiting time Turn around time 1 21 31 52 2 13 32 45 3 6 16 22 4 12 30 42 Average waiting time = 27.25 Average turn around time = 4.25
