SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 22

CS Fundamentals for Placements · Lesson 22 of 90 · 16 min

CPU scheduling 2: SJF, SRTF and priority with numericals

SJFSRTF (preemptive SJF)optimality of SJFstarvationpriority scheduling (preemptive and non-preemptive)agingpriority inversionpriority inheritanceburst time prediction by exponential averagingmixed numericals

These are the notes for CS Fundamentals for Placements, episode 22. Last episode, First Come First Served (FCFS) gave us the convoy effect: short jobs stuck behind one long job (average waiting time 17 instead of 3). Today you invent the fixes: Shortest Job First (SJF), its preemptive version Shortest Remaining Time First (SRTF), why they are optimal, how an OS predicts burst times by exponential averaging, priority scheduling (preemptive and non-preemptive), starvation and aging, and priority inversion with priority inheritance, using the real Mars Pathfinder story. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.

All program outputs below are real: the Python code was run with Python 3.13 on 2 November 2026, exactly as in the SyntaxPilot compiler.

Refresher from episode 21: arrival time (AT) is when a process enters the ready queue, burst time (BT) is the CPU time it needs, completion time (CT) is when it finishes. Turnaround time TAT = CT − AT, waiting time WT = TAT − BT, response time RT = first time on the CPU − AT. A Gantt chart is a time bar of who ran when. Preemptive means the OS can take the CPU away in the middle of a burst; non-preemptive means a process keeps the CPU until it finishes or blocks.

The six problems

Problem What it teaches
Short jobs stuck behind long ones SJF; choosing only from processes that have arrived
A tiny job arrives mid-run SRTF (preemptive SJF), remaining time
Why shortest first? The swap argument: SJF/SRTF minimise average waiting time
The burst time is unknown Exponential averaging, α, τ
Shortest isn't most urgent Priority scheduling, preemptive and non-preemptive
Low priority never runs; a low task blocks the top task Starvation, aging, priority inversion, priority inheritance

Problem 1: short jobs stuck behind long ones (SJF)

Real-life example: the photocopy shop. A student ahead of you has 200 pages (20 minutes). You have 1 page (10 seconds). A smart shopkeeper says "one page? come, you first": the student loses 10 seconds, you save 20 minutes.

Photocopy shop In the OS
200 pages A long CPU burst
1 page A short CPU burst
"You go first" Shortest Job First (SJF): among the ready processes, run the one with the smallest burst time next

SJF is non-preemptive: once a process starts, it runs its whole burst. Ties (equal bursts) are broken by FCFS, the earlier arrival first.

The obvious simulator (fails)

The obvious idea: sort all processes by burst time, then run them in that order.

procs = [("P1", 0, 7), ("P2", 2, 4), ("P3", 4, 1), ("P4", 5, 4)]
procs.sort(key=lambda p: p[2])      # shortest burst first

time = 0
for name, at, bt in procs:
    start = time
    time += bt
    print(f"{name} runs {start}-{time}, arrived at {at}, WT = {start - at}")

Output:

P3 runs 0-1, arrived at 4, WT = -4
P2 runs 1-5, arrived at 2, WT = -1
P4 runs 5-9, arrived at 5, WT = 0
P1 runs 9-16, arrived at 0, WT = 9

Why it fails: sorting the whole list looks into the future. At time 0 only P1 has arrived, so P3 cannot run at 0. A negative waiting time is always a sign that you ran a process before it arrived.

The fixed SJF simulator

At every decision, build the list of processes that have arrived and not finished, and take the shortest burst from that list. If nobody has arrived, the CPU is idle for one unit.

procs = [("P1", 0, 7), ("P2", 2, 4), ("P3", 4, 1), ("P4", 5, 4)]

