Contract-Based Scheduling Explained: Making Embedded Software Composable

Embedded products are no longer built by one team writing one program. A modern vehicle controller, industrial gateway or drone integrates software from several suppliers, open-source stacks and in-house components, often on the same multicore processor. Each component may be correct and well tested in isolation, yet the integrated system can still miss deadlines because the components compete for processor time, network bandwidth and memory in ways nobody analyzed together.

Contract-based scheduling attacks this problem directly. Instead of letting every task fight for resources under a global priority scheme, each application states what it needs in a formal contract, the platform checks whether it can honor that contract, and once accepted, the platform enforces it. The result is temporal isolation and composability: components can be developed, analyzed and certified independently, then integrated with predictable timing. This article explains the concepts, the underlying theory and the lessons from the European research projects that developed the idea for embedded systems.

The integration problem: why priorities do not compose

In classic fixed-priority systems, the timing of every task depends on all higher-priority tasks. The response-time analysis of a low-priority task includes the worst-case execution times and periods of every task above it. That works well when one team controls the entire task set, but it breaks down in an integration setting:

• Priorities are a global resource. Two suppliers cannot independently choose priorities; someone must assign a single global order and re-run the analysis for everyone.
• Faults propagate. If a high-priority task exceeds its WCET because of a bug or an unexpected input, every lower-priority task suffers, possibly in a component that was certified to a higher integrity level.
• Change is expensive. Adding a feature to one component can invalidate the schedulability argument of all others.
• Dynamic workloads do not fit. Multimedia, vision and adaptive control applications have execution times that vary widely; dimensioning everything for the worst case wastes resources.

What integrators want is the property they already enjoy for memory protection: each component gets its own space and cannot corrupt others. Contract-based scheduling extends that idea to time.

Foundations: resource reservations and servers

The mechanism behind every contract is a resource reservation, implemented by a server. A reservation is described by a budget Q and a period P: the server guarantees that its client receives Q units of processor time every P time units, and (if the reservation is “hard”) never more than that while other servers need the CPU. The ratio Q/P is the reserved bandwidth.

Several server algorithms exist. For fixed-priority systems there are the deferrable and sporadic servers. For EDF-scheduled systems, the most influential is the Constant Bandwidth Server (CBS) introduced by Abeni and Buttazzo in 1998. A CBS assigns each job a scheduling deadline; when the budget is exhausted, it is recharged and the deadline is postponed by one period. As a result, the server never demands more than its bandwidth, regardless of how its client behaves. Linux implements a variant of this algorithm in SCHED_DEADLINE.

With EDF-based servers on a single processor, admission control is particularly simple: a set of reservations is feasible if Σ Qk/Pk ≤ 1 (minus a margin for overheads). That is a direct consequence of EDF’s optimality on a uniprocessor, discussed in our comparison of Rate Monotonic and EDF.

Hierarchical and compositional analysis

A reservation turns the processor into a set of slower “virtual processors.” To check that the tasks inside a reservation meet their deadlines, you need to know the minimum service the reservation supplies in any time window. Compositional scheduling theory, notably the periodic resource model of Shin and Lee (2003), captures this with a supply bound function. For a periodic reservation (Q, P), the worst case is that the client has just missed its budget in one period and receives it as late as possible in the next, leading to a blackout of up to 2(P − Q) before service resumes. Inner tasks are then analyzed against that conservative supply, independent of every other component.

What is a scheduling contract?

A contract raises the abstraction level from “budget and period” to a statement of the application’s requirements and its flexibility. In the frameworks developed in FIRST and FRESCOR, a contract typically contained:

The essential split is between the minimum, which is guaranteed, and the range above it, which is a request for spare capacity the system may grant when available. This lets an application such as video analytics run at full quality when the platform is lightly loaded and degrade gracefully, rather than fail, when more critical functions need resources.

Negotiation, admission control and spare capacity

Contracts are not configured statically; they are negotiated at run time. The sequence is:

1. The application creates a contract object and fills in its parameters.
2. It submits the contract to the contract manager, which runs an online schedulability test with all already accepted contracts’ minimum requirements.
3. If the test passes, the manager creates a server (virtual resource) for the application and binds its threads to it. If not, the negotiation is rejected and the application keeps running under its previous contract, if any.
4. The manager redistributes spare capacity among all servers according to importance and weight, within each contract’s maximum.
5. Later, the application may renegotiate, for example when switching operating modes, or cancel the contract and release its resources.

A worked example

Assume a single CPU scheduled by EDF-based servers, with 5% reserved for system overhead, so contracts may use a total bandwidth of 0.95. Two contracts are already accepted:

The guaranteed minimums sum to 0.60, leaving 0.35 of spare capacity. A has no range above its minimum, so the spare is shared by B and C in proportion to their weights, 3:1. B receives 0.2625 and C 0.0875; both stay below their maximums, so no capping is needed. Frameworks can also apply importance first (serving higher-importance contracts up to their maximum before others) and weight second. Either policy is legitimate; what matters is that it is explicit and deterministic.

