Abu Zar Mishwani
What Does First Come, First Served (FCFS) Mean?
Operating systems and networks utilize the scheduling technique known as First Come, First Served (FCFS) to effectively and automatically carry out queued tasks, processes, and requests in the order of arrival. First-in, first-out (FIFO), and first-come, first-choice (FCFC) are other names for the FCFS scheduling algorithm.
An FCFS algorithm is predictable due to its simplicity, irrespective of the tasks or requests it must handle. FCFS algorithms mimic actual customer service scenarios where customers that come first are treated first regardless of the quantity and complexity of their interaction, similar to a grocery store checkout system.
Because it requires little to no human or artificial intelligence (AI) interaction and doesn’t waste time prioritizing jobs and requests based on their urgency or degree of complexity, first come, first served is one of the most effective and autonomous scheduling algorithms.
Furthermore, the CPU manages scheduling rather than software or another, more complicated work scheduling algorithm.
How does an FCFS Scheduling Algorithm Work?
Let’s say the CPU has three requests, P1, P2, and P3, that need to be processed. Assume that P1 is a complicated process that takes around 35 seconds to complete, P2 is a considerably easier request that only takes 10 seconds to process, and P3 is a relatively basic request that takes 20 seconds to process.
The wait time is 0 when P1 is initially added to the queue, and the CPU begins processing immediately. The wait time for P2 would be 25 seconds, though.
However, P3 would have to wait 45 seconds as he came last. To finish all three requests and clear the queue, an FCFS scheduling algorithm would need 65 seconds in total, which is comparable to other sequential processing, mono-CPU systems.
FCFS has fewer completed tasks per a predetermined amount of time than an intelligent scheduling algorithm since it does not review requests before beginning.
In this case, the FCFS scheduling algorithm would finish one job within 15 seconds of its 45-second runtime. Other algorithms, such as those that begin with the most basic queries, would have completed the two requests.
FCFS and the Convoy Effect
The Convoy Effect in operating systems is demonstrated by the situation mentioned above. In this case, the term “convoy” refers to a situation where several cars drive as a single unit in the real world.
The convoy will slow down if one vehicle is forced to follow a considerably slower vehicle for an extended period. (Note: In sequential processing, this comparison only applies when there isn’t a secondary processing unit to share some of the load with the primary processing unit.)
Despite the numerous disadvantages of utilizing an FCFS scheduling algorithm, there are many use situations where it is more efficient than intelligent scheduling algorithms, which waste time in re-evaluating each request’s priority after processing the previous one.
Types Of FCFS Algorithm
Preemptive and Non-preemptive scheduling algorithms are two commonly used approaches for process scheduling. Preemptive scheduling algorithms allow processes to be interrupted to schedule other processes, while non-preemptive scheduling algorithms do not allow processes to be interrupted once they have started.
#1. Preemptive FCFS Scheduling Algorithm
FCFS is a non-preemptive scheduling algorithm, meaning that once a process has started execution, it cannot be interrupted until it completes its CPU burst or I/O request. While FCFS is easy to understand and implement, it is not necessarily the most efficient scheduling algorithm. One major issue with FCFS is that it is vulnerable to process starvation – long-running processes can prevent shorter processes from ever executing.
To combat process starvation, FCFS can be modified to be preemptive. In a preemptive FCFS scheduling algorithm, if a new process arrives with a shorter CPU burst than the currently running process, the new process is dispatched to the CPU, and the currently running process is placed at the end of the ready queue.
Preemptive FCFS scheduling is more complex than non-preemptive FCFS, but it eliminates the issue of process starvation. However, preemptive FCFS can cause significant performance issues in a system with many process arrivals as context switches between processes become frequent.
FCFS Preemptive Scheduling Algorithm Implementation With C++
#include<iostream>
#include<conio.h>
#include<iomanip>
#include <list>
using namespace std;
class fcfs_preemptive //class representing round robin scheduling
{
int *rq; //request times
int n; //number of processes
int q; //time quantum
int *w; //wait times
int *t; //turn-around times
int *a; //arrival times
list<int> order;
public:
fcfs_preemptive(void);
~fcfs_preemptive(void);
int read(); //read input from the user
void calc(); //to calculate turn-around and wait times of all processes and the ordering
void display();
};
fcfs_preemptive::fcfs_preemptive(void)
{
rq=w=t=NULL;
}
fcfs_preemptive::~fcfs_preemptive(void)
{
if(rq!=NULL)
{
delete[] rq;
delete[] w;
delete[] t;
delete[] a;
}
}
int fcfs_preemptive::read() //read input from the user
{
int i;
cout<<"Enter The Number Of Processes: ";
cin>>n;
if(n==0)
{
cout<<endl<<endl;
cout<<"Error! The Process Can't Be Zero, Please Try Again!"<<endl;
exit(0);
}
try
{
rq=new int[n];
w=new int[n];
t=new int[n];
a=new int[n];
}
catch(bad_alloc &ba)
{
cerr<<ba.what()<<endl;
exit(1);
}
for(i=0;i<n;i++)
{
cout<<" Enter The Arrival Time For The Process "<<i+1<<" : ";
cin>>a[i];
if(a[i]==0)
{
cout<<endl<<endl;
cout<<" Error! The Arrival Time Can't Be Zero, Please Try Again!"<<endl;
exit(0);
}
}
cout<<endl<<endl;
for(i=0;i<n;i++)
{
cout<<"Enter The Burst Time For The Process "<<i+1<<" : ";
cin>>rq[i];
if(rq[i]==0)
{
cout<<endl<<endl;
cout<<" Error! The Burst Time Can't Be Zero, Please Try Again!"<<endl;
exit(0);
}
w[i]=t[i]=0;
}
cout<<endl<<endl;
cout<<"Enter The Time Slice : ";
cin>>q;
if(q==0)
{
cout<<endl<<endl;
cout<<" Error! The Time Slice Can't Be Zero, Please Try Again!"<<endl;
exit(0);
}
return 1;
}
void fcfs_preemptive::calc()//to calculate turn-around and wait times of all processes and the ordering
{
int j=0;
int time;
int k;
int i;
int *r;//remaining times
try
{
r=new int[n];
}
catch(bad_alloc &ba)
{
cerr<<ba.what()<<endl;
exit(1);
}
for(i=0;i<n;i++) r[i]=rq[i];
bool f=false; //flag to indicate whether any process was scheduled as i changed from 0 to n-1 in the next for loop
int sp=0; //time spent
for(i=0;j<n;i=(i+1)%n) //while there are uncompleted processes
{
if(r[i]>0&&sp>=a[i]) //find the next uncompleted process which has already or just arrived
{
f=true;
if(r[i]<=q) //if the process requests for time less than the quantum
time=r[i]; //time to be alloted in this turn is the complete requested time
else time=q; //else, it is the quantum time
//schedule the process
t[i]+=time,r[i]-=time,order.push_back(i+1);
if(r[i]==0) j++; //if the process has got completed, increment j
for(k=0;k<n;k++)
if(r[k]!=0&&k!=i&&a[k]<sp+time) //for all other arrived processes incompleted after scheduling this process
if(!(a[k]<=sp)) //if they arrived while scheduling this process
w[k]+=sp+time-a[k],t[i]+=sp+time-a[k]; //account for the time they spent waiting while the process was being scheduled
else
w[k]+=time,t[k]+=time; //add time to their wait times and turn-around times
sp+=time;
continue;
}
if(i==n-1)
{
if(!f)
//now there are no more arrived processes to be scheduled
//so change sp to the arrival time of next arriving process
{
int it;
int diff=0; //diff between present time spent and arrivaltime of next arriving process
for(it=0;it<n;it++)
if(sp<a[it]) //if process has'nt yet arrived
{
if(diff==0) diff=a[it]-sp;
else if(diff>a[it]-sp) diff=a[it]-sp;
}
sp+=diff;
}
f=false;
}
}
delete[] r;
}
void fcfs_preemptive::display()
{
int i;
float tav=0; //average turn-around time
float wav=0; //average wait time
for(i=0;i<n;i++)
tav+=t[i],wav+=w[i];
tav/=n,wav/=n;
cout<<endl;
cout<<"Execution Order Will Be (After Preemption):"<<endl;
cout<<endl;
list<int>::iterator oi;
for(oi=order.begin();oi!=order.end();oi++)
cout<<*oi<<"\t";
cout<<endl<<endl;
cout<<"\n\nThe Average Turn Around Time : "<<tav<<endl<<"The Average Waiting Time : "<<wav<<endl;
}
int main()
{
fcfs_preemptive r;
r.read();
r.calc();
r.display();
getch();
}
OUTPUT OF THE PROGRAM:
Enter The Number Of Processes: 4
Enter The Arrival Time For The Process 1 : 1
Enter The Arrival Time For The Process 2 : 2
Enter The Arrival Time For The Process 3 : 3
Enter The Arrival Time For The Process 4 : 4
Enter The Burst Time For The Process 1 : 3
Enter The Burst Time For The Process 2 : 5
Enter The Burst Time For The Process 3 : 2
Enter The Burst Time For The Process 4 : 1
Enter The Time Slice : 2
Execution Order Will Be (After Preemption):
1 2 3 4 1 2 2
The user is asked to input the total number of processes in the above program. The users will have to input the Arrival Time and The Burst Time (Execution/Processing Time) For each Process.
After that, the user will be asked to input the time slice for each process.
So, let’s say the user inputs the number of processes as 4, the arrival time as 1, 2, 3, 4, and the burst time for the process as 3, 5, 2, 1, and the time slice for each process as 2, respectively.
What will happen here is that process 1 will be given the time quantum of 2-sec. Process 1 will be executed for 2 sec, and after that, the processor will be assigned to process 2, and process 2 will be executed for 2 sec. In simple words, all the processes will be executed for 2-sec.
Once all the processes are processed for 2-sec, it will repeat from process 1 and execute it again for 2-sec and the others in the same way.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include <list>
using namespace std;
class fcfs_preemptive
{
int *rq;
int n;
int q;
int *w;
int *t;
int *a;
list<int> order;
public:
fcfs_preemptive(void);
~fcfs_preemptive(void);
int read();
void calc();
void display();
};
fcfs_preemptive::fcfs_preemptive(void)
{
rq=w=t=NULL;
}
fcfs_preemptive::~fcfs_preemptive(void)
{
if(rq!=NULL)
{
delete[] rq;
delete[] w;
delete[] t;
delete[] a;
}
}
int fcfs_preemptive::read()
{
int i;
printf("Enter The Number Of Processes: ");
scanf("%d", &n);
if(n==0)
{
printf("\n\nError! The Process Can't Be Zero, Please Try Again!\n");
exit(0);
}
rq=new int[n];
w=new int[n];
t=new int[n];
a=new int[n];
for(i=0;i<n;i++)
{
printf(" Enter The Arrival Time For The Process %d : ", i+1);
scanf("%d", &a[i]);
if(a[i]==0)
{
printf("\n\nError! The Arrival Time Can't Be Zero, Please Try Again!\n");
exit(0);
}
}
printf("\n\n");
for(i=0;i<n;i++)
{
printf("Enter The Burst Time For The Process %d : ", i+1);
scanf("%d", &rq[i]);
if(rq[i]==0)
{
printf("\n\nError! The Burst Time Can't Be Zero, Please Try Again!\n");
exit(0);
}
w[i]=t[i]=0;
}
printf("\n\n");
printf("Enter The Time Slice : ");
scanf("%d", &q);
if(q==0)
{
printf("\n\nError! The Time Slice Can't Be Zero, Please Try Again!\n");
exit(0);
}
return 1;
}
void fcfs_preemptive::calc()
{
int j=0;
int time;
int k;
int i;
int *r;
r=new int[n];
for(i=0;i<n;i++) r[i]=rq[i];
bool f=false;
int sp=0;
for(i=0;j<n;i=(i+1)%n)
{
if(r[i]>0&&sp>=a[i])
{
f=true;
if(r[i]<=q)
time=r[i];
else time=q;
t[i]+=time,r[i]-=time,order.push_back(i+1);
if(r[i]==0) j++;
for(k=0;k<n;k++)
if(r[k]!=0&&k!=i&&a[k]<sp+time)
if(!(a[k]<=sp))
w[k]+=sp+time-a[k],t[i]+=sp+time-a[k];
else
w[k]+=time,t[k]+=time;
sp+=time;
continue;
}
if(i==n-1)
{
if(!f)
{
int it;
int diff=0;
for(it=0;it<n;it++)
if(sp<a[it])
{
if(diff==0) diff=a[it]-sp;
else if(diff>a[it]-sp) diff=a[it]-sp;
}
sp+=diff;
}
f=false;
}
}
delete[] r;
}
void fcfs_preemptive::display()
{
int i;
float tav=0;
float wav=0;
for(i=0;i<n;i++)
tav+=t[i],wav+=w[i];
tav/=n,wav/=n;
printf("\n");
printf("Execution Order Will Be (After Preemption):\n");
printf("\n");
list<int>::iterator oi;
for(oi=order.begin();oi!=order.end();oi++)
printf("%d\t", *oi);
printf("\n\n");
printf("The Average Turn Around Time : %f\nThe Average Waiting Time : %f\n", tav, wav);
}
int main()
{
fcfs_preemptive r;
r.read();
r.calc();
r.display();
getch();
}
import sys
def fcfs_preemptive():
n = int(input("Enter the number of processes: "))
if n == 0:
print("Error! The process can't be zero, please try again!")
sys.exit(0)
rq = [0] * n
w = [0] * n
t = [0] * n
a = [0] * n
for i in range(n):
a[i] = int(input("Enter the arrival time for the process {}: ".format(i + 1)))
if a[i] == 0:
print("Error! The arrival time can't be zero, please try again!")
sys.exit(0)
for i in range(n):
rq[i] = int(input("Enter the burst time for the process {}: ".format(i + 1)))
if rq[i] == 0:
print("Error! The burst time can't be zero, please try again!")
sys.exit(0)
w[i] = t[i] = 0
q = int(input("Enter the time slice: "))
if q == 0:
print("Error! The time slice can't be zero, please try again!")
sys.exit(0)
j = 0
time = 0
k = 0
i = 0
r = [0] * n
for i in range(n):
r[i] = rq[i]
f = False
sp = 0
order = []
while j < n:
if r[i] > 0 and sp >= a[i]:
f = True
if r[i] <= q:
time = r[i]
else:
time = q
t[i] += time
r[i] -= time
order.append(i + 1)
if r[i] == 0:
j += 1
for k in range(n):
if r[k] != 0 and k != i and a[k] < sp + time:
if not (a[k] <= sp):
w[k] += sp + time - a[k]
t[i] += sp + time - a[k]
else:
w[k] += time
t[k] += time
sp += time
i = (i + 1) % n
continue
if i == n - 1:
if not f:
diff = 0
for it in range(n):
if sp < a[it]:
if diff == 0:
diff = a[it] - sp
elif diff > a[it] - sp:
diff = a[it] - sp
sp += diff
f = False
i = (i + 1) % n
tav = 0
wav = 0
for i in range(n):
tav += t[i]
wav += w[i]
tav /= n
wav /= n
print("\n")
print("Execution Order Will Be (After Preemption):\n")
print("\n")
for oi in order:
print(oi, "\t", end = "")
print("\n\n")
print("The Average Turn Around Time : {}\nThe Average Waiting Time : {}\n".format(tav, wav))
fcfs_preemptive()
Summary:
In non-preemptive scheduling, if there are four processes, P1, P2, P3, and P4, the Processing time for the P1 is 400 sec and 5 sec for P2. In this case, the P2 will have to wait for 400 sec just to have its process done, which takes 5 sec.
While in Preemptive scheduling, each process will be assigned a fixed time slice for which it has to process. So, in that case, if the time quantum is 2 sec, then P2, which has a burst time of 5 sec, will be completed in just three turns.