Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Medium

Program for First Come First Serve Scheduling

gp-icon
Operating system track
Free guided path
14 chapters
83+ problems
gp-badge
Earn badges and level up

Introduction

A CPU scheduling algorithm allocates resources (CPU cores) to different processes in the ready queue in an optimal way so that the CPU executes every process. 

FCFS Code

The two main types of scheduling algorithms are preemptive and non-preemptive. First Come First Serve uses a non-preemptive algorithm to efficiently schedule processes, which moves processes based on arrival times.

Terms in First Come First Serve Scheduling

Before moving to the program for first come first serve let's discuss some of the basic terms of FCFS:

Arrival Time

The arrival time helps the First come First serve (FCFS) scheduling algorithm to schedule the process or jobs. The task with minimum arrival time appears in the ready queue first. The task that appears first in the ready queue will receive CPU processing first. The task with minimum arrival time will receive the CPU more quickly. 

Waiting Time

The period of waiting before a procedure can start the execution process. The process stays in the queue and waits to be executed.

Completion Time

The completion time determines the time taken to complete the execution. The completion time is measured from the arrival time until the completion of the respective process.

Turnaround Time

Turnaround time is the amount of time it takes for a task to arrive in the ready queue for the first to its execution. It is calculated as the difference between the completion time and the arrival time of the process.

Burst Time

The Burst Time is the overall amount of time the CPU needs to complete the entire process. It is a pre-defined value for scheduling a process.

Time Quantum

For a specific period of time, the CPU is allotted to the task based on FCFS. That fixed amount of time is known as time quantum.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

What is First Come First Serve (FCFS)?

FCFS is often referred to as the First In First Out (FIFO) scheduling algorithm, the easiest and simplest CPU scheduling algorithm in which the first process in the ready queue is executed first. A new process will begin executing when the CPU has fully executed the current process.

How to Compute the below times in Round-robin using a Program?

To compute the below times in Round-robin using a Program are:-

  • Completion Time: The time taken to complete the execution of a process.
    Completion time = Arrival Time + Turnaround time
     
  • Turnaround Time: Turnaround time is the amount of time it takes for a task to arrive in the ready queue, it can be calculated as follows:
    Turnaround time = Completion Time - Arrival Time.
     
  • Waiting Time: The waiting time is the period of waiting before a procedure can start the execution process.
    Waiting Time = Turn Around Time - Burst Time.

FCFS Algorithm

We  will discuss the FCFS algorithm in two cases:

  • When the processes have the same arrival time.
     
  • When the processes have different arrival times.

Same Arrival Time

  • Enter the number of processes and burst time.
     
  • Calculate the waiting time of all processes. Such that wt[i] = bt[i - 1] + wt[i - 1]; 
     
  • Add the burst time and the waiting time to find the Turn Around Time for each process.
     
  • Finally, find the average turnaround time and average waiting time.

Different Arrival Time

  • Enter the number of processes, arrival time, and burst time.
     
  • Calculate the waiting time of all processes. 

    In order to store the preceding process' burst time in an array, use the formulas p_bt[i+1]=p_bt[i]+bt[i] and wt[i]=temp[i]-at[i] to determine each process' burst time, respectively.
     
  • Add the burst time and the waiting time to find the Turn Around Time for each process.
     
  • Finally, find the average turnaround time and average waiting time.

Implementation of First Come First Serve CPU Scheduling

Before jumping into the implementation, let's know some terms and formulas for FCFS (First Come First Serve) Scheduling.

Burst Time

In CPU terms, burst time is the amount of time it takes a process to complete its execution.

Waiting Time

The total amount of time a process has to wait before executing.

Turnaround time

The amount of time it takes after arrival to complete the process. In simple words, it is the difference between the completion time and the arrival time.

Completion Time

The completion time is measured from arrival until the end of the execution.

We can calculate different times for various processes with the simple formulas given below:

  • Waiting Time = Turn Around Time - Burst Time.
  • Turnaround time: Burst time + Waiting time
  • Completion time = Total Turnaround Time + Total Arrival Time

 

We will split our implementation into two parts depending on whether the processes have the same or different arrival times.

Try out Program for First Come First Serve Scheduling before moving towards the implementation.

When Processes have the Same Arrival Time

Step 1: Enter the number of processes to execute along with their burst time (bt) and arrive.
Step 2: Now, create a function that will calculate the waiting time (wt) for every process.
As the process is already in the ready queue hence the waiting time of process 1 will be 0, i.e. wt[0] = 0.
Step 3: Find the waiting time for all other processes.
wt[i] = bt[i - 1] + wt[i - 1]; (calculating the burst time of each process)
Step 4: Find Turn Around Time(tt) for each process by adding the burst time and the waiting time.
tt[i] = bt[i] + wt[i];
Step 5: Invoke the function which will calculate the average waiting(awt) and average turnaround time(awt) i.e avg_wt_tt ().
awt = awt/n;
att = att/n;

