Skip to content
Advertisement

Shortest Time Remaining Next (STRN) Scheduling

Another user posted this question on Shortest Job First (SJF). Here’s the example: enter image description here

How would this be solved for Shortest Remaining Time Next? The preemptive version of Shortest Job First.

I understand that the process with smallest amount of time remaining until completion is selected to execute. However, what happens if a new process arrives that has a burst time that is exactly the same as the remaining completion time of the currently executing process?

In the instance that a new process arrives that has a burst time that is the same as the current executing process (as evident in this example), then does the process currently executing continue?

Gantt chart showing how I understand the processes would be scheduled: enter image description here

Am I correct in my understanding? Thank you in advance.

Advertisement

Answer

Quoting from Wikipedia’s Shortest remaining time:

In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Since the currently executing process is the one with the shortest amount of time remaining by definition, and since that time should only reduce as execution progresses, processes will always run until they complete or a new process is added that requires a smaller amount of time.

Shortest remaining time is advantageous because short processes are handled very quickly. The system also requires very little overhead since it only makes a decision when a process completes or a new process is added, and when a new process is added the algorithm only needs to compare the currently executing process with the new process, ignoring all other processes currently waiting to execute. // emphasis mine.

If a new process arrives that has a burst time that is exactly the same as the remaining completion time of the currently executing process, then the CPU will keep executing the current process. This decision is taken because process context switch is heavier, and hence in cases of equal burst time left, the process which is currently executing would continue to execute until finished, or a new short process arrives.

And, YES, your Gantt Chart is correctly drawn.

But, please read about the limitations too // from Wikipedia:

Like shortest job next scheduling, shortest remaining time scheduling is rarely used outside of specialized environments because it requires accurate estimates of the runtime of each process.

User contributions licensed under: CC BY-SA
2 People found this is helpful
Advertisement