1. Home
  2. Algorithm for FCFS Scheduling

Algorithm for FCFS Scheduling

  • The waiting time for the first process is 0 as it is executed first.
  • The waiting time for the upcoming process can be calculated by:

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

where 

  • wt[i] = waiting time of current process 
  • at[i-1] = arrival time of previous process 
  • bt[i-1] = burst time of previous process 
  • wt[i-1] = waiting time of previous process 
  • at[i] = arrival time of current process 
  • The Average waiting time can be calculated by: 

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

Examples to Show Working of Non-Preemptive First come First Serve CPU Scheduling Algorithm

Example-1: Consider the following table of arrival time and burst time for five processes P1, P2, P3, P4 and P5. 

Processes        Arrival Time      Burst Time      
P1 0 4
P2 1 3
P3 2 1
P4 3 2
P5 4 5

The First come First serve CPU Scheduling Algorithm will work on the basis of steps as mentioned below:

Step 0: At time = 0,

  • The process begins with P1 
  • As it has an arrival time 0
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
0-1ms P1 0ms   1ms 4ms 3ms

Step 1: At time = 1,

  • The process P2 arrives
  • But process P1 still executing, 
  • Thus, P2 is kept on a waiting table and waits for its execution.
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
1-2ms P1 0ms   1ms 3ms 2ms
P2 1ms P2 0ms 3ms 3ms

Step 3: At time = 2,

  • The process P3 arrives and kept in a waiting queue 
  • While process P1 is still executing as its burst time is 4.
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
2-3ms P1 0ms   1ms 2ms 1ms
P2 1ms P2 0ms 3ms 3ms
P3 2ms P2, P3 0ms 1ms 1ms

Step 4: At time = 3,

  • The process P4 arrives and kept in the waiting queue 
  • While process P1 is still executing as its burst time is 4
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
3-4ms P1 0ms   1ms 1ms 0ms
P2 1ms P2 0ms 3ms 3ms
P3 2ms P2, P3 0ms 1ms 1ms
P4 3ms P2, P3, P4 0ms 2ms 2ms

Step 5: At time = 4,

  • The process P1 completes its execution 
  • Process P5 arrives in waiting queue while process P2 starts executing
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
4-5ms P2 1ms   1ms 3ms 2ms
P3 2ms P3 0ms 1ms 1ms
P4 3ms P3, P4 0ms 2ms 2ms
P5 4ms P3, P4, P5 0ms 5ms 5ms

Step 6: At time = 5,

  • The process P2 completes its execution 
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
5-7ms P2 1ms   2ms 2ms 0ms
P3 2ms P3 0ms 1ms 1ms
P4 3ms P3, P4 0ms 2ms 2ms
P5 4ms P3, P4, P5 0ms 5ms 5ms

Step 7: At time = 7,

  • Process P3 starts executing, it has burst time of 1 thus, it completes execution at time interval 8
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
7-8ms P3 2ms   1ms 1ms 0ms
P4 3ms P4 0ms 2ms 2ms
P5 4ms P4, P5 0ms 5ms 5ms

Step 8: At time 8,

  • The process of P3 completes its execution 
  • Process P4 starts executing, it has burst time of 2 thus, it completes execution at time interval 10.
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
8-10ms P4 3ms   2ms 2ms 0ms
P5 4ms P5 0ms 5ms 5ms

Step 9: At time 10,

  • The process P4 completes its execution 
  • Process P5 starts executing, it has burst time of 5 thus, it completes execution at time interval 15.
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
10-15ms P5 4ms   5ms 5ms 0ms

Step 10: At time 15,

  • Process P5 will finish its execution.
  • The overall execution of the processes will be as shown below:
Time Instance Process Arrival Time Waiting Table Execution Time Initial Burst Time Remaining Burst 
Time
0-1ms P1 0ms   1ms 4ms 3ms
1-2ms P1 0ms   1ms 3ms 2ms
P2 1ms P2 0ms 3ms 3ms
2-3ms P1 0ms   1ms 2ms 1ms
P2 1ms P2 0ms 3ms 3ms
P3 2ms P2, P3 0ms 1ms 1ms
3-4ms P1 0ms   1ms 1ms 0ms
P2 1ms P2 0ms 3ms 3ms
P3 2ms P2, P3 0ms 1ms 1ms
P4 3ms P2, P3, P4 0ms 2ms 2ms
4-5ms P2 1ms   1ms 3ms 2ms
P3 2ms P3 0ms 1ms 1ms
P4 3ms P3, P4 0ms 2ms 2ms
P5 4ms P3, P4, P5 0ms 5ms 5ms
5-7ms P2 1ms   2ms 2ms 0ms
P3 2ms P3 0ms 1ms 1ms
P4 3ms P3, P4 0ms 2ms 2ms
P5 4ms P3, P4, P5 0ms 5ms 5ms
7-8ms P3 2ms   1ms 1ms 0ms
P4 3ms P4 0ms 2ms 2ms
P5 4ms P4, P5 0ms 5ms 5ms
8-10ms P4 3ms   2ms 2ms 0ms
P5 4ms P5 0ms 5ms 5ms
10-15ms P5 4ms   5ms 5ms 0ms

