research-article

Algorithmic Complexity of Correctness Testing in MC-Scheduling

Authors:

Rany Kahil,

Dario Socci,

Peter Poplavko,

Saddek BensalemAuthors Info & Claims

RTNS '18: Proceedings of the 26th International Conference on Real-Time Networks and Systems

Pages 180 - 190

https://doi.org/10.1145/3273905.3273916

Published: 10 October 2018 Publication History

Get Access

Abstract

Previously, a lot of research has been done on scheduling a finite set of mixed criticality jobs with two levels of criticality on a single processor, which is also the subject of this work.

It has been claimed that testing the correctness of solutions for this scheduling problem can be done in polynomial time. In this paper, we give a counter example to one of the lemmas used in that proof, reopening the question on whether the scheduling problem is in class NP. Taking into account our counter example, the authors who initially proved that correctness testing can be done in polynomial time published a fix to their proof.

In the past, we proved that a previously existing correctness test is applicable for a quite general class of policies. From these results, for essentially the same class of policies, in this work we derive another correctness test, which transforms the policy to a new policy having a set of time-triggered tables, one for each criticality level. We show that the two policies are equivalent, in the sense that if one successfully schedules a jobs instance then so does the other. Thus the new transformed policy can be used for testing correctness of the original policy. We show that this correctness test has a lower algorithmic complexity than the existing test, due to the fact that the testing is done on only two static tables.

References

[1]

Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Pontus Ekberg, Haohan Li, Alberto Marchetti-Spaccamela, Nicole Megow, and Leen Stougie. 2018. Erratum for Scheduling real-time mixed-criticality jobs. (2018).

Google Scholar

[2]

Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Nicole Megow, and Leen Stougie. 2012. Scheduling Real-Time Mixed-Criticality Jobs. IEEE Trans. Comput. 61, 8 (aug. 2012), 1140--1152.

Digital Library

Google Scholar

[3]

Sanjoy Baruah and Alan Burns. 2006. Sustainable scheduling analysis. In null. IEEE, 159--168.

Digital Library

Google Scholar

[4]

Vicent Brocal, Patricia Balbastre, Rafael Ballester, and Ismael Ripoll. 2011. Task period selection to minimize hyperperiod. In Emerging Technologies & Factory Automation (ETFA), 2011 IEEE 16th Conference on. IEEE, 1--4.

Crossref

Google Scholar

[5]

Rhan Ha and J. W S Liu. 1994. Validating timing constraints in multiprocessor and distributed real-time systems. In Proc. Int. Conf. Distributed Computing Systems. 162--171.

Google Scholar

[6]

Rany Kahil, Peter Poplavko, Dario Socci, and Saddek Bensalem. 2017. Revisiting the Computational Complexity of Mixed-Critical Scheduling. Proc. WMC, RTSS (2017), 25--30.

Google Scholar

[7]

Rany Kahil, Dario Socci, Peter Poplavko, and Saddek Bensalem. 2018. Predictability in Mixed-Criticality Systems. In RTCSA2018.

Google Scholar

[8]

Ismael Ripoll and Rafael Ballester-Ripoll. 2013. Period selection for minimal hyperperiod in periodic task systems. IEEE Trans. Comput. 62, 9 (2013), 1813--1822.

Digital Library

Google Scholar

[9]

Dario Socci, Peter Poplavko, Saddek Bensalem, and Marius Bozga. 2013. Mixed Critical Earliest Deadline First. In Euromicro Conf. on Real-Time Systems (ECRTS'13). IEEE, 93--102.

Digital Library

Google Scholar

[10]

Dario Socci, Peter Poplavko, Saddek Bensalem, and Marius Bozga. 2013. Time-Triggered Mixed-Critical Scheduler. Proc. WMC, RTSS (2013), 67--72.

Google Scholar

[11]

Steve Vestal. 2007. Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance. In Real-Time Systems Symposium (RTSS'07). IEEE, 239--243.

Digital Library

Google Scholar

Cited By

View all

Socci DPoplavko PBensalem SBozga M(2019)Priority-based scheduling of mixed-critical jobsReal-Time Systems10.1007/s11241-019-09329-955:4(709-773)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s11241-019-09329-9
Singh JSantinelli LReghenzani FBletsas KDoose DGuo Z(2019)Mixed Criticality Scheduling of Probabilistic Real-Time SystemsDependable Software Engineering. Theories, Tools, and Applications10.1007/978-3-030-35540-1_6(89-105)Online publication date: 18-Nov-2019
https://doi.org/10.1007/978-3-030-35540-1_6

Index Terms

Algorithmic Complexity of Correctness Testing in MC-Scheduling
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
  2. Real-time systems

Recommendations

Complexity issues in vertex-colored graph pattern matching

Searching for motifs in graphs has become a crucial problem in the analysis of biological networks. In the context of metabolic network analysis, Lacroix et al. [V. Lacroix, C.G. Fernandes, M.-F. Sagot, IEEE/ACM Transactions on Computational Biology and ...
Parameterized complexity of a coupled-task scheduling problem

In this article, we investigate the parameterized complexity of coupled-task scheduling in the presence of compatibility constraints given by a compatibility graph. In this model, each task contains two sub-tasks delayed by an idle time. Moreover, a sub-...
Complexity of preemptive minsum scheduling on unrelated parallel machines

We show that the problems of minimizing total completion time and of minimizing the number of late jobs on unrelated parallel machines, when preemption is allowed, are both NP-hard in the strong sense. The former result settles a long-standing open ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

RTNS '18: Proceedings of the 26th International Conference on Real-Time Networks and Systems

October 2018

277 pages

ISBN:9781450364638

DOI:10.1145/3273905

General Chairs:
Yassine Ouhammou
LIAS, ISAE-ENSMA, France
,
Frédéric Ridouard
LIAS, University of Poitiers, France
,
Emmanuel Grolleau
LIAS, ISAE-ENSMA, France
,
Program Chairs:
Mathieu Jan
CEA LIST, France
,
Moris Behnam
Mälardalen University, Sweden

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

University of Poitiers: University of Poitiers

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 October 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

RTNS '18

RTNS '18: 26th International Conference on Real-Time Networks and Systems

October 10 - 12, 2018

Chasseneuil-du-Poitou, France

Acceptance Rates

RTNS '18 Paper Acceptance Rate 25 of 52 submissions, 48%;

Overall Acceptance Rate 119 of 255 submissions, 47%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
48
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Socci DPoplavko PBensalem SBozga M(2019)Priority-based scheduling of mixed-critical jobsReal-Time Systems10.1007/s11241-019-09329-955:4(709-773)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s11241-019-09329-9
Singh JSantinelli LReghenzani FBletsas KDoose DGuo Z(2019)Mixed Criticality Scheduling of Probabilistic Real-Time SystemsDependable Software Engineering. Theories, Tools, and Applications10.1007/978-3-030-35540-1_6(89-105)Online publication date: 18-Nov-2019
https://doi.org/10.1007/978-3-030-35540-1_6

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Complexity issues in vertex-colored graph pattern matching

Parameterized complexity of a coupled-task scheduling problem

Complexity of preemptive minsum scheduling on unrelated parallel machines

Comments

Information

Published In

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations