Skip to main content

What is the ARINC653 Scheduler?

By December 16, 2013March 4th, 2019Uncategorized

The Xen ARINC 653 scheduler is a real time scheduler that has been in Xen since 4.1.0.  It is a cyclic executive scheduler with a specific usage in mind, so unless one has aviation experience they are unlikely to have ever encountered it.
The scheduler was created and is currently maintained by DornerWorks.

Background

The primary goal of the ARINC 653 specification [1] is the isolation or partitioning of domains.  The specification goes out of its way to prevent one domain from adversely affecting any other domain, and this goal extends to any contended resource, including but not limited to I/O bandwidth, CPU caching, branch prediction buffers, and CPU execution time.
This isolation is important in aviation because it allows applications at different levels of certification (e.g. Autopilot – Level A Criticality, In-Flight Entertainment – Level E Criticality, etc…) to be run in different partitions (domains) on the same platform.  Historically to maintain this isolation each application had its own separate computer and operating system, in what was called a federated system.  Integrated Modular Avionics (IMA) systems were created to allow multiple applications to run on the same hardware.  In turn, the ARINC653 specification was created to standardize an Operating System for these platforms.  While it is called an operating system and could be implemented as such, it can also be implemented as a hypervisor running multiple virtual machines as partitions.  Since the transition from federated to IMA systems in avionics closely mirrors the transition to virtualized servers in the IT sector, the latter implementation seems more natural.
Beyond aviation, an ARINC 653 scheduler can be used where temporal isolation of domains is a top priority, or in security environments with indistinguishability requirements, since a malicious domain should be unable to extract information through a timing side-channel.  In other applications, the use of an ARINC 653 scheduler would not be recommended due to the reduced performance.

Scheduling Algorithm

The ARINC 653 scheduler in Xen provides the groundwork for the temporal isolation of domains from each other. The domain scheduling algorithm itself is fairly simple:  a fixed predetermined list of domains is repeatedly scheduled with a fixed periodicity resulting in a complete and, most importantly, predictable schedule.  The overall period of the scheduler is know as a major frame, while the individual domain execution windows in the schedule are know as minor frames.
Major_Minor_Frame
As an example, suppose we have 3 domains all with periods of 5, 6, 10 ms and worst case running times respectively of 1 ms, 2 ms, and 3 ms.  The major frame is set to the least common multiple of these periods (30 ms) and minor frames are selected so that the period, runtime, and deadline constraints are met.  One resulting schedule is shown below, though there are other possibilities.
ExampleSchedule
The ARINC 653 scheduler is only concerned with the scheduling of domains. The scheduling of real-time processes within a domain is performed by that domain’s process scheduler.  In a compliant ARINC 653 system, these processes are scheduled using a fixed priority scheduling algorithm, but if ARINC 653 compliance is not a concern any other process scheduling method may be used.

Using the Scheduler

Directions for using the scheduler can be found on the Xen wiki at ARINC653 Scheduler. When using the scheduler, the most obvious effect will be that the cpu usage and execution windows for each domain will be fixed regardless of whether the domain is performing any work.
Currently multicore operation of the scheduler is not supported.  Extending the scheduling algorithm to multiple cores is trivial, but the isolation of domains in a multicore system requires a number of mitigation techniques not required in single-core systems.[2]

References

[1] ARINC Specification 653P1-3, “Avionics Application Software Standard Interface Part 1 – Required Services” November 15, 2010
[2] EASA.2011/6 MULCORS – Use of Multicore Processors in airborne systems