research-article

Utility-Based Resource Overbooking for Cyber-Physical Systems

Authors:

Dionisio De Niz,

Ragunathan (Raj) RajkumarAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 13, Issue 5s

Article No.: 162, Pages 1 - 25

https://doi.org/10.1145/2660497

Published: 06 October 2014 Publication History

Abstract

Traditional hard real-time scheduling algorithms require the use of the worst-case execution times to guarantee that deadlines will be met. Unfortunately, many algorithms with parameters derived from sensing the physical world suffer large variations in execution time, leading to pessimistic overall utilization, such as visual recognition tasks. In this article, we present ZS-QRAM, a scheduling approach that enables the use of flexible execution times and application-derived utility to tasks in order to maximize total system utility. In particular, we provide a detailed description of the algorithm, the formal proofs for its temporal protection, and a detailed, evaluation. Our evaluation uses the Utility Degradation Resilience (UDR) showing that ZS-QRAM is able to obtain 4× as much UDR as ZSRM, a previous overbooking approach, and almost 2× as much UDR as Rate-Monotonic with Period Transformation (RM/TP). We then evaluate a Linux kernel module implementation of our scheduler on an Unmanned Air Vehicle (UAV) platform. We show that, by using our approach, we are able to keep the tasks that render the most utility by degrading lower-utility ones even in the presence of highly dynamic execution times.

References

[1]

