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).
- The low-priority weather task took the mutex.
- The high-priority bus task needed the same mutex, so it blocked, waiting for the low task.
- 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.
- 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
- 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).
- SJF vs SRTF? SRTF is preemptive SJF: on each arrival, compare the newcomer's burst with the running process's remaining time.
- Why can't an OS implement SJF exactly? It doesn't know future burst lengths; it predicts them with exponential averaging.
- Write the exponential averaging formula and explain α. τ(n+1) = α t(n) + (1 − α) τ(n); α weights the latest burst against history.
- What is priority scheduling? Is SJF a special case? Run the most important ready process; yes, with priority = predicted burst.
- What is starvation? How does aging solve it? A ready process waiting forever; aging raises its priority the longer it waits.
- 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.
- How do you fix priority inversion? Priority inheritance (or priority ceiling).
- 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.
- 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.