IEICE TRANSACTIONS on Fundamentals
Optimal Configuration for Multiversion Real-Time Systems Using Slack Based Schedulability
Summary :
In an embedded control system, control performances of each job depend on its latency and a control algorithm implemented in it. In order to adapt a job set to optimize control performances subject to schedulability, we design several types of control software for each job, which will be called versions, and select one version from them when the job is released. A real-time system where each job has several versions is called a multiversion real-time system. A benefit and a CPU utilization of a job depend on the versions. So, it is an important problem to select a version of each job so as to maximize the total benefit of the system subject to a schedulability condition. Such a problem will be called an optimal configuration problem. In this paper, we assume that each version is specified by the relative deadline, the execution time, and the benefit. We show that the optimal configuration problem is transformed to a maximum path length problem. We propose an optimal algorithm based on the forward dynamic programming. Moreover, we propose sub-optimal algorithms to reduce computation times. The efficiencies of the proposed algorithms are illustrated by simulations.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.12 pp.2709-2716
- Publication Date
- 2010/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E93.A.2709
- Type of Manuscript
- Special Section PAPER (Special Section on Theory of Concurrent Systems and its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Sayuri TERADA, Toshimitsu USHIO, "Optimal Configuration for Multiversion Real-Time Systems Using Slack Based Schedulability" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 12, pp. 2709-2716, December 2010, doi: 10.1587/transfun.E93.A.2709.
Abstract: In an embedded control system, control performances of each job depend on its latency and a control algorithm implemented in it. In order to adapt a job set to optimize control performances subject to schedulability, we design several types of control software for each job, which will be called versions, and select one version from them when the job is released. A real-time system where each job has several versions is called a multiversion real-time system. A benefit and a CPU utilization of a job depend on the versions. So, it is an important problem to select a version of each job so as to maximize the total benefit of the system subject to a schedulability condition. Such a problem will be called an optimal configuration problem. In this paper, we assume that each version is specified by the relative deadline, the execution time, and the benefit. We show that the optimal configuration problem is transformed to a maximum path length problem. We propose an optimal algorithm based on the forward dynamic programming. Moreover, we propose sub-optimal algorithms to reduce computation times. The efficiencies of the proposed algorithms are illustrated by simulations.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.2709/_p
Copy
@ARTICLE{e93-a_12_2709,
author={Sayuri TERADA, Toshimitsu USHIO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Optimal Configuration for Multiversion Real-Time Systems Using Slack Based Schedulability},
year={2010},
volume={E93-A},
number={12},
pages={2709-2716},
abstract={In an embedded control system, control performances of each job depend on its latency and a control algorithm implemented in it. In order to adapt a job set to optimize control performances subject to schedulability, we design several types of control software for each job, which will be called versions, and select one version from them when the job is released. A real-time system where each job has several versions is called a multiversion real-time system. A benefit and a CPU utilization of a job depend on the versions. So, it is an important problem to select a version of each job so as to maximize the total benefit of the system subject to a schedulability condition. Such a problem will be called an optimal configuration problem. In this paper, we assume that each version is specified by the relative deadline, the execution time, and the benefit. We show that the optimal configuration problem is transformed to a maximum path length problem. We propose an optimal algorithm based on the forward dynamic programming. Moreover, we propose sub-optimal algorithms to reduce computation times. The efficiencies of the proposed algorithms are illustrated by simulations.},
keywords={},
doi={10.1587/transfun.E93.A.2709},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - Optimal Configuration for Multiversion Real-Time Systems Using Slack Based Schedulability
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2709
EP - 2716
AU - Sayuri TERADA
AU - Toshimitsu USHIO
PY - 2010
DO - 10.1587/transfun.E93.A.2709
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2010
AB - In an embedded control system, control performances of each job depend on its latency and a control algorithm implemented in it. In order to adapt a job set to optimize control performances subject to schedulability, we design several types of control software for each job, which will be called versions, and select one version from them when the job is released. A real-time system where each job has several versions is called a multiversion real-time system. A benefit and a CPU utilization of a job depend on the versions. So, it is an important problem to select a version of each job so as to maximize the total benefit of the system subject to a schedulability condition. Such a problem will be called an optimal configuration problem. In this paper, we assume that each version is specified by the relative deadline, the execution time, and the benefit. We show that the optimal configuration problem is transformed to a maximum path length problem. We propose an optimal algorithm based on the forward dynamic programming. Moreover, we propose sub-optimal algorithms to reduce computation times. The efficiencies of the proposed algorithms are illustrated by simulations.
ER -
English
