Multicore real-time scheduling

Single-core processors are becoming the exception even in embedded systems. Microcontrollers with two or more cores, application processors with four or eight, and systems-on-chip combining real-time cores with general-purpose ones are now common in vehicles, industrial controllers and sensors. More cores mean more processing capacity, but they also bring new scheduling choices and new sources of timing interference. Results that hold on one processor, such as the optimality of EDF and of rate-monotonic priorities, fail on several. This lesson introduces the two main approaches, partitioned and global scheduling, the surprising anomalies that arise, the bin-packing problem at the heart of partitioning and the interference through shared hardware that makes multicore timing analysis hard.

Northway Sensing's next product is the NS-5D, a variant of the NS-5 that watches two approaches of an intersection with two radar sensors. Hardware lead Ines Carvalho has chosen a dual-core version of the same RISC-V microcontroller. The task set nearly doubles: two radar tasks, two classifiers, the CAN service, statistics, logging and housekeeping, with a total utilization of 1.644. Jonah must decide how to spread it across the two cores.

Partitioned and global scheduling

In partitioned scheduling, each task is assigned permanently to one core, and each core runs its own uniprocessor scheduler, such as fixed priority or EDF, on its own tasks. Once the assignment is made, every result of lessons 4 to 8 applies to each core separately. Partitioning is simple, has no migration overhead, and isolates cores from each other's overloads. Its difficulty is the assignment itself, which is a bin-packing problem: fitting tasks of various sizes into cores of capacity 1.

In global scheduling, there is one ready queue for all cores, and at every instant the m highest-priority ready jobs run on the m cores. A job can start on one core and resume on another after preemption, which is called migration. Global scheduling balances load automatically and can use idle time on any core, but migration costs time and cache contents, the run queue is shared and must be locked, and the analysis is much harder. Between the two lie semi-partitioned schemes, in which most tasks are fixed to cores and a few are split, with parts of their jobs running on different cores at planned points, and clustered schemes, in which tasks are partitioned among groups of cores and scheduled globally within each group.

The Dhall effect

It is natural to expect global EDF or global rate-monotonic scheduling to be excellent on m cores, since they are optimal on one. Dhall and Liu showed in 1978 that they are not. Consider two cores and three tasks: a and b each with C = 2 and T = D = 10, and H with C = 10 and T = D = 11. The total utilization is 0.2 + 0.2 + 0.909 = 1.309, barely more than half the capacity of two cores. At time 0 all three are released. Global EDF picks the two earliest deadlines, a and b at 10, and runs them on the two cores. H starts only at time 2, needs 10 ticks and cannot finish by 11. One core sat idle from 2 to 10 while H missed its deadline.

# Dhall's effect: global EDF on two cores misses a deadline at total utilization 1.31 of 2.
tasks = [("a", 2, 10), ("b", 2, 10), ("H", 10, 11)]     # name, C, T = D in ticks
M, HORIZON = 2, 22

def global_edf():
    jobs, rows, misses = [], [[] for _ in range(M)], []
    for t in range(HORIZON):
        for name, c, per in tasks:
            if t % per == 0:
                jobs.append([t + per, name, c])
        for j in [j for j in jobs if j[0] <= t]:
            misses.append((j[1], j[0]))
            jobs.remove(j)
        jobs.sort()                                        # earliest deadline first
        running = jobs[:M]
        for k in range(M):
            rows[k].append(running[k][1] if k < len(running) else ".")
        for j in running:
            j[2] -= 1
        jobs = [j for j in jobs if j[2] > 0]
    return rows, misses

rows, misses = global_edf()
print("tick     " + "".join(str(t % 10) for t in range(HORIZON)))
for k, row in enumerate(rows):
    print(f"core {k}   " + "".join(row))
for name, dl in misses:
    print(f"job of {name} with deadline {dl} missed")
print("partitioned instead: H alone on core 0 (U = 0.909), a and b on core 1 (U = 0.4): both schedulable")

