Multicore Real-Time Scheduling: Partitioned, Global and Semi-Partitioned Approaches

Uniprocessor real-time scheduling is a well-settled theory. Rate monotonic and EDF are optimal in their classes, utilization bounds and response-time analysis are exact or close to it, and decades of tooling exist. Multicore processors changed the picture. Today even microcontrollers ship with two or more cores, and application processors have eight or more. Yet scheduling real-time tasks across several cores turns out to be a different problem, not just a bigger one. Intuitions from the single-core world can fail badly, and the hardware adds interference that no scheduler can see.

This article surveys the three main families of multicore real-time scheduling: partitioned, global and semi-partitioned (plus the clustered hybrid). It explains their theoretical limits and the practical concerns of shared resources and interference, and shows how to apply them on Linux and common RTOSes.

Why multicore is different

On one processor, the question is when each job runs. On m processors it is also where, and whether a job may move. Two consequences surprise newcomers.

First, work-conserving greedy algorithms are no longer optimal. EDF is optimal on a uniprocessor, but on multiple processors there is no simple per-job priority rule that is optimal for sporadic task sets. Fisher, Goossens and Baruah showed in 2010 that no optimal online algorithm exists for constrained-deadline sporadic tasks.

Second, scheduling anomalies appear. Reducing a task’s execution time, or adding a processor, can make a schedule worse. Graham described such anomalies for multiprocessor list scheduling in the 1960s. They mean that testing with “typical” execution times is even less trustworthy than on one core, and that analysis must be designed to be safe under such effects.

Finally, cores are not independent. They share last-level caches, memory controllers, buses and peripherals. A task’s execution time depends on what runs on the other cores at the same moment, which undermines the WCET values our analysis takes as input. We return to this below; our article on WCET analysis methods covers the single-core baseline.

Partitioned scheduling

In partitioned scheduling, every task is statically assigned to one core and never migrates. Each core then runs an ordinary uniprocessor scheduler: fixed priority (P-FP) or EDF (P-EDF). Once the assignment is fixed, everything from the uniprocessor world applies directly, including response-time analysis, utilization bounds and well-understood locking protocols.

The bin-packing problem

The hard part is the assignment. Deciding whether tasks can be partitioned onto m cores is a bin-packing problem and NP-hard in the strong sense, so practical systems use heuristics. The usual ones are First-Fit, Best-Fit and Worst-Fit, typically applied to tasks sorted by decreasing utilization (“Decreasing” variants such as FFD). The admission test for each core can be the exact EDF utilization test or an exact fixed-priority response-time test:

from math import ceil
from fractions import Fraction

def rta_ok(tasks):
    """Exact fixed-priority response-time test, deadline-monotonic order.
    tasks: list of (C, T, D) with D <= T."""
    tasks = sorted(tasks, key=lambda t: t[2])
    for i, (C, T, D) in enumerate(tasks):
        R = C
        while True:
            R_next = C + sum(ceil(R / Tj) * Cj for Cj, Tj, _ in tasks[:i])
            if R_next > D:
                return False
            if R_next == R:
                break
            R = R_next
    return True

def edf_ok(tasks):
    """Exact uniprocessor EDF test for implicit deadlines (D == T)."""
    return sum(Fraction(C, T) for C, T, _ in tasks) <= 1

def first_fit_decreasing(tasks, m, fits=rta_ok):
    cores = [[] for _ in range(m)]
    for task in sorted(tasks, key=lambda t: t[0] / t[1], reverse=True):
        for core in cores:
            if fits(core + [task]):
                core.append(task)
                break
        else:
            return None          # no core can take this task
    return cores

tasks = [(3, 5, 5), (4, 10, 10), (6, 20, 20), (2, 8, 8), (5, 25, 25), (1, 4, 4)]
print(first_fit_decreasing(tasks, 2, fits=edf_ok))  # fits: each core at 100%
print(first_fit_decreasing(tasks, 2))               # None: P-FP needs a 3rd core

This task set has total utilization exactly 2.0. Partitioned EDF packs it onto two cores at 100% each. Partitioned fixed priority with the same heuristic needs a third core. That illustrates how much the per-core test matters. You can check any single core’s assignment with our schedulability calculator.

