First Come First Serve (FCFS) Scheduling Algorithm in Operating System

A computer executes a lot of processes simultaneously. There are multiple techniques put in place to maintain the order in which activity gets processed first. A simple scheduling technique used is the FCFS scheduling algorithm.

In this tutorial, I will explain the FCFS scheduling algorithm in OS in detail. But first, let us define FCFS scheduling in OS.

In the FCFS scheduling algorithm, to explain in easy terms, the CPU executes the processes based on their time of arrival. The CPU executes them one by one until the processes finish. FCFS scheduling algorithm is not biased, it does not prioritize any process over the other. FCFS scheduling algorithm does not segregate processes on any basis.

What is the First Come First Serve Scheduling Algorithm

To explain the concept of the FCFS algorithm in a way you can relate, let me talk about a real-life example and compare it with a first come first serve example.

Take a bank teller as an example. 

People queue up in a line and present their queries one by one. The bank teller then processes each customer one by one maintaining the order of the queue. Supposing there is no VIP list, the line is not broken and then people who come first get their queries sorted first.

Similarly, in the case of First Come First Serve scheduling, processes queue up one by one and the CPU(Central Processing Unit) processes them in order. The processes are not ranked by importance or priority in this case and thus, the processes in the queue are processed on the first in first out method.

Key Features of FCFS Scheduling Algorithm

Let me share the key features of the FCFS algorithm. This should clear some of your doubts regarding the topic.

FIFO in nature

FCFS(First Come First Serve) as the name suggests is FIFO or first in first out in nature. This means the process that enters first in the queue is executed first by the computer.

Easy to implement

FCFS in the operating system is simple to develop since it only requires minimum logic to select the next process for execution. Processes are processed in the order they arrive, simplifying the scheduling procedure.

Non-preemptive

Once a process begins, it runs until it either completes its CPU burst or becomes blocked. The CPU is not preempted from an existing process in FCFS in operating system.

Convoy effect

FCFS scheduling may cause the convoy effect, in which short processes become stuck behind large processes. If a long CPU-bound process arrives first, shorter processes in the queue may face increased wait times, resulting in inefficient CPU utilization and potentially longer turnaround times for some processes.

Important Terms to Keep In Mind

Before we know more about the inner workings of the FCFS scheduling algorithm, you should know some keywords to understand the concepts better. Here I will elaborate on those keywords.

wt[i]: Waiting time for the current process (i). This shows the amount of time the process must wait before it may begin executing on the CPU.

at[i-1]: The arrival time of the previous process (i-1). This is the moment when the previous process arrives in the ready queue or enters the system.

bt[i-1]: The burst time of the previous process (i-1). Burst time is the period of time it takes for a process to finish its execution after it begins to execute on the CPU.

wt[i-1]: Waiting time for the previous process (i-1). This is the waiting time of the process that was in the system before the current one arrived.

at[i]: Arrival time for the current procedure (i). This refers to the time at which the current process enters the ready queue.

tat[i]: Turnaround time is the total time taken from when a process arrives and gets completed.

These variables are often used in scheduling algorithms to calculate waiting times and make decisions about process execution order based on factors like arrival and burst times. 

FCFS Algorithm

Now let me explain how exactly first come first serve scheduling works with the help of an FCFS scheduling example.

Below is a table given to visualize a program for FCFS CPU scheduling.

The arrival time indicates when each process enters the ready queue, but the burst time specifies how much CPU time each process requires to complete its execution.

Step 1

Initially, the system is empty and no processes are running. The CPU is doing no work.

Step 2 - Processes start arriving

Now, one by one, processes start arriving according to their arrival times.

• When time is t = 0, process p1 arrives.
• When time is t = 1, process p2 arrives.
• When time is t = 2, process p3 arrives.
• When time is t = 3, process p4 arrives.
  

Step 3 - Processes start getting executed

Meanwhile, processes start getting executed according to their order. As the FCFS scheduling algorithm follows a first come first serve, processes are executed according to their arrival times.

• When time is t=0, p1 starts getting executed and keeps the CPU busy for t=2. This is because the burst time needed by 1 to execute is 2 as mentioned in the above diagram.
  

• When time is t=2, p1 gets completed and p2 arrives for execution.
  

• When time is t=6, p2 gets executed as p2 takes a burst time of 4. After p2 is completed, p3 arrives.
  

• When time is t=11, p3 gets executed as p3 has a burst time of 5. After p3 gets executed, p4 arrives.
  

• When time is t=18, p4 gets executed.
  

Step 4 - Completion

All processes have been completed, and the CPU is idle.

Calculating waiting time

We can calculate the wait times for each process. The waiting time for a process is the entire amount of time it spends in the ready queue before beginning to execute.

The formula for calculating wt(Wait Time) is given by:

wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i]

Calculating Average Wait Time

We can also calculate the average waiting time. The formula for average waiting time is:

Average Waiting Time = (sum of all waiting time)/(Number of processes)

