Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 37 ยท RTOS and Scheduling

Scheduling Algorithms and Deadline Analysis

Compare round-robin, fixed-priority, rate-monotonic and earliest-deadline-first scheduling, compute CPU utilization and worst-case response times, and simulate deadline misses.

Choosing priorities by gut feeling works for small systems, but when deadlines are tight you want a way to prove that every task will finish on time, before the hardware is built. Real-time scheduling theory gives simple, practical tools for exactly that. In this lesson you will meet the common scheduling policies, learn the vocabulary of periodic task sets, and use two analyses (a utilization bound and response-time analysis) in code.

Vocabulary of a periodic task

Most embedded tasks are periodic: they run again and again at a fixed interval. Each is described by three numbers:

  • C (computation time): the worst-case execution time (WCET) of one run.
  • T (period): the time between releases.
  • D (deadline): when the run must be finished, measured from its release. Often D = T ("finish before the next release").

The utilization of a task is C/T, the fraction of the CPU it needs. The total utilization is the sum over all tasks, and it must obviously be at most 100%. But as you will see, "at most 100%" is not enough for fixed-priority scheduling.

Other terms: response time is the time from a task's release to its completion (including waiting for higher-priority tasks); jitter is its variation; the hyperperiod is the least common multiple of all the periods, after which the whole schedule repeats.

Common policies

Policy How it chooses Notes
Round-robin Each ready task gets a time slice in turn Fair, but gives no deadline guarantees; used within one priority level
Fixed priority (preemptive) Highest static priority wins What most RTOSes use; simple and predictable
Rate Monotonic (RM) Fixed priority, shorter period gets higher priority Optimal among fixed-priority policies for D = T
Deadline Monotonic (DM) Shorter relative deadline gets higher priority Like RM when D differs from T
Earliest Deadline First (EDF) Dynamic: the job with the nearest absolute deadline runs Optimal on one CPU: schedulable whenever U <= 1; harder to implement and to debug under overload
Cooperative / run-to-completion The running task is never preempted See the cooperative scheduler lesson

Rate-monotonic scheduling is the workhorse. Its rule is easy to remember: the faster the task repeats, the higher its priority. A 1 ms control loop outranks a 100 ms display refresh, which matches intuition.

The utilization bound

For n periodic tasks under RM with D = T, the set is guaranteed schedulable if

TEXT
U = sum(C_i / T_i) <= n * (2^(1/n) - 1)

The bound is 100% for one task, 82.8% for two, 78.0% for three and falls toward ln 2, about 69.3%, as n grows. If you stay under it, no further analysis is needed. If you are over it, the set may still be schedulable, so you have to check precisely with response-time analysis.

Response-time analysis

For a fixed-priority preemptive system, the worst-case response time of task i is the smallest R that satisfies

TEXT
R_i = C_i + sum over higher-priority j of ceil(R_i / T_j) * C_j

The right side includes the task's own work plus all the interruptions by higher-priority tasks during that time. You solve it by iteration: start with R = C_i, compute the right side, and repeat until the value stops changing (or exceeds the deadline). The task set is schedulable if every R_i is at most D_i. The code below does this for a three-task set sorted by priority.

C Utilization bound and response-time analysis

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The set has U = 0.814, above the 0.780 guarantee for three tasks, yet response-time analysis shows the lowest-priority task finishes in 10 ms against a 13 ms deadline. This is the general lesson: the utilization bound is sufficient but not necessary. Passing it is a proof; failing it is just a reason to look closer.

To use this in a real project you need a trustworthy WCET for each task. Measure with a cycle counter or a logic analyzer on a pin toggled at task start and end, run the worst-case input, and add margin. Include time spent in interrupts as extra "tasks" at the highest priority, and the context-switch and tick overhead.

RM versus EDF in a simulation

Rate-monotonic priorities are fixed, so they cannot always use the whole CPU. EDF can. The classic example: task 1 needs 2 ms every 5 ms, task 2 needs 4 ms every 7 ms. U = 0.4 + 0.571 = 0.971, which is far above the 0.828 bound for two tasks. The simulation below runs both policies for one hyperperiod (35 ms) in 1 ms steps and prints which task runs in each step.

C Rate monotonic misses a deadline that EDF meets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Under RM, task 2 (the lower priority) is preempted by task 1 every five ticks and runs out of time before its deadline at tick 7. Under EDF, the scheduler notices that task 2's deadline is nearer than task 1's at the critical moment and lets it finish. EDF is theoretically better, but most RTOSes still use fixed priorities because they are easy to analyze, easy to debug, and fail gracefully under overload: the low-priority tasks suffer first and the important ones keep running. EDF under overload can cascade, with every task missing deadlines.

Practical guidance

  • Assign priorities by deadline or rate, not by importance. A critical but slow task (daily backup) does not belong above a fast control loop.
  • Keep high-priority tasks short. Their run time is added to everyone below them.
  • Reserve headroom. Aim for total utilization well below the limit, often 60 to 70%, to absorb estimation errors and future features.
  • Count everything that preempts. Interrupts, the kernel tick and other tasks all add to the response time.
  • Monitor at run time. Many RTOSes can report each task's CPU share and stack high-water mark. Check them during testing (see debugging embedded systems).
  • Use a watchdog so that a missed deadline that turns into a hang still ends in a controlled reset.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Under rate-monotonic scheduling, which task gets the highest priority?

    RM assigns higher priority to tasks that repeat more often.
  2. 2. Three tasks have total utilization 0.75. The RM bound for n = 3 is about 0.78. What can you conclude?

    U is below the bound, which is a sufficient condition, so all deadlines are guaranteed (with D = T and accurate WCETs).
  3. 3. Utilization is 0.9 for two tasks, above the RM bound. Is the set definitely unschedulable?

    Exceeding the bound only means the guarantee is gone; an exact analysis can still show all deadlines are met.
  4. 4. What does EDF choose to run at each moment?

    EDF is a dynamic-priority policy: the nearest deadline always wins.

Summary

  • Periodic tasks are described by C (WCET), T (period) and D (deadline); utilization is the sum of C/T.
  • Rate-monotonic priorities (shorter period, higher priority) are optimal among fixed priorities and guaranteed when U is under n*(2^(1/n)-1).
  • Response-time analysis solves R = C + the sum of ceil(R/T_j)*C_j iteratively and is exact for fixed priorities.
  • EDF can use the whole CPU but is harder to debug under overload, so most RTOS projects stay with fixed priorities and leave headroom.

Next: Debugging Embedded Systems