CPU scheduling treats with the issues of deciding which of the processes in the ready queue needs to be allocated to the CPU. There are several different CPU scheduling algorithms used nowadays within an operating system. In this tutorial, you will get to know about some of them.
In this post, we will discuss the Shortest Job First (SJF) Non-preemptive Process Scheduling algorithm and also write a program for the Shortest Job First (SJF) Non-preemptive Process Scheduling algorithm. In the Shortest Job First (SJF) algorithm, if the CPU is available, it is assigned to the process that has the minimum next CPU burst. If the subsequent CPU bursts of two processes become the same, then FCFS scheduling is used to break the tie.
We will use C++ to write this algorithm due to the standard template library support. Hence, we will write the program of the Shortest Job First algorithm in C++, although, it’s very similar to C.
INPUT:
The first line is the number of processes(n).
The next n lines contain three variables: process name(pname), arrival time(atime) and burst time(btime).
OUTPUT:
Print the matrix for process name, arrival time, burst time, completion time, turn around time, waiting time and response time.
Also, print the Gantt chart.
The following is the SJF Process Scheduling program in C++.
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
char pname[50];
int btime;
int atime;
}a[50];
void insert(int n){
int i;
for(i=0;i<n;i++){
cin>>a[i].pname;
cin>>a[i].atime;
cin>>a[i].btime;
}
}
bool btimeSort(node a,node b){
return a.btime < b.btime;
}
bool atimeSort(node a,node b){
return a.atime < b.atime;
}
void disp(int n){
sort(a,a+n,btimeSort);
sort(a,a+n,atimeSort);
int ttime=0,i;
int j,tArray[n];
for(i=0;i<n;i++){
j=i;
while(a[j].atime<=ttime&&j!=n){
j++;
}
sort(a+i,a+j,btimeSort);
tArray[i]=ttime;
ttime+=a[i].btime;
}
tArray[i] = ttime;
float averageWaitingTime=0;
float averageResponseTime=0;
float averageTAT=0;
cout<<"\n";
cout<<"P.Name AT\tBT\tCT\tTAT\tWT\tRT\n";
for (i=0; i<n; i++){
cout << a[i].pname << "\t";
cout << a[i].atime << "\t";
cout << a[i].btime << "\t";
cout << tArray[i+1] << "\t";
cout << tArray[i]-a[i].atime+a[i].btime << "\t";
averageTAT+=tArray[i]-a[i].atime+a[i].btime;
cout << tArray[i]-a[i].atime << "\t";
averageWaitingTime+=tArray[i]-a[i].atime;
cout << tArray[i]-a[i].atime << "\t";
averageResponseTime+=tArray[i]-a[i].atime;
cout <<"\n";
}
cout<<"\n";
cout<<"\nGantt Chart\n";
for (i=0; i<n; i++){
cout <<"| "<< a[i].pname << " ";
}
cout<<"\n";
for (i=0; i<n+1; i++){
cout << tArray[i] << "\t";
}
cout<<"\n";
cout<<"Average Response time: "<<(float)averageResponseTime/(float)n<<endl;
cout<<"Average Waiting time: "<<(float)averageWaitingTime/(float)n<<endl;
cout<<"Average TA time: "<<(float)averageTAT/(float)n<<endl;
}
int main(){
int nop,choice,i;
cout<<"Enter number of processes\n";
cin>>nop;
insert(nop);
disp(nop);
return 0;
}
OUTPUT:
Enter number of processes 5 1 0 5 2 1 2 3 2 4 4 3 1 5 4 7 P.Name AT BT CT TAT WT RT 1 0 5 5 5 0 0 4 3 1 6 3 2 2 2 1 2 8 7 5 5 3 2 4 12 10 6 6 5 4 7 19 15 8 8 Gantt Chart | 1 | 4 | 2 | 3 | 5 0 5 6 8 12 19 Average Response time: 4.2 Average Waiting time: 4.2 Average TA time: 8
Other process scheduling algorithms
- SJF (Non-preemptive) Process Scheduling
- HRRN (Preemptive) Process Scheduling
- Round Robin Process Scheduling
- Priority Scheduling (preemptive)
- LRTF Process Scheduling
- SJF (preemptive) Process Scheduling
Let us know in the comments if you are having any questions regarding this Shortest Job First Processing Scheduling algorithm.
And if you found this post helpful, then please help us by sharing this post with your friends. Thank You