S. Baruah, H. Li, and L. Stougie. 2010. Towards the design of certifiable mixed-criticality systems. In Proceedings of the IEEE Real-Time Technology and Applications Symposium (RTAS'10). 13--22.

Digital Library

[2]

S. Baruah and S. Vestal. 2008. Schedulability analysis of sporadic tasks with multiple criticality specifications. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS'08). 147--155.

Digital Library

[3]

G. Buttazzo, G. Lipari, and L. Abeni. 1998. Elastic task model for adaptive rate control. In Proceedings of the IEEE 19^th Real-Time Systems Symposium (RTSS'98). 286.

Digital Library

[4]

G. Buttazzo, M. Spuri, and F. Sensini. 1995. Value vs deadline scheduling in overload conditions. In Proceedings of the 16^th IEEE Real-Time Systems Symposium (RTSS'95). 90.

Digital Library

[5]

S. Cho, S.-K. Lee, A. Han, and K.-J. Lin. 2002. Efficient real-time scheduling algorithms for multiprocessor systems. IEICE Trans. Comm. E85-B, 2859--2867.

[6]

M. Cirinei and T. Baker. 2007. EDZL scheduling analysis. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS'08). 9--18.

Digital Library

[7]

D. De Niz, K. Lakshmanan, and R. Rajkumar. 2009. On the scheduling of mixed-criticality real-time task sets. In Proceedings of the 30^th IEEE Real-Time Systems Symposium (RTSS'09). 291--300.

Digital Library

[8]

D. De Niz, L. Wrage, N. Storer, A. Rowe, and R. Rajkumar. 2012. On resource overbooking in an unmanned aerial vehicle. In Proceedings of the 3^rd IEEE/ACM International Conference on Cyber-Physical Systems (ICCPS'12). 97--106.

Digital Library

[9]

DRONE-RK. 2013. Drone-rk. http://www.drone-rk.org/.

[10]

H.-M. Huan, C. Gill, and C. Lu. 2012. Implementation and evaluation of mixed-criticality scheduling approaches for periodic tasks. In Proceedings of the IEEE Real-Time Technology and Applications Symposium (RTAS'12). 22--32.

Digital Library

[11]

M. Joseph and P. Padya. 1986. Finding response times in a real-time system. The Comput. J. 29, 5, 390--395.

[12]

S. Kato, R. Rajkumar, and Y. Ishikawa. 2009. A loadable real-time scheduler suite for multicore platforms. http://ertl.jp/~shinpei/papers/techrep09.pdf.

[13]

K. Lakshmanan, D. De Niz, R. Rajkumar, and G. Moreno. 2010. Resource allocation in distributed mixed-criticality cyber-physical systems. In Proceedings of the 30^th IEEE International Conference on Distributed Computing Systems (ICDCS'10). 169--178.

Digital Library

[14]

C. L. Liu and J. W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1, 46--61.

Digital Library

[15]

P. Mejia-Alvarez, R. Melhem, and D. Mosse. 2000. An incremental approach to scheduling during overloads in real-time systems. In Proceedings of the 21^st IEEE Real-Time Systems Symposium (RTSS'00). 283--293.

Digital Library

[16]

S. Oikawa and R. Rajkumar. 1999. Portable rk: A portable resource kernel for guaranteed and enforced timing behavior. In Proceedings of the 5^th IEEE Real-Time Technology and Applications Symposium (RTAS'99). 111.

Digital Library

[17]

Parrot. 2011. Parrot ar drone. http://ardrone.parrot.com/.

[18]

R. Rajkumar, C. Lee, J. Lehoczky, and D. Siewiorek. 1997. A resource allocation model for qos management. In Proceedings of the 18^th IEEE Real-Time Systems Symposium (RTSS'97). 298.

Digital Library

[19]

C.-S. Shih, P. Ganti, and L. Sha. 2004. Schedulability and fairness for computation tasks in surveillance radar systems. In Proceedings of the 10^th IEEE Real-Time Technology and Applications Symposium (RTAS'04).

[20]

S. Vestal. 2007. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the 28^th IEEE International Real-Time Systems Symposium (RTSS'07). 239--243.

Digital Library

[21]

ZS-QRAM. 2013. ZS-QRAM documentation. http://andrew.cmu.edu/dionisio/projects.html.

Cited By

Hu BChen GHuang K(2018)Semi-Slack Scheduling Arbitrary Activation Patterns in Mixed-Criticality SystemsIEEE Access10.1109/ACCESS.2018.28797176(68507-68524)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2879717
Wang NWu J(2018)Rethink data dissemination in opportunistic mobile networks with mutually exclusive requirementJournal of Parallel and Distributed Computing10.1016/j.jpdc.2018.03.012119(50-63)Online publication date: Sep-2018
https://doi.org/10.1016/j.jpdc.2018.03.012
Guan FPeng LPerneel LFayyad-Kazan HTimmerman M(2017)A Design That Incorporates Adaptive Reservation into Mixed-Criticality SystemsScientific Programming10.1155/2017/34036852017(4)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1155/2017/3403685
Show More Cited By

Recommendations

Adaptive data-aware utility-based scheduling in resource-constrained systems

This paper addresses the problem of the dynamic scheduling of data-intensive multiprocessor jobs. Each job requires some number of CPUs and some amount of data that needs to be downloaded into a local storage. The completion of each job brings some ...
A Utility Accrual Scheduling Algorithm for Real-Time Activities with Mutual Exclusion Resource Constraints

This paper presents a uni-processor real-time scheduling algorithm called the Generic Utility Scheduling algorithm (which we will refer to simply as GUS). GUS solves a previously open real-time scheduling problem—scheduling application activities that ...
Optimizing Expected Time Utility in Cyber-Physical Systems Schedulers
RTSS '10: Proceedings of the 2010 31st IEEE Real-Time Systems Symposium

Classical scheduling abstractions such as deadlines and priorities do not readily capture the complex timing semantics found in many real-time cyber-physical systems. Time utility functions provide a necessarily richer description of timing semantics, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 13, Issue 5s

Special Issue on Risk and Trust in Embedded Critical Systems, Special Issue on Real-Time, Embedded and Cyber-Physical Systems, Special Issue on Virtual Prototyping of Parallel and Embedded Systems (ViPES)

November 2014

501 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2660459

Editor:
Sandeep K. Shukla
Virginia Tech, USA

Issue’s Table of Contents

Copyright © 2014 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 06 October 2014

Accepted: 01 May 2014

Received: 01 September 2013

Published in TECS Volume 13, Issue 5s

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Carnegie Mellon University
Department of Defense under contract no. FA8721-05-C-0003 with Carnegie Mellon University for the operation of the Software Engineering Institute

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
256
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hu BChen GHuang K(2018)Semi-Slack Scheduling Arbitrary Activation Patterns in Mixed-Criticality SystemsIEEE Access10.1109/ACCESS.2018.28797176(68507-68524)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2879717
Wang NWu J(2018)Rethink data dissemination in opportunistic mobile networks with mutually exclusive requirementJournal of Parallel and Distributed Computing10.1016/j.jpdc.2018.03.012119(50-63)Online publication date: Sep-2018
https://doi.org/10.1016/j.jpdc.2018.03.012
Guan FPeng LPerneel LFayyad-Kazan HTimmerman M(2017)A Design That Incorporates Adaptive Reservation into Mixed-Criticality SystemsScientific Programming10.1155/2017/34036852017(4)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1155/2017/3403685
Vanga MBastoni ATheiling HBrandenburg BBini EPagetti C(2017)Supporting low-latency, low-criticality tasks in a certified mixed-criticality OSProceedings of the 25th International Conference on Real-Time Networks and Systems10.1145/3139258.3139274(227-236)Online publication date: 4-Oct-2017
https://dl.acm.org/doi/10.1145/3139258.3139274
Lu Y(2017)Cyber Physical System (CPS)-Based Industry 4.0: A SurveyJournal of Industrial Integration and Management10.1142/S242486221750014202:03(1750014)Online publication date: Sep-2017
https://doi.org/10.1142/S2424862217500142
Wang NWu J(2016)Mutually Exclusive Data Dissemination in the Mobile Publish/Subscribe System2016 IEEE 13th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)10.1109/MASS.2016.020(75-83)Online publication date: Oct-2016
https://doi.org/10.1109/MASS.2016.020
Ruchkin IRao ADe Niz DChaki SGarlan DRay IThomas RCardenas A(2015)Eliminating Inter-Domain Vulnerabilities in Cyber-Physical SystemsProceedings of the First ACM Workshop on Cyber-Physical Systems-Security and/or PrivaCy10.1145/2808705.2808714(11-22)Online publication date: 16-Oct-2015
https://dl.acm.org/doi/10.1145/2808705.2808714

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents