Shortest-Job-Next

from Wikipedia, the free encyclopedia

Shortest-Job-Next (SJN) or Shortest-Job-First (SJF) is a non-preemptive scheduling method that is used to distribute threads and / or processes willing to compute to the physical processors of the computer .

Modifications of this scheduling method are

  • Shortest-Processing-Time ( SPT ) also known as Shortest-Remaining-Time-Next ( SRTN )
This is a preemptive version of SJF
  • Shortest-Process-Next ( SPN )
For interactive processes

The basis of the SJF procedure is a ranking list, similar to the FIFO procedure. The length of the CPU burst (computing time) is used to determine the priority. Threads with a short burst length are preferred to longer ones. As a result, it can lead to the problem that a thread with a long CPU burst almost never gets a chance. However, it is easy to run into problems like this once you are prioritizing. If several CPU bursts are of the same length, the FCFS procedure is the same.

Compared to the FCFS process, SJF has the advantage that it avoids the disadvantageous convoy effect . Furthermore, it can be proven that SJF brings the waiting time to an optimum. In contrast, there is the great disadvantage that the method cannot be implemented in practice, since the CPU burst lengths are generally unknown. However, approximate implementations are possible.

There is a simple idea behind the approximation of the SJF method. Since the length of the future CPU burst is unknown, it is possible to observe how a thread has behaved in the past, hoping it will behave similarly in the future.

Burst estimated ( n + 1) = α · Burst measured ( n ) + (1 - α) · Burst estimated ( n ) The weighting of the previous measurements can be determined with the variable α. Values ​​close to 1 attach little importance to the past.

SJF can preemptively (this algorithm shortest remaining time Next is called) and not preemptively implement . With the non-preemptive implementation, the thread change only takes place after a voluntary release by the thread itself or after a blocking operation (e.g. I / O) or when the life condition of the thread and / or process has expired. In other words, there is no automatic interruption such as B. instead of round robin methods.

SJF can also be modified for interactive processes. One then speaks of the Shortest-Process-Next. As an alternative, there is the preemptive shortest remaing time, which is based on the shortest process next.

example

process arrival time Duration
A. 0 4th
B. 2 7th
C. 3 6th
D. 9 2
E. 16 1
Shortest Process Next, example

Process B and C are available for the fifth processing step. Since C only takes 6 steps and B takes 7 steps to complete, C is executed first.

At time 11, process D, which is only 2 steps long, is preferred to 7-step process B.

Processes A, C and D have been processed at time 13. Process E does not yet exist, so process B can be executed.