time, done, wt, gantt = 0, [], {}, ""
while len(done) < len(procs):
    ready = [p for p in procs if p[1] <= time and p not in done]
    if not ready:                   # nobody has arrived: CPU idle
        time += 1
        continue
    p = min(ready, key=lambda p: p[2])   # shortest burst among arrived
    name, at, bt = p
    gantt += f"| {name} {time}-{time + bt} "
    time += bt                      # non-preemptive: runs to the end
    wt[name] = time - at - bt
    done.append(p)
print(gantt + "|")
print("WT:", wt)
print("avg WT =", sum(wt.values()) / len(wt))

Output:

| P1 0-7 | P3 7-8 | P2 8-12 | P4 12-16 |
WT: {'P1': 0, 'P3': 3, 'P2': 6, 'P4': 7}
avg WT = 4.0

min(ready, key=...) returns the first of several equal minimums, and ready keeps the original arrival order, so ties go FCFS automatically.

The same numerical by hand

P AT BT CT TAT = CT − AT WT = TAT − BT
P1 0 7 7 7 0
P2 2 4 12 10 6
P3 4 1 8 4 3
P4 5 4 16 11 7

Gantt chart: | P1 0-7 | P3 7-8 | P2 8-12 | P4 12-16 |. Average TAT = 32/4 = 8, average WT = 16/4 = 4. (FCFS on the same processes gives P1 0-7, P2 7-11, P3 11-12, P4 12-16: WT 0, 5, 7, 7, average 4.75.)

Problem 2: a tiny job arrives mid-run (SRTF)

P3 needs 1 unit, arrives at 4, and still waits until 7, because SJF is non-preemptive. The fix: re-decide whenever a process arrives. Compare the newcomer's burst with the remaining time of the running process (how much of its burst is still left). If the newcomer is shorter, preempt. This is Shortest Remaining Time First (SRTF), also called preemptive SJF or Shortest Remaining Time Next (SRTN).

SRTF simulator

The trick: run only one time unit, then decide again.

procs = [("P1", 0, 7), ("P2", 2, 4), ("P3", 4, 1), ("P4", 5, 4)]
left = {name: bt for name, at, bt in procs}   # remaining time

time, gantt, ct = 0, [], {}
while left:
    ready = [p for p in procs if p[1] <= time and p[0] in left]
    if not ready:
        time += 1
        continue
    name = min(ready, key=lambda p: left[p[0]])[0]  # least left
    if not gantt or gantt[-1][0] != name:
        gantt.append([name, time, time])  # a new block starts
    left[name] -= 1                 # run ONE time unit, then re-check
    time += 1
    gantt[-1][2] = time
    if left[name] == 0:
        del left[name]
        ct[name] = time
print("".join(f"| {n} {s}-{e} " for n, s, e in gantt) + "|")
wt = {n: ct[n] - at - bt for n, at, bt in procs}
print("WT:", wt)
print("avg WT =", sum(wt.values()) / len(wt))

Output:

| P1 0-2 | P2 2-4 | P3 4-5 | P2 5-7 | P4 7-11 | P1 11-16 |
WT: {'P1': 9, 'P2': 1, 'P3': 0, 'P4': 2}
avg WT = 3.0

By hand: decide only at arrivals and completions

Time Event Compare Decision
0 P1 arrives (7) alone P1 runs
2 P2 arrives (4) P1 has 5 left P2 preempts
4 P3 arrives (1) P2 has 2 left P3 preempts
5 P3 done; P4 arrives (4) P2 2, P4 4, P1 5 P2 continues
7 P2 done P4 4, P1 5 P4
11 P4 done P1 5 P1
P AT BT CT TAT WT RT
P1 0 7 16 16 9 0
P2 2 4 7 5 1 0
P3 4 1 5 1 0 0
P4 5 4 11 6 2 2

Average WT = 12/4 = 3, average TAT = 28/4 = 7. Long jobs pay (P1 waits 9), and there are more context switches (switching the CPU from one process to another, which costs time): 5 switches here vs 3 for SJF.

In SRTF, waiting time is still TAT − BT; a preempted process waits in several pieces, and the formula adds them all up automatically.

