Stability of Online Resource Managers for Distributed Systems under Execution Time Variations
Article No.: 21, Pages 1 - 29
Abstract
Today's embedded systems are exposed to variations in resource usage due to complex software applications, hardware platforms, and impact of the runtime environments. When these variations are large and efficiency is required, on-line resource managers may be deployed on the system to help it control its resource usage. An often neglected problem is whether these resource managers are stable, meaning that the resource usage is controlled under all possible scenarios. In distributed systems, this problem is particularly hard because applications distributed over many resources generate complex dependencies between their resources. In this article, we develop a mathematical model of the system, and derive conditions that, if satisfied, guarantee stability.
References
[1]
T. F. Abdelzaher, J. A. Stankovic, C. Lu, R. Zhang, and Y. Lu. 2003. Feedback performance control in software services—using a control-theoretic approach to achieve quality of service guarantees. IEEE Control Systems Magazine 23, 74--90.
[2]
K. J. Åström and B. Wittenmark. 1997. Computer-Controlled Systems. Prentice Hall.
[3]
S. K. Baruah, L. E. Rosier, and R. R. Howell. 1990. Algorithms and complexity concerning the preemptive scheduling of periodic real-time tasks on one processor. Journal of Real-Time Systems 2, 4, 301--324.
[4]
M. Bramson. Stability of Queueing Networks. Springer.
[5]
G. C. Buttazzo, G. Lipari, and L. Albeni. Elastic task model for adaptive rate control. In Proceedings of the IEEE Real-Time Systems Symposium. 286.
[6]
G. C. Buttazzo and L. Albeni. 2002. Adaptive workload management through elastic scheduling. Journal of Real-Time Systems 23, 7--24.
[7]
G. C. Buttazzo, M. Velasco, P. Marti, and G. Fohler. 2004. Managing quality-of-control performance under overload conditions. In Proceedings of the Euromicro Conference on Real-Time Systems. 53--60.
[8]
A. Cervin, J. Eker, B. Bernhardsson, and K. E. Årzén. 2002. Feedback-feedforward scheduling of control tasks. Journal of Real-Time Systems 23, 25--53.
[9]
A. Cervin and J. Eker. 2003. The control server: A computational model for real-time control tasks. In Proceedings of the 15th Euromicro Conference on Real-Time Systems.
[10]
T. Cucinotta and L. Palopoli. 2010a. QoS control for pipelines of tasks using multiple resources. IEEE Transactions on Computers 59, 416--430.
[11]
T. Cucinotta, L. Palopoli, L. Abeni, D. Faggioli, and G. Lipari. 2010b. On the integration of application level and resource level QoS control for real-time applications. IEEE Transactions Industrial Informatics (TII) 6, 4, 479--491.
[12]
Z. P. Jiang, and Y. Wang. 2001. Input-to-state stability for discrete-time nonlinear systems. Automatica 37, 6, 857--869.
[13]
E. Kreyszing. 1989. Introduction to Functional Analysis with Applications. John Wiley & Sons.
[14]
P. R. Kumar, S. Meyn. 1995. Stability of queueing networks and scheduling policies. IEEE Transactions on Automatic Control 40, 2, 251--260.
[15]
C. Lee, J. Lehoczky, R. Rajkumar, and D. Siewiorek. 1998. On quality of service optimization with discrete QoS options. In Proceedings of the Real-Time Technology and Applications Symposium. 276.
[16]
J. P. Lehoczky, L. Sha, and Y. Ding. 1989. The rate-monotonic scheduling algorithm: Exact characterization and average case behavior. In Proceedings of the 10th IEEE Real-Time Systems Symposium. 166--172.
[17]
X. Liu, X. Zhu, P. Padala, Z. Wang, and S. Singhal. 2007. Optimal multivariate control for differentiated services on a shared hosting platform. In Proceedings of the Conference on Decision and Control. 3792--3799.
[18]
C. Lu, J. A. Stankovic, S. H. Son, and G. Tao. 2002. Feedback control real-time scheduling: Framework, modeling, and algorithms. Journal of Real-Time Systems 23, 85--126.
[19]
C. Lu, X. Wang and X. Koutsoukos. 2005. Feedback utilization control in distributed real-time systems with end-to-end tasks. IEEE Transactions on Parallel and Distributed Systems 16, 550--561.
[20]
M. Marioni and G. C. Buttazzo. 2007. Elastic DVS management in processors with discrete voltage/frequency modes. IEEE Transactions on Industrial Informatics 3, 51--62.
[21]
L. Palopoli, T. Cucinotta, L. Marzario, and G. Lipari. 2009. AQuoSA—adaptive quality of service architecture. Journal of Software--Practice and Experience 39, 1--31.
[22]
S. Rafiliu, P. Eles, and Z. Peng. 2010. Low overhead dynamic qos optimization under variable execution times. In Proceedings of 16th IEEE Embedded and Real-Time computing Systems and Applications (RTCSA). 293--303.
[23]
S. Rafiliu, P. Eles, and Z. Peng. 2013. Stability of adaptive feedback-based resource managers for systems with execution time variations. Journal of Real-Time Systems 49, 367--400.
[24]
E. D. Sontag. 2001. The ISS philosophy as a unifying framework for stability-like behavior. Lecture Notes in Control and Information Sciences 256, 443--467.
[25]
J. Yao, X. Liu, M. Yuan, and Z. Gu. 2008. Online adaptive utilization control for real-time embedded multiprocessor systems. In Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis. 85--90.
[26]
K. Zhou, J. C. Doyle, and K. Glover. 1996. Robust and Optimal Control. Prentice Hall, 40.
Index Terms
- Stability of Online Resource Managers for Distributed Systems under Execution Time Variations
Recommendations
Stability of adaptive feedback-based resource managers for systems with execution time variations
Today's embedded systems are exposed to variations in load demand due to complex software applications, dynamic hardware platforms, and the impact of the run-time environment. When these variations are large, and efficiency is required, adaptive on-line ...
Improved Stability Criteria for Linear Neutral Time-Delay Systems
This paper is concerned with the problem of stability analysis of linear neutral time delay systems. First, a new simple Lyapunov-Krasovskii functional is constructed based on delay partitioning approach, then, a novel improved delay-dependent stability ...
Asymptotic Stability Criterion for the Networked Control Systems Based on Time-Delay System
UIC-ATC '10: Proceedings of the 2010 Symposia and Workshops on Ubiquitous, Autonomic and Trusted ComputingIn This paper, the networked control systems (NCSs) is modeled as a time-delay system. In terms of the given model. Two new asymptotic stability criterions for the linear time-invariant networked control systems are derived from the inequality of matrix ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2015
472 pages
Copyright © 2015 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 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
Journal Family
Publication History
Published: 09 March 2015
Accepted: 01 May 2014
Revised: 01 January 2014
Received: 01 July 2013
Published in TECS Volume 14, Issue 2
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- Swedish Foundation for Strategic Research under the Software Intensive program
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 179Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)1
Reflects downloads up to 30 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in