Priority & Round Robin Scheduling

By the end of this lesson you will be able to schedule processes by priority and by round robin, fix starvation with aging, and choose a sensible time quantum.

FCFS, SJF and SRTF choose by arrival or by length. Real systems also care about importance: a phone call must ring now, while a backup can wait. They also care about fairness, so that every app keeps responding. Priority scheduling handles the first need and round robin the second.

Priority scheduling

In priority scheduling, every process has a priority number and the CPU goes to the most important ready process. In this course a smaller number means higher priority, which is the usual exam convention. Always check the convention in a question, because some books use the opposite.

A hospital emergency ward is the classic picture. A patient with chest pain is seen before someone with a sprained ankle, even if the ankle patient came first.

Like SJF, priority scheduling comes in two forms:

• Non-preemptive: the chosen process runs its whole burst, even if a more important one arrives.
• Preemptive: a newly arrived process with higher priority takes the CPU immediately.

Use these four processes:

Step 1: trace the preemptive version by hand. P1 starts at 0. At 1, P2 (priority 1) arrives and preempts P1. P2 runs to 4. At 4, the ready processes are P1 (3), P3 (4) and P4 (2), so P4 runs 4 to 6. Then P1 runs 6 to 10 and P3 runs last, 10 to 11.

Step 2: run both versions.

# (name, arrival, burst, priority) - smaller number = more important
procs = [("P1", 0, 5, 3), ("P2", 1, 3, 1), ("P3", 2, 1, 4), ("P4", 3, 2, 2)]

def priority_np(procs):
    todo = list(procs)
    chart, clock = [], 0
    while todo:
        ready = [p for p in todo if p[1] <= clock]
        if not ready:
            clock = min(p[1] for p in todo); continue
        job = min(ready, key=lambda p: (p[3], p[1]))
        todo.remove(job)
        chart.append((job[0], clock, clock + job[2]))
        clock += job[2]
    return chart

def priority_p(procs):
    left = {p[0]: p[2] for p in procs}
    info = {p[0]: p for p in procs}
    chart, clock = [], 0
    while any(left.values()):
        ready = [n for n in left if left[n] and info[n][1] <= clock]
        name = min(ready, key=lambda n: (info[n][3], info[n][1])) if ready else "idle"
        if chart and chart[-1][0] == name:
            chart[-1] = (name, chart[-1][1], clock + 1)
        else:
            chart.append((name, clock, clock + 1))
        if name != "idle":
            left[name] -= 1
        clock += 1
    return chart

def avg_wait(procs, chart):
    end = {n: e for n, s, e in chart}
    waits = [end[n] - at - bt for n, at, bt, pr in procs]
    return sum(waits) / len(waits)

for label, fn in [("Non-preemptive", priority_np), ("Preemptive", priority_p)]:
    chart = fn(procs)
    print(label, chart)
    print("  average WT =", avg_wait(procs, chart))

Non-preemptive [('P1', 0, 5), ('P2', 5, 8), ('P4', 8, 10), ('P3', 10, 11)]
  average WT = 4.25
Preemptive [('P1', 0, 1), ('P2', 1, 4), ('P4', 4, 6), ('P1', 6, 10), ('P3', 10, 11)]
  average WT = 3.5

Notice that SJF is really a special case of priority scheduling, where the priority is the burst length.

Starvation and aging

Priority scheduling has a serious weakness. If important processes keep arriving, a low-priority process may never run. This is starvation (also called indefinite blocking).

The standard cure is aging: the longer a process waits, the better its priority becomes. Eventually even the least important job becomes important enough to run. It is like a token system at a government office that also serves anyone who has waited more than two hours.

# A low-priority report job waits while urgent jobs keep arriving.
priority = {"report": 9}
AGE_EVERY = 4          # improve priority by 1 for every 4 time units of waiting
URGENT = 3             # each new urgent job has priority 3

for t in range(0, 41, AGE_EVERY):
    if t > 0:
        priority["report"] = max(0, priority["report"] - 1)
    winner = "report" if priority["report"] < URGENT else "urgent job"
    print(f"t={t:2}: report priority={priority['report']}, CPU goes to {winner}")
    if winner == "report":
        break

