First Come First Serve (FCFS) Scheduling Algorithm

First Come First Serve (FCFS) is a CPU scheduling algorithm where the process that arrives first in the ready queue will be served first by the CPU. FCFS is a non-preemptive scheduling algorithm i.e. once the CPU is allocated to a process, the process releases the CPU only when the process gets terminated or it requests for I/O.

FCFS is a Batch System algorithm in which the user doesn’t expect a quick reply from the system. The Batch system accepts the algorithms that serve the process for a 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. Example
3. Computation
4. Convoy Effect
5. Advantages
6. Disadvantages
7. 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 in the process arrives. With reference to the arrival time given in the table, the processes arrive in the order p1, p2, p3, p4.

The 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.

Gantt Chart

Gantt chart is the graphical representation of the process scheduling. 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 milliseconds 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 the ready queue, but P2 has to wait till P1 is completely executed because of the non-preemptive nature of this scheduling algorithm (waiting time of P2 = 2 milliseconds).

While P2 is performing its execution both the remaining processes P3 and P4 arrive in the ready queue. Process P3 gets a chance to execute at the 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.

Example

People standing in a queue in a supermarket for billing is the best example for FCFS. The first person standing in the queue will be the one to be served first. In a similar way, the first process in the ready queue will be served by the CPU first.

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 the 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 a long CPU burst and requires less time for I/O. Whereas, I/O-bound process requires less time for computation and has a 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 the CPU-bound process is getting executed in the CPU, I/O devices are sitting idle.

After some time, the CPU-bound process 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. FCFS is the simplest and easy to implement algorithm programmatically.
2. FCFS works well with processes that have a 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 its execution time i.e. 3 milliseconds. On the other hand, look at the process P4, though it has a 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 of 12.5 milliseconds. 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 an equal share of the CPU at regular intervals.
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 a high average waiting time it is good for processes with long burst time.