Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 66 ยท CPU Scheduling

SRTF and Priority Scheduling

Learn Shortest Remaining Time First (preemptive SJF) and priority scheduling, preemptive and non-preemptive, with Gantt charts, static vs dynamic priorities and runnable simulators.

Non-preemptive SJF has a weakness: a long job that started a moment before a tiny job arrived keeps the CPU anyway. Shortest Remaining Time First (SRTF) fixes this by making SJF preemptive: whenever a new process arrives, the scheduler compares its burst with the remaining time of the running process and switches if the newcomer is shorter.

SRTF is one example of a wider family, priority scheduling, where every process has a number and the scheduler always picks the best one. SJF is just a priority scheduler whose priority is the predicted burst length. In this lesson you will simulate SRTF and priority scheduling (both preemptive and non-preemptive) and learn about the issues priorities bring: starvation and how to define priorities in practice.

Preemptive shortest job

Track remaining time Not the original burst.
On every arrival Compare newcomer to the running job.
Preempt if shorter The running job goes back to ready.

SRTF gives the lowest average waiting time of any algorithm.

1 / 2

SRTF: Shortest Remaining Time First

Rule: at every moment, run the ready process with the smallest remaining burst time. A new arrival that is shorter than what the running process has left preempts it.

Take the same workload as before: A(0,6), B(1,8), C(2,2), D(3,4), E(4,3).

  • t=0: A starts (remaining 6).
  • t=1: B arrives (8) โ€“ A has 5 left, A continues.
  • t=2: C arrives (2) โ€“ A has 4 left, C is shorter, so C preempts A. C runs 2-4.
  • t=3: D(4) arrives; C has 1 left, continues. t=4: E(3) arrives; C finishes at 4.
  • t=4: ready are A(4 left), B(8), D(4), E(3). E runs 4-7.
  • Then A(4) vs D(4): tie, A arrived earlier, so A runs 7-11, then D 11-15, then B 15-23.

Average waiting time works out to 5.4, lower than non-preemptive SJF (6.0).

The price: more context switches, the need to know (or estimate) burst times, and starvation of long jobs when short jobs keep coming.

Python SRTF simulator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Priority scheduling

Each process gets a priority (a number). The scheduler runs the best one. Systems differ on whether low or high numbers are better; in the examples here a lower number means higher priority (as in many textbooks). Processes of equal priority run FCFS.

  • Non-preemptive priority: the chosen process runs to completion of its burst; the newcomer waits even if more important.
  • Preemptive priority: if a newly arrived process has higher priority than the running one, it takes the CPU immediately.

Where do priorities come from?

  • Internal (dynamic): computed by the OS from measurable properties, such as burst length (SJF), memory use, I/O-to-CPU ratio, or how long the process has waited.
  • External (static): set from outside, such as the importance of the user or the job, or the nice value on Linux (nice -n 10 command lowers priority).

Workload with priorities (lower number = more important):

Process Arrival Burst Priority
A 0 6 3
B 1 8 1
C 2 2 4
D 3 4 2
E 4 3 5
Python Priority scheduling, both flavors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the preemptive run, B (priority 1) takes the CPU from A as soon as it arrives at time 1 and runs to completion, then D, then A resumes; the unimportant jobs C and E come last. Note that priorities are not tuned for waiting time: here preemptive priority (10.0) is even worse on average than non-preemptive (9.6). Priorities express importance, not efficiency.

The big problems: starvation and priority inversion

Starvation (indefinite blocking): in a busy system a steady stream of high-priority processes can keep a low-priority process waiting forever. Legend has it that when the IBM 7094 at MIT was shut down in 1973, a low-priority job submitted in 1967 had not yet run.

Aging is the standard cure: periodically increase the priority of every process that has waited a long time. Eventually any waiting process becomes important enough to run.

Python Aging in action

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Priority inversion is a different problem: a high-priority process waits for a lock held by a low-priority one, which can itself be blocked by medium-priority work. The cure is priority inheritance (the lock holder temporarily inherits the waiter's priority). More about it in the Synchronization chapter.

SRTF vs. priority vs. SJF

Algorithm Priority is Preemptive? Starvation?
SJF Burst length No Yes
SRTF Remaining time Yes Yes
Priority (static) Assigned number Either Yes, fixed by aging
Priority (aged) Number plus waiting Either No

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does SRTF compare when a new process arrives?

    SRTF is preemptive: it runs the process with the smallest remaining time at all times.
  2. 2. In preemptive priority scheduling, a new process arrives with higher priority than the running one. What happens?

    Preemptive priority scheduling always runs the highest-priority ready process.
  3. 3. What is aging?

    Aging prevents starvation by making long-waiting processes more important over time.
  4. 4. Which problem can occur with SRTF and priority scheduling but not with FCFS?

    FCFS serves everyone in arrival order, but SRTF and priority policies can keep postponing some jobs indefinitely.
  5. 5. SJF is a special case of which family of algorithms?

    SJF is priority scheduling with priority equal to the (predicted) burst time.

Summary

  • SRTF preempts the running process whenever a newcomer has a shorter remaining time; it minimizes average waiting time but costs context switches and may starve long jobs.
  • Priority scheduling runs the most important ready process; it can be preemptive or not.
  • Priorities may be static (assigned) or dynamic (computed); SJF is priority = burst length.
  • Starvation is solved by aging; priority inversion by priority inheritance.

Next: Round Robin Scheduling