CPU priorities, aging and switching overhead

Goals and assumptions

Extend the existing FCFS/SJF/SRTF/RR lesson with priority scheduling, starvation/aging, explicit context-switch costs and a small multilevel-feedback trace. Prerequisite: arrival, burst, completion, turnaround, waiting and response. Unless changed in an example, one CPU is used, there is no I/O, bursts are known, overhead is zero, smaller priority numbers mean higher priority, and ties prefer earlier arrival then lower process number. Priorities are policy parameters; their numeric direction must never be guessed.

1. Priority is a dispatch rule

Imagine a clinic that assigns urgency levels. Choosing the highest-urgency waiting patient is a priority rule. Whether a new urgent arrival interrupts an examination already in progress is a separate preemption rule. Similarly, priority scheduling can be preemptive or non-preemptive. A priority is not necessarily a short burst or an early arrival.

Use P1:(arrival 0,burst 5,priority 3), P2:(1,2,1), P3:(2,1,2). Under non-preemptive priority, only P1 is ready at time 0, so it runs to completion despite later arrivals. Then P2 outranks P3:

[0,5) P1; [5,7) P2; [7,8) P3.

Completion times in P1,P2,P3 order are 5,7,8. Turnarounds C−A are 5,6,6; waits T−B are 0,4,5; responses equal waits because each runs only once. Average waiting=3.

2. Preemption changes the trace

Under preemptive priority with the same workload, P2 arrives at time 1 with higher priority and interrupts P1. P3 arrives at 2, but it is lower priority than running P2, so it does not preempt P2. After P2 finishes at 3, P3 outranks the remaining P1:

[0,1) P1; [1,3) P2; [3,4) P3; [4,8) P1.

Completion times are 8,3,4; turnarounds 8,2,2; waits 3,0,1; responses 0,0,1. P1's three waiting units are [1,4), after it first ran. Average waiting=4/3. This improvement belongs to this workload; priority scheduling does not minimize every metric for every workload. Only a strictly higher priority arrival preempts here; a same-priority arrival follows the declared tie convention.

3. Starvation and aging

A low-priority job can remain ready indefinitely if higher-priority work keeps arriving. It is not blocked on I/O, and the system can keep making progress while that one job starves. Aging gradually improves priority based on waiting. Define a specific example: effective priority=max(1,base priority−floor(ready-wait/2)); running and blocked time do not increase ready-wait. A base-5 job that has accumulated 6 ready-wait units has effective priority max(1,5−3)=2.

Aging is a policy family, not one universal formula. A fairness claim depends on the ceiling/floor, tie rules, arrivals, execution lengths and scheduling assumptions. Merely saying “aging exists” does not prove a finite real-time deadline for every job. Priority inversion is distinct: a high-priority thread can wait for a lock held by a low-priority thread while intermediate-priority work delays the holder. Priority inheritance can let the holder temporarily run at a waiting higher priority; it is not the same as aging every old ready job.

4. Count overhead as time, not useful service

Now change the model. P1 and P2 both arrive at 0, each needs 4 CPU service units, and RR starts with P1 using quantum 2. Every change from one process to the other costs 1 unit; initial dispatch and final termination cost zero. There are no other events or I/O, and all unfinished processes remain ready during switching. Trace:

[0,2) P1; [2,3) switch; [3,5) P2; [5,6) switch; [6,8) P1; [8,9) switch; [9,11) P2.

Useful service=8 and switching=3, so elapsed completion span=11. Useful CPU-service fraction over [0,11) is 8/11; if an operating-system measurement counts switching as CPU busy, its busy fraction would differ. Completion times are 8 and 11; turnaround is the same because both arrivals are 0; ready waiting including dispatch delays is 4 and 7. First response times are 0 and 3. The switch interval is not credited toward either process's requested burst.

With quantum 4 instead, P1 runs 0–4, switch 4–5, P2 runs 5–9. Useful fraction rises to 8/9, but P2 first waits 5 rather than 3. This makes the overhead/responsiveness tradeoff visible. A quantum expiration with no actual process change need not incur the same cost under a differently stated model; count the events the question charges.

5. Multilevel feedback requires explicit rules

