First Come First Serve (FCFS) Scheduling Algorithm with Examples!!

First Come First Serve (FCFS) scheduling is a types of CPU scheduling algorithm used by operating systems to schedule processes or tasks for execution. In FCFS scheduling, the operating system simply executes the processes in the order in which they arrive, without any prioritization or preemption.

The FCFS algorithm maintains a queue of processes, with the first process to arrive at the front of the queue. When the CPU becomes available, the process at the front of the queue is selected for execution, and it runs until it either completes or is blocked. Once a process completes or is blocked, the next process in the queue is selected for execution, and the process continues until all processes have completed.

FCFS scheduling is easy to implement and provides a fair allocation of CPU time, but it can suffer from the "convoy effect," where a long-running process can hold up other processes that arrive later. This effect can result in poor overall system performance and longer average response times for users.

In general, FCFS scheduling is suitable for batch processing systems where the arrival of processes is predictable and there is no need for interactive or real-time processing. However, for systems that require faster response times and more efficient use of system resources, other scheduling algorithms such as Round Robin scheduling algorithm or Shortest Job First may be more appropriate.

How FCFS Scheduling Algorithm Works?

FCFS (First-Come-First-Serve) works on the principle of serving tasks in the order they arrive. The first task to arrive is the first task to be served.

The FCFS algorithm maintains a queue of tasks waiting to be executed. When a new task arrives, it is added to the back of the queue. The CPU executes the task at the front of the queue until it completes, and then moves on to the next task in the queue. This continues until all the tasks in the queue are executed.

The FCFS algorithm is non-preemptive, meaning that once a task is started, it runs to completion before the next task in the queue can be started. This can lead to long waiting times for tasks that arrive later, especially if the first task takes a long time to complete.

The FCFS algorithm is simple to implement and can be used in many situations. However, it is not suitable for real-time systems or systems with high-priority tasks. In such systems, a preemptive scheduling algorithm such as Round Robin or Priority Scheduling may be used.

Calculate Average Waiting Time in FCFS Scheduling

In First-Come-First-Serve (FCFS) scheduling algorithm, processes are executed in the order they arrive in the queue. The average waiting time in FCFS scheduling can be calculated using the following formula:

Average Waiting Time = (Total Waiting Time for all processes) / (Number of processes)

To calculate the total waiting time for all processes, we need to know the arrival time and burst time of each process. Let's assume we have n processes with arrival time denoted by ATi and burst time denoted by BTi, where i varies from 1 to n.

To calculate the waiting time for the first process, we assume that it arrives at time 0. For subsequent processes, the waiting time can be calculated as the difference between the time the process arrives and the time it starts executing.

Let's denote the waiting time for the i-th process by WTi. Then, we can calculate the total waiting time for all processes as follows:

Total Waiting Time = (WT1 + WT2 + ... + WTn)
To calculate the waiting time for each process, we can use the following formula:

WTi = (WTi-1 + BTi-1 - ATi) if ATi <= CTi-1, where CTi-1 is the completion time of the (i-1)th process.WTi = 0 if ATi > CTi-1
Note that the waiting time for the first process is always 0.
Once we have calculated the waiting time for each process, we can calculate the average waiting time using the formula given above.

Here's the step-by-step process to calculate the average waiting time in FCFS scheduling:

Step 1: Calculate the waiting time for the first process (WT1 = 0)
Step 2: For each subsequent process i (i = 2 to n), calculate the waiting time using the formula:WTi = (WTi-1 + BTi-1 - ATi) if ATi <= CTi-1WTi = 0 if ATi > CTi-1
Step 3: Calculate the total waiting time for all processes:Total Waiting Time = (WT1 + WT2 + ... + WTn)
Step 4: Calculate the average waiting time:Average Waiting Time = (Total Waiting Time) / (Number of processes)
Note that CTi-1 is the completion time of the (i-1)th process and can be calculated as CTi-1 = ATi-1 + BTi-1.
Once you have calculated the average waiting time using the above steps, you can interpret the result as the average amount of time each process had to wait in the ready queue before it could start executing.

Real-Life Example of FCFS Scheduling

Here is a real-life example of FCFS scheduling:
Imagine you have a single printer in an office, and multiple users send their printing requests to the printer. The printer follows the FCFS scheduling algorithm and executes the print jobs in the order they arrive.

