Necessary feasibility analysis for mixed-criticality task systems on uniprocessor

Hoon Sung Chwa, Hyeongboo Baek, Jinkyu Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


While feasibility of timing guarantees has been extensively studied for single-criticality (SC) task systems, the same cannot be said true for mixed-criticality (MC) task systems. In particular, there exist only a few studies that address necessary feasibility conditions for MC task systems, and all of them have derived trivial results from existing SC studies that rely on simple demand-supply comparison. In this paper, we develop necessary feasibility tests for MC task systems on a uniprocessor platform, which is the first study that yields non-trivial results for MC necessary feasibility. To this end, we investigate characteristics of MC necessary feasibility conditions. Due to the existence of the mode change and consequences thereof, the characteristics pose new challenges that cannot be resolved by existing techniques for SC task systems, including how to calculate demand when the mode change occurs, how to determine the target sub-intervals for demand-supply comparison, how to derive an infeasibility condition from demand-supply comparisons with different possible mode change instants, how to select a scenario to specify the mode change instant without the target scheduling algorithm, and how to find infeasible task sets with reasonable time-complexity. By addressing those challenges, we develop a new necessary feasibility test and its simplified version. The simulation results demonstrate that the proposed tests find a number of additional infeasible task sets which have been proven neither feasible nor infeasible by any existing studies.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 40th Real-Time Systems Symposium, RTSS 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages12
ISBN (Electronic)9781728144030
StatePublished - Dec 2019
Event40th IEEE Real-Time Systems Symposium, RTSS 2019 - Hong Kong, China
Duration: 3 Dec 20196 Dec 2019

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Conference40th IEEE Real-Time Systems Symposium, RTSS 2019
CityHong Kong


  • Feasibility Analysis
  • Mixed Criticality Systems
  • Uniprocessor Scheduling


Dive into the research topics of 'Necessary feasibility analysis for mixed-criticality task systems on uniprocessor'. Together they form a unique fingerprint.

Cite this