First Come First Serve (FCFS) Scheduling Algorithm

First Come First Serve (FCFS) is the simplest CPU scheduling algorithm where the process that arrives first in the ready queue will be serviced first by CPU. Secondly, the FCFS is a non-preemptive scheduling algorithm in which once the process is allotted the CPU cycles it releases CPU when the process terminates or if it requests I/O.

We can understand it with an example, people standing in a line at a ticket counter, the person who is first in the line will buy the ticket first. Likewise, the process arriving first will be serviced first by CPU.

FCFS is a Batch System algorithm in which the user doesn’t expect a quick reply from the system. Batch system accepts the algorithms that serve process with the long-time period.

Further, we will discuss how the FCFS algorithm schedules the processes in the CPU.

Contents: First Come First Serve (FCFS) Scheduling Algorithm

1. Working
2. Computation
3. Convoy Effect
4. Advantages
5. Disadvantages
6. Key Takeaways

Working

In the table below you can see we have 4 processes p1, p2, p3, p4 along with their arrival time and their burst time.

Processes	Arrival Time	Burst Time
P1	0	5
P2	3	24
P3	5	3
P4	8	20

Here, the arrival time is not the real-time of the system it is the relative time of the system. Arrival time is the time at which the process arrives in the ready queue, lower the time, earlier is the process arrives. With reference to the arrival time given in the table, the processes arrive in the order p1, p2, p3, p4.

Burst time is the time required by the process to complete its execution. There are two types of burst time CPU burst and I/O burst. CPU burst is the time required by the process to utilize CPU cycles. I/O burst is the time required by the process to utilize I/O devices. Consider the Burst time given in the table is CPU burst time and is in milliseconds. We have no I/O bursts here.

Now let us serve the processes in the First-Come-First-Serve order using the Gantt Chart.

Observe the Gantt Chart and table above, the process P1 arrives at 0 millisecond i.e. earlier than any other process in the ready queue. So P1 doesn’t have to wait (waiting time=0) and is allotted the CPU first. Now P1 requires 5 milliseconds to execute meanwhile process P2 has arrived in ready queue, but P2 has to wait till P1 is completely executed because of non-preemptive nature of this scheduling algorithm (waiting time P2 = 2 milliseconds).

While P2 is performing its execution both the remaining process P3 and P4 arrive in the ready queue. Process P3 gets chance to execute at 29^th millisecond (waiting time P3 = 24 milliseconds) and it requires 3 milliseconds to execute. While P4 get CPU at 32^nd milliseconds and require 3 milliseconds to complete its execution.

Computation

The formula for calculating the following:

Processes	Turnaround Time	Waiting Time	Response Time
P1	5	0	0
P2	26	2	5
P3	27	24	29
P4	42	24	32

Throughput = 4/50

Average waiting time = 12.5

Convoy Effect

For understanding the Convoy effect easily consider a scenario where CPU has to serve one CPU-bound process and many I/O bound processes. As we know the CPU-bound process requires heavy time for computation i.e. it has long CPU burst and requires less time for I/O. Whereas, I/O-bound process less time for computation and it has short CPU burst.

Consider the CPU-bound process holds the CPU first and start execution. At the same time, I/O bound processes will finish doing their I/O and will return to the ready queue waiting for the CPU. When the I/O-bound processes are waiting in the ready queue and CPU-bound process is getting executed in CPU, I/O devices are sitting idle.

After some time, the CPU-bound finishes its CPU burst time and moves on to I/O devices. So the I/O-bound processes hold the CPU and quickly finishes their execution as they have short CPU burst and move to the I/O devices, now, the CPU sits idle. This is a convoy effect where the short processes have to wait for one big process to finish its CPU burst. This also lower downs the CPU and I/O device utilization.

Advantages of the First Come First Serve Scheduling

1. It is the simplest and easy to implement algorithm programmatically. The FCFS algorithm is implemented using a FIFO Queue in the data structure. Just like in FIFO, the new data element enters from the tail of the queue and exit from the head of the queue. Similarly, in FCFS the CPU scheduler first serves the process present at the head of the ready queue.
2. It works well with the processes that have long burst time. we will understand this with the help of the example we discussed above. Look at the process P3, its waiting time in the ready queue is 24 milliseconds that is approximately 8 times of its execution time i.e. 3 milliseconds. On the other hand, look at the process P4, though it has longer burst time i.e. 20 milliseconds than P3 (burst time 3 millisecond), its waiting time in the ready queue (24 milliseconds) is far more acceptable for the lengthy process like P4 than that of P3. P4 has to wait only 3 milliseconds more than P3. So, we can surely say that the First Come First Serve scheduling performs better for processes that have long burst time.

Disadvantages of the First Come First Serve scheduling

1. In First Come First Serve scheduling the average waiting time is not optimal. Let us verify this using the above example where we get the average waiting time 12.5 millisecond. Suppose if the processes would have come in the order P1, P3, P2, P4 (don’t consider the arrival time).
   
   The average waiting time would have been (0+5+8+32)/4= 11.25
2. The First Come First Serve scheduling is Non-preemptive in nature. Thus, it would not be productive for the time-sharing environment. Because in time-sharing systems each process gets the equal share of the CPU at regular interval.
3. As the First come First Serve scheduling is Non-preemptive, it does not understand the priority of processes. It would be worse in case an interrupt causing system failure occurs and it has to wait long in the queue to get processed.
4. The First Come First Serve exhibits convey effect which lower downs the CPU or I/O utilization as for the execution of one big process the other short processes have to wait for long.

It is simple to understand and easy to implement the algorithm. Though it generates the high average waiting time it is good for processes with long burst time.