Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Easy

Convoy Effect in Operating System

Author Divyansh Jain
1 upvote
gp-icon
Operating system track
Free guided path
14 chapters
83+ problems
gp-badge
Earn badges and level up

Introduction

The convoy effect is directly linked with the First Come, First Serve (FCFS) algorithm. FCFS serves as a non-preemptive scheduling algorithm where the CPU is managing a process until it is completed, which implies that other processes will have to wait, which leads to slowing down of the operating system.

Convoy Effect in Operating System

Didn’t get much of it? Okay, let’s dive deeper into the process to understand how big intensive processes make the operating system work slowly while using the FCFS scheduling algorithm. And to understand this, first, we need to clearly understand what the Convoy Effect is.

What is the Convoy Effect?

The Convoy Effect is a phenomenon in which the entire Operating System slows down owing to a few slower processes in the system. When Central processing unit (CPU) time is allotted to a process, the FCFS algorithm assures that other processes only get Central processing unit (CPU) time when the current one is finished.

When a CPU-bound process reaches the system before I/O-bound processes, it will be retained in the ready queue ahead of I/O-bound processes. Even if I/O-bound processes demand less CPU time, that CPU-bound process is granted the CPU according to FCFS policy.

The majority of the I/O modules will be idle during this period. When a CPU-bound process completes its execution, I/O-bound processes swiftly move through the CPU and collect in their respective I/O queues, resulting in leaving the CPU idle. Here, resource utilisation is low because the CPU or I/O modules must sit idle. This is known as the convoy effect. Because of this, the average waiting time for a process is longer.

Convoy Effect in os

We can visulalize from the image where a longer job takes longer time to complete and other shorter jobs have to wait resulting in the slowing down of the processes.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Let’s take a look at an example to get a clear understanding of the convoy effect.

Our system comprises three processes: P1, P2, and P3. The process P1 has the longest Burst Time. As we all know, to calculate ‘turn around time’ and ‘waiting time’, we can use the following formulas.

To calculate the TAT, i.e., Turn Around Time  =  Completion Time - Arrival Time  

And similarly, the WT is Waiting Time  =  Turn Around Time - Burst Time 

  • In the first case, process P1 is the first in line, despite the fact that its burst time is the longest of all the processes.
     
  • The CPU will execute process P1 first since we are using the FCFS Scheduling algorithm.
     
  • The system's average waiting time will be quite long in this scenario because of the convoy effect in this case.
     
  • Other processes, P2 and P3, must wait very long for the CPU to execute them, and the burst time of these two processes is relatively short, as we can see from the number of units in the following table.

Process ID

Arrival Time

Burst Time

Completion Time

Turn Around Time

Waiting Time

P1

0

50

50

50

0

P2

1

1

51

50

49

P3

1

2

53

52

50

 

Gantt Chart Visualisation

Gantt Chart Visualisation 1

Let’s calculate the average waiting time, Average WT = (0 + 49 + 50)/3 = 33

The problem of waiting for a long time would not have occurred in the second phase if the other processes, P2 and P3, had arrived sooner and process P1 had arrived last.

Now, let’s consider another scenario in which process P1 arrives after processes P2 and P3.

Process ID

Arrival Time

Burst Time

Completion Time

Turn Around Time

Waiting Time

P1

1

50

53

52

2

P2

0

1

1

1

0

P3

0

2

3

3

1

 

Gantt Chart Visualisation

Gantt Chart Visualisation 2

The waiting periods for both stages may be seen in this example. Even so, the duration of the schedule is the same but the waiting period will be lesser in this schedule.

Average waiting Time = (2 + 0 + 1)/3 = 1

Finally, we can understand from both examples that when an intensive process occurs first in the lead, then it slows down the operating system and it makes shorter jobs wait for a long time.

Stages of Convoy Effect in Operating Systems

Assume there is one CPU-intensive (long burst time) process in the ready queue, as well as many other processes that have shorter burst periods but are I/O bound (need frequent I/O operations).

Note: Burst time is the amount of time required for a process to execute on a computer systems CPU.

The stages are as follows:

  • The CPU time is first assigned to I/O-bound tasks. They are swiftly executed and go to I/O queues since they are less CPU-heavy.
     
  • As we know, CPU time is now assigned to the CPU-intensive process, which takes a long time to finish due to its long burst time.
     
  • While the CPU-intensive process is running, the I/O bound processes execute their I/O operations and are restored to the ready queue.
     
  • I/O-bound processes, on the other hand, must wait while the CPU-intensive task continues to run. As a result, I/O devices become inactive.
     
  • When the CPU-intensive task is completed, it is queued to access an I/O device in the I/O queue.
     
  • Eventually, the I/O bound processes acquire the CPU time they require and return to the I/O queue.
     
  • They must, however, wait since the CPU-intensive process is still using an I/O device. The CPU is currently idle as a result of this.
     

So, as a result, one sluggish process degrades the performance of the entire collection of processes, wasting CPU time and other resources.

Prevention of Convoy Effect in OS

Preemptive scheduling, such as round-robin scheduling, can be used to prevent the Convoy Effect since each process is given an equal chance to use the CPU in these methods. These smaller processes don't have to wait as long for CPU time, resulting in speedier execution and fewer resources lying idle.

Frequently Asked Questions

Is there any difference between the Convoy effect and starvation? 

The Convoy effect causes the entire operating system to slow down for a short period of time. However, starvation is the indefinite postponement of a process, despite the fact that it is ready for allocation. 

When does starvation and convoy effect occur?

When the processor is biased, it can lead to starvation, and when smaller processes have to wait for larger processes to release the CPU, it can result in the convoy effect. 

What strategies can be used to optimise the convoy effect?

Strategies to optimize the convoy effect may include selecting appropriate routes, maintaining a consistent speed, using defensive tactics, and enhancing decision-making.

Explain convoy effect in fcfs?

The convoy effect in First-Come-First-Serve (FCFS) scheduling arises when shorter processes are delayed by longer ones in the queue. This leads to inefficient resource utilization as smaller tasks wait behind longer ones, impacting overall system efficiency and response times. 

What is a convoy in computer architecture?

In computer architecture, a convoy refers to a situation where shorter tasks are held up by longer ones, causing potential bottlenecks. This delay can hinder overall system performance by impeding the efficient execution of shorter processes, affecting resource allocation and response times.

Conclusion

In conclusion, the convoy effect in operating systems, particularly in scheduling algorithms like First-Come-First-Serve (FCFS), highlights the challenge of resource allocation efficiency. The phenomenon, where shorter tasks are delayed by longer ones, underscores the importance of choosing scheduling algorithms that prioritize fair and optimized task execution for enhanced system performance. 

For more articles related to operating systems, you can refer following links:

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences for placement preparations.

Happy Coding!

Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass