Real-Time Systems and RTOS

Real-Time Scheduling and Multitasking in Embedded Systems

How embedded systems schedule tasks to meet deadlines: cyclic executives, fixed-priority preemption, rate monotonic, EDF, and a worked schedulability example.

On this page
  1. What real-time scheduling has to do
  2. Multitasking on a single processor
  3. The vocabulary of a task set
  4. Scheduling policies used in embedded systems
  5. Assigning priorities: rate monotonic and deadline monotonic
  6. Checking a task set will meet its deadlines
  7. What the simple tests leave out
  8. Scheduling on multicore microcontrollers
  9. Practical guidelines
  10. Frequently asked questions

What real-time scheduling has to do

A general-purpose operating system schedules work to keep the CPU busy and to be fair to everyone. A real-time scheduler has a different job: make sure every task finishes before its deadline, every time, including in the worst case. Fairness, average throughput, and average response time come second.

That changes how scheduling is designed and judged. Instead of asking “how fast is it on average?”, you ask “can I prove, or at least show with good evidence, that the slowest possible response is still on time?” This article covers the policies embedded systems use, how priorities are assigned, and how to check a task set. If you need a refresher on deadline types first, see hard vs soft real-time and timing constraints.

Multitasking on a single processor

Most microcontrollers have one CPU core, which runs one instruction stream at a time. Multitasking creates the appearance of several activities running at once by switching between them.

Each task (also called a thread) has its own stack and saved register state. When the scheduler decides a different task should run, it performs a context switch: it saves the current task’s registers, picks the next task, and restores that task’s registers. Switches happen when:

  • a task blocks, for example waiting for a message, a semaphore, or a delay to expire;
  • an interrupt makes a higher-priority task ready; or
  • a time slice expires, if the scheduler uses time slicing.

Context switches cost time, typically a small number of microseconds or less on modern microcontrollers, depending on the core, clock speed, and kernel. That’s cheap but not free, which is one reason to avoid splitting work into more tasks than you need.

Multitasking vs multiprocessing

  • Multitasking is several tasks sharing one processor through switching. Only one runs at any instant.
  • Multiprocessing is several processors or cores running tasks at the same time, in true parallel.

Many systems do both: a dual-core microcontroller can run several tasks on each core. Multiprocessing brings its own scheduling questions, covered later in this article.

The vocabulary of a task set

Real-time scheduling theory describes each periodic task with a few numbers:

  • C – worst-case execution time (WCET): the longest the task takes to run once, without interruption.
  • T – period: how often the task is released.
  • D – relative deadline: how long after release the task must finish. Often D = T.
  • U = C / T – utilization: the fraction of the CPU the task needs.

The total utilization U of a task set is the sum of each task’s C/T. If U is greater than 1, no scheduler can meet all deadlines on one core. If U is at or below 1, it depends on the policy, as you’ll see below.

Scheduling policies used in embedded systems

Cyclic executive / time-triggered scheduling

The simplest real-time “scheduler” is a fixed timetable built at design time. A timer interrupt fires at a regular interval (the minor cycle), and the code runs a predetermined list of functions in each slot. The whole pattern repeats every major cycle.

  • Pros: very predictable, easy to test, no kernel needed, and timing is fixed by construction. Time-triggered designs are used in some safety-related systems for this reason.
  • Cons: inflexible. Adding a task or changing a period can mean redesigning the whole table, and sporadic events have to be polled in a slot rather than handled immediately.

Cooperative scheduling

In cooperative (non-preemptive) scheduling, each task runs until it voluntarily returns or yields. A simple timer-tick scheduler that calls functions when they’re due is cooperative.

  • Pros: no preemption means no race conditions between tasks, since only one runs at a time and it can’t be interrupted by another task. Very low overhead.
  • Cons: response time is limited by the longest task, because an urgent task has to wait until the current one finishes. One task that runs too long breaks everyone else’s timing.

Fixed-priority preemptive scheduling

This is the default in most embedded RTOSes, including FreeRTOS, Zephyr, and ThreadX. Every task has a priority, and the highest-priority ready task always runs. If a higher-priority task becomes ready, perhaps because an interrupt gave it a semaphore, it preempts the running task immediately.

  • Pros: urgent work gets the CPU quickly regardless of what lower-priority tasks are doing. Well-understood analysis exists.
  • Cons: low-priority tasks can starve if higher-priority work never pauses. Preemption introduces race conditions that must be managed with mutexes, queues, and similar tools. See RTOS task synchronization and inter-task communication.

