Difficulty: Beginner
What is starvation in CPU scheduling? How does aging solve it, and what is priority inversion?
Starvation is one of those words that sounds vivid, and the concept truly is intuitive once you picture the scenario. Imagine a busy emergency room that always treats the most critical patient first. If critical patients keep arriving all day, a patient with a sprained ankle may never be seen. Nobody made a mistake; the policy itself has a hole. That is starvation, sometimes called indefinite blocking: a ready process is perpetually denied the CPU (or another resource) because the scheduler always prefers others.
Which algorithms are prone to it? Any algorithm that favours some processes systematically. Priority scheduling is the classic case: a steady stream of high-priority processes can keep a low-priority one waiting forever. Shortest Job First and SRTF have the same disease, because a long job can be pushed back indefinitely by newly arriving short jobs. FCFS and Round Robin do not starve anyone, since every ready process eventually reaches the front of the queue. There is a memorable story that when the IBM 7094 at MIT was shut down in 1973, they found a low-priority job that had been submitted in 1967 and had never run.
The standard cure is aging. The scheduler gradually increases the priority of a process the longer it waits in the ready queue. For example, raise priority by one level every 15 minutes, or in modern terms every few milliseconds of waiting. Eventually even the lowest-priority process climbs high enough to be scheduled. Once it runs, its priority can be reset. Aging converts a strict priority scheme into one with a bounded waiting time. Multilevel feedback queues use the same principle by promoting processes that have waited too long in a lower-priority queue, and Linux's CFS avoids starvation structurally through virtual runtime accounting.
Do not confuse starvation with deadlock. In deadlock, processes are blocked forever waiting on each other in a cycle, and none can progress. In starvation, the system as a whole makes progress; only certain processes are unlucky. Deadlock is a permanent circular wait; starvation is unfairness which might be resolved if the higher-priority load subsides.
Now the related and very popular follow-up: priority inversion. Suppose a low-priority task L holds a lock. A high-priority task H arrives and needs that lock, so H blocks and waits for L. Meanwhile, a medium-priority task M becomes ready. M has higher priority than L, so it preempts L, and L cannot release the lock. Effectively M, though lower priority than H, has blocked H indefinitely. This happened in reality: the Mars Pathfinder rover in 1997 kept resetting because of priority inversion on a shared bus, and engineers fixed it remotely by enabling priority inheritance.
Priority inheritance is the standard fix. When H blocks on a lock held by L, L temporarily inherits H's priority, so M cannot preempt it. L finishes its critical section quickly, releases the lock, and reverts to its normal priority. The alternative is the priority ceiling protocol, where a lock is assigned the highest priority of any task that may use it. Either way, the lesson is that priority scheduling and locks interact, which is critical for real-time systems in the automotive and embedded domains.
starvation, aging, priority inversion, priority scheduling