Rany Kahil, Peter Poplavko, Dario Socci, Saddek Bensalem
Revisiting the Computational Complexity of Mixed-Criticality Scheduling (2017)
Revisiting the Computational Complexity of Mixed-Criticality Scheduling (2017)
TR-2017-7.pdf
Keywords: mixed-critical systems, real-time scheduling, computational complexity
Abstract: In this paper we revisit and correct some previous theoretical results on mixed critical scheduling. We find a counter-example to the proof that this optimisation problem belongs to the class NP, which reopens the question on its computational complexity upper bound. Nevertheless, we show that the quite common dual-critical single-processor fixed priority per mode scheduling is in NP, as it is not concerned by the refuted result. However, to show this required to find a proof that this scheduling policy is sustainable in common mixed criticality sense. On a multiprocessor this, quite unexpectedly, turns out to be not the case, as shown by analysing a counterexample.
