Shortest job next

From Infogalactic: the planetary knowledge core
Jump to: navigation, search
Shortest job next being executed.

Shortest job next (SJN), also known as Shortest Job First (SJF) or Shortest Process Next (SPN), is a scheduling policy that selects the waiting process with the smallest execution time to execute next.[1] SJN is a non-preemptive algorithm. Shortest remaining time is a preemptive variant of SJN.

Shortest job next is advantageous because of its simplicity and because it minimizes the average amount of time each process has to wait until its execution is complete. However, it has the potential for process starvation for processes which will require a long time to complete if short processes are continually added. Highest response ratio next is similar but provides a solution to this problem.

Another disadvantage of using shortest job next is that the total execution time of a job must be known before execution. While it is not possible to perfectly predict execution time, several methods can be used to estimate the execution time for a job, such as a weighted average of previous execution times.[2]

Shortest job next can be effectively used with interactive processes which generally follow a pattern of alternating between waiting for a command and executing it. If the execution burst of a process is regarded as a separate "job", past behaviour can indicate which process to run next, based on an estimate of its running time.

Shortest job next is used in specialized environments where accurate estimates of running time are available. Estimating the running time of queued processes is sometimes done using a technique called aging.[3]

Weighted shortest job first

Weighted shortest job first (WSJF) is a modification of the concept used in agile development where the jobs get weighted with the cost of delay so that the most costly jobs get done sooner.

See also


  1. Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter Scheduling Introduction] (PDF), Arpaci-Dusseau Books<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  2. Silberschatz, A.; Galvin, P.B.; Gagne, G. (2005). Operating Systems Concepts (7th ed.). Wiley. p. 161. ISBN 0-471-69466-5.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  3. Tanenbaum, A. S. (2008). Modern Operating Systems (3rd ed.). Pearson Education, Inc. p. 156. ISBN 0-13-600663-9.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>

External links