Worst-case limits

Partitioning has an unavoidable worst case. Consider m + 1 tasks, each with utilization just over 0.5. No two fit on one core, so the set cannot be partitioned onto m cores, even though total utilization is only about (m + 1)/2. So no partitioning algorithm can guarantee more than roughly 50% of platform capacity in general. For rate-monotonic first-fit, Oh and Baker proved a sufficient bound of m(√2 − 1) ≈ 0.41m. In practice, typical task sets partition far better than these worst cases, which is why partitioning dominates industrial practice.

Global scheduling

Global scheduling keeps a single ready queue for all cores. At any time, the m highest-priority ready jobs run, and jobs migrate freely. Global EDF (G-EDF) and global fixed priority (G-FP) are the natural extensions of their uniprocessor counterparts. Linux’s SCHED_DEADLINE uses global EDF within each root domain, as described in our SCHED_DEADLINE article.

The Dhall effect

In 1978, Dhall and Liu identified a fundamental weakness. Take m processors and m + 1 tasks. The first m tasks are “light”: execution time 2ε, period 1. The last is “heavy”: execution time 1, period 1 + ε. At time 0 global EDF runs the light tasks first, because their deadlines are earlier. The heavy task starts at 2ε and finishes at 1 + 2ε, missing its deadline at 1 + ε. Total utilization is only slightly above 1, no matter how large m is. Partitioning schedules the same set trivially: the heavy task alone on one core, the light tasks on another.

Optimal global algorithms

For implicit-deadline periodic tasks, total utilization U ≤ m (with each U_i ≤ 1) is achievable. Pfair scheduling (Baruah et al., 1996) makes every task progress at a rate proportional to its utilization by dividing time into quanta. LLREF and later RUN (Regnier et al., 2011) reach the same bound with fewer scheduling events; RUN reduces multiprocessor scheduling to a series of uniprocessor problems. These algorithms are elegant, but their preemption and migration counts and implementation complexity have limited their industrial use.

Analyzing global fixed priority

Response-time analysis also extends to global fixed priority. Bertogna and Cirinei (2007) bound the interference that higher-priority tasks can cause on m cores. The results are sufficient rather than exact, and noticeably more pessimistic than uniprocessor RTA. That is one reason certifiable systems still favor partitioning.

Semi-partitioned and clustered scheduling

Semi-partitioned scheduling partitions most tasks but allows a few to be split across cores, running part of each job on one core and the rest on another, under carefully controlled migration. EKG (Andersson and Tovar, 2006), EDF-WM (Kato et al., 2009) and C=D splitting (Burns et al., 2012) are representative. They recover most of the capacity that bin packing loses while keeping migrations rare and predictable.

Clustered scheduling groups cores, often those sharing an L2 cache, into clusters. Tasks are partitioned among clusters and scheduled globally within each one. Migration then stays within a cache domain, so it is cheap, and bin-packing losses fall because each “bin” is larger. RTEMS supports clustered scheduling directly, and Linux achieves it with cpuset partitions.

Shared resources and inter-core interference

Software locks across cores

When tasks on different cores share data, uniprocessor protocols like the priority ceiling protocol (see priority inversion and the priority ceiling protocol) no longer suffice. Multiprocessor protocols include MPCP (Rajkumar, 1990), which uses suspension-based waiting; MSRP (Gai et al., 2001), where waiting tasks spin non-preemptively in FIFO order; FMLP (Block et al., 2007); and MrsP (Burns and Wellings, 2013), which lets a preempted lock holder migrate to a core where a waiter is spinning. Short critical sections favor spinning; long ones favor suspension.

Hardware interference

Shared hardware creates interference that the OS scheduler cannot see. A task’s memory-bound loop can run several times slower when other cores saturate the memory controller or evict its cache lines. The main mitigations are:

• Cache partitioning: hardware way-partitioning (Intel Cache Allocation Technology, Arm MPAM) or software page coloring.
• Memory bandwidth regulation: per-core budgets enforced by performance-counter interrupts (MemGuard, Yun et al., 2013) or hardware such as Intel Memory Bandwidth Allocation. On Linux, both CAT and MBA are exposed through the resctrl file system.
• Time-triggered coordination: scheduling memory-intensive phases so that they don’t overlap across cores.

