Priority scheduling, starvation and aging; highest response ratio next

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. When does SRTF re-decide? from Lesson 2.1.2
2. Average WT of the running example under FCFS? from Lesson 2.1.1
3. What does fork return in the child? from Lesson 1.1.2

1 · The Hook

In a hospital, a heart attack is treated before a sprained ankle regardless of who came first: priority scheduling. But if serious cases keep arriving, the sprained ankle may wait forever. The cure is aging: the longer you wait, the more important you become. GATE asks traces of both versions and the response ratio formula that builds aging in.

3 · Core Concept

Predict First — the answer

It may never run: starvation. Aging raises its priority over time so it eventually runs.

In plain words

Each process has a priority number; the scheduler always picks the most important ready process. In the pre-emptive version, a more important arrival interrupts the running one. To stop unimportant processes waiting forever, increase their importance as they wait (aging), or use a ratio that grows with waiting time (HRRN).

1. Priority scheduling

• Convention here: smaller number = higher priority (questions always say).
• Non-pre-emptive: when the CPU is free, run the highest-priority ready process to completion.
• Pre-emptive: if a higher-priority process arrives, pre-empt the running one.
• SJF is priority scheduling with priority = burst length.

Running example (priorities P1 3, P2 1, P3 4, P4 2, P5 5):

• Non-pre-emptive: P1 0–8 (only one there), then P2 8–12, P4 12–17, P3 17–26, P5 26–28. Average WT = 53/5 = 10.6.
• Pre-emptive: P1 0–1, P2 (priority 1) pre-empts: 1–5, then P4 5–10, P1 10–17, P3 17–26, P5 26–28. Average WT = 48/5 = 9.6.

2. Starvation and aging

Low-priority processes may wait indefinitely. Aging: gradually increase the priority of processes that wait long (e.g. +1 every 15 minutes).

3. Highest Response Ratio Next (HRRN)

Non-pre-emptive. When the CPU is free, compute for each ready process response ratio = (waiting time + burst time) / burst time, and pick the largest. Short jobs get high ratios quickly, but long jobs' ratios grow while they wait, so nobody starves. Running example at t = 8 (after P1): P2 (7 + 4)/4 = 2.75, P3 (6 + 9)/9 ≈ 1.67, P4 (5 + 5)/5 = 2, P5 (4 + 2)/2 = 3 → P5 next. Then at t = 10: P2 (9 + 4)/4 = 3.25, P3 (8 + 9)/9 ≈ 1.89, P4 (7 + 5)/5 = 2.4 → P2.

4 · Visual

Pre-emptive priority on the running example (smaller = higher)

| P1 | P2 (1)  | P4 (2)    | P1 (3)        | P3 (4)            | P5 |
0    1         5           10              17                  26   28

5 · Worked Examples

Example 1 Easy

All arrive at 0: P1 (BT 10, pr 3), P2 (1, 1), P3 (2, 4), P4 (1, 5), P5 (5, 2). Non-pre-emptive priority order?

Solution

P2, P5, P1, P3, P4.

Example 2 Medium

Average waiting time for the Easy example?

Solution

Order P2 0–1, P5 1–6, P1 6–16, P3 16–18, P4 18–19. Waits: P1 6, P2 0, P3 16, P4 18, P5 1 → 41/5 = 8.2.

Example 3 GATE

HRRN: at time 20 the CPU is free. Ready: A (waiting 10, burst 5), B (waiting 6, burst 2). Which runs?

Solution

A: 15/5 = 3; B: 8/2 = 4 → B.

6 · GATE Traps

• Check which way the priority numbers go (small = high is common, not universal).
• Pre-emptive priority re-decides at every arrival, like SRTF.
• HRRN is non-pre-emptive; the ratio uses waiting time so far.
• Aging fixes starvation; it is not an algorithm on its own.

7 · Memory Hook

"Most important first; age the forgotten; HRRN = (wait + burst)/burst."

8 · Connect the Dots

Chapter 2.1 is complete. None of these algorithms guarantees every process a quick turn. Chapter 2.2 introduces round robin, the basis of time-sharing, where each process gets the CPU for a small slice in turn.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — Priority

Running example under non-pre-emptive priority: average waiting time?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Pre-emptive priority

Running example under pre-emptive priority: completion time of P1?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Priority, all at 0

All arrive at 0: P1 (BT 10, pr 3), P2 (1, 1), P3 (2, 4), P4 (1, 5), P5 (5, 2). Non-pre-emptive priority: average waiting time?

Numerical answer: ________

Q4 · NAT · 1 mark(s) — Response ratio

A process has waited 12 ms and needs 4 ms. Its response ratio?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Starvation

Which technique prevents starvation in priority scheduling?

1. (A) Pre-emption
2. (B) FCFS tie-breaking
3. (C) A larger time quantum
4. (D) Aging

10 · Rule Card

• Priority: pick the most important ready process (state the direction of numbers); non-pre-emptive or pre-emptive.
• Starvation of low priorities; aging raises priority over time.
• HRRN: non-pre-emptive; pick the largest (W + S)/S; no starvation.
• SJF = priority by burst length.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

priority schedulingpre-emptive and non-pre-emptive prioritystarvationaginghighest response ratio nextresponse ratio