What's changed: Initial version
3.2Scheduling
Covers the difference between priority-based scheduling and round-robin, the rate-monotonic (RM) fixed-priority algorithm and its utilization-bound schedulability test (the Liu & Layland bound), the Earliest Deadline First (EDF) dynamic-priority algorithm, and how the presence or absence of preemption affects responsiveness—together with judging whether a real periodic task set can meet its deadlines.
When multiple tasks all claim to be ready to run, the RTOS scheduler must decide which task gets the next slice of CPU time. What matters to an embedded designer is not memorizing algorithm names but a single practical question: can we mathematically guarantee, in advance, that a given set of periodic tasks will meet every deadline? This section examines the two major approaches—rate-monotonic and EDF—together with worked schedulability examples.
3.2.1Priority-based scheduling and round-robin
- Priority-based scheduling assigns each task a priority and always allocates the CPU to the highest-priority task among those that are ready. This is the standard approach for embedded RTOSes; priorities may be fixed (static) or may change dynamically at run time.
- Round-robin allocates the CPU in turn to tasks that share the same priority, each getting a fixed time slice (time quantum), to preserve fairness. It is typically combined with priority-based scheduling: priority decides ordering across different priority levels, while round-robin fairly distributes CPU time among tasks at the same priority level.
3.2.2Rate-monotonic (RM) and schedulability
- Rate-monotonic (RM) statically assigns higher priority to tasks with shorter periods. For a set of periodic tasks whose periods do not change at run time, this assignment is theoretically proven to be the optimal fixed-priority policy.
- A sufficient schedulability test (the Liu & Layland utilization bound): compute the utilization U = sum(Ci/Ti) from each task's execution time
Ciand periodTi; ifU <= n(2^(1/n) - 1)(wherenis the number of tasks) holds, the task set is guaranteed schedulable under RM. This bound is about 0.828 for n=2, about 0.780 for n=3, and asymptotically approaches ln2 (about 0.693) as n grows large. - Exceeding this bound does not necessarily mean the task set is unschedulable—it is only a sufficient condition, not a necessary one. A more precise test uses response-time analysis (RTA). Conversely, the practical value of the bound is that staying under it lets you assert schedulability unconditionally.
3.2.3EDF (Earliest Deadline First)
- EDF does not fix priorities; it dynamically allocates the CPU to whichever task currently has the nearest deadline. On a single processor, it has the looser (more favorable) schedulability condition of guaranteed schedulability whenever utilization U <= 1 (100%), making it the theoretically optimal dynamic-priority policy.
- EDF can theoretically tolerate higher utilization than RM (using the CPU without waste), but in practice it carries downsides: priorities change at run time, making the implementation more complex and adding overhead, and behavior under overload is harder to predict (multiple tasks can miss deadlines in a domino-like cascade). Most embedded RTOSes therefore favor RM for its implementation simplicity and predictable overload behavior.
Most-tested: "RM is a fixed-priority policy that gives higher priority to shorter periods," "the Liu & Layland utilization bound is about 0.828 for n=2 and approaches about 0.693 as n grows large," and "EDF can be schedulable up to 100% utilization but its behavior under overload is harder to predict." Do not confuse "exceeding the bound does not immediately mean infeasible (it is a sufficient condition)" with "EDF permits higher utilization than RM but at the cost of implementation complexity."
Suppose a firmware developer is designing two periodic tasks for a motor-control embedded system. Task A has period T1=20ms and worst-case execution time C1=3ms (reading the current sensor and running the PID control computation); Task B has period T2=50ms and worst-case execution time C2=10ms (sending status over a communication interface). Computing the utilization first: U = C1/T1 + C2/T2 = 3/20 + 10/50 = 0.15 + 0.20 = 0.35. With n=2 tasks, the Liu & Layland bound is 2*(2^(1/2) - 1) ~= 2*0.414 = 0.828, so U=0.35 <= 0.828 holds, letting you guarantee at design time that both tasks will meet their deadlines under RM. Following the rate-monotonic principle, the shorter-period Task A (20ms) gets higher priority, and Task B (50ms) gets lower priority. If future growth in communication volume increases Task B's execution time to C2=25ms, then U = 0.15 + 0.5 = 0.65, still under 0.828 and thus RM-schedulable. But if you then add Task C with period T3=100ms and C3=30ms, n becomes 3 and the bound drops to 3*(2^(1/3)-1) ~= 3*0.26 = 0.78. The total utilization at this point, U=0.15+0.5+0.3=0.95, exceeds 0.78, so RM's sufficient condition can no longer assert "schedulable"—you would need either a more precise response-time analysis (RTA) to compute each task's worst-case response time, or a switch to EDF (under which U=0.95<=1 immediately confirms schedulability). The correct practical judgment is thus to recompute utilization every time a task is added, and when the bound is exceeded, not simply assume "it will probably still make it" but instead run an RTA or consider switching to EDF.
| Aspect | Rate-monotonic (RM) | EDF |
|---|---|---|
| How priority is decided | Shorter period = higher priority (fixed, static) | Nearer deadline = higher priority (changes dynamically) |
| Sufficient schedulability condition | U <= n(2^(1/n) - 1) (about 0.828 for n=2) | U <= 1 (schedulable in theory up to 100%) |
| Implementation complexity | Simple (fixed priority, low overhead) | Complex (deadlines are compared and priorities recomputed continuously) |
| Behavior under overload | Lower-priority tasks predictably miss deadlines first | Multiple tasks can miss deadlines in a cascade (harder to predict) |
Trap: "Once utilization exceeds the Liu & Layland bound, the task set is definitely unschedulable" is wrong—the bound is a sufficient condition, not a necessary one, so a task set can still be schedulable in practice even above the bound (RTA is needed for an exact test). Also wrong: "EDF is simple to implement, so it is widely used in embedded RTOSes"—EDF's dynamic priorities tend to make implementation more complex, and most embedded RTOSes favor RM for its implementation simplicity.
3.2.4Section summary
- Rate-monotonic (RM) fixes higher priority for shorter periods; meeting
U <= n(2^(1/n)-1)guarantees schedulability (a sufficient condition) - EDF dynamically prioritizes the nearest deadline and is schedulable in theory up to
U <= 1, but its implementation is more complex and overload behavior is harder to predict - Do not assume infeasibility just because the bound is exceeded—consider precise response-time analysis (RTA) or switching to EDF as the practical next step
Sign in to track progress — Log in.
Quick check
(just a quick review)Q1. Two periodic tasks, A (T1=20ms, C1=3ms) and B (T2=50ms, C2=10ms), are to be scheduled under rate-monotonic. Which utilization-based schedulability judgment is correct?
Q2. After adding a third periodic task to a motor-control system, utilization becomes U=0.95 with n=3 tasks (the n=3 bound is about 0.78). What is the most appropriate response in this situation?
Q3. A design requires prioritizing predictable behavior under overload and keeping the implementation as simple as possible. Which of rate-monotonic (RM) or EDF should be chosen, and for what reason?