Putting it into practice

Linux

Fixed-priority partitioned scheduling is just affinity plus SCHED_FIFO: taskset -c 2 chrt -f 80 ./loop. For deadline tasks, which must have affinity spanning their root domain, create cgroup v2 cpuset partitions:

# Make CPUs 2-3 a separate scheduling (root) domain
echo "+cpuset" > /sys/fs/cgroup/cgroup.subtree_control
mkdir /sys/fs/cgroup/rt
echo 2-3  > /sys/fs/cgroup/rt/cpuset.cpus
echo root > /sys/fs/cgroup/rt/cpuset.cpus.partition
echo $PID > /sys/fs/cgroup/rt/cgroup.procs   # G-EDF within CPUs 2-3 only

A partition of one CPU gives you partitioned EDF with the exact uniprocessor test. A partition of two or more CPUs gives you clustered EDF.

RTOSes

Zephyr and FreeRTOS (V11+) offer SMP schedulers with per-thread CPU affinity, so you can implement partitioning by pinning. RTEMS lets you assign different schedulers to different processor sets, and NuttX supports SMP with affinity. Many safety-critical designs instead run separate RTOS instances on each core (AMP). That is effectively partitioning enforced by the software architecture. Our RTOS comparison discusses each platform’s multicore support.

Contracts and multiprocessors

Multiprocessor support was one of the explicit objectives of the FRESCOR project: extending contract-based reservations so that an application’s timing requirements remain valid regardless of which core serves it. The same idea of a reserved, enforced budget per component underpins mixed-criticality platforms today. For a review of your own multicore task allocation and interference assumptions, see our Real-Time Schedulability Audit.

Frequently asked questions

Is global or partitioned scheduling better?

Neither dominates. Partitioning has simpler, exact analysis and no migration overhead, but it can waste capacity through bin-packing fragmentation. Global scheduling balances load automatically and suits soft real-time work, but its hard real-time analysis is more pessimistic and migrations cost cache warmth. For hard real-time systems, partitioned or clustered scheduling is the common choice.

What exactly is the Dhall effect?

It is the observation, by Dhall and Liu (1978), that global EDF and global rate-monotonic scheduling can miss deadlines with total utilization just above 1 on any number of processors. It happens when one heavy task is delayed by many light tasks with earlier deadlines. Giving heavy tasks top priority (EDF-US and similar hybrids) or partitioning avoids it.

Can I use my uniprocessor schedulability tools on a multicore system?

Yes, for partitioned scheduling. Once tasks are assigned to cores, analyze each core independently, using WCETs that include inter-core interference. For global scheduling you need multiprocessor-specific tests.

Does adding cores always make a system more schedulable?

Not necessarily. Multiprocessor scheduling anomalies mean extra processors or shorter execution times can occasionally lengthen response times under some algorithms. More importantly, more active cores usually mean more contention for shared memory, which can increase every task’s WCET.

Which semi-partitioned algorithm should I use?

Choose one your RTOS or tooling supports and whose split-task analysis you can verify. In practice, many teams apply a simple manual version: partition with FFD, then split only the one or two tasks that don’t fit, at points chosen to keep migrations infrequent.

References and further reading

1. R. I. Davis and A. Burns, “A Survey of Hard Real-Time Scheduling for Multiprocessor Systems,” ACM Computing Surveys, 43(4), 2011.
2. S. K. Dhall and C. L. Liu, “On a Real-Time Scheduling Problem,” Operations Research, 26(1), 1978.
3. J. Goossens, S. Funk and S. Baruah, “Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors,” Real-Time Systems, 25, 2003.
4. M. Bertogna and M. Cirinei, “Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms,” Proc. IEEE RTSS, 2007.
5. Control Group v2: cpuset controller — Linux kernel documentation
6. Deadline Task Scheduling (SMP and root domains) — Linux kernel documentation
7. Certification Authorities Software Team, “CAST-32A: Multi-core Processors,” position paper, 2016; superseded by EASA AMC 20-193 (2022) and FAA AC 20-193 (2024).