First-come, first-served (FCFS) scheduling algorithm

Operating systems use different scheduling algorithms to schedule the execution of processes by the CPU. Some scheduling algorithms are as follows:

First-come, first-served (FCFS) scheduling
Shortest-job-next (SJN) scheduling
Priority scheduling
Shortest remaining time
Round robin (RR) scheduling
Multiple-level queues scheduling

Note: Algorithms are either preemptivePreemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state. or non-preemptiveNon-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time..

In this answer, we'll discuss the first-come, first-served scheduling algorithm.

First-come, first-served scheduling

This algorithm is like a first-in, first-out (FIFO) algorithm. As the name suggests, the process or request which arrives first gets executed first. In case of a tie, if two processes request CPU simultaneously, the process with a smaller process ID gets the CPU allocation first. This is the simplest and easiest-to-implement CPU scheduling algorithm.

Note: This algorithm is non-preemptive.

Example

Suppose we have a set of five processes whose arrival timeArrival time is the time when a process enters into the ready state and is ready for its execution. and burst time Burst time is the total time taken by the process for its execution on the CPU.are given. We have to schedule the processes using FCFS scheduling and calculate the average waiting timeBurst time is the total time taken by the process for its execution on the CPU..

#include<iostream>
using namespace std;
// Function to find the waiting time
void findWait_Time(int processes[], int size, int burst_time[],
								int wait_t[], int arrival_t[])
{
	int service_time[size];
	service_time[0] = arrival_t[0];
	wait_t[0] = 0;
	int i = 1;
	// calculating waiting time
	while ( i < size )
	{
		// Add burst time of previous processes
		service_time[i] = service_time[i-1] + burst_time[i-1];
		//waiting time = sum - at[i]
		wait_t[i] = service_time[i] - arrival_t[i];
		if (wait_t[i] < 0)
			wait_t[i] = 0;
		i++;
	}
}
// Function to calculate average waiting time
void findavg_wait_Time(int processes[], int size, int burst_t[], int arrival_t[])
{
	int wt[size], tat[size];
	findWait_Time(processes, size, burst_t, wt, arrival_t);
	// Display processes along with all details
	cout << "Processes " << " Burst Time " << " Arrival Time "
		<< " Waiting Time \n";
	int total_wt = 0, total_tat = 0;
	int i = 0;
	while (i < size)
	{
		total_wt = total_wt + wt[i];
		total_tat = total_tat + tat[i];
		int compl_time = tat[i] + arrival_t[i];
		cout << " " << i+1 << "\t\t" << burst_t[i] << "\t\t"
			<< arrival_t[i] << "\t\t" << wt[i] << "\t\t "
			 << endl;
		
		i++;
	}
	cout << "Average waiting time = "
		<< (float)total_wt / (float)size;
	
}
// Driver code
int main()
{
	// Process numbers
	
	int processes[] = {4, 3, 1, 5, 2};
	int n = sizeof processes / sizeof processes[0];
	// Arrival time of all processes
	int arrival_time[] = {0, 1, 2, 4, 5};
	// Burst time of all processes
	int burst_time[] = {3, 8, 6, 4, 2};
	findavg_wait_Time(processes, n, burst_time, arrival_time);
	return 0;
}

Explanation

Execution order: The program finds the waiting time first for all processes using the given burst and arrival time, and once it's done, it computes the average waiting time by (float)total_wt / (float)size and displays details along processes.

Line 23–24: If the waiting time for any process is negative, that means it's already in the queue, so before the CPU becomes idle, its waiting time becomes 0, wt[i] = 0.

Advantages

The advantages of the FCFS algorithm are the following:

This algorithm is simple to implement and easy to understand.
It uses a very simple data structure queue for maintaining processes.
FCFS does not lead the process to starvationStarvation is the problem that occurs when low priority processes get jammed for an unspecified time as the high priority processes keep executing. .

Disadvantages

The disadvantages of the FCFS algorithm are the following:

As it is a non-preemptive algorithm, it doesn't consider any process's priority or burst time.
This algorithm mostly suffers from the convoy effectIn convoy effect, consider processes with higher burst time arrived before the processes with smaller burst time. Then, smaller processes have to wait for a long time for longer processes to release the CPU..
The average waiting time for processes is not optimal.
Parallel utilization of resources for processes is not possible.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Process	Burst Time	Arrival Time
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

First-come, first-served (FCFS) scheduling algorithm

First-come, first-served scheduling

Example

Solution

Gantt chart

Waiting time

Average waiting time

Code

Explanation

Advantages

Disadvantages