CPU Scheduling Algorithms| First Come First Serve (FCFS)

CPU Scheduling: CPU scheduling is a process that allows one process to use the CPU while the execution of another process is on hold (in waiting state) due to unavailability of any resource like I/O(Input Output) etc. thereby making full use of CPU.
- The aim of CPU scheduling is to make the system efficient, fast, and fair.
There are different types of time-related to CPU scheduling. Before going to look at that algorithm let first see some of the terms that need to know before the algorithm.
Arrival time:
- Arrival time is the time at which the process enters the ready queue or state.
- Arrival time is a particular point of time.
Burst time:
- Burst time is the time required by a process to get executed on the CPU.
- It is the time duration ( how much time it takes to execute, it is process execution time ) not the point of time.
Completion time:
- Completion time is the time at which the process completes its execution.
- Completion time is a particular point of time.
- It is time when the process finishes its job.
Turnaround time:
- The total time taken by the process to get completely executed is known as turnaround time.
- Turnaround time = Completion time - Arrival time.
- It time duration not point of time.
Waiting time:
- Waiting time is the time duration at which the process was ideal and was not executing.
- Waiting time = Turnaround time - Burst time.
- It is time duration not the point of time.
Response time:
- How much time the CPU responded to a process after its arrival in the CPU is known as response time.
- Response time = The time at which process gets CPU first time - Arrival time.
Now we will see the different algorithm
First Come First Serve (FCFS)
- As the name suggests it is related to arrival time of the process, which means that the process comes first will be executed first.
- Mode is non pre-emptive which means that, if a process comes into running state from ready state, it will not be sent back to the ready state it will be executed completely and terminated.
- First Come First Serve, is just like FIFO(First in First out) Queue data structure, where the data element which is added to the queue first, is the one who leaves the queue first.
- This is used in Batch Systems.
- It's easy to understand and implement programmatically, using a Queue data structure, where a new process enters through the tail of the queue, and the scheduler selects process from the head of the queue.
- A perfect real life example of FCFS scheduling is buying tickets at ticket counter.
- Calculating Average Waiting Time:
  - For every scheduling algorithm, Average waiting time is a crucial parameter to judge it's performance.
  - AWT or Average waiting time is the average of the waiting times of the processes in the queue, waiting for the scheduler to pick them for execution.
  - Lower the Average Waiting Time, better the scheduling algorithm.
  - Consider the processes P1, P2, P3, P4 given in the below table, arrives for execution in the same order, with Arrival Time 0, and given Burst Time, let's find the average waiting time using the FCFS scheduling algorithm.

The average waiting time will be 18.75 ms
For the above given processes, first P1 will be provided with the CPU resources,
Hence, waiting time for P1 will be 0
P1 requires 21 ms for completion, hence waiting time for P2 will be 21 ms
Similarly, waiting time for process P3 will be execution time of P1 + execution time for P2, which will be (21 + 3) ms = 24 ms.
For process P4 it will be the sum of execution times of P1, P2 and P3.
The GANTT chart above perfectly represents the waiting time for each process.

Problems with FCFS Scheduling

Below we have a few shortcomings or problems with the FCFS scheduling algorithm:
- It is Non-Pre-emptive algorithm, which means the process priority doesn't matter. If a process with the very least priority is being executed, more like a daily routine backup process, which takes more time, and all of a sudden some other high priority process arrives, like interrupt to avoid system crash, the high priority process will have to wait, and hence, in this case, the system will crash, just because of improper process scheduling.
- Not optimal Average Waiting Time.
- Resources utilization in parallel is not possible, which leads to Convoy Effect, and hence poor resource(CPU, I/O, etc) utilization.
What is Convoy Effect?
- Convoy Effect is a situation where many processes, who need to use a resource for short time are blocked by one process holding that resource for a long time.
- This essentially leads to poor utilization of resources and hence poor performance.

Program for FCFS Scheduling

Here we have a simple C++ program for processes with an arrival time as 0.
In the program, we will be calculating the Average waiting time and Average turnaround time for a given array of Burst times for the list of processes.

 /* Simple C++ program for implementation 
 of FCFS scheduling */

 #include<iostream>

 using namespace std;

 // function to find the waiting time for all processes
 void findWaitingTime(int processes[], int n, int bt[], int wt[])
 {
    // waiting time for first process will be 0
    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
 void findTurnAroundTime( int processes[], int n, int bt[], int wt[], int tat[])
 {
    // calculating 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 findAverageTime( int processes[], int n, int bt[])
 {
    int wt[n], tat[n], total_wt = 0, total_tat = 0;

    // function to find waiting time of all processes
    findWaitingTime(processes, n, bt, wt);

    // function to find turn around time for all processes
    findTurnAroundTime(processes, n, bt, wt, tat);

    // display processes along with all details
    cout << "Processes  "<< " Burst time  "<< " Waiting time  " << " Turn around time\n";

    // calculate total waiting time and total turn around time
    for (int i = 0; i < n; i++)
    {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << "   " << i+1 << "\t\t" << bt[i] <<"\t    "<< wt[i] <<"\t\t  " << tat[i] <<endl;
    }

    cout << "Average waiting time = "<< (float)total_wt / (float)n;
    cout << "\nAverage turn around time = "<< (float)total_tat / (float)n;
 }

 // main function
 int main()
 {
    // process ids
    int processes[] = { 1, 2, 3, 4};
    int n = sizeof processes / sizeof processes[0];

    // burst time of all processes
    int  burst_time[] = {21, 3, 6, 2};

    findAverageTime(processes, n,  burst_time);

    return 0;
 }

Output:

 - Processes Burst time Waiting time Turn around time
   1 21 0 21
   2 3 21 24
   3 6 24 30
   4 2 30 32
- Average waiting time = 18.75
- Average turn around time = 26.75

We will see another algorithm also I like to hear your feedback and suggestion.

CPU Scheduling Algorithms| First Come First Serve (FCFS) | Operating System EP-13

Problems with FCFS Scheduling

Program for FCFS Scheduling