First Come, First Served (FCFS)

The first come first served (FCFS) is the simplest CPU-scheduling algorithm. The process which requests CPU first will be allocated CPU first and so on.

The process enters the ready queue and its PCB is linked to the tail of the queue. When the CPU is free, it is assigned a new process from the head of the queue. The FCFS scheduling can be managed with a first in, the first queue. Also, its code is simple to understand.

Example: consider a set of processes arrive at time 0, with burst time in milliseconds.

The order in which process arrives is p1, p2, p3, and p4.

The wait time for p1 = 0
The wait time for p2 = 20 + 0 = 20
The wait time for p3 = 5 + 20 + 0 = 25
The wait time for p4 = 10 + 5 + 20 + 0 = 35

Therefore, the average wait time is (0 + 20 + 25 + 35)/ 4 = 80/4 = 20 milliseconds.

Now consider the order, p2, p3, p1, and p4.

The wait time for p2 = 0
The wait time for p3 = 0 + 5 = 5
The wait time for p1 = 0 + 5 + 10 = 15
The wait time for p4 = 0 + 5 + 10 + 20 = 35

Therefore, The average wait time is (0 + 5 + 15 + 35)/4 = 55/4 = 13.75 milliseconds.

The average wait time in FCFS is greater than other algorithms. Suppose there is a single big CPU bound process and many I/O bound processes. If a CPU bound process takes time while all I/O bound process finish their I/O operations and wait in ready queue for CPU. This will lead to an idle I/O device.

The CPU-bound process finishes and goes to I/O queue and all the I/O bound processes whose CPU bursts are small finishes and goes back to I/O devices. The CPU remains idle at this time.

This is a convoy effect where a big process causes other processes to wait and results in lower CPU and device utilization. The FCFS scheduling is non-preemptive, once CPU is allocated, the process remains in CPU until released.

References

• Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edn., : Wiley.
• Tanenbaum, Andrew S. (March 3, 2001) Modern Operating Systems, 2nd edn., : Prentice Hall.