Home » Operating System

Convoy Effect in FCFS Scheduling

In this tutorial, we will learn about the convoy effect in the FCFS scheduling algorithm in Operating System, how can we overcome this problem. By Monika Jha Last updated : May 08, 2023

What is Convoy Effect in FCFS Scheduling?

In FCFS scheduling the burst time of the first job is the highest among all the other jobs so this situation is referred to as a convoy effect.

• For example, there is one CPU intensive process (which has large burst time) in the ready queue, and many more other processes comparatively fewer burst times but are Input/ Output (I/O) bound processes that mean processes need I/O operations frequently.
• Let's take an example of real life, suppose a convoy is passing through the road. So, other persons may get blocked until it passes completely.
• If the CPU currently executing the process that has higher burst time at the front end of the ready queue then the processes of lower burst time may get blocked by the currently running process which means they may never get the CPU if the job in the execution has a very high burst time. This is known as the convoy effect or starvation.

Convoy Effect

Steps are as follows,

• Firstly allocate the CPU time to the I/O bound processes because they are less CPU intensive, they will take less time to execute and after execution goes to the I/O queues.
• Now, allocated the CPU time to the CPU intensive process because its burst time is high, it takes a long time to execute.
• During the execution of the CPU intensive process, the I/O bound processes complete their I/O operations and are a return to ready queue.
• However, the CPU intensive process still hasn’t finished its execution so the I/O bound processes are waiting in the ready queue. At this time I/O devices being idle.
• When the CPU intensive process finishes its execution, it is sent to the I/O queue so that it can access an I/O device.
• Meanwhile, move back to the I/O queue as these processes get their required CPU time.
• However, I/O bound processes are waiting because the CPU intensive process is still accessing an I/O device. So, now the CPU is sitting idle.

Convoy Effect Example

In Example, We have 3 processes named P1, P2, and P3. Among these three processes, P1 has the highest burst time.

We can calculate the Turnaround time by Turn Around Time = Completion Time - Arrival Time.

Calculate the waiting time by the formula: Waiting Time = Turn Around Time - Burst Time.

• In the first phase, the process P1 arrives at the first in the queue. The process P1 has the highest burst time among all.
• According to the FCFS scheduling algorithm, the process comes the first CPU will execute that process first. So, here CPU will execute process P1.
• In this schedule, the average waiting time of the system will also be very high. This is because of the convoy effect or starvation.
• The other processes P2, P3 have to wait for their execution by the processor for 50 units of time and the burst time of these two processes is very small. This schedule suffers from starvation.

Process Id	Arrival time	Burst time	Turnaround time	Waiting time
P1	0	35	35	0
P2	1	2	36	34
P3	1	4	40	36

Gantt Chart

Average waiting Time = 0+34+36/3 = 70/3 = 23.33

• In the second phase, the problem of starvation would not occur only if the other processes P2 and P3 would have arrived earlier and process P1 would have arrived at the last.
• Let's take another example where process P1 will arrive after processes P2 and P3.

Process Id	Arrival time	Burst time	Turnaround time	Waiting time
P1	1	35	40	5
P2	0	2	2	0
P3	0	4	6	1

Gantt Chart

• In this example, we can see the waiting times of both phases. However, the length of the schedule is the same that is 41 units but the waiting time will be lesser in this schedule.
  Average waiting Time = 5+1+0/3 = 6/3 = 2

How to Avoid Convoy Effect in FCFS Scheduling?

Preemptive scheduling like round-robin scheduling can be used to avoid Convoy Effect as in these algorithms every process will be given an equal chance to access the CPU. By using these smaller processes don’t have to wait much for CPU time – making their execution faster and leading to fewer resources sitting idle.

---