Problem 3: why is shortest-first optimal?

The swap argument. Two jobs arrive together: L needs 10, S needs 1.

Order L waits S waits Total
L then S 0 10 10
S then L 1 0 1

Moving a shorter job in front of a longer neighbour lowers the total waiting time (by the difference of the bursts). Keep swapping every long-before-short pair and you get shortest-first. So:

  • SJF gives the minimum average waiting time among non-preemptive schedules for a given set of jobs.
  • SRTF gives the minimum average waiting time when preemption is allowed (ignoring context-switch cost).

Both are provably optimal, yet no general-purpose OS uses them exactly. Why? Problem 4.

Problem 4: the burst time is unknown (exponential averaging)

In numericals, the burst time is given. A real OS cannot know how long a process will compute before it next waits for I/O. But a process's bursts tend to look alike (an editor computes briefly, then waits for keys), so the OS predicts the next burst from the past.

Real-life example: guessing your commute. Yesterday the bus took 40 minutes. Your usual guess is 30. Today you plan for 35: half the newest day, half the old habit.

Exponential averaging:

τ(n+1) = α · t(n) + (1 − α) · τ(n)

Symbol Meaning Commute
t(n) the n-th actual CPU burst (the latest real value) 40 min yesterday
τ(n) the prediction for that burst (it holds all history) usual guess 30
τ(n+1) the prediction for the next burst today's guess 35
α weight, 0 ≤ α ≤ 1 0.5
  • α = 1: only the last burst counts (τ(n+1) = t(n)).
  • α = 0: history only, the guess never changes.
  • Expanding the formula: τ(n+1) = α t(n) + (1−α) α t(n−1) + (1−α)² α t(n−2) + ... Each older burst's weight is multiplied by (1 − α), so it shrinks exponentially. That is where the name comes from. τ(0), the first guess, is a constant (often a system default).
alpha = 0.5
guess = 10                          # first guess, tau0
actual = [6, 4, 6, 4, 13, 13, 13]   # real CPU bursts, one by one

for t in actual:
    print(f"predicted {guess:5.2f}   actual {t:2}")
    guess = alpha * t + (1 - alpha) * guess
print(f"next prediction: {guess:.2f}")

Output:

predicted 10.00   actual  6
predicted  8.00   actual  4
predicted  6.00   actual  6
predicted  6.00   actual  4
predicted  5.00   actual 13
predicted  9.00   actual 13
predicted 11.00   actual 13
next prediction: 12.00

When the real bursts jump to 13, the prediction follows (9, 11, 12): it lags a little but learns. An SJF/SRTF scheduler uses the predicted burst instead of the real one.

Problem 5: shortest isn't most urgent (priority scheduling)

Real-life example: hospital triage. A heart attack is seen before a small cut, even though it takes longer. A triage nurse tags each patient with a priority.

Priority scheduling: every process has a priority number; the scheduler always runs the most important ready process. Conventions differ: in most textbooks and GATE questions a smaller number means higher priority, but always read the question. Ties go FCFS. SJF is priority scheduling with priority = (predicted) burst time.

Priority can be internal (computed by the OS from measurable things: memory needs, number of open files, I/O vs CPU ratio) or external (set from outside: importance, who pays, politics).

Numerical (smaller = higher priority)

P AT BT Priority
P1 0 4 2
P2 1 3 1
P3 2 1 3
P4 3 2 1

Non-preemptive: P1 0-4 (alone at 0). At 4: P2 and P4 both priority 1, P2 arrived earlier: P2 4-7, P4 7-9, P3 9-10. WT = 0, 3, 7, 4 → average 3.5.

Preemptive: decide at every arrival.

# (name, arrival, burst, priority)   smaller number = more important
procs = [("P1", 0, 4, 2), ("P2", 1, 3, 1), ("P3", 2, 1, 3), ("P4", 3, 2, 1)]
left = {p[0]: p[2] for p in procs}

