CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 3 of 7 · 2 min read

Aging

In plain words: At the hospital, if emergency patients keep arriving, the sprained wrist waits for ever. This is starvation (page 2). The remedy is to let the wait itself raise a patient's urgency.

With fixed priorities, a low-priority process can starve. A made-up example: process L (priority 10, needing 4 units) arrives at time 0. At times 0, 3, 6 and so on, a new priority-5 job of 3 units arrives, so the processor is always busy with a more important job, and L never runs.

Aging repairs this. The system raises the priority of a process by one step for every fixed amount of time it waits. In the example, give L one step of priority for every 6 time units of waiting. L starts at 10 and loses one per 6 units: at time 30, it has waited 30 units, five steps, and its priority is 5, the same as the other jobs. Ties go to the earlier arrival, which is L. L runs from 30 to 34 and finishes.

Time Priority of L
0 10
6 9
12 8
18 7
24 6
30 5 (runs now)

A simulation of this example gave the finish time 34 with aging and no finish at all without it (it was stopped at 80 units). So no process waits for ever, since priority rises until the process is the best one.

Aging

Aging is a technique that gradually raises the priority of a process the longer it waits in the ready queue, so that every process eventually becomes the highest priority and cannot be starved.

Example: a process that gains one priority step per 6 time units of waiting rises from priority 10 to 5 in 30 units.

Check yourself: 1. Why does a low-priority process starve without aging? 2. What was the priority of L at time 18? 3. What would change if L gained one step per 3 units?