Gantt Chart for Above Execution

Gantt chart for First come First serve Scheduling

Waiting Time = Start time – Arrival time

P1 = 0 – 0 = 0
P2 = 4 – 1 = 3
P3 = 7 – 2 = 5
P4 = 8 – 3 = 5
P5 = 10 – 4 = 6

Average waiting time = (0 + 3 + 5 + 5+ 6 )/ 5 = 19 / 5 = 3.8 

First Come First Serve – CPU Scheduling (Non-Preemptive)

Simplest CPU scheduling algorithm that schedules according to arrival times of processes. The first come first serve scheduling algorithm states that the process that requests the CPU first is allocated the CPU first. It is implemented by using the FIFO queue. When a process enters the ready queue, its PCB is linked to the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue. FCFS is a non-preemptive scheduling algorithm.

Similar Reads

Characteristics of FCFS

FCFS supports non-preemptive and preemptive CPU scheduling algorithms. Tasks are always executed on a First-come, First-serve concept. FCFS is easy to implement and use. This algorithm is not very efficient in performance, and the wait time is quite high....

Algorithm for FCFS Scheduling

The waiting time for the first process is 0 as it is executed first. The waiting time for the upcoming process can be calculated by:...

Program for First Come First Serve Algorithm

C++ // C++ program to Calculate Waiting // Time for given Processes #include using namespace std;   // Function to Calculate waiting time // and average waiting time void CalculateWaitingTime(int at[],                           int bt[], int N) {       // Declare the array for waiting     // time     int wt[N];       // Waiting time for first process     // is 0     wt[0] = 0;       // Print waiting time process 1     cout << "PN\t\tAT\t\t"          << "BT\t\tWT\n\n";     cout << "1"          << "\t\t" << at[0] << "\t\t"          << bt[0] << "\t\t" << wt[0] << endl;       // Calculating waiting time for     // each process from the given     // formula     for (int i = 1; i < 5; i++) {         wt[i] = (at[i - 1] + bt[i - 1]                  + wt[i - 1]) - at[i];           // Print the waiting time for         // each process         cout << i + 1 << "\t\t" << at[i]              << "\t\t" << bt[i] << "\t\t"              << wt[i] << endl;     }       // Declare variable to calculate     // average     float average;     float sum = 0;       // Loop to calculate sum of all     // waiting time     for (int i = 0; i < 5; i++) {         sum = sum + wt[i];     }       // Find average waiting time     // by dividing it by no. of process     average = sum / 5;       // Print Average Waiting Time     cout << "\nAverage waiting time = "          << average; }   // Driver code int main() {     // Number of process     int N = 5;       // Array for Arrival time     int at[] = { 0, 1, 2, 3, 4 };       // Array for Burst Time     int bt[] = { 4, 3, 1, 2, 5 };       // Function call to find     // waiting time     CalculateWaitingTime(at, bt, N);     return 0; } //this code is contributed by snehalsalokhe Java // Java program to Calculate Waiting // Time for given Processes class GFG {    // Function to Calculate waiting time // and average waiting time static void CalculateWaitingTime(int at[],                           int bt[], int N) {        // Declare the array for waiting     // time     int []wt = new int[N];        // Waiting time for first process     // is 0     wt[0] = 0;        // Print waiting time process 1     System.out.print("P.No.\tArrival Time\t"         + "Burst Time\tWaiting Time\n");     System.out.print("1"         + "\t\t" +  at[0]+ "\t\t"          + bt[0]+ "\t\t" +  wt[0] +"\n");        // Calculating waiting time for     // each process from the given     // formula     for (int i = 1; i < 5; i++) {         wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];            // Print the waiting time for         // each process         System.out.print(i + 1+ "\t\t" +  at[i]             + "\t\t" +  bt[i]+ "\t\t"              + wt[i] +"\n");     }        // Declare variable to calculate     // average     float average;     float sum = 0;        // Loop to calculate sum of all     // waiting time     for (int i = 0; i < 5; i++) {         sum = sum + wt[i];     }        // Find average waiting time     // by dividing it by no. of process     average = sum / 5;        // Print Average Waiting Time     System.out.print("Average waiting time = "          + average); }    // Driver code public static void main(String[] args) {     // Number of process     int N = 5;        // Array for Arrival time     int at[] = { 0, 1, 2, 3, 4 };        // Array for Burst Time     int bt[] = { 4, 3, 1, 2, 5 };        // Function call to find     // waiting time     CalculateWaitingTime(at, bt, N); } }   // This code is contributed by 29AjayKumar Python3 # Python3 program to Calculate Waiting # Time for given Processes   # Function to Calculate waiting time # and average waiting time def CalculateWaitingTime(at, bt, N):       # Declare the array for waiting     # time     wt = [0]*N;       # Waiting time for first process     # is 0     wt[0] = 0;       # Print waiting time process 1     print("P.No.\tArrival Time\t" , "Burst Time\tWaiting Time");     print("1" , "\t\t" , at[0] , "\t\t" , bt[0] , "\t\t" , wt[0]);       # Calculating waiting time for     # each process from the given     # formula     for i in range(1,5):         wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];           # Print the waiting time for         # each process         print(i + 1 , "\t\t" , at[i] , "\t\t" , bt[i] , "\t\t" , wt[i]);             # Declare variable to calculate     # average     average = 0.0;     sum = 0;       # Loop to calculate sum of all     # waiting time     for i in range(5):         sum = sum + wt[i];           # Find average waiting time     # by dividing it by no. of process     average = sum / 5;       # Print Average Waiting Time     print("Average waiting time = " , average);     # Driver code if __name__ == '__main__':     # Number of process     N = 5;       # Array for Arrival time     at = [ 0, 1, 2, 3, 4 ];       # Array for Burst Time     bt = [ 4, 3, 1, 2, 5 ];       # Function call to find     # waiting time     CalculateWaitingTime(at, bt, N);   # This code is contributed by 29AjayKumar C# // C# program to Calculate Waiting // Time for given Processes using System;   class GFG {     // Function to Calculate waiting time // and average waiting time static void CalculateWaitingTime(int []at,                           int []bt, int N) {         // Declare the array for waiting     // time     int []wt = new int[N];         // Waiting time for first process     // is 0     wt[0] = 0;         // Print waiting time process 1     Console.Write("P.No.\tArrival Time\t"         + "Burst Time\tWaiting Time\n");     Console.Write("1"         + "\t\t" +  at[0]+ "\t\t"          + bt[0]+ "\t\t" +  wt[0] +"\n");         // Calculating waiting time for     // each process from the given     // formula     for (int i = 1; i < 5; i++) {         wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];             // Print the waiting time for         // each process         Console.Write(i + 1+ "\t\t" +  at[i]             + "\t\t" +  bt[i]+ "\t\t"              + wt[i] +"\n");     }         // Declare variable to calculate     // average     float average;     float sum = 0;         // Loop to calculate sum of all     // waiting time     for (int i = 0; i < 5; i++) {         sum = sum + wt[i];     }         // Find average waiting time     // by dividing it by no. of process     average = sum / 5;         // Print Average Waiting Time     Console.Write("Average waiting time = "          + average); }     // Driver code public static void Main(String[] args) {     // Number of process     int N = 5;         // Array for Arrival time     int []at = { 0, 1, 2, 3, 4 };         // Array for Burst Time     int []bt = { 4, 3, 1, 2, 5 };         // Function call to find     // waiting time     CalculateWaitingTime(at, bt, N); } }   // This code is contributed by 29AjayKumar Javascript // Function to calculate waiting time and average waiting time function calculateWaitingTime(at, bt, n) {   // Declare the array for waiting time   let wt = new Array(n);     // Waiting time for first process is 0   wt[0] = 0;     // Print waiting time for process 1   console.log("PN\t\tAT\t\tBT\t\tWT\n\n");   console.log(`1\t\t${at[0]}\t\t${bt[0]}\t\t${wt[0]}\n`);     // Calculate waiting time for each process from the given formula   for (let i = 1; i < n; i++) {     wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];       // Print the waiting time for each process     console.log(`${i + 1}\t\t${at[i]}\t\t${bt[i]}\t\t${wt[i]}\n`);   }     // Declare variable to calculate average   let average;   let sum = 0;     // Loop to calculate sum of all waiting time   for (let i = 0; i < n; i++) {     sum = sum + wt[i];   }     // Find average waiting time by dividing it by no. of process   average = sum / n;     // Print Average Waiting Time   console.log(`\nAverage waiting time = ${average}`); }   // Driver code function main() {   // Number of processes   let n = 5;     // Array for arrival time   let at = [0, 1, 2, 3, 4];     // Array for burst time   let bt = [4, 3, 1, 2, 5];     // Function call to find waiting time   calculateWaitingTime(at, bt, n); }   // Call the main function main();...

Advantages of FCFS

...

Disadvantages of FCFS

...

Categories

HTML CSS3 Bootstrap Foundation Sass JavaScript TypeScript JQuery AngularJS React NodeJS Highcharts PHP Python Python3 Django Linux Docker Ruby Java C C ++ Perl Servlet JSP Lua Scala Go ASP C # SQL MySQL SQLite MongoDB Redis Android Swift ionic Kotlin XML tutorial

Contact US