Priority scheduling is an algorithm that assigns each process a numeric priority before organizing those processes according to this priority.
For example, a live video chat might have a high priority due to its latency requirements, while the process rendering the computer’s wallpaper may have a lower priority due to it being considered more inconsequential. With priority scheduling, the processing of the wallpaper would be delayed or even interrupted in order to provide sufficient resources for the video chat.
Shortest job first, as shown in the example to the right, is a variation of priority scheduling that prioritizes running the process with the shortest execution time first. If the scheduler supports preemption, then a similar algorithm for shortest remaining time can be used instead. This reevaluates the priority of the processes every time an interruption occurs.
This algorithm typically works best in specialized situations where all of the process times can be reasonably estimated beforehand.
While this algorithm minimizes the average amount of time each process has to wait until it is fully executed and thereby maximizes throughput, this comes at a cost. Some longer processes may become “starved” and never execute if shorter processes are continually prioritized in front of them. This can be mitigated by “aging” each process such that the priority of a process increases the longer it has been waiting.
This algorithm also has a fair amount of overhead as processes can be arbitrarily interrupted whenever a shorter one comes along. Similarly, the sorted queue at the heart of the algorithm must be maintained as processes are added, removed, or modified.
To the right is an example animation for Shortest Job First, where the processes with the shortest execution time are run by the processor first.
P3 has the shortest execution time of 0.5 seconds, so it is the first process sent to the CPU by the scheduler. P4 and P1 have the next shortest execution times with 1 second and 2 seconds respectively, so they are run when P3 completes.
While P1 is being executed, P5 and P6 are added to the Ready Queue. As these processes have run times of 2 and 3 seconds, they are executed before P2. Once all other processes have been executed, the longest job, P2 is executed.