Shortest Time-to-Completion First (STCF)

In this lesson, you will get familiar with the Shortest Time-to-Completion First (STCF) scheduling policy.

We'll cover the following

Relaxing assumption 3

To address this concern, we need to relax assumption 3 (that jobs must run to completion), so let’s do that. We also need some machinery within the scheduler itself. As you might have guessed, given our previous discussion about timer interrupts and context switching, the scheduler can certainly do something else when B and C arrive: it can preempt job A and decide to run another job, perhaps continuing A later. SJF by our definition is a non-preemptive scheduler and thus suffers from the problems described before.

Introducing STCF

Fortunately, there is a scheduler which does exactly that: add preemption to SJF, known as the Shortest Time-to-Completion First (STCF) or Preemptive Shortest Job First (PSJF) schedule“Computer Scheduling Methods and their Countermeasures” by Edward G. Coffman and Leonard Kleinrock. AFIPS ’68 (Spring), April 1968. An excellent early introduction to and analysis of a number of basic scheduling disciplines.. Any time a new job enters the system, the STCF scheduler determines which of the remaining jobs (including the new job) has the least time left, and schedules that one. Thus, in our example, STCF would preempt A and run B and C to completion; only when they are finished would A’s remaining time be scheduled. The figure above shows an example.

The result is a much-improved average turnaround time: 50 seconds ( (120−0)+(20−10)+(30−10)3\frac{(120-0)+(20-10)+(30-10)}3 ). And as before, given our new assumptions, STCF is provably optimal; given that SJF is optimal if all jobs arrive at the same time, you should probably be able to see the intuition behind the optimality of STCF.

Get hands-on with 1400+ tech skills courses.