More Web Proxy on the site http://driver.im/

research-article

Optimal Priority Assignment to Control Tasks

Authors:

Giulio M. Mancuso,

Gabriele PannocchiaAuthors Info & Claims

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

Article No.: 161, Pages 1 - 17

https://doi.org/10.1145/2660496

Published: 06 October 2014 Publication History

Abstract

In embedded real-time systems, task priorities are often assigned to meet deadlines. However, in control tasks, a late completion of a task has no catastrophic consequence; rather, it has a quantifiable impact in the control performance achieved by the task.

In this article, we address the problem of determining the optimal assignment of priorities and periods of sampled-data control tasks that run over a shared computation unit. We show that the minimization of the overall cost can be performed efficiently using a branch and bound algorithm that can be further speeded up by allowing for a small degree of suboptimality. Detailed numerical simulations are presented to show the advantages of various branching alternatives, the overall algorithm effectiveness, and its scalability with the number of tasks.

References

[1]

Eitan Altman and Adam Shwartz. 1989. Optimal priority assignment: A time sharing approach. IEEE Trans. Autom. Control 34, 10, 1098--1102.

[2]

Amir Aminifar, Enrico Bini, Petru Eles, and Zebo Peng. 2014. Bandwidth-efficient controller — Server co-design with stability guarantees. In Proceedings of the Design, Automation and Test in Europe Conference (DATE'14).

Digital Library

[3]

Amir Aminifar, Soheil Samii, Petru Eles, Zebo Peng, and Anton Cervin. 2012. Designing high-quality embedded control systems with guaranteed stability. In Proceedings of the 33^rd IEEE Real-Time Systems Symposium (RTSS'12).

Digital Library

[4]

Karl-Johan Åström and Björn Wittenmark. 1997. Computer-Controlled Systems: Theory and Design 3^rd Ed. Prentice Hall.

[5]

Neil Audsley. 1991. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Tech. rep. YCS 164, Department of Computer Science, University of York.

[6]

Enrico Bini and Anton Cervin. 2008. Delay-aware period assignment in control systems. In Proceedings of the 29^th IEEE Real-Time Systems Symposium (RTSS'08). 291--300.

Digital Library

[7]

Enrico Bini, Thi Huyen Chau Nguyen, Pascal Richard, and Sanjoy K. Baruah. 2009. A response-time bound in fixed-priority scheduling with arbitrary deadlines. IEEE Trans. Comput. 58, 2, 279--286.

Digital Library

[8]

Renu Chipalkatti, James F. Kurose, and Don Towsley. 1989. Scheduling policies for real-time and non-real-time traffic in a statistical multiplexer. In Proceedings of the 8^th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'89). 774--783.

[9]

Gene Franklin, Abbas Emami-Naeini, and J. Davis Powell. 1994. Feedback Control of Dynamic Systems 3^rd Ed. Addison-Wesley Longman.

Digital Library

[10]

Huijun Gao, Weichao Sun, and Peng Shi. 2010. Robust sampled-data control for vehicle active suspension systems. IEEE Trans. Control Syst. Technol. 18, 238--245.

[11]

Reiner Horst and Hoang Tuy. 1990. Global Optimization: Deterministic Approaches. Springer.

[12]

Mathai Joseph and Paritosh K. Pandya. 1986. Finding response times in a real-time system. Comput. J. 29, 5, 390--395.

[13]

Chung-Yao Kao and Anders Rantzer. 2007. Stability analysis of systems with uncertain time-varying delays. Automatica 43, 6, 959--970.

Digital Library

[14]

Ryou Kondo and Katsuhisa Furuta. 1985. Sampled-data optimal control of continuous systems for quadratic criterion function taking account of delayed control action. Int. J. Control 41, 1051--1060.

[15]

Huibert Kwakernaak and Raphael Sivan. 1972. Linear Optimal Control Systems. John Wiley and Sons.

Digital Library

[16]

Joseph Y.-T. Leung and Jennifer Whitehead. 1982. On the complexity of fixed-priority scheduling of periodic real-time tasks. Perform. Eval. 2, 4, 237--250.

[17]

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

Digital Library

[18]

Giulio M. Mancuso, Enrico Bini, and Gabriele Pannocchia. 2011. Optimal computational resource allocation for control task under fixed priority scheduling. In Proceedings of the 18^th IFAC World Congress. Vol. 18. 12599--12604.

[19]

Philippe Nain and Keith W. Ross. 1986. Optimal priority assignment with hard constraint. IEEE Trans. Autom. Control 31, 10, 883--888.

[20]

Johan Nilsson, Bo Bernhardsson, and Björn Wittenmark. 1998. Stochastic analysis and control of real-time systems with random time delays. Automatica 34, 1, 57--64.

Digital Library

[21]

R. Gary Parker and Ronald L. Rardin. 1988. Discrete Optimization. Academic Press.

Digital Library

[22]

Danbing Seto, John P. Lehoczky, Lui Sha, and Kang G. Shin. 1996. On task schedulability in real-time control systems. In Proceedings of the 17^th IEEE Real-Time Systems Symposium (RTSS'96). 13--21.

Digital Library

[23]

M. Shin and Myoungho Sunwoo. 2007. Optimal period and priority assignment for a networked control system scheduled by a fixed priority scheduling system. Int. J. Automot. Technol. 8, 1, 39--48.

[24]

Martin Stigge, Pontus Ekberg, Nan Guan, and Wang Yi. 2011. The digraph real-time task model. In Proceeding of the 17^th IEEE Real-Time and Embedded Technology and Applications Symposium. 71--80.

Digital Library

[25]

Spyros Tzafestas and Alekos Triantafyllakis. 1993. Deterministic scheduling in computing and manufacturing systems: A survey of models and algorithms. Math. Comput. Simul. 35, 5, 97--434.

Digital Library

[26]

Yifan Wu, Giorgio Buttazzo, Enrico Bini, and Anton Cervin. 2010. Parameter selection for real-time controllers in resource-constrained systems. IEEE Trans. Industr. Inf. 6, 4, 610--620.

[27]

Yang Xu, Karl-Erik Arzén, Enrico Bini, and Anton Cervin. 2014. Response time driven design of control systems. In Proceedings of the 19^th IFAC World Congress.

Cited By

Wang SWilliams RZeng H(2023)A General and Scalable Method for Optimizing Real-Time Systems with Continuous Variables2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00017(119-132)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00017
Zhao YZhou RZeng H(2022)Design optimization for real-time systems with sustainable schedulability analysisReal-Time Systems10.1007/s11241-022-09388-558:3(275-312)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11241-022-09388-5
Senapati DSarkar AKarfa C(2021)HMDS: A Makespan Minimizing DAG Scheduler for Heterogeneous Distributed SystemsACM Transactions on Embedded Computing Systems10.1145/347703720:5s(1-26)Online publication date: 17-Sep-2021
https://dl.acm.org/doi/10.1145/3477037
Show More Cited By

Index Terms

Optimal Priority Assignment to Control Tasks

Recommendations

A review of priority assignment in real-time systems

It is over 40 years since the first seminal work on priority assignment for real-time systems using fixed priority scheduling. Since then, huge progress has been made in the field of real-time scheduling with more complex models and schedulability ...
Optimal priority assignment for real-time systems: a coevolution-based approach
Abstract
In real-time systems, priorities assigned to real-time tasks determine the order of task executions, by relying on an underlying task scheduling policy. Assigning optimal priority values to tasks is critical to allow the tasks to complete their ...
Optimal priority assignment in the presence of blocking

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

Seventh Framework Programme
Linneaus Center LCCC
ELLIIT Excellence Center

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
221
Total Downloads

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

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang SWilliams RZeng H(2023)A General and Scalable Method for Optimizing Real-Time Systems with Continuous Variables2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00017(119-132)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00017
Zhao YZhou RZeng H(2022)Design optimization for real-time systems with sustainable schedulability analysisReal-Time Systems10.1007/s11241-022-09388-558:3(275-312)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11241-022-09388-5
Senapati DSarkar AKarfa C(2021)HMDS: A Makespan Minimizing DAG Scheduler for Heterogeneous Distributed SystemsACM Transactions on Embedded Computing Systems10.1145/347703720:5s(1-26)Online publication date: 17-Sep-2021
https://dl.acm.org/doi/10.1145/3477037
Zhao YZhou RZeng H(2020)An Optimization Framework for Real-Time Systems with Sustainable Schedulability Analysis2020 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS49844.2020.00038(333-344)Online publication date: Dec-2020
https://doi.org/10.1109/RTSS49844.2020.00038
Mahfouzi RAminifar ASamii SPayer MEles PPeng Z(2019)Butterfly Attack: Adversarial Manipulation of Temporal Properties of Cyber-Physical Systems2019 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS46320.2019.00019(93-106)Online publication date: Dec-2019
https://doi.org/10.1109/RTSS46320.2019.00019
Zhao YZeng H(2019)The concept of Maximal Unschedulable Deadline Assignment for optimization in fixed-priority scheduled real-time systemsReal-Time Systems10.1007/s11241-019-09332-055:3(667-707)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s11241-019-09332-0
Xu YCervin AArzen K(2018)Jitter-Robust LQG Control and Real-Time Scheduling Co-Design2018 Annual American Control Conference (ACC)10.23919/ACC.2018.8430953(3189-3196)Online publication date: Jun-2018
https://doi.org/10.23919/ACC.2018.8430953
Zhao YGala VZeng H(2018)A Unified Framework for Period and Priority Optimization in Distributed Hard Real-Time SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.285738037:11(2188-2199)Online publication date: Nov-2018
https://doi.org/10.1109/TCAD.2018.2857380
Roy DZhang LChang WMitter SChakraborty S(2018)Semantics-Preserving Cosynthesis of Cyber-Physical SystemsProceedings of the IEEE10.1109/JPROC.2017.2779456106:1(171-200)Online publication date: Jan-2018
https://doi.org/10.1109/JPROC.2017.2779456
Roy DBalszun MHeurung TChakraborty S(2018)Multi-Domain Coupling for Automated Synthesis of Distributed Cyber-Physical Systems2018 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2018.8351410(1-5)Online publication date: May-2018
https://doi.org/10.1109/ISCAS.2018.8351410
Show More Cited By

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.

Media

Figures

Other

Tables

View Issue’s Table of Contents