As the name suggests, the average wait time is the average time taken for a process to wait upon arrival until it gets called for processing.

Advantages of FCFS Scheduling Algorithm

Here I will discuss some of the advantages of using First Come First Serve scheduling.

Predictable behaviour

FCFS scheduling displays consistent behavior, with the order of execution determined only by the arrival sequence of processes. This predictability might be useful in real-time or embedded systems when determinism is required for system dependability and performance.

Simple to implement

FCFS scheduling is simple to construct, with minimal logic and overhead. This simplicity makes it simple to learn and implement, particularly in systems with limited resources or where complexity must be reduced.

Easy to manage

FCFS scheduling can effectively manage I/O(Input-Output) operations without excessive overhead in systems where CPU-bound processes are dominating or where I/O operations are few and short. Because processes normally run to completion without preemption, I/O activities can be handled efficiently while processes are in the waiting state.

Minimal idle time

Processes are performed in the order they come, therefore there is no prospect of endless postponement or idle time for any process in the ready queue. Every process finally has its turn to run, guaranteeing equitable resource allocation.

No overhead complexity

FCFS scheduling eliminates the overhead associated with more complex scheduling techniques, such as maintaining priority queues, calculating dynamic priorities, and estimating process runtimes. FCFS can be a good option in situations when simplicity is more important than optimization.

Dedicated FCFS scheduling calculator

An advantage of the FCFS scheduling algorithm is the availability of a dedicated calculators. An  FCFS scheduling calculator is a specialized tool or software application designed to simulate and analyze its performance. These calculators empower users to input parameters like arrival times, burst times, and process priorities, facilitating the computation of scheduling orders and key performance metrics such as turnaround time, waiting time, and response time. 

Disadvantages of FCFS Scheduling Algorithm

Now let us discuss some of the disadvantages of FCFS scheduling.

Lack of process priority 

FCFS scheduling does not consider the priority or importance of processes. Critical procedures may be pushed behind less important ones, compromising system responsiveness or meeting service-level agreements.

Poor responsiveness

Because FCFS scheduling is non-preemptive, once a process begins, it continues until it completes or becomes blocked. This absence of preemption can contribute to decreased system responsiveness, particularly in contexts where short interactive tasks must be prioritized.

Lack of process burst time optimization 

When making scheduling decisions, the FCFS scheduling algorithm does not take into account the length of CPU bursts or process execution times. Short operations may be delayed in favor of longer ones, resulting in inefficient CPU resource use and potentially longer average wait times.

Deadlocks and livelocks 

While the FCFS scheduling algorithm does not directly cause livelock or deadlock situations, a lack of prioritization or resource allocation optimization might escalate such problems in systems with complex resource dependencies or shared resources.

Convoy effect

One of the most notable disadvantages of the FCFS scheduling algorithm is the convoy effect, in which shorter operations are delayed behind larger ones. If a long-running CPU-bound activity arrives first, shorter processes may face increased wait periods, resulting in inefficient CPU utilization and slower response times for some processes.

FCFS scheduling, though simple, may not suit environments needing efficient resource usage, timely execution, and optimal process management due to its constraints.

Wrapping Up

All in all, the FCFS scheduling algorithm is a relatively simple algorithm that executes processes one by one in order. Although it is easy to implement, it is not used in present operating systems much. Nowadays we use sophisticated and complex scheduling methods like Round-Robin, SJF(Shortest Job First), or Priority Scheduling for operating systems. 

Learning newer and more complex scheduling processes like FCFS in OS may sound daunting and thus checking out certified courses from upGrad might be of help. The courses offered by upGrad are in collaboration with some of the best universities around the world.

Frequently Asked Questions

1. What is the FCFS scheduling algorithm?

The FCFS scheduling algorithm is a simple process used to determine which process will be executed first based on their arrival. 

2. How does FCFS scheduling work?

This algorithm executes processes in the order that they appear in the ready queue. When a process enters the system, it moves to the end of the queue.

3. What are the advantages of FCFS scheduling?

Some of the advantages of first-come first-serve scheduling are simple implementation, low overhead, and predictable behavior.

4. What are the disadvantages of FCFS scheduling?

There are a lot of disadvantages to FCFS scheduling in OS. Some are the convoy effect, lack of process priority, inefficiency, and poor turnaround time.

5. When is FCFS scheduling used?

FCFS  scheduling algorithm is commonly used in situations where simplicity takes priority over efficiency. It is commonly used in systems that have predictable workloads.

6. Can FCFS scheduling lead to starvation?

No, FCFS scheduling can not lead to starvation as there is a process in the queue continuously. The only exception is if a process takes indefinitely long.

7. How is the turnaround time calculated in FCFS scheduling?

Turnaround time is calculated with the formula: Turnaround time = Completion time - Arrival time

8. Is FCFS preemptive or non-preemptive?

The first-come-first-serve scheduling algorithm is non-preemptive in nature.