tick     0123456789012345678901
core 0   aaHHHHHHHHHabHHHHHHHHH
core 1   bb........abH.......aa
job of H with deadline 11 missed
partitioned instead: H alone on core 0 (U = 0.909), a and b on core 1 (U = 0.4): both schedulable

The simulation shows H running from tick 2 to tick 10 on core 0 while core 1 idles, and the job of H with deadline 11 misses by one tick. By making the light tasks' execution times tiny and H's utilization approach 1, the construction can be scaled so that a task set with total utilization barely above 1 is unschedulable on any number of cores. The cause is that EDF and rate-monotonic priorities ignore how heavy a task is. Partitioning avoids the problem here trivially, by giving H a core to itself. Global schedulers avoid it with rules that give heavy tasks top priority: EDF-US, for example, gives the highest priority to every task with utilization above m/(2m − 1) and schedules the rest by EDF.

For global EDF there is a clean sufficient test, due to Goossens, Funk and Baruah in 2003, for tasks with implicit deadlines on m identical cores:

where u_max is the largest task utilization. With light tasks the bound approaches m, the full capacity; with one heavy task it collapses toward 1, which is the Dhall effect in formula form. For the example, m − (m − 1)u_max = 2 − 0.909 = 1.091, below the set's 1.309, so the test fails, as the simulation confirmed.

Optimal multiprocessor schedulers exist. Proportionate fairness (Pfair), introduced by Baruah and colleagues in 1996, schedules every task at a rate close to its utilization in every quantum and can meet all deadlines of implicit-deadline periodic tasks whenever U ≤ m. Later algorithms reduce Pfair's very high preemption and migration counts while keeping optimality. They are mostly used in research and in a few specialized kernels, because migrations and preemptions are expensive on real hardware.

Partitioning as bin packing

Deciding whether a set of tasks can be partitioned onto m cores is NP-hard in the strong sense, so practical tools use heuristics. The common ones sort tasks by decreasing utilization and place each in turn. First-fit decreasing puts each task on the first core where it still passes the uniprocessor schedulability test. Best-fit puts it on the core where it leaves the least spare capacity. Worst-fit puts it on the core with the most spare capacity, which balances load and leaves slack on every core. The schedulability test used inside the heuristic can be a utilization bound or exact response-time analysis; the exact test packs more tightly.

There are limits. With rate-monotonic scheduling on each core and a utilization-bound test, the worst-case guaranteed utilization of first-fit partitioning is only about 41 % of the total capacity, as Oh and Baker showed in 1998. In practice, with exact tests and realistic periods, partitioned fixed-priority scheduling often reaches 80 to 90 %. The code below partitions the NS-5D task set onto two cores with first-fit and worst-fit decreasing, using exact response-time analysis on each core.

from math import ceil

# name, C, T (= D) in microseconds for the two-approach NS-5D
tasks = [("RADAR-N", 1_200, 6_250), ("RADAR-S", 1_200, 6_250), ("CANTX", 800, 10_000),
         ("STATS", 4_000, 20_000), ("CLASS-N", 11_000, 25_000), ("CLASS-S", 11_000, 25_000),
         ("LOG", 8_000, 100_000), ("HOUSE", 20_000, 1_000_000)]

def schedulable(core):
    """exact response-time analysis under rate-monotonic priorities on one core"""
    core = sorted(core, key=lambda x: x[2])
    for i, (_, c, t) in enumerate(core):
        r = c
        while True:
            nxt = c + sum(ceil(r / tj) * cj for _, cj, tj in core[:i])
            if nxt > t:
                return False
            if nxt == r:
                break
            r = nxt
    return True

def partition(tasks, m, fit):
    cores = [[] for _ in range(m)]
    for task in sorted(tasks, key=lambda x: x[1] / x[2], reverse=True):   # decreasing utilization
        order = range(m)
        if fit == "worst":
            order = sorted(range(m), key=lambda k: sum(c / t for _, c, t in cores[k]))
        for k in order:
            if schedulable(cores[k] + [task]):
                cores[k].append(task)
                break
        else:
            return None, task[0]
    return cores, None

