1.6K

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 their 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 types of scheduling algorithms.

Furthermore, the CPU itself 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 right away. 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 aforementioned situation. In this case, the term “convoy” refers to a situation in which 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. Non-Preemptive FCFS Scheduling Algorithm

The non-preemptive FCFS scheduling algorithm is a process scheduling algorithm that assigns processes to processors in a first come, first served order. The non-preemptive FCFS scheduling algorithm is not preemptive, meaning that once a process has been assigned to a processor, another process cannot be preempted. This can lead to problems if a process is assigned to a processor that is not the most efficient for that process, as the process will have to wait for its turn to be scheduled again.

Program #1: FCFS Non-Preemptive Scheduling Algorithm Implementation With C++

#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
    int exe[20], num, wt=0, tnt=0;
    float avg_wt=0, avg_tnt=0;
    cout<<"Enter The Number Of Processes: ";
    cin>>num;
    if(num==0)
    {
    	cout<<endl<<endl;
        cout<<"Error! The Processes Can't Be Zero. Please try again!"<<endl;
        return 0;
    }
    for(int i=0; i<num; i++)
    {
        cout<<" Enter The Total Execution Time For The Process "<<i+1<< " : ";
        cin>>exe[i];
        if(exe[i]==0)
        {
        	cout<<endl<<endl;
            cout<<"Error The Burst Time Can't Be Zero. Please try again!"<<endl;
            return 0;
        }
    }
    cout<<"\nProcess ID\tExecution Time\tArrival Time"<<endl;
    for(int i=0; i<num; i++)
        cout<<setw(5)<<i+1<<setw(17)<<exe[i]<<setw(17)<<"0"<<endl;
    cout<<"\nProcess ID\tWaiting Time\tTurn Around Time"<<endl;
    for(int i=0; i<num; i++)
    {
        tnt+=exe[i];
        avg_wt+=wt;
        avg_tnt+=tnt;
        cout<<setw(5)<<i+1<<setw(17)<<wt<<setw(17)<<tnt<<endl;
        wt+=exe[i];
    }
    avg_wt=avg_wt/(float)num;
    avg_tnt/=(float)num;
    cout<<" \nThe Average Waiting Time       : "<<   avg_wt;
    cout<<" \nThe Average Turn Around Time   : "<<   avg_tnt;
    return 0;
}

OUTPUT OF THE PROGRAM:

Explanation Of The Above Program Line-by-Line:

Line 1: Includes the input/output stream header file iostream.

Line 2: Includes the input/output manipulation header file iomanip.

Line 3: Allows the standard namespace to be accessed.

Line 4: Begins the main function.

Line 5: Declares an integer array exe, an integer num, integers wt and tnt, and floats avg_wt and avg_tnt.

Line 6: Asks the user to input the number of processes.

Line 7: Stores the user input in the integer num.

Line 8: Asks the user to input the total execution time for each process.

Line 9: Stores the user input in the integer array exe.

Line 10: Begins a for loop that will iterate num times.

Line 11: Asks the user to input the total execution time for the current process.

Line 12: Stores the user input in the current element of the integer array exe.

Line 13: Ends the for loop.

Line 14: Prints a table header for the process ID, execution time, and arrival time.

Line 15: Begins a for loop that will iterate num times.

Line 16: Prints the current process ID, execution time, and arrival time.

Line 17: Ends the for loop.

Line 18: Prints a table header for the process ID, waiting time, and turnaround time.

Line 19: Begins a for loop that will iterate num times.

Line 20: Adds the execution time of the current process to the total turnaround time.

Line 21: Adds the current waiting time to the total waiting time.

Line 22: Calculates the average waiting time.

Line 23: Calculates the average turnaround time.

Line 24: Prints the current process ID, waiting time, and turnaround time.

Line 25: Adds the execution time of the current process to the current waiting time.

Line 26: Ends the for loop.

Line 27: Calculates the average waiting time.

Line 28: Calculates the average turnaround time.

Line 29: Prints the average waiting time.

Line 30: Prints the average turnaround time.

Line 31: Ends the main function.

Line 32: Ends the program.

Program #2: FCFS Non-Preemptive Scheduling Algorithm Implementation With C++ [Using Functions]

#include <iostream>
#include <iomanip>
using namespace std;
int burst_time[3];
int n;

void inputdata()
{
	cout<<"Number Of Processes To Be Entered: ";
	cin>>n;
	for(int i=0; i<n; i++)
	{
		cout<<" Enter The Burst Time Of The Process "<<i+1<<" : ";
		cin>>burst_time[i];
	}
}

void display()
{
	cout<<endl;
	cout<<"Process ID\tBurst Time\tArrival Time"<<endl;
	for(int i=0; i<n; i++)
	cout<<setw(5)<<i+1<<setw(15)<<burst_time[i]<<setw(17)<<"0"<<endl;
}

