Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems

Nan Guan, Pontus Ekberg, Martin Stigge, Yi Wang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

97 Citations (Scopus)


An increasing trend in embedded system design is to integrate components with different levels of criticality into a shared hardware platform for better cost and power efficiency. Such mixed-criticality systems are subject to certifications at different levels of rigorousness, for validating the correctness of different subsystems on various confidence levels. The real-time scheduling of certifiable mixed-criticality systems has been recognized to be a challenging problem, where using traditional scheduling techniques may result in unacceptable resource waste. In this paper we present an algorithm called PLRS to schedule certifiable mixed-criticality sporadic tasks systems. PLRS uses fixed-job-priority scheduling, and assigns job priorities by exploring and balancing the asymmetric effects between the workload on different criticality levels. Comparing with the state-of-the-art algorithm by Li and Baruah for such systems, which we refer to as LB, PLRS is both more effective and more efficient: (i) The schedulability test of PLRS not only theoretically dominates, but also on average significantly outperforms LB's. (ii) The run-time complexity of PLRS is polynomial (quadratic in the number of tasks), which is much more efficient than the pseudo-polynomial run-time complexity of LB.
Original languageEnglish
Title of host publicationProceedings - 2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011
Number of pages11
Publication statusPublished - 1 Dec 2011
Externally publishedYes
Event2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011 - Vienna, Austria
Duration: 29 Nov 20112 Dec 2011


Conference2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems'. Together they form a unique fingerprint.

Cite this