time, gantt, ct = 0, [], {}
while left:
    ready = [p for p in procs if p[1] <= time and p[0] in left]
    if not ready:
        time += 1
        continue
    name = min(ready, key=lambda p: p[3])[0]   # most important first
    if not gantt or gantt[-1][0] != name:
        gantt.append([name, time, time])
    left[name] -= 1                 # one unit, then re-check: preemptive
    time += 1
    gantt[-1][2] = time
    if left[name] == 0:
        del left[name]
        ct[name] = time
print("".join(f"| {n} {s}-{e} " for n, s, e in gantt) + "|")
wt = {p[0]: ct[p[0]] - p[1] - p[2] for p in procs}
print("WT:", wt, " avg =", sum(wt.values()) / len(wt))

Output:

| P1 0-1 | P2 1-4 | P4 4-6 | P1 6-9 | P3 9-10 |
WT: {'P1': 5, 'P2': 0, 'P3': 7, 'P4': 1}  avg = 3.25

At 3, P4 (priority 1) arrives while P2 (also 1) runs: an equal priority does not preempt, so P2 continues.

Problem 6: low priority never runs (starvation and aging)

A backup job (priority 5) arrives at 0, and urgent jobs (priority 1) keep arriving, one every 2 units, 1000 of them.

# a backup job (priority 5) and a steady stream of urgent jobs (priority 1)
procs = [("backup", 0, 3, 5)]
procs += [(f"u{i}", 2 * i, 2, 1) for i in range(1000)]   # one every 2 units

AGING = False
time, done = 0, set()
while len(done) < len(procs):
    ready = [p for p in procs if p[1] <= time and p[0] not in done]
    def prio(p):
        wait = time - p[1]
        return p[3] - wait // 4 if AGING else p[3]   # aging: +1 per 4 units
    name, at, bt, pr = min(ready, key=prio)
    if name == "backup":
        print(f"backup starts at {time} after waiting {time - at}")
    time += bt                      # non-preemptive
    done.add(name)
print("all done at", time)

Output with AGING = False:

backup starts at 2000 after waiting 2000
all done at 2003

The backup runs only when no urgent job is left. With an endless stream, it would never run. This is starvation (also called indefinite blocking): a ready process waits forever because others always win. SJF and SRTF starve long jobs the same way.

Real-life example: a government office. VIP files always go first, so your file keeps getting skipped. A fair rule: any file waiting more than three days moves up the pile. That is aging: gradually raise the priority of a process the longer it waits.

Output with AGING = True (every 4 units of waiting lowers the priority number by 1):

backup starts at 16 after waiting 16
all done at 2003

After 16 units, priority 5 has aged to 1, it ties with the urgent jobs, and the tie goes to the earlier arrival (the backup). Starvation is gone.

Problem 7: a low task blocks the top task (priority inversion)

True story: Mars Pathfinder (1997). NASA's Pathfinder landed on Mars on 4 July 1997. Its computer ran the VxWorks real-time operating system. Three tasks matter:

Task Priority What it did
Information bus manager High Moved data in and out of a shared memory area, the "information bus"
Communications Medium Long-running communications work
Meteorological data gathering Low Published weather data through the bus

The bus was protected by a mutex (mutual-exclusion lock: a lock only one task can hold at a time).

  1. The low-priority weather task took the mutex.
  2. The high-priority bus task needed the same mutex, so it blocked, waiting for the low task.
  3. The medium-priority communications task became ready. It outranks the low task, so it preempted it and ran on. The low task could not run to release the mutex, so the high task waited behind the medium task.
  4. A watchdog timer (a hardware/software alarm that checks the system is still making progress) saw the bus task had not run in time and forced a total system reset. A few days after landing, Pathfinder kept resetting, losing data each time.

The highest-priority task was effectively running at the lowest priority: priority inversion.

