in Operating System
10,305 views
7 votes
7 votes

Which of the following algorithm leads convoy effect?

  1. FCFS
  2.   SJF
  3.   Priority scheduling
  4.   All of the above
in Operating System
10.3k views

3 Comments

possible in FCFS .
dun think possible in SJF.
not sure about priority.
0
0
The convoy effect is a phenomenon that can occur in scheduling algorithms that use the shortest-job-first (SJF) approach. It refers to a situation in which a number of short jobs are followed by a long job, and the long job causes all of the short jobs to be delayed. This can happen because the long job occupies the CPU for a long time, preventing the short jobs from being executed including the shortest job first (SJF) algorithm. The convoy effect occurs when a long running process blocks a number of shorter processes from being executed, causing them to wait in a "convoy" behind the longer process. This can result in poorer performance for the shorter processes, as they have to wait for the longer process to complete before they can be executed.

It is correct that the shortest job first (SJF) scheduling algorithm does not typically suffer from the convoy effect. The convoy effect, also known as the convoy phenomenon, is a situation in which a group of processes or jobs with similar execution times are all scheduled to run consecutively, resulting in poor overall performance. This effect is most commonly associated with first-come, first-served (FCFS) scheduling, where the first job to arrive at the ready queue is the first one to be executed.

SJF, on the other hand, is a scheduling algorithm that selects the job with the shortest execution time for execution, regardless of when it arrived in the ready queue. This means that, in SJF, the order in which jobs arrive does not affect their execution order, and thus the convoy effect is not an issue.

It is worth noting, however, that the SJF algorithm can only work effectively if the execution times of the jobs are known in advance. In cases where this information is not available, the algorithm may not perform as well as other scheduling algorithms. Additionally, the SJF algorithm can be subject to the so-called "starvation" effect, where long-running jobs are continually preempted by shorter jobs and are never able to complete. This can be mitigated by using a variant of the SJF algorithm called "shortest remaining time first" (SRTF), which considers the remaining execution time of each job rather than its total execution time.
0
0
Totally depends on the  defnition of convoy effect !!
P.S There is two commonly used (accepted) defnitions
0
0

3 Answers

11 votes
11 votes

Not a answer but Personal Opinion (Actually for this question, every student is just giving opinions only because No one can answer it with 100% certainty, Some students have assumed their own opinion on this question as The Answer , But I don't have that delusion) : 

I have nowhere found where SJF is said to suffer from Convoy effect in any standard text so far. I have done extensive research on internet about this question and I have not found a single standard text in which SJF is said to be suffering from convoy effect. But I have found one standard book in which it is written that SJF doesn’t suffer from Convoy effect.
https://books.google.co.in/books?id=XRf5vw9xlsQC&pg=PA281&lpg=PA281&dq=sjf+convoy+effect&source=bl&ots=3zov2vPeVH&sig=4oQNVodjSxBy3CElxFBxE09Jok0&hl=en&sa=X&ved=0ahUKEwjWvuP4wMLVAhXGK48KHWuxDywQ6AEIjwEwFA#v=onepage&q=sjf%20convoy%20effect&f=false

But I’d say this : Every year many students come up with this doubt and waste significant amount of time arguing yes or no with other students. You shouldn’t do it. This won’t be asked in GATE and If it is asked, Answer only FCFS.

Adding Arjun Sir's comment which tells why answer is Not Clear for this question : 

Currently the answer is not clear as to what convoy effect really means. If that is clear, it can be better understood why FCFS suffers from it and others don't.

edited by

3 Comments

I think you can answer this easily without requiring a reference. Currently the answer is not clear as to what convoy effect really means. If that is clear, it can be better understood why FCFS suffers from it and others don't.
1
1
edited by

Thanks, GO for adding this type of surprising question to the test series.

______________________________________________________________________________

@Arjun @Deepak Poonia  Sir,

I'm Adding one snapshot from the OSTEP book also referred  by Mythili mam in their OS coursework. In this book, they used the term convey effect in SJF scheduling .Kindly Help me.

https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf 

page no 5 

0
0
it seems that the convoy effect is a situation that can occur when using certain scheduling algorithms in computer science. In particular, it seems to refer to a situation where a process with a very high burst time can prevent other processes from receiving adequate processing time, leading to the "starvation" of those processes.
0
0
9 votes
9 votes

Convoy Effect: If a process has very high Burst Time, then all other processes which come after that will go to starvation.

FCFS: If first process has very large BT, then all will go to starvation.

SJF: Let P1 come at t=0 having BT=50, after 1 second other processes come having BT=1. all other will go to starvation, bcz there is no preemption.

Priority: If the process having highest priority has BT=50, and all other lower priority processes have BT=1, all other will go to starvation.

Anwer should be All

4 Comments

In SJF, It will happen for the first time.

But in FCFS, it will repeat again and again, Until the highest burst process gets terminated.

See this, https://cs.stackexchange.com/questions/11325/the-convoy-effect-in-process-scheduling

3
3
@Hemant Parihar, I think what you are saying is true. In SJF for first process, if burst time is large then it will indeed take the entire CPU time but from then on, all the remaining processes would execute properly as they would have been arrived by then and scheduler will choose the process with less burst time properly.

What do you think about preemptive and non preemptive priority scheduling ? In priority scheduling, I can give the process with large burst time higher priority. So in both preemptive and non preemptive priority scheduling, convoy effect can occur I guess.
0
0
FCFS have no starvation because every processes get a chance to execute after a definite amount of time.But if all the other processes are waiting for the bog one process(CPU Bound processes) to get off the cpu then convoy effect taken place.
0
0
4 votes
4 votes
FCFS - When first process is large enough then it increases the waiting time of the remaining process

SJF- Would initiallly choose smalller process from the ready queue

Priority Scheduling - It depends solely on the priority assigned by the process thus it may or may not lead to

So the answer is FCFS

Related questions