Multi-core cyclic executives for safety-critical systems

In a cyclic executive, a series of pre-determined frames are executed in sequence; once the series is complete the sequence is repeated. Within each frame individual units of computation are executed, again in a pre-specified sequence. Although they suffer from a number of limitations, cyclic executives have the advantage of being fully deterministic, and may be implemented with very low runtime overhead; as a consequence of these advantages, run-time schedulers in highly safety-critical real-time systems have historically been implemented as cyclic executives.Industrial applications of the cyclic executive framework are currently primarily restricted to uniprocessor platforms; in this paper, we consider the implementation of cyclic executives upon multi-core platforms. We present a Linear Programming (LP) based formulation of the problem of constructing cyclic executives upon multiprocessors for a particular kind of recurrent real-time workload — collections of implicit-deadline periodic tasks. We describe techniques for solving the LP formulation under different kinds of restrictions in order to obtain preemptive and non-preemptive cyclic executives. Our algorithms for constructing preemptive cyclic executives have running time polynomial in the size of the cyclic executive. We present an exact algorithm for constructing non-preemptive cyclic executives that has worst-case running time exponential in the size of the cyclic executive; however, state-of-the-art LP solvers appear to often be able to construct fairly large cyclic executives in a reasonable amount of time. We also present an approximation algorithm for constructing non-preemptive cyclic executives that does run in polynomial time, and evaluate the effectiveness of this approximation algorithm both theoretically via the speedup factor metric, and experimentally via experiments on synthetically generated workloads. We additionally identify a particular restricted kind of workload that is quite commonly found in practice, for which non-preemptive cyclic executives can be constructed more efficiently than in the general case.