Round-robin time slicing among equal priorities

Many RTOSes let several tasks share a priority level. Among those, the kernel can time-slice: each gets the CPU for a tick or a set quantum, then the next equal-priority task runs. In FreeRTOS, for example, this is controlled by configUSE_TIME_SLICING. Time slicing never lets a lower-priority task run ahead of a higher-priority one; it only divides time among equals.

Earliest deadline first (EDF)

EDF is a dynamic-priority policy: at every moment, the ready task with the nearest absolute deadline runs. On a single processor, for independent preemptible tasks, EDF is optimal in the sense that if any scheduler can meet all deadlines, EDF can.

EDF is less common in microcontroller RTOSes than fixed priorities. Fixed priorities are simpler to implement, and their behavior under overload is easier to predict: the lowest-priority tasks miss first, whereas under EDF an overload can cause misses that are harder to contain. Linux offers an EDF-based policy, SCHED_DEADLINE, and some RTOSes provide deadline-based options.

Assigning priorities: rate monotonic and deadline monotonic

With fixed priorities, which task gets which priority matters as much as the policy itself.

  • Rate monotonic (RM): the shorter a task’s period, the higher its priority. When deadlines equal periods, RM is optimal among fixed-priority assignments: if any fixed-priority order can meet all deadlines, RM can.
  • Deadline monotonic (DM): the shorter a task’s relative deadline, the higher its priority. DM is the generalization for tasks whose deadlines are shorter than their periods.

A common mistake is to assign priorities by importance (“the safety task is most important, so it gets top priority”). Importance and urgency are different. A safety check that runs every 100 ms with a 100 ms deadline usually doesn’t need to preempt a motor-control loop that runs every 100 µs. If the analysis shows deadlines are met, everything is on time, whatever the importance.

Checking a task set will meet its deadlines

The utilization bound

For n independent periodic tasks with deadlines equal to periods, scheduled rate monotonically on one processor, Liu and Layland showed in 1973 that all deadlines are met if:

U ≤ n (2^(1/n) − 1)

Number of tasks (n) Bound
1 1.000
2 0.828
3 0.780
4 0.757
5 0.743
Large n approaches ln 2 ≈ 0.693

The bound is sufficient but not necessary. Passing it guarantees schedulability; failing it doesn’t mean the set fails. For that you need a more exact test.

Response-time analysis: a worked example

Response-time analysis (RTA) computes the worst-case response time R of each task: its own execution time plus all the interference from higher-priority tasks that can preempt it. For task i, ignoring blocking for now:

R = C_i + Σ over higher-priority tasks j of ⌈R / T_j⌉ × C_j

You solve it by iteration: start with R = C_i, plug it into the right-hand side, and repeat until the value stops changing. If it exceeds the deadline, the task can miss.

Take three tasks, rate-monotonic priorities, deadlines equal to periods:

Task C T = D U
τ1 (highest) 1 4 0.250
τ2 2 6 0.333
τ3 (lowest) 3 12 0.250
Total 0.833

Total utilization is 0.833, above the three-task bound of 0.780. The simple test can’t confirm the set. Now apply RTA:

  • τ1: nothing preempts it, so R1 = 1. That’s within its deadline of 4.
  • τ2: start with R = 2. Interference from τ1 is ⌈2/4⌉ × 1 = 1, so R = 3. Recompute: ⌈3/4⌉ × 1 = 1, so R = 3. It has converged. R2 = 3, within 6.
  • τ3: start with R = 3.
    • R = 3 + ⌈3/4⌉×1 + ⌈3/6⌉×2 = 3 + 1 + 2 = 6
    • R = 3 + ⌈6/4⌉×1 + ⌈6/6⌉×2 = 3 + 2 + 2 = 7
    • R = 3 + ⌈7/4⌉×1 + ⌈7/6⌉×2 = 3 + 2 + 4 = 9
    • R = 3 + ⌈9/4⌉×1 + ⌈9/6⌉×2 = 3 + 3 + 4 = 10
    • R = 3 + ⌈10/4⌉×1 + ⌈10/6⌉×2 = 3 + 3 + 4 = 10. It has converged.
    • R3 = 10, within its deadline of 12.

Every task meets its deadline, even though the utilization bound said “can’t tell.” This is why the exact test is worth knowing: the bound is a quick screen, and RTA gives the real answer for the model.

EDF’s test

