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 post, we will discuss the Longest Remaining Time First Process Scheduling Algorithm and also write a program for the LRTF Scheduling algorithm. In this scheduling algorithm, we find the process with the maximum remaining time and then process it. We check for the maximum remaining time after some interval of time(say 1 unit each) to check if another process having more Burst Time arrived up to that time.
We will use C++ to write this algorithm due to the standard template library support. Hence, we will write the program of the Longest Remaining Time First Process Scheduling Algorithm in C++, although, it’s very similar to C.
INPUT:
The first line is the number of processes(nop).
The next nop lines contain four 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 Longest Remaining Time First Process Scheduling Algorithm program in C++.
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
char pname;
int btime;
int atime;
int restime=0;
int ctime=0;
int wtime=0;
}a[1000],b[1000],c[1000];
void insert(int n){
int i;
for(i=0;i<n;i++){
cin>>a[i].pname;
cin>>a[i].atime;
cin>>a[i].btime;
a[i].wtime=-a[i].atime+1;
}
}
bool btimeSort(node a,node b){
return a.btime < b.btime;
}
bool btimeOppSort(node a,node b){
if(a.btime!=b.btime)
return a.btime > b.btime;
return a.atime < b.atime;
}
bool atimeSort(node a,node b){
return a.atime < b.atime;
}
int k=0,f=0,r=0;
void disp(int nop,int qt){
int n=nop,q;
sort(a,a+n,atimeSort);
int ttime=0,i;
int j,tArray[n];
int alltime=0;
bool moveLast=false;
for(i=0;i<n;i++){
alltime+=a[i].btime;
// cout<<"start is "<<a[i].pname<<" to "<<ttime<<"\n";
}
alltime+=a[0].atime;
for(i=0;ttime<=alltime;){
j=i;
while(a[j].atime<=ttime&&j!=n){
// cout<<"less than atime is "<<a[j].pname<<" to "<<ttime<<"\n";
b[r]=a[j];
j++;
r++;
}
if(r==f){
c[k].pname='i';
c[k].btime=a[j].atime-ttime;
c[k].atime=ttime;
ttime+=c[k].btime;
k++;
continue;
}
i=j;
if(moveLast==true){
// cout<<"moving "<<b[f].pname<<" to "<<r<<"\n";
sort(b+f,b+r,btimeOppSort);
// b[r]=b[f];
// f++;
// r++;
}
j=f;
if(b[j].btime>qt){
c[k]=b[j];
c[k].btime=qt;
k++;
b[j].btime=b[j].btime-qt;
ttime+=qt;
moveLast=true;
for(q=0;q<n;q++){
if(b[j].pname!=a[q].pname){
a[q].wtime+=qt;
}
}
}
else{
c[k]=b[j];
k++;
f++;
ttime+=b[j].btime;
moveLast=false;
for(q=0;q<n;q++){
if(b[j].pname!=a[q].pname){
a[q].wtime+=b[j].btime;
}
}
// cout<<"called for "<<b[j].pname<<" "<<b[j].btime<<"\n";
}
if(f==r&&i>=n)
break;
}
tArray[i]=ttime;
ttime+=a[i].btime;
for(i=0;i<k-1;i++){
if(c[i].pname==c[i+1].pname){
c[i].btime+=c[i+1].btime;
for(j=i+1;j<k-1;j++)
c[j]=c[j+1];
k--;
i--;
}
}
int rtime=0;
for(j=0;j<n;j++){
rtime=0;
for(i=0;i<k;i++){
if(c[i].pname==a[j].pname){
a[j].restime=rtime;
break;
}
rtime+=c[i].btime;
}
}
float averageWaitingTime=0;
float averageResponseTime=0;
float averageTAT=0;
cout<<"\nGantt Chart\n";
rtime=0;
for (i=0; i<k; i++){
if(i!=k)
cout<<"| "<<'P'<< c[i].pname << " ";
rtime+=c[i].btime;
for(j=0;j<n;j++){
if(a[j].pname==c[i].pname)
a[j].ctime=rtime;
}
}
cout<<"\n";
rtime=0;
for (i=0; i<k+1; i++){
cout << rtime << "\t";
tArray[i]=rtime;
rtime+=c[i].btime;
}
cout<<"\n";
cout<<"\n";
cout<<"P.Name AT\tBT\tCT\tTAT\tWT\tRT\n";
for (i=0; i<nop&&a[i].pname!='i'; i++){
if(a[i].pname=='\0')
break;
cout <<'P'<< a[i].pname << "\t";
cout << a[i].atime << "\t";
cout << a[i].btime << "\t";
cout << a[i].ctime << "\t";
cout << a[i].wtime+a[i].ctime-rtime+a[i].btime << "\t";
averageTAT+=a[i].wtime+a[i].ctime-rtime+a[i].btime;
cout << a[i].wtime+a[i].ctime-rtime << "\t";
averageWaitingTime+=a[i].wtime+a[i].ctime-rtime;
cout << a[i].restime-a[i].atime << "\t";
averageResponseTime+=a[i].restime-a[i].atime;
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,qt;
cout<<"Enter number of processes\n";
cin>>nop;
cout<<"Enter process, AT, BT\n";
insert(nop);
disp(nop,1);
return 0;
}
OUTPUT:
Enter number of processes 5 Enter process, AT, BT 1 0 5 2 1 3 3 2 4 4 3 5 5 4 2 Gantt Chart | P1 | P3 | P4 | P1 | P2 | P3 | P4 | P1 | P2 | P3 | P4 | P5 | P1 | P2 | P3 | P4 | P5 0 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P.Name AT BT CT TAT WT RT P1 0 5 15 15 10 0 P2 1 3 16 15 12 5 P3 2 4 17 15 11 0 P4 3 5 18 15 10 0 P5 4 2 19 15 13 9 Average Response time: 2.8 Average Waiting time: 11.2 Average TA time: 15
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 Longest Remaining Time First Process Scheduling Algorithm.
And if you found this post helpful, then please help us by sharing this post with your friends. Thank You
Hello! May I ask if how to convert your code into shortest remaining time first? Thank you in advanced!