Why is the average wait time of pre-emptive SJF guaranteed to be no larger than that of non-preemptive SJF scheduling?

0
votes

SJF = Shortest Job First, title wouldn't let me fit it

Wouldn't the preemptive SJF scheduling make the average wait time of a process be greater than if it was simply executed in a non-preemptive SJF scheduling algorithm? After all, you are continually context switching and forcing a process to wait longer to be completed.

I can't seem to understand why it is that pre-emptive SJF (aka. Shortest-Time-Remaining-First, or STRF) is better than non-preemptive SJF (in terms of average wait time for a process).

Can someone explain this to me?

Thank you.

1
schedulingjob-scheduling
Can you cite the resource from where you studied this! I also doubt this,but,upon a deep-pondering might come with something to explain it to you. You please cite the source from where you read this! – Am_I_Helpful

1 Answers

1
votes

Suppose p1(8 ms burst time) arrived at the queue at 0 ms, after executing p1 for 1 ms, another process p2 came into the queue with 4 ms burst time. The processor will stop executing process p1 and will start executing process p2. Why ? because p1 has 7ms remaining to finish execution, while p1 has only 4 ms remaining to finish.

I think it's clear why it is called "shortest-time-remaining-first" scheduling. Because it always chooses a process which has the smallest amount of time remained to execute.

For your other question, why it is better....let's extend the scenario.

Process p1 --> burst time 8 ms, arrival time 0 ms,

Process p2 --> burst time 4 ms, arrival time 1 ms,

Process p3 --> burst time 9 ms, arrival time 2 ms,

Process p4 --> burst time 5 ms, arrival time 3 ms.

for preemptive SJF, average waiting time =[ (for p1)(10-1) + (for p2)(1-1) + (for p3)(17-2)+(for p4)(5-3)]/4 = 6.5 ms

for non preemptive SJF it would be, average waiting time =[ (for p1)(0) + (for p2)(8-1) + (for p3)(17-2)+(for p4)(12-3)]/4 = 7.75 ms

you can see why it is said that preemptive is better than non-preemptive, it's because it takes less time to execute all the process using this algorithm.

Reference: Operating System Concepts by Galvin, Silberschatz, Gagne (8th edition).