Scheduling Analysis of Imprecise Mixed-Criticality Real-Time Tasks

Di Liu, Nan Guan, Jelena Spasic, Gang Chen, Songran Liu, Todor Stefanov, Wang Yi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)


In this paper, we study the scheduling problem of the imprecise mixed-criticality model (IMC) under earliest deadline first with virtual deadline (EDF-VD) scheduling upon uniprocessor systems. Two schedulability tests are presented. The first test is a concise utilization-based test which can be applied to the implicit deadline IMC task set. The suboptimality of the proposed utilization-based test is evaluated via a widely-used scheduling metric, speedup factors. The second test is a more effective test but with higher complexity which is based on the concept of demand bound function (DBF). The proposed DBF-based test is more generic and can apply to constrained deadline IMC task set. Moreover, in order to address the high time cost of the existing deadline tuning algorithm, we propose a novel algorithm which significantly improve the efficiency of the deadline tuning procedure. Experimental results show the effectiveness of our proposed schedulability tests, confirm the theoretical suboptimality results with respect to speedup factor, and demonstrate the efficiency of our proposed algorithm over the existing deadline tunning algorithm. In addition, issues related to the implementation of the IMC model under EDF-VD are discussed.

Original languageEnglish
Article number8247214
Pages (from-to)975-991
Number of pages17
JournalIEEE Transactions on Computers
Issue number7
Publication statusPublished - 1 Jul 2018


  • imprecise model
  • mixed-criticality
  • Real-time systems

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this