Search⌘ K
Home
Courses
Operating Systems: Virtualization, Concurrency & Persistence

Shortest Job First (SJF)

Explore how the Shortest Job First (SJF) CPU scheduling method prioritizes tasks based on shortest execution time to minimize average turnaround. Understand the benefits of SJF, its historical context, and challenges when jobs arrive at different times. This lesson helps you grasp effective CPU scheduling strategies fundamental to operating systems.

We'll cover the following...

Introduction #

It turns out that a very simple approach solves this problem; in fact, it is an idea stolen from operations research“1. Priority Assignment in Waiting Line Problems” by A. Cobham. Journal of Operations Research, 2-70, pages 70–76, 1954. The pioneering paper on using an SJF approach in scheduling the repair of machines; 2. “Machine Repair as a Priority Waiting-Line Problem” by Thomas E. Phipps Jr., W. R. Van Voorhis. Operations Research, 4-1, pages 76–86, February 1956. Follow-on work that generalizes the SJF approach to machine repair from Cobham’s original work; also postulates the utility of an STCF approach in such an environment. Specifically, “There are certain types of repair work, … involving much dismantling and covering the floor with nuts and bolts, which certainly should not be interrupted once undertaken; in other cases, it would be inadvisable to continue work on a long job if one or more short ones became available (p.81).” and applied to the scheduling of jobs in computer systems. This new scheduling discipline is known as Shortest Job First (SJF), and the name should be easy to remember because it describes the policy quite completely: it runs the shortest job first, then the next shortest, and so on.

Examples

Let’s take our example above but with SJF as our scheduling policy.

The figure above shows the results of running A, B, and C. Hopefully the diagram makes it clear why SJF performs much better with regards to average turnaround time. Simply by running B and C before A, SJF ...