Now a new contract D (a communication stack, minimum 0.30) arrives. The admission test checks 0.20 + 0.30 + 0.10 + 0.30 = 0.90 ≤ 0.95: accepted. The spare capacity shrinks to 0.05, so B drops to 0.3375 and C to 0.1125, reductions both were designed to tolerate. A further request E with minimum 0.10 would give 1.00 > 0.95 and is rejected, protecting every existing guarantee.

Inside contract A, a control task with WCET 1 ms and a 20 ms deadline can be verified in isolation: with Q = 2 ms and P = 10 ms the worst-case blackout is 2(10 − 2) = 16 ms, so the task completes within 17 ms ≤ 20 ms no matter what B, C or D do. You can reproduce the processor-level part of such calculations in our schedulability calculator.

What the API looks like

The following pseudocode shows the typical flow. It is illustrative, written in the general style of contract APIs from this research line rather than reproducing any specific function signature.

contract c = contract_init();
contract_set_basic(&c, budget_min = 2ms, period_max = 10ms,
                   workload = BOUNDED);
contract_set_reclamation(&c, budget_max = 4ms, period_min = 10ms,
                         importance = 1, weight = 1);
contract_set_deadline(&c, 8ms);

if (contract_negotiate(&c, &vres) == ACCEPTED) {
    bind_thread(self(), vres);
    for (;;) {
        do_control_step();      // budget enforced by the server
        wait_for_next_period(vres);
    }
} else {
    enter_safe_degraded_mode();
}

The FIRST and FRESCOR projects

Contract-based scheduling for embedded systems was developed largely in two consecutive European research projects. The FIRST project (IST-2001-34140) produced the Flexible Scheduling Framework (FSF), which defined the contract model for the processor: minimum budget and period, deadlines, and rules for distributing spare capacity among applications, all accessed through a common API over different underlying scheduling policies, both fixed-priority and EDF.

The FRESCOR project (Framework for Real-time Embedded Systems based on COntRacts, FP6 IST-034026, 2006–2009), coordinated by Universidad de Cantabria, built directly on FSF. It broadened the contract model beyond the CPU to other resources such as networks and memory, addressed distributed transactions spanning several nodes, and connected contracts with design-time analysis and component-based development tools. Implementations targeted several platforms, including MaRTE OS, Linux, a Partikle/RTLinux-style environment and ERIKA Enterprise, among others. A broader description of the goals and outcomes is available in the archived project overview and the list of consortium partners.

Benefits, limitations and design advice

Benefits

• Composability: components are analyzed against their reservations; integration requires only an admission test.
• Robustness: overruns are contained in the offending server.
• Efficiency: spare capacity is reclaimed by applications that can use it instead of being wasted on worst-case dimensioning.
• Adaptivity: renegotiation supports mode changes and graceful degradation.

Limitations

• Budgets still need execution-time estimates. For hard requirements the minimum budget must cover a safe WCET; see our guide to WCET analysis methods.
• Abstraction overhead. Servers add latency (the blackout effect) and some run-time cost, so reservations are typically over-provisioned relative to raw utilization.
• Shared resources such as locks, caches and memory buses can break isolation unless explicitly handled, a challenge that grows on multicore hardware.
• Certification practice in some domains still favors static, time-partitioned designs (such as ARINC 653 in avionics) over dynamic negotiation.

Contracts also connect naturally with mixed-criticality systems, where importance levels map onto criticality, and with multicore scheduling, where reservations can be partitioned across cores. If your team wants hands-on practice, our contract-based scheduling training workshop covers reservation design and analysis with exercises on Linux.

References and further reading

1. FRESCOR: Framework for Real-time Embedded Systems based on COntRacts — CORDIS, European Commission
2. Aldea, M. et al. (2006). “FSF: A Real-Time Scheduling Architecture Framework.” Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS).
3. Abeni, L. and Buttazzo, G. (1998). “Integrating Multimedia Applications in Hard Real-Time Systems.” Proceedings of the IEEE Real-Time Systems Symposium (RTSS).
4. Shin, I. and Lee, I. (2003). “Periodic Resource Model for Compositional Real-Time Guarantees.” Proceedings of the IEEE Real-Time Systems Symposium (RTSS).
5. Rajkumar, R., Juvva, K., Molano, A. and Oikawa, S. (1998). “Resource Kernels: A Resource-Centric Approach to Real-Time and Multimedia Systems.” Proceedings of SPIE/ACM Multimedia Computing and Networking.
6. Deadline Task Scheduling (SCHED_DEADLINE) — Linux kernel documentation
7. Buttazzo, G. C. (2011). Hard Real-Time Computing Systems, 3rd ed., chapters on aperiodic servers and resource reservations — Springer