Operating System Design/Scheduling Processes/SPN

Shortest Process Next (SPN) scheduling, also called Shortest Job First (SJF) scheduling, assigns the process estimated to complete fastest to the CPU as soon as CPU time is available.

This method falls prey to the halting problem. The halting problem is unsolvable, but basically states that given a program and a particular input, can we determine if it will ever finish? With a simple program we could try to run it, and if it completes then we know it will finish, but if it doesn't complete in a given time, perhaps we just didn't wait long enough.

There is no way to determine which process is going to run in the least amount of time unless you allow all processes to run and record their execution times or take input from the user.

This method also allows for live lock with many short processes locking a longer process out from the CPU.

Analogy

The cashier in a store finds the person with the fewest items, and checks out their items first.

Implementation

it can be implemented by choosing the shortest job before the higher job.

Advantages and Disadvantages

SPN tends to be the most optimal scheduling system for total number of jobs completed short of SRT, but requires exact knowledge of how long a process will take. This is usually input by the user. If the mechanism to determine what is the shortest job is faulty then this might significantly reduce the throughput. Given a system with a lot of short jobs and one long job then the long job might never be run.