Suppose the printer receives three printing requests from three users, A, B, and C, in the following order:
User A sends a printing request at 10:00 AM.User B sends a printing request at 10:05 AM.User C sends a printing request at 10:10 AM.The printer will execute the print jobs in the order they arrive, so it will first print User A's request, then User B's, and finally User C's. This is an example of FCFS scheduling, where the first task to arrive is the first to be executed.
In the case of the printer, the FCFS scheduling algorithm ensures that all print requests are processed and printed in the order they are received, avoiding any confusion or delays in printing.

Advantages and Disadvantages of FCFS Scheduling

In FCFS scheduling, the process that arrives first is executed first, followed by the next process in the queue, and so on. Here are some advantages and disadvantages of FCFS scheduling:

Advantages of FCFS Scheduling

The main advantage of FCFS scheduling is its simplicity, which makes it easy to implement and understand. Here are some other advantages of FCFS scheduling:

Fairness: FCFS scheduling provides a fair allocation of CPU time to all processes, as it executes them in the order of their arrival. This means that no process is given preference over another.

Minimal overhead: FCFS scheduling has minimal overhead as it does not require any special data structures or bookkeeping. It simply executes processes in the order they are received.

Easy to implement: FCFS scheduling is one of the simplest scheduling algorithms to implement. It does not require complex calculations or decision-making processes.

No starvation: FCFS scheduling ensures that all processes will eventually be executed, as there is no possibility of a process being starved of CPU time indefinitely.

Low context switching: FCFS scheduling has a low context switching overhead because it is a non-preemptive algorithm. This means that once a process starts executing, it will continue to do so until it completes, or it enters a blocked state.

Disadvantages of FCFS Scheduling

FCFS scheduling has several disadvantages, including:

Convoy effect: The FCFS scheduling algorithm can lead to a convoy effect, where a long process holds the CPU, blocking the execution of shorter processes waiting in the queue behind it. This can result in poor performance and increased waiting time for other processes.

Poor utilization of resources: The FCFS scheduling algorithm may result in poor utilization of resources, as short processes may have to wait for a long process to finish, even if the CPU is idle. This can lead to inefficient use of resources and reduced system performance.

High average waiting time: The FCFS scheduling algorithm may result in a high average waiting time, particularly if there are many long processes in the system. This can make the system less responsive and reduce user satisfaction.

No priority scheduling: The FCFS scheduling algorithm does not take into account the priority of processes. This means that high-priority processes may have to wait for low-priority processes to finish, which can result in reduced system performance and increased response time.

No preemption: The FCFS scheduling algorithm does not support preemption, which means that once a process has been allocated the CPU, it will continue to execute until it completes or blocks. This can lead to increased response time for high-priority processes and reduced system performance.

First Come First Serve Algorithm Program in C

Here’s an example program for First Come First Serve (FCFS) algorithm in C:

#include <stdio.h>
// Function to find the waiting time for all processes
void findWaitingTime(int n, int bt[], int wt[])
{
// Waiting time for first process is 0
wt[0] = 0;
// Calculate waiting time for remaining processes
for (int i = 1; i < n; i++)
wt[i] = wt[i-1] + bt[i-1];
}
// Function to find the turnaround time for all processes
void findTurnAroundTime(int n, int bt[], int wt[], int tat[])
{
// Calculate turnaround time by adding bt[i] + wt[i]
for (int i = 0; i < n; i++)
tat[i] = bt[i] + wt[i];
}
// Function to calculate average time
void findAvgTime(int n, int bt[])
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Find waiting time of all processes
findWaitingTime(n, bt, wt);
// Find turnaround time of all processes
findTurnAroundTime(n, bt, wt, tat);
// Display processes along with all details
printf(“Processes Burst time Waiting time Turn around time\n”);
// Calculate total waiting time and total turnaround time
for (int i = 0; i < n; i++) {
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
printf(” %d\t\t%d\t %d\t\t %d\n”, i+1, bt[i], wt[i], tat[i]);
}
// Calculate the average waiting time and average turnaround time
printf(“\nAverage waiting time = %f”, (float)total_wt / (float)n);
printf(“\nAverage turn around time = %f”, (float)total_tat / (float)n);
}
// Main function
int main()
{
int n = 4;
int burst_time[] = { 5, 8, 2, 6 };
findAvgTime(n, burst_time);
return 0;
}
This program finds the waiting time and turnaround time for a set of processes using the FCFS scheduling algorithm. It takes the number of processes and an array of burst times for each process as input. The output is the average waiting time and average turnaround time for all the processes.