The fix: priority inheritance. While a low-priority task holds a lock that a higher-priority task is waiting for, the low task temporarily inherits the higher priority. The medium task can no longer preempt it; it finishes its critical work, releases the lock, drops back to its own priority, and the high task runs immediately. On Pathfinder the mutex had been created with priority inheritance off; engineers used a C interpreter left enabled in the flight software to change the initialisation flags to on, and the resets stopped.

Source: Glenn Reeves' account, "What really happened on Mars?", https://www.cs.cornell.edu/courses/cs614/1999sp/papers/pathfinder.html (fetched 2 November 2026).

The whole chain

Step Problem Invention
1 Short jobs stuck behind a long one SJF, chosen from arrived processes
2 A tiny job arrives mid-run SRTF (compare with remaining time)
3 Is it the best? Swap argument: minimum average WT
4 Burst times are unknown Exponential averaging
5 Urgent isn't always short Priority scheduling
6 Low priority never runs Aging
7 Low task holds the top task's lock Priority inheritance

Algorithms at a glance

Algorithm Preemptive? Picks Optimal for avg WT? Starvation?
FCFS No Earliest arrival No No
SJF No Smallest burst Yes (non-preemptive) Yes (long jobs)
SRTF Yes Least remaining time Yes (overall) Yes (long jobs)
Priority (non-preemptive) No Most important No Yes (low priority)
Priority (preemptive) Yes Most important No Yes, fix with aging

Common mistakes

Mistake What you see Why Fix
Sorting all jobs by burst at time 0 P3 runs 0-1, arrived at 4, WT = -4 Ran a job that hadn't arrived Choose only from arrived, unfinished jobs
In SRTF, comparing with the running job's full burst wrong preemptions Must use the time left Compare with remaining time
Assuming smaller number = higher priority whole Gantt chart wrong Questions differ Read the convention first
Breaking ties at random different averages No tie rule Equal values: FCFS order
Letting an equal priority preempt extra switches, wrong WT Preempt only if strictly better <, not <=
Forgetting idle time when nobody has arrived negative waits The clock must jump Idle until the next arrival

Mini project: one simulator for four algorithms (plus aging)

def schedule(procs, policy, preemptive, age_every=None):
    """procs: (name, arrival, burst, priority). policy: 'sjf' or 'prio'."""
    left = {p[0]: p[2] for p in procs}
    time, gantt, ct, running = 0, [], {}, None
    while left:
        ready = [p for p in procs if p[1] <= time and p[0] in left]
        if not ready:
            time += 1
            continue
        def key(p):
            if policy == "sjf":
                return left[p[0]] if preemptive else p[2]
            boost = (time - p[1]) // age_every if age_every else 0
            return p[3] - boost             # aging: waiting lowers the number
        if preemptive or running not in left:
            running = min(ready, key=key)[0]
        if not gantt or gantt[-1][0] != running:
            gantt.append([running, time, time])
        left[running] -= 1
        time += 1
        gantt[-1][2] = time
        if left[running] == 0:
            del left[running]
            ct[running] = time
    wt = {p[0]: ct[p[0]] - p[1] - p[2] for p in procs}
    chart = "".join(f"| {n} {s}-{e} " for n, s, e in gantt) + "|"
    return chart, wt, sum(wt.values()) / len(wt)

jobs = [("P1", 0, 7, 3), ("P2", 2, 4, 1), ("P3", 4, 1, 4), ("P4", 5, 4, 2)]
for policy, pre in [("sjf", False), ("sjf", True), ("prio", False), ("prio", True)]:
    chart, wt, avg = schedule(jobs, policy, pre)
    print(f"{policy:4} preemptive={pre!s:5} {chart}  avg WT = {avg}")
chart, wt, avg = schedule(jobs, "prio", True, age_every=2)
print("prio + aging every 2:", chart, " avg WT =", avg)

Output:

