Technical Reports

Rany Kahil, Peter Poplavko, Dario Socci, Saddek Bensalem
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.

Contact | Plan du site | Site réalisé avec SPIP 4.2.16 + AHUNTSIC [CC License]

info visites 4198253