Implementation in JAVA

  • Java

Java

import java.util.Scanner;


public class Example1 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
System.out.print("Enter the number of processes: "); //Entering the number of processes
       
int n = sc.nextInt();
int bt[] = new int[20]; //Initializing an array for storing Burst Time

System.out.println("\nEnter the Burst Time for each process.");       
for (int i = 0; i < n; i++) {
System.out.print("\nFor Process " + (i + 1) + ":");
bt[i] = sc.nextInt();       
}

avg_wt_tt(n, bt); //Invoking the function to calculate the average waiting and turnaround times.
}

//function to calculate Waiting Time for each process
private static void waiting_time(int n, int[] bt, int[] wt) {       
wt[0] = 0;
// calculating waiting time

for (int i = 1; i < n; i++) {           
wt[i] = bt[i - 1] + wt[i - 1];       
}
}

//function to calculate Turn Around Time
private static void turnaround_time(int n, int[] bt, int[] wt, int[] tt) {       
for (int i = 0; i < n; i++) {           
tt[i] = bt[i] + wt[i]; //Calculating turn around time
}   
}

//function to calculate average waiting time and average turn around time.   
private static void avg_wt_tt(int n, int[] bt) {       
int wt[] = new int[n];       
int tt[] = new int[n];

// Invoking the function for waiting time
waiting_time(n, bt, wt);

// Invoking the function for turn around time
turnaround_time(n, bt, wt, tt);

//Displaying the headings
System.out.println("\nProcesses ||" + " Burst Time ||" + " Arrival Time ||" + " Waiting Time ||" + " Turn-Around Time ");

float awt = 0;
float att = 0;

for (int i = 0; i < n; i++) {           
awt = awt + wt[i]; //Calculating the total waiting time for all processes
att = att + tt[i]; //Calculating the total turn around time for all processes

//Displaying all the details
System.out.println(i + 1 + "\t  ||\t" + bt[i] + "\t||\t" + "\t||\t" + wt[i] + "\t||\t " + tt[i]);       
}
       
awt = awt / n; //Calculating average waiting time
att = att / n; //Calculating average turn around time

System.out.println("\nAverage waiting time = " + awt);       
System.out.println("\nAverage turn around time = " + att);   
}
}

Input:

Enter the number of processes: 4
Enter the Burst Time for each process.
For Process 1:5
For Process 2:4
For Process 3:1
For Process 4:3
Implementation in Java

Output:

Processes || Burst Time || Waiting Time || Turn-Around Time 
1                ||        5         ||        0             || 5
2                ||        4         ||        5             || 9
3                ||        1         ||        9             || 10
4                ||        3         ||       10            || 13
Average waiting time = 6.0
Average turnaround time = 9.25


Also see: Multiprogramming vs Multitasking

When the processes have Different Arrival Time 

Step 1: Enter the number of processes to execute along with their burst time (bt) and arrival time (at).
Step 2: Now, create a function that will calculate the waiting time (wt) for every process.
As the process is already in the ready queue hence the waiting time of process 1 will be 0, i.e. wt[0] = 0.
Step 3: Find the waiting time for all other processes.
p_bt[i+1]=p_bt[i]+bt[i]; (for storing the burst time of the previous process in an array p_bt [ ] process)
wt[i]=temp[i]-at[i]; (calculating the burst time of each process))
Step 4: Find Turn Around Time(tt) for each process by adding the burst time and the waiting time.
tt[i] = bt[i] + wt[i];
Step 5: Invoke the function which will calculate the average waiting(awt) and average turnaround time(att) i.e avg_wt_tt ().
awt = awt/n;
att = att/n;

Implementation in JAVA

  • Java

Java

import java.util.Scanner;


