Does SJF suffer from convoy effect?

Question

SJF suffers from convoy effect ? It states "SJF will not preempt a current long job that arrives before shorter jobs." So please clarify this whether SJF suffers from convoy effect or not? this is i think from uc berkeley

Answer 1

The convoy effect is most commonly associated with FCFS, because FCFS can place a long CPU-bound process before many short processes.

SJF usually reduces the convoy effect because it chooses the shortest job first. However, since SJF is non-preemptive, a long process that has already started can still cause short processes arriving afterward to wait.

SJF does not know the exact future CPU burst time

SJF stands for Shortest Job First. To choose the shortest job, the scheduler needs to know or estimate how long each process will run.

But in a real system, the scheduler generally cannot know the future CPU burst time exactly.

So SJF uses an estimate of the next CPU burst, often based on previous CPU bursts.

SJF:

• Non-preemptive scheduling
• Selects the process with the shortest CPU burst time
• Once a process starts executing, it cannot be interrupted by another process.

SRTF (Shortest Remaining Time First):

• Preemptive version of SJF
• If a new process arrives with a shorter remaining burst time, the currently running process can be preempted.

Comments

Yes all that is true but they specifically mentioned SJF will not preempt a current long job that arrives before shorter jobs in that case SJF suffers from convoy effect. Lets say many long jobs arrive before shorter ones and one of them is currently running and as SJF is non preemptive and doesn't know the CPU burst of this process and future processes which happens to be shorter than the currently running "Long Job", this long job may make shorter jobs wait indefinitely again according to that specific statement mentioned.

If they ask exactly like this " SJF will not preempt a current long job which arrives before shorter jobs" then can we say SJF suffers from minor Convoy Effect in this case because longer jobs keep getting the cpu because they arrive before shorter jobs?

But i think that's more of a starvation case than convoy effect.

---

Yeah, it is a little bit confusing.

If the long process eventually finishes and the next waiting shorter process gets the CPU, then it is not starvation. Once the shorter process enters the ready queue, if it has the shortest burst time among the ready processes, SJF will select it at the next scheduling decision.

Long waiting time does not necessarily mean starvation.

This is simply waiting, and it can resemble a convoy effect if many short processes are waiting behind a long-running process. So, we might call it a small/limited convoy-like effect, but convoy effect is more strongly associated with FCFS.

Also, as you said, “indefinitely waiting = starvation”, we cannot conclude starvation just because a process waits for a long time. We need to know whether it can be postponed indefinitely.

---

According to me, convey effect 《 starvation.

If srtf is suffering from srarvation, then it should suffer from convey effect.

If multiple standard resources saying different things, see what happened https://gateoverflow.in/399294/gate-cse-2023-question-17