Multilevel queues and real-time scheduling

Why it exists

FCFS, SJF, priority and round robin each fit one kind of system and fail in another. Real systems mix kinds of work: interactive jobs that want a quick response, batch jobs that want throughput, system processes that must not be delayed. A single queue and a single rule cannot serve all of them. Multilevel queues keep one queue per kind of work; the feedback queue lets a process move between queues according to how it behaves, which approximates shortest-job-first without knowing the bursts in advance. And in real-time systems the question is not "how fast on average?" but "does every job finish before its deadline?", which needs different algorithms (rate monotonic, earliest deadline first) and a test of whether a task set can be scheduled at all.

Prerequisites

You need CPU scheduling (FCFS, SJF, SRTF, turnaround, waiting and response time) and priority and round-robin scheduling (quantum, preemption, starvation and aging). The part on priority inversion uses locks, see critical sections and semaphores.

Precise definitions

Multilevel queue. The ready queue is split into separate queues by the kind of process (for example system, interactive, batch). A process stays in its queue for ever. Each queue has its own algorithm (round robin for interactive, FCFS for batch). The queues are scheduled against each other either by fixed priority (a lower queue runs only when all higher queues are empty; starvation of the low queues is possible) or by time slicing between queues (for example 80 per cent of the time to the interactive queue, 20 per cent to batch).

Multilevel feedback queue. Like the multilevel queue, but a process moves between queues. The scheduler is defined by: the number of queues, the algorithm and quantum of each queue, the rule to move a process down (it used its whole quantum: it is CPU-bound), the rule to move it up (it waited too long: aging; or it gave up the CPU before the quantum ended), and the queue that a new process enters. The version used on this page: three queues with quanta 2, 4 and FCFS; a new process enters the top queue; using the whole quantum moves it one queue down; a ready process in a higher queue pre-empts a running process of a lower queue.

Periodic real-time task. A task $\tau_i$ with period $T_i$ and worst-case execution time $C_i$ releases a job every $T_i$ time units; each job must finish within its relative deadline $D_i$ after its release (usually $D_i = T_i$). Utilisation of a set: $U = \sum_i C_i / T_i$. Hard real time: a missed deadline is a failure; soft real time: it only lowers the quality.

Rate-monotonic (RM) scheduling. Static priorities: the shorter the period, the higher the priority; preemptive. Earliest-deadline-first (EDF). Dynamic priorities: at every moment the ready job with the nearest absolute deadline runs; preemptive. (Absolute deadline of a job = its release time plus $D_i$.)

Priority inversion. A high-priority job waits for a lock held by a low-priority job, and a medium-priority job keeps the low one from running, so the high-priority job is delayed by a job of lower priority. Priority inheritance: the lock holder runs with the priority of the highest job it blocks, until it releases the lock.

How it works

The feedback queue

Four processes with bursts 9, 3, 2 and 5. Everything enters the top queue with a quantum of 2. $P_1$ runs 2 units and has not finished, so it sinks to the middle queue; the same for $P_2$; $P_3$ (burst 2) finishes inside its first quantum and never leaves the top. When $P_4$ arrives at time 6 it enters the top queue and runs first, ahead of the older but lower $P_1$. The long process $P_1$ ends in the last queue, which is FCFS, and runs last. The short jobs have been favoured without anyone knowing their bursts: a job that is short finishes while it is still in a high queue.

On a mix of one long and four short jobs the feedback queue has an average response time close to that of SRTF (which needs to know the bursts), a lower turnaround than round robin and a far lower one than FCFS.

Real-time: rate monotonic and earliest deadline first

Two tasks: $T_1$ (period 5, needs 2) and $T_2$ (period 7, needs 4). Utilisation $2/5 + 4/7 = 0.971$.

Rate monotonic gives $T_1$ the higher priority. $T_2.1$ (released at 0, deadline 7) gets the CPU only between the jobs of $T_1$ and has not finished at time 7: deadline missed. The CPU is almost fully used and still a job is late, because the fixed priorities cannot move the work around. The same tasks with EDF:

