Question 2 of 6: Scheduling Concepts

Question 2: Scheduling Concepts (20%)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Fixed Priority Preemptive Scheduling (FPPS). Every task is assigned a priority once, at design time, and that priority never changes while the system runs. At every instant the scheduler runs whichever ready task currently has the highest priority, preempting a lower-priority task the moment a higher-priority one becomes ready. Because the priority ordering is static, FPPS is simple to implement (a fixed priority queue), analysable offline (classical response-time analysis and the utilisation-bound tests apply directly), and predictable under overload (low-priority tasks degrade gracefully while high-priority tasks are unaffected). Its weakness is that the priority assignment itself is a design choice made in advance and does not adapt to which task actually has the most urgent deadline at run time, so a poor static assignment can leave the CPU under-utilised relative to what a dynamic scheme could achieve.

Dynamic-Priority Preemptive Scheduling. Here priority is recomputed at run time from some time-varying attribute of each task — most commonly its current absolute deadline (EDF) or its current slack (LST) — rather than fixed once. The scheduler still always runs the highest-priority ready task and preempts on arrival of a higher-priority one, but "highest priority" is a moving target: a task's priority can rise as its deadline approaches. Dynamic-priority schemes achieve higher achievable utilisation than any fixed-priority scheme (EDF is provably optimal on a single processor — see part 5), at the cost of more run-time bookkeeping (recomputing/re-sorting priorities on every event) and messier overload behaviour, since there is no single task that is "always" low priority and therefore predictably sacrificed first.

Rate-Monotonic Scheduling (RMS). A fixed-priority policy, specifically for periodic tasks, in which priority is assigned inversely to period: the task with the shortest period gets the highest fixed priority, permanently. RMS is the optimal fixed-priority assignment for periodic tasks with deadlines equal to their periods — no other static assignment can schedule a task set that RMS cannot. Liu & Layland's classical sufficient (but not necessary) schedulability test bounds total utilisation: for n tasks, the set is guaranteed schedulable if Σ(C_i/T_i) ≤ n(2^{1/n} - 1), which tends to ln 2 ≈ 0.693 as n → ∞ — i.e. up to roughly 69% CPU utilisation is always safe, and exact analysis (response-time analysis) can certify feasibility at higher utilisations on a case-by-case basis.

Deadline-Monotonic Scheduling (DMS). A generalisation of RMS to the case where a task's relative deadline need not equal its period: priority is assigned inversely to relative deadline (shortest deadline → highest fixed priority), again fixed for the life of the task set. DMS reduces to RMS exactly when every task's deadline equals its period. Like RMS it is a fixed-priority scheme, so all the standard fixed-priority analysis techniques (response-time analysis, utilisation bounds) apply; DMS is the optimal fixed-priority policy for the more general deadline-not-equal-to-period case, just as RMS is optimal for the deadline-equals-period case.

Earliest-Deadline-First Scheduling (EDF). A dynamic-priority policy: at every instant, run the ready task whose absolute deadline is soonest, re-evaluating (and preempting) whenever a new task arrives or a deadline changes. EDF is provably optimal among all scheduling algorithms on a single processor — if any algorithm can meet all deadlines for a given task set, EDF can too — and its exact schedulability condition (the processor-demand criterion) allows up to 100% CPU utilisation for periodic tasks with deadlines equal to periods, well beyond RMS's conservative bound. The cost is run-time overhead (the ready queue must be kept sorted, or searched, by deadline on every event) and unpredictable overload behaviour: when the task set is overloaded, EDF can enter a "domino effect" where many tasks miss their deadlines together, whereas a fixed-priority scheme sacrifices only its lowest-priority tasks first.

Least Slack Scheduling (LST, also Least Laxity First). Another dynamic-priority policy, which schedules by slack (laxity) rather than raw deadline: slack(t) = (deadline - t) - (remaining computation time), the amount of time a task could still be delayed and just barely meet its deadline if run flat-out from now on. The scheduler always runs the ready task with the smallest current slack, recomputing slack continuously (in principle) as time advances, so two tasks with the same deadline but different remaining work are correctly distinguished — a case EDF alone cannot break a tie on. LST is also optimal on a uniprocessor in the same sense as EDF, but is markedly more expensive to implement exactly (slack changes continuously with the clock even when no task arrives or completes, causing frequent context switches / "thrashing" near ties in practice), so it is used less often than EDF despite the theoretical equivalence.