Shortest Job First (SJF)

In this lesson, you will learn about the Shortest Job First (SJF) scheduling policy.

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 reduces average turnaround from 110 seconds to 50 (10+20+1203=50\frac{10+20+120}3 = 50), more than a factor of two improvement.

ASIDE: PREEMPTIVE SCHEDULERS

In the old days of batch computing, a number of non-preemptive schedulers were developed; such systems would run each job to completion before considering whether to run a new job. Virtually all modern schedulers are preemptive, and quite willing to stop one process from running in order to run another. This implies that the scheduler employs the mechanisms we learned about previously; in particular, the scheduler can perform a context switch, stopping one running process temporarily and resuming (or starting) another.

In fact, given our assumptions about jobs all arriving at the same time, we could prove that SJF is indeed an optimal scheduling algorithm. However, you are in a systems course, not theory or operations research; no proofs are allowed.

Thus we arrive upon a good approach to scheduling with SJF, but our assumptions are still fairly unrealistic. Let’s relax another assumption. In particular, we can target assumption 2, and now assume that jobs can arrive at any time instead of all at once. What problems does this lead to?

(Another pause to think … are you thinking? Come on, you can do it)

Here we can illustrate the problem again with an example. This time, assume A arrives at t=0t = 0 and needs to run for 100 seconds, whereas B and C arrive at t=10t = 10 and each needs to run for 10 seconds. With pure SJF, we’d get the schedule seen in the figure below.

As you can see from the figure, even though B and C arrived shortly after A, they still are forced to wait until A has completed, and thus suffer the same convoy problem. Average turnaround time for these three jobs is 103.33 seconds (100+(110−10)+(120−10)3\frac {100+(110-10)+(120-10)}3).What can a scheduler do?

Get hands-on with 1400+ tech skills courses.