At time 5, the new job $T_1.2$ (deadline 10) has a later deadline than $T_2.1$ (deadline 7), so $T_2.1$ keeps the CPU and finishes in time. No job misses its deadline in the whole hyperperiod (35 time units).

Is the task set schedulable?

For deadline equal to period and one processor, two classical results (Liu and Layland):

• EDF meets all deadlines if and only if $U \le 1$.
• RM meets all deadlines if $U \le n(2^{1/n} - 1)$ (a sufficient condition). The bound is 1 for one task, 0.828 for two, 0.780 for three, and decreases to $\ln 2 \approx 0.693$ for many tasks. Above the bound the test says nothing: the set may or may not be schedulable.

RM is the best fixed-priority assignment for such task sets (if any fixed-priority order works, RM works), and EDF is the best of all.

Each row compares the tests with a simulation over a whole hyperperiod. Row 2: $U = 0.833$ is above the RM bound 0.780, yet RM does schedule the set; the bound is only sufficient. Row 3: periods 2, 4, 8 are harmonic (each divides the next): RM works up to $U = 1$. Rows 4 and 5: $U$ is below 1, so EDF works, but RM fails. Row 6: $U > 1$, nothing can work.

The exact test for fixed priorities: response-time analysis

With the tasks in priority order and all released together, the worst case for task $i$ is its first job (the critical instant). Its response time is $R_i = C_i + \sum_{j \text{ with higher priority}} \lceil R_i / T_j \rceil\, C_j$: its own work plus all the jobs of higher-priority tasks released before it finishes. Start with $R = C_i$ and iterate until $R$ stops changing; the task meets its deadline exactly when the final $R \le D_i$.

For the three-task set whose utilisation 0.833 is above the bound, the iteration for $T_3$ goes 3, 6, 7, 9, 10, 10: the worst-case response time is 10, within the period 12. So the first job of $T_3$ completes at time 10 (with RM and all tasks released at 0).

Priority inversion

$L$ takes the lock and is pre-empted by $M$. $H$ arrives and needs the lock: it is blocked. Without inheritance $M$ keeps running because it has a higher priority than $L$; $L$ cannot release the lock until $M$ is finished. $H$, the most important job, waits for the less important $M$ (five units) as well as for $L$: priority inversion. With inheritance, as soon as $H$ blocks, $L$ runs with $H$'s priority, finishes its critical section, releases the lock, and $H$ goes on; the delay of $H$ is now bounded by the length of the critical section. (A well-known real case is the Mars Pathfinder lander in 1997, where a priority inversion on a lock caused repeated resets until priority inheritance was switched on; this is from the literature, not computed here.)

Other policies you may meet (quoted from the textbooks, not computed)

Worked examples

Cheat box

Traps and GATE patterns

Connections

The feedback queue is a refinement of priority and round-robin scheduling: the priority changes with behaviour, the quantum depends on the level. Real-time scheduling is CPU scheduling with a different aim, deadlines instead of averages. Priority inversion is a meeting of scheduling with locks and semaphores. Gang scheduling concerns threads that run in parallel.

PYQs

Consider a uniprocessor system executing three tasks
T1, T2 and T3, each of which is composed of an
infinite sequence of jobs (or instances) which arrive
periodically at intervals of 3, 7 and 20 milliseconds,
respectively. The priority of each task is the inverse
of its period and the available tasks are scheduled in
order of priority, with the highest priority task
scheduled first. Each instance of T1, T2 and T3
requires an execution time of 1, 2 and 4 milliseconds,
respectively. Given that all tasks initially arrive at the
beginning of the 1st millisecond and task preemptions
are allowed, the first instance of T3 completes its
execution
at
the
end
of
______________
milliseconds.

Group 1 contains some CPU scheduling algorithms
and Group 2 contains some applications. Match
entries in Group 1 to entries in Group 2.

Group 1
P. Gang Scheduling
Q. Rate Monotonic Scheduling
R. Fair Share Scheduling

Group 2
1.
Guaranteed Scheduling
2.
Real-time Scheduling
3.
Thread Scheduling

Self-check

Revision card

References