public class Example {

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);

       //Entering the number of processes
       System.out.print("Enter the number of processes: ");
       int n = sc.nextInt();

       //Initializing an array for storing Burst Time
       int bt[] = new int[20];
       //Initializing an array for storing Arrival Time
       int at[] = new int[20];

       System.out.println("\nEnter the Burst Time for each process.");
       for (int i = 0; i < n; i++) {
           System.out.print("\nFor Process " + (i + 1) + ":");
           bt[i] = sc.nextInt();
       }

       System.out.println("\nEnter the arrival time for each process.");
       for (int j = 0; j < n; j++) {
           System.out.print("\nFor Process " + (j + 1) + ":");
           at[j] = sc.nextInt();
       }

       //Invoking the function to calculate the average waiting and turnaround times.
       avg_wt_tt(n, bt, at);
   }

   //function to calculate Waiting Time for each process
   private static void waiting_time(int n, int[] bt, int[] wt, int[] at) {
       //To store the burst time of previous process.
       int temp[] = new int[20];
       temp[0] = 0;
       
       for (int i = 0; i < n; i++) {
           wt[i] = 0;
           temp[i + 1] = temp[i] + bt[i];

           //Calculating waiting time
           wt[i] = temp[i] - at[i];
       }
   }

   //function to calculate Turn Around Time
   private static void turnaround_time(int n, int[] bt, int[] wt, int[] tt) {
       for (int i = 0; i < n; i++) {
           //Calculating turn around time
           tt[i] = bt[i] + wt[i];
       }
   }

   //function to calculate average waiting time and average turn around time.
   private static void avg_wt_tt(int n, int[] bt, int[] at) {
       int wt[] = new int[n];
       int tt[] = new int[n];

       // Invoking the function for waiting time
       waiting_time(n, bt, wt, at);

       // Invoking the function for turn around time
       turnaround_time(n, bt, wt, tt);

       //Displaying the headings
       System.out.println("\nProcesses ||" + " Burst Time ||" + " Arrival Time ||" + " Waiting Time ||" + " Turn-Around Time ");

       float awt = 0;
       float att = 0;

       for (int i = 0; i < n; i++) {
           //Calculating the total waiting time for all processes
           awt = awt + wt[i];

           //Calculating the total turn around time for all processes
           att = att + tt[i];

           //Displaying all the details
           System.out.println(i + 1 + "\t  ||\t" + bt[i] + "\t||\t" + at[i] + "\t||\t" + wt[i] + "\t||\t " + tt[i]);
       }

       //Calculating average waiting time
       awt = awt / n;
       //Calculating average turn around time
       att = att / n;

       System.out.println("\nAverage waiting time = " + awt);
       System.out.println("\nAverage turn around time = " + att);
   }
}

Input:

Enter the number of processes: 4
Enter the Burst Time for each process.
For Process 1:4
For Process 2:5
For Process 3:3
For Process 4:1
Enter the arrival time for each process.
For Process 1:0
For Process 2:3
For Process 3:1
For Process 4:2
Implementation in Java

Output:

Processes || Burst Time || Arrival Time || Waiting Time || Turn-Around Time 
1                ||        4         ||       0            ||        0            ||        4
2                ||        5         ||       3            ||        1            ||        6
3                ||        3         ||       1            ||        8            ||        11
4                ||        1         ||       2            ||        10          ||         11
Average waiting time = 4.75
Average turnaround time = 8.0

 

You can also read about layered structure of operating system.

Characteristics of FCFS CPU Process Scheduling

First-Come-First-Serve (FCFS) is a simple CPU process scheduling algorithm with the following characteristics:

  • Processes are scheduled based on their arrival order. The first process to arrive is the first to be executed.
  • Once a process starts its execution, it continues until completion. It cannot be interrupted or preempted by the operating system.
  • Processes are maintained in a queue, and the CPU serves them in a First-In-First-Out manner. The process at the front of the queue is the first to be executed.
  • FCFS has low scheduling overhead as it doesn't involve complex priority decisions. It follows a straightforward principle of serving processes in the order they arrive.
  • Since every process gets its turn in the queue, there's no starvation. Even if a process has a long burst time, it will eventually get CPU time.

Advantages of the FCFS Algorithm

The FCFS algorithm offers the following advantages:

  • A queue Data Structure can be used to implement it and easily.
  • There is no starvation involved.

Disadvantages of the FCFS Algorithm

There are two major disadvantages to FCFS:

  • According to this algorithm, the Average Waiting Time is much longer than that of other CPU Scheduling algorithms.
  • Using FCFS, you can lock resources until a process has been completed.

 

As a result, processes located at the end of the ready queue with low burst/execution times wait more due to the high burst/execution time found at the start of the queue, commonly known as "starvation." FCFS does not allow resource utilization in parallel.

The algorithm is not ideal for scheduling processes.

Must Read Evolution of Operating System

Frequently Asked Questions

What is the algorithm of FCFS scheduling?

FCFS (First-Come-First-Serve) scheduling follows a simple algorithm where processes are executed in the order of their arrival without preemption.

What is FIFO scheduling?

FIFO (First-In-First-Out) scheduling, often used interchangeably with FCFS, refers to a queue-based scheduling approach where the first item in is the first one out.

What is the FCFS algorithm particularly?

The FCFS algorithm schedules processes based on their arrival order. The first process to arrive is the first to be executed, without interruption until completion.

Conclusion

The Operating System uses this scheduling algorithm to process queued requests in the order they arrive automatically. It supports both non-preemptive and preemptive scheduling algorithms. The CPU is not released before executing the process using this scheduling algorithm. After the process has been allocated to the CPU, it cannot be released until it has been completed executing.

Recommended Readings: 


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Shortest Remaining Time First Scheduling Algorithm
Next article
Convoy Effect in Operating System
Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass