By the same authors

From the same journal

From the same journal

Multi-core cyclic executives for safety-critical systems

Research output: Contribution to journalArticle

Published copy (DOI)

Author(s)

  • Calvin Deutschbein
  • Thomas David Fleming
  • Alan Burns
  • Sanjoy Baruah

Department/unit(s)

Publication details

JournalScience of Computer Programming
DateAccepted/In press - 20 Nov 2018
DateE-pub ahead of print - 30 Nov 2018
DatePublished (current) - 1 Mar 2019
Volume172
Number of pages15
Pages (from-to)102-116
Early online date30/11/18
Original languageEnglish

Abstract

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.

Bibliographical note

©2018 Elsevier B.V. All rights reserved. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy.

    Research areas

  • Multiprocessor scheduling Cyclic executives Linear program (LP) Approximation algorithm

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations