First Come First Serve (FCFS) CPU Scheduling Algorithm

 

CPU Scheduling Algorithms:

These algorithms decide which of the processes in the ready queue is to be allocated the CPU. There are many different CPU scheduling algorithms. Out of these, an algorithm that maximizes CPU utilization and throughput; and minimize turnaround time, waiting time, and response time are considered as best of all algorithms.

First Come First Serve Scheduling (FCFS):

 

FCFS is the simplest scheduling method. CPU is allocated to the process in the order of arrival. The process that requests the CPU first is allocated the CPU first. FCFS is also called FIFO (First In First Out). FCFS is non - preemptive scheduling algorithm. Implementation of the FCFS policy is easily managed with a FIFO queue.

 

When a process enters the ready queue, its process control block (PCB) is linked onto 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 removed from the queue.

The performance metric used is average waiting time. Average waiting time for FCFS is often quite long. Usually, FCFS is used in batch systems. Real life analogy of FCFS is buying tickets at the ticket counter. The FCFS is a not suitable for real time systems.

 

Consider following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds:

Process	Burst time
P1	24
P2	3
P3	3

Now, we calculate an average waiting time when the processes arrive in the following order:

 

a)    P1, P2, P3     b)  P2, P3, P1

 

The Gantt chart for the same is as follows:

 

For process arrival order,

 

a)    P1, P2, P3

Waiting time:

 

Process	Waiting time
P1	0
P2	24
P3	27

 

b)  P2, P3, P1

Gantt chart:

Waiting time:

Process	Waiting time
P1	6
P2	0
P3	3

The long CPU burst P1 seriously delays the completion of the shorter bursts P2 and P3.The CPU burst of P1 can be very long and all other processes will have no chance to run at all. It is not responsive. If P2 and P3 are interactive, users won't feel it a reasonable arbitrarily longer than the time really needed. It lengthens the average completion time, since it is possible that all processes completes only after P1 completes.

 

It reduces IO device utilisation, since all IO bound processes will be waiting long for CPU bound ones. This is called as convoy effect. For these reasons FCFS is usable only when all CPU bursts are known to be short, ex: within the kernel.

 

 Convoy Effect:

Consider 10 IO bound processes and 1 CPU bound process in the system. IO bound processes pass quickly through the ready queue and suspend them waiting for IO. The CPU bound process arrives at the head of the queue and execute the program until completion. IO bound processes rejoin the ready queue and wait for the CPU bound process releasing the CPU.

IO device is idle until the CPU bound process completes. A convoy effect happens when a set of processes need to use a resource for a short time and one process holds the resource for the long time, blocking all other processes.

 

Advantages:

·         FCFS is relatively simple to implement.

·         It incurs minimum overhead

 

Disadvantages:

·         It has unpredictable turnaround time.

·         In FCFS, average waiting time is more.