sjf  preemptive=False | P1 0-7 | P3 7-8 | P2 8-12 | P4 12-16 |  avg WT = 4.0
sjf  preemptive=True  | P1 0-2 | P2 2-4 | P3 4-5 | P2 5-7 | P4 7-11 | P1 11-16 |  avg WT = 3.0
prio preemptive=False | P1 0-7 | P2 7-11 | P4 11-15 | P3 15-16 |  avg WT = 5.5
prio preemptive=True  | P1 0-2 | P2 2-6 | P4 6-10 | P1 10-15 | P3 15-16 |  avg WT = 5.0
prio + aging every 2: | P1 0-2 | P2 2-6 | P1 6-11 | P4 11-15 | P3 15-16 |  avg WT = 5.25

With aging, P1 (priority 3, waiting since 2) ages past P4 (priority 2, arrived at 5) and finishes earlier. Aging trades a little average waiting time for fairness. Try it: add response time, and count context switches.

Practice

1. SJF and SRTF: P1 (AT 0, BT 6), P2 (1, 8), P3 (2, 7), P4 (3, 3). Find the average TAT and WT for both.

Solution

SJF: | P1 0-6 | P4 6-9 | P3 9-16 | P2 16-24 |. CT = 6, 24, 16, 9; TAT = 6, 23, 14, 6 (average 12.25); WT = 0, 15, 7, 3 (average 6.25).

SRTF gives the same chart: at every arrival P1's remaining time (5, 4, 3) is the smallest, so no preemption happens. Preemptive algorithms don't always preempt.

2. Exponential averaging with α = 0.5, τ0 = 12, actual bursts 8, 10, 6. Find τ1, τ2, τ3.

Solution

τ1 = 0.5·8 + 0.5·12 = 10; τ2 = 0.5·10 + 0.5·10 = 10; τ3 = 0.5·6 + 0.5·10 = 8.

3. With α = 0.8, which matters more, the latest burst or history?

Solution

The latest burst: it gets weight 0.8, all history only 0.2. A high α reacts fast but is jumpy; a low α is smooth but slow to react.

4. Non-preemptive priority (smaller = higher): P1 (0, 5, 3), P2 (1, 2, 1), P3 (2, 4, 2). Find the average WT.

Solution

P1 0-5 (alone), then P2 (priority 1) 5-7, P3 7-11. WT = 0, 4, 5 → average 3. Preemptive would give P1 0-1, P2 1-3, P3 3-7, P1 7-11: WT = 6, 0, 1 → average 2.33.

5. Explain priority inversion with three tasks and how priority inheritance fixes it.

Solution

Low holds a lock; High needs it and blocks; Medium preempts Low, so Low can't release the lock and High waits for Medium: the top task behaves as if it had the lowest priority. With priority inheritance, Low runs at High's priority while High waits for its lock, so Medium can't preempt it; Low releases the lock quickly and drops back. (Another fix is the priority ceiling protocol: a task holding a lock runs at the highest priority of any task that may use it.)

6. Can SRTF starve a process? Give an example.

Solution

Yes. A job with burst 10 arrives at 0; a job with burst 2 arrives every 2 units. Each newcomer (2) beats the long job's remaining time, so the long job never finishes while short jobs keep coming. Aging (or a cap on waiting) fixes it.

Quick quiz

Process AT BT
P1 0 8
P2 1 4
P3 2 2

SRTF: what is the average waiting time? A. 2 B. 2.67 C. 3 D. 4.67

Answer

B. 2.67. Gantt: P1 0-1, P2 1-2, P3 2-4, P2 4-7, P1 7-14. WT: P1 = 14 − 0 − 8 = 6, P2 = 7 − 1 − 4 = 2, P3 = 0. Average = 8/3 = 2.67.