void call_wt_tt()
{
	int wt=0, tnt=0;
	float avg_wt=0, avg_tnt=0;
	cout<<"\nProcess ID\tWaiting Time\tTurn Around Time"<<endl;
	for(int i=0; i<n; i++)
	{
		tnt+=burst_time[i];
		avg_wt+=wt;
		avg_tnt+=tnt;
		cout<<setw(5)<<i+1<<setw(15)<<wt<<setw(17)<<tnt<<endl;
		wt+=burst_time[i];
	}
	avg_wt=avg_wt/(float)n;
	avg_tnt/=(float)n;
	cout<<"\nThe Average Waiting Time       : "<< avg_wt;
	cout<<"\nThe Average Turn Around Time   : "<< avg_tnt<<endl;
}

int main()
{
	inputdata();
	display();
	call_wt_tt();
	return 0;
}

The output would be the same as for Program #1.

Program #3: FCFS Non-Preemptive Scheduling Algorithm Implementation With C++ [Using Functions and Class]

#include <iostream>
#include <iomanip>
using namespace std;
class fcfs_nonpreemptive
{
	int num;
	int burst_time[20];
public:
	void getdata();
	void display();
	void call_wt_tt();
};
void fcfs_nonpreemptive::getdata()
{
	cout<<"Enter The Number Of Processes: ";
	cin>>num;
	for(int i=0; i<num; i++)
	{
		cout<<" Enter Total Execution Time For Process "<<i+1<< " : ";
		cin>>burst_time[i];
	}
}
void fcfs_nonpreemptive::display()
{
	cout<<endl<<"Process ID\tExecution Time\tArrival Time"<<endl;
	for(int i=0; i<num; i++)
	cout<<setw(5)<<i+1<<setw(17)<<burst_time[i]<<setw(17)<<"0"<<endl;
}
void fcfs_nonpreemptive::call_wt_tt()
{
	int wt=0, tnt=0;
	float avg_wt=0, avg_tnt=0;
	cout<<"\nProcess ID\tWaiting Time\tTurn Around Time"<<endl;
	for(int i=0; i<num; i++)
	{
		tnt+=burst_time[i];
		avg_tnt+=tnt;
		avg_wt+=wt;
		cout<<setw(5)<<i+1<<setw(17)<<wt<<setw(17)<<tnt<<endl;
		wt+=burst_time[i];
	}
	avg_wt=avg_wt/(float)num;
	avg_tnt/=(float)num;
	cout<<"\nAverage Waiting Time      : "<<avg_wt;
	cout<<"\nAverage Turn Around Time  : "<<avg_tnt<<endl;
}
int main()
{
	fcfs_nonpreemptive call;
	call.getdata();
	call.display();
	call.call_wt_tt();
	return 0;
}

The output would be the same as for Program #2.

FCFS Non-Preemptive Scheduling Algorithm Implementation With C

#include<stdio.h>
int main()
{
    int exe[20], num, wt=0, tnt=0;
    float avg_wt=0, avg_tnt=0;
    printf("Enter The Number Of Processes: ");
    scanf("%d", &num);
    if(num==0)
    {
        printf("Error! The Processes Can't Be Zero. Please try again!");
        return 0;
    }
    for(int i=0; i<num; i++)
    {
        printf(" Enter The Total Execution Time For The Process %d : ", i+1);
        scanf("%d", &exe[i]);
        if(exe[i]==0)
        {
            printf("Error The Burst Time Can't Be Zero. Please try again!");
            return 0;
        }
    }
    printf("\nProcess ID\tExecution Time\tArrival Time\n");
    for(int i=0; i<num; i++)
        printf("%5d\t\t%d\t\t%d\n", i+1, exe[i], 0);
    printf("\nProcess ID\tWaiting Time\tTurn Around Time\n");
    for(int i=0; i<num; i++)
    {
        tnt+=exe[i];
        avg_wt+=wt;
        avg_tnt+=tnt;
        printf("%5d\t\t%d\t\t%d\n", i+1, wt, tnt);
        wt+=exe[i];
    }
    avg_wt=avg_wt/(float)num;
    avg_tnt/=(float)num;
    printf(" \nThe Average Waiting Time       : %f", avg_wt);
    printf(" \nThe Average Turn Around Time   : %f", avg_tnt);
    return 0;
}

Summary:

• Definition: The FCFS operating system scheduling algorithm executes queued requests and processes them automatically by order of their arrival.
• Both preemptive and non-preemptive scheduling algorithms are supported.
• First Come, First Serve is referred to as FCFS.
• Purchasing a movie ticket at the ticket counter is a practical application of the FCFS approach.
• It is a CPU scheduling method in its most basic configuration.
• Because it uses a non-preemptive CPU scheduling mechanism, once a process has been given access to the CPU, the CPU will not be released until it has been completed.

Please click here to read the FCFS Preemptive Scheduling Algorithm with the C++ Program implementation.