PRODUCT HOW-TO: Improve CPU Utilization with DEOS Slack RTOS Scheduling

The Deos real-time operating system with slack scheduling satisfies mission-critical requirements while providing developers with simplified access to the CPU's full performance.

A time-partitioned real-time operating system that conforms to mission-critical specification ARINC-653 will guarantee that a specific computation will have access to the CPU for a specific amount of time (i.e., budget) at a bounded, deterministic location within the scheduling timeline's major frame (i.e., the hyper-period).

This guarantee is a key enabler towards the development of highly integrated systems that allow software of varying degrees of criticality to coexist on the same platform.

By assigning computational tasks (processes) to run at specific times within the hyper-period, and budgeting enough time for worst case execution of each process, developers can develop a timeline that ensures high criticality applications will have the CPU time and deterministic operation they require. The RTOS terminates any lower criticality applications that exceed their budget to prevent any interference.

This time-partitioning approach works well for periodic computations that have a small deviation between their worst case execution and their nominal case execution. The timing guarantees come at a price, however.

By setting aside worst case execution times for each process, the scheduler ensures worst case system performance, every time. In other words, from a CPU bandwidth perspective, it is as if every time the hyper-period is executed, every computation always experiences its worst case execution.

The approach thus leads to the all-too-common occurrence that the system runs out of CPU budget time (i.e., no more time available to allocate in the hyper-period), while profiling shows actual average CPU utilization of 50% (or less in some scenarios).

The situation arises because, in the vast majority of cases, computations experiencing their worst case executions are rare. The occurrence of multiple computations experiencing their worst case executions during the same period is even more improbable. Thus, for the vast majority of executions, unused CPU budget shows up as useless CPU idle time. (Figure 1 below)

Figure 1. ARINC-653 Time partitioning often yields unused CPU time.

Some common scenarios further exacerbate the problem: First, the system must perform aperiodic activities, such as interrupts to service, aperiodic client-server exchanges, etc. Second, the CPU budget required in order to guarantee safe execution is insufficient to meet performance needs; and third, significant deviation exists between nominal case and worst case execution times.

The need to poll for the occurrence of an interrupt, for example, increases unused CPU idle time because of the requirement to budget worst-case time for interrupt handling within each hyper-period, even if the expected interrupt rate is low.

A byproduct of this scheduling can be significant latency in interrupt response. If the interrupt occurs after the handler's scheduled time with in the hyper-period, the system cannot respond until the next scheduled execution of the handler. Thus, latency can be as great as a full hyper-period.

DDC-I's Deos rate monotonic scheduling (RMS) RTOS with patented slack scheduling technology provides an alternative approach to the fixed time partitioning of ARINC-653 that guarantees time and scheduling of processes (called threads in Deos) while also enabling designs to utilize up to 100% of the CPU's processing potential.

One key is allowing the RTOS to schedule thread execution, subject to any needed constraints, at run time rather than having the schedule fixed at software integration time as in ARINC-653. The other key is recovering CPU slack time for use by threads as needed.