A multilevel queue can separate fixed job classes. A multilevel feedback queue (MLFQ) allows jobs to move between levels according to observed behavior. It does not require advance knowledge of each job's total burst. Exact policies vary, so a name alone is not enough for a numeric trace.

Small specified example: Q0 has higher priority and quantum 1; Q1 has quantum 2. New jobs enter Q0; consuming a whole Q0 quantum without finishing demotes a job to Q1. Use FIFO within a level and zero overhead. P1 and P2 arrive at 0 in that order, with service 3 and 1. P1 runs 0–1 and moves to Q1 with 2 left. P2 runs in Q0 on 1–2 and finishes. P1 then runs in Q1 on 2–4 and finishes. A periodic priority boost is one possible anti-starvation feature, but no boost is assumed in this tiny trace.

Exam checklist

Specify numeric priority direction, preemption, ties and aging formula. Keep remaining burst separate from priority. Mark switching intervals explicitly, state the utilization window and definition, and write every MLFQ movement rule before tracing it.

Original practice: six single-correct MCQs

Choose exactly one option. Each question states its own required assumptions.

CP01. Lower number means higher priority. P1=(A0,B5,p3), P2=(A1,B2,p1), P3=(A2,B1,p2). Under non-preemptive priority with zero overhead/no I/O, what is average waiting?

A. 4/3 B. 3 C. 5 D. 0

Answer: B

A: 4/3 is the preemptive result for this workload.

B: Order P1,P2,P3 yields waits 0,4,5; average 3.

C: Five is P3 waiting alone.

D: P2 and P3 wait while P1 executes.

CP02. Lower number means higher priority. P1=(A0,B5,p3), P2=(A1,B2,p1), P3=(A2,B1,p2). Preempt immediately for strictly higher priority, with no overhead/I/O. What is P1 total waiting?

A. 0 B. 1 C. 3 D. 5

Answer: C

A: Zero is P1 first-response delay.

B: One is P1 initial execution duration.

C: P1 runs 0–1, waits 1–4, runs 4–8; wait=3.

D: Five is its required CPU service.

CP03. Aging uses effective priority=max(1,base−floor(ready-wait/2)), smaller is higher. Base priority is 5 and accumulated ready-wait is 6. What is effective priority?

A. 1 B. 2 C. 3 D. 5

Answer: B

A: The floor at 1 is not reached yet.

B: floor(6/2)=3; max(1,5−3)=2.

C: Three is the amount subtracted, not the result.

D: This ignores aging.

CP04. Two jobs arrive at 0, each needing 4 CPU units. RR q=2 starts P1. Switching between processes costs 1; initial dispatch and final termination cost zero. Useful-service fraction until both finish is?

A. 1 B. 8/9 C. 8/11 D. 8/12

Answer: C

A: This ignores three charged switches.

B: 8/9 applies to one switch, as with q=4 here.

C: Four run segments contain 8 service units and three switches: 8/(8+3).

D: There are three switches, not four under the stated endpoints.

CP05. New jobs enter Q0. Q0 outranks Q1. Q0 quantum=1; a job using its whole quantum unfinished moves to Q1 with quantum=2. FIFO within a level, no overhead. P1 then P2 arrive at 0, bursts 3 and 1. When does P2 finish?

A. 1 B. 2 C. 3 D. 4

Answer: B

A: P1 uses the first Q0 quantum.

B: P1 runs 0–1 and demotes; P2 runs 1–2 in Q0 and finishes.

C: P2 need not wait for demoted P1 to finish.

D: Four is P1 completion in this trace.

CP06. A high-priority thread waits for a lock held by a low-priority thread; medium-priority CPU work delays the lock holder. Which mechanism directly addresses this dependency by raising the holder temporarily?

A. Priority inheritance B. FIFO disk scheduling C. Increasing every CPU burst D. Page replacement

Answer: A

A: The holder can inherit the waiting higher priority to release the lock sooner.

B: Disk ordering does not change this CPU/lock dependency.

C: Longer required service does not fix inversion.

D: Page eviction is unrelated to the described priority dependency.

Sources and scope

This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.

• Official GATE 2026 CS syllabus, Section 8
• OSTEP: Scheduling Introduction
• OSTEP: Multilevel Feedback Queue

Sources checked 2026-10-14.