For EDF with independent preemptible tasks and deadlines equal to periods, the test is simple: the set is schedulable on one processor if and only if U ≤ 1. The example above (U = 0.833) is schedulable under EDF too, with more room to spare.

What the simple tests leave out

The textbook model assumes independent tasks, exact WCETs, and zero overhead. Real systems need a few additions:

  • Blocking: if a high-priority task waits for a mutex held by a lower-priority task, that time adds to its response. RTA handles this with a blocking term B, added to C. Priority inheritance or priority ceiling protocols keep B bounded; without them, priority inversion can make it unbounded.
  • Interrupts: ISRs run above all tasks. Treat each interrupt source as a high-priority “task” with its own C and minimum inter-arrival time, and include it in the interference.
  • Kernel overheads: context switches and tick interrupts take time. Add them to C, or account for them separately.
  • Release jitter: if a task isn’t released exactly on its period, perhaps because its triggering interrupt is itself delayed, the analysis needs a jitter term.
  • Non-preemptible sections: critical sections that disable interrupts or the scheduler delay everyone above them. Keep them short and include the longest one in your blocking estimate.
  • Uncertain WCET: measured worst cases may not be true worst cases. Caches, flash wait states, and rarely taken code paths can all add time. Margins exist for a reason.

Scheduling on multicore microcontrollers

Dual-core and multicore microcontrollers are now common, and RTOSes increasingly support them. FreeRTOS added symmetric multiprocessing (SMP) support to its main kernel in version 11, and Zephyr and ThreadX both have multicore support. There are two broad approaches:

  • AMP (asymmetric multiprocessing): each core runs its own software, often its own RTOS instance or bare-metal code, and the cores communicate through shared memory or mailboxes. This is common when one core handles hard real-time control and another runs communications or a user interface.
  • SMP (symmetric multiprocessing): one kernel schedules tasks across all cores.

Within SMP, tasks can be partitioned (each pinned to one core, so single-core analysis applies to each core) or scheduled globally (any task can run on any core). Partitioning is usually easier to analyze and is a common choice for timing-critical work. Global scheduling can use cores more efficiently but is harder to reason about. Shared caches, buses, and memory controllers also introduce interference between cores that single-core analysis doesn’t capture.

Practical guidelines

  • Start with fixed-priority preemptive scheduling and rate- or deadline-monotonic priorities, unless you have a reason to do otherwise.
  • Use as few priority levels and tasks as the design needs. Group work with similar timing into one task.
  • Keep ISRs short. Capture data, clear the hardware flag, signal a task, and return. Long ISRs add interference to every task.
  • Bound every blocking call. Use timeouts on semaphores and queues in time-critical code, and decide what to do when they expire.
  • Leave headroom. A design running at 95% CPU on paper is fragile in practice.
  • Measure. Toggle GPIO pins at task start and end and watch them on a logic analyzer, or use a trace tool, to confirm response times under maximum load.

For simpler alternatives to an RTOS, see RTOS vs super loop: when do you actually need an RTOS?. If you’ve studied scheduling in an operating systems course, our articles on the four main types of scheduling algorithms and the four main processor scheduling policies explain how FCFS, SJF, priority, and round robin relate to real-time scheduling.

Frequently asked questions

What is task scheduling in an embedded system?

It’s the decision, made continuously by the scheduler, about which task runs on the processor right now. In most embedded RTOSes the rule is simple: run the highest-priority task that’s ready. The design work is in choosing the priorities and checking that every task still meets its deadline in the worst case.

Which scheduling policy is best for real-time embedded systems?

Fixed-priority preemptive scheduling is the most widely used, because it’s simple, well supported by RTOSes, and backed by mature analysis. EDF can schedule more demanding task sets on one core. Time-triggered schedules give the most predictable timing for small, fixed systems.

Is round robin used in real-time systems?

Usually only as a tie-breaker among tasks at the same priority. Pure round robin gives every task a turn regardless of urgency, so an urgent task may wait for several time slices. That makes it a poor fit for hard deadlines on its own.

What’s the difference between preemptive and cooperative multitasking?

In preemptive multitasking the scheduler can stop a running task at almost any point to run a more urgent one. In cooperative multitasking each task keeps the CPU until it chooses to give it up. Preemption gives better response times for urgent work, at the cost of more complexity in protecting shared data.

The complete guide to real-time systems and rtos

Real-Time Embedded Systems Explained
Read the guide

Keep exploring

Guides from other topics

All topics →