Program for First Come First Serve Scheduling

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

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

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

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

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: 

• Types of Operating Systems
• Multiuser Operating Systems
• Features of Operating Systems
• CPU Scheduling
• Shortest Job First Scheduling
• Kadane's Algorithm
• Java
• Open Source Operating System
• scheduling algorithms in operating system
• Multiprocessing in Operating System

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.