DROPS

Document

DOI: 10.4230/LIPIcs.ECRTS.2026.21

Semi-Clairvoyant Scheduling for Jobs with Multiple Criticalities

Authors: Kunal Agrawal, Tung Duc Thai, and Jinhao Zhao

Published in: LIPIcs, Volume 375, 38th European Conference on Real-Time Systems (ECRTS 2026)

Abstract

This paper considers scheduling jobs semi-clairvoyantly in mixed-criticality systems. In the semi-clairvoyant model, unlike the non-clairvoyant model, we know the WCET mode of the job at job arrival. Prior work has only considered this model for dual criticality jobs. We consider this problem for an arbitrary number of criticalities. We prove that there exist semi-clairvoyant schedulers that guarantee schedulability with speedup (2^m-1)/2^{m-1} for systems with m criticality levels. In addition, we prove that this bound is tight by providing a job set construction that requires this speed for any semi-clairvoyant scheduler. Finally we provide a linear programming formulation that optimally schedules the semi-clairvoyant system of jobs. The number of variables and constraints is polynomial in the number of jobs, but exponential in the number of criticalities.

Cite as

Kunal Agrawal, Tung Duc Thai, and Jinhao Zhao. Semi-Clairvoyant Scheduling for Jobs with Multiple Criticalities. In 38th European Conference on Real-Time Systems (ECRTS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 375, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2026.21,
  author =	{Agrawal, Kunal and Thai, Tung Duc and Zhao, Jinhao},
  title =	{{Semi-Clairvoyant Scheduling for Jobs with Multiple Criticalities}},
  booktitle =	{38th European Conference on Real-Time Systems (ECRTS 2026)},
  pages =	{21:1--21:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-429-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{375},
  editor =	{Kritikakou, Angeliki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2026.21},
  URN =		{urn:nbn:de:0030-drops-266130},
  doi =		{10.4230/LIPIcs.ECRTS.2026.21},
  annote =	{Keywords: mixed-criticality, semi-clairvoyance, schedulers, linear programming}
}

Search Results

Documents authored by Thai, Tung Duc

Semi-Clairvoyant Scheduling for Jobs with Multiple Criticalities

Abstract

Cite as

Thanks for your feedback!

Could not send message