t= 0: report priority=9, CPU goes to urgent job
t= 4: report priority=8, CPU goes to urgent job
t= 8: report priority=7, CPU goes to urgent job
t=12: report priority=6, CPU goes to urgent job
t=16: report priority=5, CPU goes to urgent job
t=20: report priority=4, CPU goes to urgent job
t=24: report priority=3, CPU goes to urgent job
t=28: report priority=2, CPU goes to report

Without aging the report would wait for ever. With aging it gets the CPU at time 28.

Round robin

Round robin (RR) is designed for time-sharing. The ready queue is a circle. Each process gets the CPU for at most one time quantum (also called a time slice), say 2 units. If it is not finished, it goes to the back of the queue. RR is always preemptive.

Picture students taking turns at a single computer in a school lab: each gets ten minutes, then the next student sits down, and you rejoin the line if you need more time.

One rule decides many exam answers: if a new process arrives at the same moment another's quantum ends, the new arrival joins the queue first, then the preempted process goes behind it. The code below follows this rule. Some questions state a different rule, so read carefully.

Step 1: trace this by hand with quantum 2, using the same four processes without priorities. P1 runs 0 to 2. Meanwhile P2 (at 1) and P3 (at 2) joined the queue, and then P1 goes behind them.

Step 2: run the simulation and compare it with your trace.

from collections import deque

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

def round_robin(procs, quantum):
    procs = sorted(procs, key=lambda p: p[1])
    left = {n: bt for n, at, bt in procs}
    queue, chart, clock, i = deque(), [], 0, 0
    while i < len(procs) or queue:
        while i < len(procs) and procs[i][1] <= clock:   # admit arrivals
            queue.append(procs[i][0]); i += 1
        if not queue:                                    # CPU idle
            clock = procs[i][1]; continue
        name = queue.popleft()
        run = min(quantum, left[name])
        chart.append((name, clock, clock + run))
        clock += run
        left[name] -= run
        while i < len(procs) and procs[i][1] <= clock:   # arrivals during this slice
            queue.append(procs[i][0]); i += 1
        if left[name]:
            queue.append(name)                           # back of the line
    return chart

chart = round_robin(procs, 2)
print(chart)
end, first = {}, {}
for n, s, e in chart:
    first.setdefault(n, s); end[n] = e
for n, at, bt in procs:
    print(f"{n}: CT={end[n]:2} WT={end[n] - at - bt} RT={first[n] - at}")

[('P1', 0, 2), ('P2', 2, 4), ('P3', 4, 5), ('P1', 5, 7), ('P4', 7, 9), ('P2', 9, 10), ('P1', 10, 11)]
P1: CT=11 WT=6 RT=0
P2: CT=10 WT=6 RT=1
P3: CT= 5 WT=2 RT=2
P4: CT= 9 WT=4 RT=4

Average waiting time is higher than SRTF (4.5 here), but look at the response times: every process starts within 4 units. That is what interactive users feel.

Choosing the time quantum

• Quantum too large: RR behaves just like FCFS and response time suffers.
• Quantum too small: the CPU spends a big share of its time on context switches instead of real work.

If each quantum is q and each context switch costs s, then at best the CPU does useful work q / (q + s) of the time. With q = 4 ms and s = 1 ms, only 80% is useful. A common rule of thumb is that most CPU bursts should finish within one quantum. Modern systems use quanta of a few milliseconds while context switches take microseconds.

Common mistakes

• Assuming the priority direction. Always check whether a small number means high or low priority.
• Putting the preempted process ahead of a new arrival in RR. Unless the question says otherwise, arrivals at the same instant join the queue first.
• Forgetting that RR with a huge quantum is FCFS. Exams test this.

Key points

• Priority scheduling runs the most important ready process; it can be preemptive or not.
• Low-priority processes can starve; aging raises their priority as they wait.
• Round robin gives each process one time quantum in turn and then sends it to the back of the queue.
• RR gives good response time but often higher average waiting time than SRTF.
• A very large quantum turns RR into FCFS; a very small one wastes time on context switches.

for q in [1, 2, 5]:
    chart = round_robin(procs, q)
    end = {}
    for n, s, e in chart:
        end[n] = e
    avg = sum(end[n] - at - bt for n, at, bt in procs) / len(procs)
    print(f"q={q}: {len(chart)} slices, average WT = {avg}")

q=1: 11 slices, average WT = 3.75
q=2: 7 slices, average WT = 4.5
q=5: 4 slices, average WT = 4.0