Investigating Mixed Criticality Cyclic Executive Schedule Generation

Mixed Criticality systems require a difficult compromise to be drawn between efficient system utilisation and sufficient separation of critical components. In addition to these challenges, hardware platforms are becoming increasingly multi- core in nature bringing up additional scheduling issues. Previous publications have met these challenges by suggesting a Cyclic Executive based approach for Mixed Criticality scheduling. They make use of a barrier protocol to separate the execution within each minor cycle, executing higher critical work, then less critical work. The barrier protocol allowed such a separation of criticalities to remain consistent across all cores in a given platform. This strict separation has the advantage that higher criticality work cannot suffer interference from lower, including communication and recourse access. One of the key challenges of using a Cyclic Executive is the construction of a valid schedule. In this work we consider the question, “Is it worth using an optimal solver such as Integer Linear Programming (ILP) for Cyclic Executive schedule generation?”. We start by extending the Cyclic Executive model to include multiple minor cycles. An ILP model is described and evaluated against the heuristic worst fit. The results show that ILP significantly outperforms worst fit. Finally we show that ILP is not only effective, but also efficient in terms of runtime and scalability for the examples and parameters considered in this work, making it a practical choice for Cyclic Executive schedule generation of real systems.