research-article

Public Access

A scheduling model inspired by control theory

Authors:

Sanjoy Baruah,

Vincenzo Bonifaci,

Alberto Marchetti-Spaccamela,

Victor VerdugoAuthors Info & Claims

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

Pages 78 - 87

https://doi.org/10.1145/3139258.3139272

Published: 04 October 2017 Publication History

PDF eReader

Abstract

Certain control computations may be modeled as periodic tasks with the correctness requirement that for each task, the fraction of jobs of the task that complete execution by their respective deadlines be no smaller than a specified value. This appears to be a correctness requirement that has not previously been studied in the real-time scheduling theory community; this paper formulates the problem and proposes some solution strategies.

References

[1]

G. Bernat, A. Burns, and A. Liamosi, "Weakly hard real-time systems" IEEE Transactions on Computers, vol. 50, no. 4, pp. 308--321, 2001.

Digital Library

Google Scholar

[2]

M. Branicky, S. Phillips, and W. Zhang, "Scheduling and feedback co-design for networked control systems," in Proceedings of the 41st IEEE Conference on Decision and Control, vol. 2, Dec 2002, pp. 1211--1217.

Google Scholar

[3]

A. Cervin, "Analysis of overrun strategies in periodic control tasks," in IFAC Proceedings, vol. 38, no. 1, pp. 219--224. Elsevier, 2005.

Crossref

Google Scholar

[4]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.

Digital Library

Google Scholar

[5]

M. Hamadaoui and P. Ramanathan, "A dynamic priority assignment technique for streams with (m, k)-firm deadlines," in Proceedings of the 23rd Annual International Symposium on Fault-Tolerant Computing (FTCS '94). IEEE Computer Society Press, Jun. 1994, pp. 196--205.

Google Scholar

[6]

D. S.Johnson, "Near-optimal bin packing algorithms," Ph.D. dissertation, Department of Mathematics, Massachusetts Institute of Technology, 1973.

Google Scholar

[7]

D. S. Johnson, "Fast algorithms for bin packing," Journal of Computer and Systems Science, vol. 8, no. 3, pp. 272--314, 1974.

Digital Library

Google Scholar

[8]

G. Koren and D. Shasha, "D^over: An optimal on-line scheduling algorithm for overloaded real-time systems," Computer Science Department, New York University, Tech. Rep. TR 594, 1992.

Google Scholar

[9]

R. Majumdar, I. Saha, and M. Zamani, "Performance-aware scheduler synthesis for control systems," in Proceedings of the Ninth ACM International Conference on Embedded Software, ser. EMSOFT '11. ACM, 2011, pp. 299--308.

Digital Library

Google Scholar

[10]

T. Yoshimoto and T. Ushio, "Optimal arbitration of control tasks by job skipping in cyber-physical systems" in Proceedings IEEE/ACM Second International Conference on Cyber-Physical Systems. IEEE, 2011, pp. 55--64.

Digital Library

Google Scholar

Cited By

View all

Willcock AFisher NChantem T(2021)Demand Characterization of CPS with Conditionally-Enabled Sensors2021 IEEE 27th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA52859.2021.00025(149-158)Online publication date: Aug-2021
https://doi.org/10.1109/RTCSA52859.2021.00025
Lee KKim MKim HChwa HLee JShin I(2019)Fault-Resilient Real-Time Communication Using Software-Defined Networking2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2019.00025(204-215)Online publication date: Apr-2019
https://doi.org/10.1109/RTAS.2019.00025
Yan RGuo J(2019)Timing Modeling and Analysis for AUTOSAR Schedule Tables2019 IEEE 19th International Symposium on High Assurance Systems Engineering (HASE)10.1109/HASE.2019.00027(123-130)Online publication date: Jan-2019
https://doi.org/10.1109/HASE.2019.00027
Show More Cited By

Index Terms

A scheduling model inspired by control theory

Recommendations

Scheduling and admission control
EDZL Scheduling Analysis
ECRTS '07: Proceedings of the 19th Euromicro Conference on Real-Time Systems

A schedulability test is derived for the global Earliest Deadline Zero Laxity (EDZL) scheduling algorithm on a platform with multiple identical processors. The test is sufficient, but not necessary, to guarantee that a system of independent sporadic ...
Early-release fair scheduling
Euromicro-RTS'00: Proceedings of the 12th Euromicro conference on Real-time systems

We present a variant of Pfair scheduling, which we call early-release fair (ERfair) scheduling. Like conventional Pfair scheduling, ERfair scheduling algorithms can be applied to optimally schedule periodic tasks on a multiprocessor system in polynomial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

October 2017

318 pages

ISBN:9781450352864

DOI:10.1145/3139258

Program Chairs:
Enrico Bini
University of Turin, Italy
,
Claire Pagetti
ONERA/ENSEEIHT/TUHH, Toulouse, France

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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF
AFOSR
ARO

Conference

RTNS '17

RTNS '17: 25th International Conference on Real-Time Networks and Systems

October 4 - 6, 2017

Grenoble, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
252
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)7

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Willcock AFisher NChantem T(2021)Demand Characterization of CPS with Conditionally-Enabled Sensors2021 IEEE 27th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA52859.2021.00025(149-158)Online publication date: Aug-2021
https://doi.org/10.1109/RTCSA52859.2021.00025
Lee KKim MKim HChwa HLee JShin I(2019)Fault-Resilient Real-Time Communication Using Software-Defined Networking2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2019.00025(204-215)Online publication date: Apr-2019
https://doi.org/10.1109/RTAS.2019.00025
Yan RGuo J(2019)Timing Modeling and Analysis for AUTOSAR Schedule Tables2019 IEEE 19th International Symposium on High Assurance Systems Engineering (HASE)10.1109/HASE.2019.00027(123-130)Online publication date: Jan-2019
https://doi.org/10.1109/HASE.2019.00027
Chwa HShin KLee J(2018)Closing the Gap Between Stability and Schedulability: A New Task Model for Cyber-Physical Systems2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2018.00040(327-337)Online publication date: Apr-2018
https://doi.org/10.1109/RTAS.2018.00040

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Scheduling and admission control

EDZL Scheduling Analysis

Early-release fair scheduling

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations