Questions: Scheduling Fairness and Starvation Prevention

Question 1

A system uses strict priority scheduling. Low-priority process P1 has been waiting 10 hours while a continuous stream of high-priority processes arrives. According to strict priority scheduling, P1:

• A. Will eventually run after all currently queued high-priority processes complete
• B. May never run if high-priority processes continue arriving faster than they finish
• C. Will be automatically promoted to high priority after a threshold wait time
• D. Will run because strict priority scheduling uses round-robin as a tiebreaker between priority levels

Answer: (B)

This is the definition of starvation: a process that is perpetually bypassed because higher-priority processes keep arriving. Strict priority scheduling has no mechanism to help P1 — it simply always picks the highest-priority ready process. Automatic promotion (option C) is the aging solution, which addresses starvation — but it is not part of strict priority scheduling by default. Starvation is what motivates aging as an add-on.

Question 2

Priority inversion occurs when:

• A. A high-priority process is blocked waiting for a lock held by a low-priority process, which is then preempted by a medium-priority process — indirectly blocking the high-priority one
• B. Two high-priority processes compete for the same CPU time slice simultaneously
• C. A low-priority process runs before a high-priority one because aging has boosted its priority
• D. The scheduler runs out of priority levels and demotes all processes to the same tier

Answer: (A)

Priority inversion is the specific scenario where a high-priority process is effectively blocked by a medium-priority one through an indirect chain: high waits for a lock held by low; medium preempts low; now high is blocked while medium runs — despite medium having lower priority than high. Priority inheritance fixes this by temporarily boosting the lock holder (low) to the priority of its highest-priority waiter, so medium cannot preempt it.

Question 3

Aging prevents starvation by gradually increasing the priority of a process the longer it waits in the ready queue.

• T. True
• F. False

Answer: True

Aging is the standard solution to starvation in priority-based schedulers. By incrementally raising a waiting process's priority, aging ensures that even the lowest-priority process will eventually reach a priority level high enough to be scheduled. This converts a system with potential indefinite postponement into one with bounded waiting time.

Question 4

A proportional-share scheduler like Linux's CFS guarantees that most process receives exactly equal CPU time regardless of its share weight.

• T. True
• F. False

Answer: False

Proportional-share schedulers allocate CPU in proportion to each process's assigned shares — a process with twice the shares gets roughly twice the CPU time, not equal time. CFS specifically tracks 'virtual runtime' and always schedules the process with the least accumulated virtual runtime, scaled by its weight. Equality is a special case when all processes have equal shares; the general guarantee is proportionality, not equality.

Question 5

Explain why priority inheritance is needed to solve priority inversion, and why simply permanently raising the lock holder's priority to 'high' would be wrong.

Model answer: Priority inheritance temporarily elevates the lock holder's priority to match the highest-priority process waiting for the lock. Once the lock is released, the holder's priority reverts to normal. This ensures the lock holder is not preempted before releasing the resource, unblocking the high-priority waiter quickly. Permanently raising the low-priority process's priority would be wrong because it would change its scheduling behavior for all future work — giving it unfair CPU access even after the contested lock is released — and could itself cause starvation for other medium-priority processes.

The key is that the priority boost is scoped to the lock-holding period only. The goal is to eliminate the indirect blocking chain, not to fundamentally reassign priorities.