The convoy effect in process scheduling

Question Detail: 

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.

Asked By : jsj

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11325

Answered By : Shivam Singh Sengar

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.