Interview questions

  1. What is SJF and why is it optimal? Run the shortest ready burst next; swapping any long-before-short pair lowers total waiting, so shortest-first minimises average WT (non-preemptive).
  2. SJF vs SRTF? SRTF is preemptive SJF: on each arrival, compare the newcomer's burst with the running process's remaining time.
  3. Why can't an OS implement SJF exactly? It doesn't know future burst lengths; it predicts them with exponential averaging.
  4. Write the exponential averaging formula and explain α. τ(n+1) = α t(n) + (1 − α) τ(n); α weights the latest burst against history.
  5. What is priority scheduling? Is SJF a special case? Run the most important ready process; yes, with priority = predicted burst.
  6. What is starvation? How does aging solve it? A ready process waiting forever; aging raises its priority the longer it waits.
  7. What is priority inversion? A high-priority task waits for a lock held by a low-priority task, while medium tasks preempt the low one.
  8. How do you fix priority inversion? Priority inheritance (or priority ceiling).
  9. Tell the Mars Pathfinder story in 30 seconds. Low weather task held the bus mutex, medium comms task preempted it, the high bus task missed its deadline, the watchdog reset the system; enabling priority inheritance on the mutex fixed it.
  10. Which algorithms can cause starvation? SJF, SRTF, priority (both kinds); FCFS and Round Robin do not.

Glossary

Term Meaning in plain words Example
SJF (Shortest Job First) Non-preemptive: run the ready process with the smallest burst next 1 page before 200 pages
SRTF (Shortest Remaining Time First) Preemptive SJF: run the process with the least time left; re-check on arrivals P3 (1) preempts P2 (2 left)
Remaining time The part of a burst still to run P1 7 − 2 = 5 left
Preemptive SJF / SRTN Other names for SRTF —
Optimality of SJF No other non-preemptive order gives a lower average waiting time swap argument
Swap argument Moving a shorter job ahead of a longer neighbour lowers total waiting 10 → 1
Burst prediction Estimating the next CPU burst from past bursts commute guess
Exponential averaging τ(n+1) = α t(n) + (1 − α) τ(n) 0.5·40 + 0.5·30 = 35
t(n) The n-th actual CPU burst 6
τ(n) (tau) The prediction for the n-th burst 10
α (alpha) Weight of the latest burst, 0 to 1 0.5
Priority scheduling Run the most important ready process triage
Priority number Number expressing importance; usually smaller = higher 1 is top
Internal / external priority Computed by the OS / set from outside I/O ratio / paid user
Preemptive priority A more important arrival takes the CPU P2 preempts P1
Non-preemptive priority Priority decides only when the CPU is free P1 keeps running
Starvation (indefinite blocking) A ready process waits forever because others always win the backup waits 2000
Aging Raising a process's priority the longer it waits +1 every 4 units
Priority inversion A high-priority task waits for a low one, while a medium one runs Mars Pathfinder
Priority inheritance A lock holder temporarily gets the priority of the highest task waiting for it weather task runs at high
Priority ceiling A lock holder runs at the highest priority of any task that may use the lock alternative fix
Mutex A lock only one task can hold at a time the bus lock
Watchdog timer An alarm that resets the system if work stops progressing Pathfinder resets
Real-time operating system (RTOS) An OS built to meet deadlines VxWorks
Context switch Saving one process's state and loading another's 5 in SRTF example
Tie-breaking Rule for equal values; usually FCFS P2 before P4
Gantt chart Time bar of who ran when | P1 0-2 | P2 2-4 |

Summary

  • SJF runs the shortest burst among the processes that have arrived; ties go FCFS; it is non-preemptive.
  • SRTF is preemptive SJF: at each arrival, compare with the running process's remaining time.
  • Both give the minimum average waiting time (swap argument), but need burst times, which an OS predicts with exponential averaging τ(n+1) = α t(n) + (1 − α) τ(n).
  • Priority scheduling runs the most important process (read the number convention); SJF is priority = burst.
  • SJF, SRTF and priority can cause starvation; aging fixes it.
  • Priority inversion (high waits for a lock held by low while medium runs) is fixed by priority inheritance, as on Mars Pathfinder in 1997.

Next episode: CPU scheduling 3: Round Robin, HRRN, multilevel (feedback) queues, multiprocessor and real-time scheduling, and Linux.