Operating System Design/Scheduling Processes/SPN

From Wikibooks, open books for an open world
< Operating System Design
Jump to: navigation, search

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 and 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 lots of short processes locking a longer process out from the CPU.

Analogy[edit]

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

Implementation[edit]

Advantages and Disadvantages[edit]

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.