print(f"total utilization {sum(c / t for _, c, t in tasks):.3f} on 2 cores")
for fit in ("first", "worst"):
    cores, failed = partition(tasks, 2, fit)
    print(f"\n{fit}-fit decreasing:")
    if cores is None:
        print("  no partition found; could not place", failed)
        continue
    for k, core in enumerate(cores):
        u = sum(c / t for _, c, t in core)
        names = ", ".join(n for n, _, _ in sorted(core, key=lambda x: x[2]))
        print(f"  core {k}: U = {u:.3f}  {names}")

total utilization 1.644 on 2 cores

first-fit decreasing:
  core 0: U = 0.980  CANTX, CLASS-N, CLASS-S, HOUSE
  core 1: U = 0.664  RADAR-N, RADAR-S, STATS, LOG

worst-fit decreasing:
  core 0: U = 0.820  CANTX, STATS, CLASS-N, LOG, HOUSE
  core 1: U = 0.824  RADAR-N, RADAR-S, CLASS-S

Both heuristics succeed. First-fit packs core 0 to a utilization of 0.980 with CANTX, both classifiers and housekeeping, which passes exact analysis only because the classifiers' 25 ms period is a multiple of CANTX's 10 ms; core 1 carries the rest at 0.664. Worst-fit balances the cores at 0.820 and 0.824. Jonah prefers the balanced partition. Its margins are similar on both cores, so either classifier can grow without forcing a repartition, although, as the last section of this lesson shows, its placement of the radar tasks still needs adjusting. A first-fit partition that leaves one core almost full is efficient on paper but fragile in a product that will gain features.

Interference through shared hardware

On a single core, a task's execution time depends mainly on its own code and data. On a multicore processor, cores share the memory bus, the memory controller, the last-level cache, the interconnect and peripherals. A task's execution time then depends on what runs on the other cores at the same time: if core 0 streams through a large buffer while core 1 runs the classifier, core 1's memory accesses wait in the controller's queue and its cache lines may be evicted by core 0's traffic. Measurements on commercial multicore processors have shown execution times growing several-fold under heavy co-runner memory traffic. The avionics certification guidance for multicore processors, published by the major aviation authorities as CAST-32A in 2016 and later as AMC 20-193 in Europe, requires applicants to identify these interference channels and show that their effects are bounded.

Several techniques make the interference manageable. Cache partitioning, through hardware way-locking or page coloring, gives each core or task a fixed part of the shared cache. Memory bandwidth regulation gives each core a budget of memory accesses per period, enforced by performance counters, so that one core cannot saturate the bus. Time-division access to shared resources makes interference independent of co-runners at some cost in average speed. Local memories avoid the problem altogether: the NS-5D gives each core its own tightly coupled memory for code and data, and Jonah keeps the classifiers' working sets inside it so that their execution times do not depend on the other core.

Shared resources across cores

Mutexes shared between tasks on different cores raise a new problem. A task blocked on a remote lock cannot simply donate its priority to the holder, because the holder runs on another core under another scheduler. Multiprocessor locking protocols such as the multiprocessor stack resource policy (MSRP) use non-preemptive spinning: a task that needs a global resource spins on its own core, at raised priority, until the resource is free, and the holder runs its critical section non-preemptively. Blocking then includes spin time, bounded by the critical sections of tasks on other cores. Other protocols suspend instead of spinning or allow a waiting task to help the holder finish. All of them make global critical sections more expensive than local ones, so a good partition places tasks that share resources on the same core. In the NS-5D, each classifier shares its frame buffer with its own radar task, and CANTX shares the detection queue with both classifiers; the worst-fit partition puts both radar tasks on core 1 with only one classifier, so one radar and classifier pair would share its frame buffer across cores. Jonah therefore swaps RADAR-N with STATS, giving core 0 RADAR-N, CANTX, CLASS-N, LOG and HOUSE at 0.812 and core 1 RADAR-S, STATS and CLASS-S at 0.832. Exact analysis confirms both cores, and only the detection queue remains a cross-core resource.