Shortest-Job-Next

Shortest -Job- First ( SJF ) is a nonpräemptives scheduling method, which is used to distribute willing to compute threads and / or processes to physical processors of the computer.

Modifications of this scheduling method are

  • Shortest Processing Time ( SPT ) also known as Shortest - Remaining- Time -Next ( SRTn )
  • Shortest -Process -Next (SPN)

The basis of the SJF method is a ranked list, similar to the FIFO method. Here, the length of the CPU bursts ( calculation time ) is used to determine the ranking. Threads with a short burst length are the longer preferred. Consequently, it may lead to the problem that a thread with a long CPU burst almost never comes into play. Mind you, easily to such problems as forming priorities. If more than one CPU bursts of equal length, it is the FCFS method the same.

Compared with the FCFS method SJF has the advantage that it avoids the adverse convoy effect. Furthermore, it can be proved that SJF brings the waiting time for an optimum. This contrasts with the great disadvantage that the method is not practical to implement, because the CPU burst lengths are usually unknown. However, approximately implementations are possible.

Behind the approximation of the SJF process lies a simple idea. Since the length of future CPU bursts is not known, one can observe how a thread has behaved in the past, in the hope it will behave similarly in the future.

It is estimated burst (n 1) = α · Burst Measured ( n ) ( 1 - α ) · Estimated burst (s) with the variable α can be the weighting of past measurements set. Values ​​close to 1 indicate the past to a low priority.

SJF can be preemptively ( this algorithm is then called Shortest Remaining Time Next) and do not implement pre-emptive. Where in the non-preemptive thread implementation of the change ( eg I / O) or takes place by the end of the life condition of the thread and / or process only after a voluntary contribution by the thread itself or by a blocking operation. That is, there is no automatic interruption such as in a round-robin method instead.

SJF can also be modified for interactive processes. One then speaks of the Shortest -Process -Next. Alternatively, there is the preemptive Shortest remaing -Time, which is based on Shortest -Process -Next.

Example

In the fifth processing step process B and C are available. Since C only 6 steps, but B 7 steps for completing required, C is executed first.

At this point, 11 of only 2 steps long process D is the seven steps process preferred B.

At this point, processes 13 A, C and D are processed. Process E are not yet available, so that process B can be executed.

  • Operating system theory
487301
de