The convoy effect in process scheduling

Question

As I understand the convoy effect, in the context of vehicular traffic in a road system. A slow moving group of vehicles passes through the system, slowing traffic even in areas which were not directly affected by the convoy.

How does this apply in the context of CPU scheduling? It does not seem to be an analogous situation.

Answer 1

Convoy Effect is a result of using First-Come-First-Serve (FCFS) Scheduling algorithm. In this case the dispatcher (short term scheduling) feeds the processes present in ready state to the processor in FIFO fashion. This is basically a simple implementation of Queue. Processes coming first gets to use the processor first.

Since it implements the non-preemptive policy, which means that once the process starts running it won't stop unless it completes its task or is blocked by OS because of some fatal error or I/O need, it obstructs processes behind itself. If a CPU intense process gets to run, then a number of I/O intense processes don't get to dispatched. In this case the I/O devices are idle. When the CPU intense process relinquish the control, the I/O bound processes quickly pass through the CPU following by adding into the I/O queues. During this period CPU is idle.

As you can see this method is not very efficient as both CPU and I/O devices are left idle for a long time. Apart from that this method often gives very high average waiting time.

The effect is analogous to the traffic example. Because of slow moving vehicles, the traffic system is turning inefficient. Vehicles that can move faster and reach their destination (similar to exit state of a process) quicker than the slow moving vehicles ahead of them are not able to do that. If these vehicles were able to move on their potential speed, then the road would be less congested then what it is in this case. Vehicles are analogous to the processes in the ready queue.

Answer 2

FCFS (First-Come, First-Served) scheduling can also cause blocking in a busy dynamic system in another way, known as the convoy effect.

When one CPU intensive process blocks the CPU, a number of I/O intensive processes can get backed up behind it, leaving the I/O devices idle. When the CPU hog finally relinquishes the CPU, then the I/O processes pass through the CPU quickly, leaving the CPU idle while everyone queues up for I/O, and then the cycle repeats itself when the CPU intensive process gets back to the ready queue.

Answer 3

In a multiprogramming system, if multiple processes are waiting for the CPU for execution in an F.C.F.S. system, and a slow processing process is utilizing the CPU then due to the convoy all fast processes waiting for CPU waits for unnecessarily long time. This is convoy effect.

Answer 4

in the FCFS if the first process is having large service time than other processes having shorter service time then it will lead to increase in the average waiting time , which will not in the case if in the same first shorter service time processes will be served first and then the process having large service time in the last, then it will result in lesser average waiting time then that of the first case above when we are taking the process having larger service time first. it is termed as convoy effect.