On the Problem of Finding Optimal Harmonic Periods
(2016) International Conference on RealTime Networks and Systems p.171180 Abstract
 Harmonic periods have wide applicability in industrial realtime systems. Rate monotonic (RM) is able to schedule task sets with harmonic periods up to 100% utilization. Also, if there is no release jitter and execution time variation, RM and EDF generate the same schedule for each instance of a task. This property decreases the jitters which happen during sampling and actuation of the tasks, and hence, it increases the quality of service in control systems. In this paper, we consider the problem of optimal period assignment where the periods are constrained to be harmonic. First, we assume that an interval is determined a priori for each task from which its period can be selected. The goal is to assign a (harmonic) period to each task... (More)
 Harmonic periods have wide applicability in industrial realtime systems. Rate monotonic (RM) is able to schedule task sets with harmonic periods up to 100% utilization. Also, if there is no release jitter and execution time variation, RM and EDF generate the same schedule for each instance of a task. This property decreases the jitters which happen during sampling and actuation of the tasks, and hence, it increases the quality of service in control systems. In this paper, we consider the problem of optimal period assignment where the periods are constrained to be harmonic. First, we assume that an interval is determined a priori for each task from which its period can be selected. The goal is to assign a (harmonic) period to each task such that the total system utilization is maximized while the task set remains feasible. We show that this problem is (at least) weakly NPhard. This is shown by reducing the NPcomplete number partitioning problem to the mentioned harmonic period assignment problem. Afterwards, we consider a variant of the problem in which the periods are not restricted to a special interval and the objective is to minimize the total weighted sum of the periods with the same feasibility constraint. We present two approximation algorithms for the second problem and show that the maximum error of these algorithms is bounded by a factor of 2. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/f46477542da949259fdb2ae90177f48a
 author
 Mohaqeqi, Morteza; Nasri, Mitra; Xu, Yang ^{LU} ; Cervin, Anton ^{LU} and Årzén, KarlErik ^{LU}
 organization
 publishing date
 20161020
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Proceedings of the 24rd International Conference on Real Time and Networks Systems
 pages
 10 pages
 publisher
 ACM
 conference name
 International Conference on RealTime Networks and Systems
 conference location
 Brest, France
 conference dates
 20161019  20161021
 external identifiers

 scopus:84997079603
 wos:000391255400017
 ISBN
 9781450347877
 DOI
 10.1145/2997465.2997490
 language
 English
 LU publication?
 yes
 id
 f46477542da949259fdb2ae90177f48a
 date added to LUP
 20161024 12:01:40
 date last changed
 20190319 03:13:19
@inproceedings{f46477542da949259fdb2ae90177f48a, abstract = {Harmonic periods have wide applicability in industrial realtime systems. Rate monotonic (RM) is able to schedule task sets with harmonic periods up to 100% utilization. Also, if there is no release jitter and execution time variation, RM and EDF generate the same schedule for each instance of a task. This property decreases the jitters which happen during sampling and actuation of the tasks, and hence, it increases the quality of service in control systems. In this paper, we consider the problem of optimal period assignment where the periods are constrained to be harmonic. First, we assume that an interval is determined a priori for each task from which its period can be selected. The goal is to assign a (harmonic) period to each task such that the total system utilization is maximized while the task set remains feasible. We show that this problem is (at least) weakly NPhard. This is shown by reducing the NPcomplete number partitioning problem to the mentioned harmonic period assignment problem. Afterwards, we consider a variant of the problem in which the periods are not restricted to a special interval and the objective is to minimize the total weighted sum of the periods with the same feasibility constraint. We present two approximation algorithms for the second problem and show that the maximum error of these algorithms is bounded by a factor of 2. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution.}, author = {Mohaqeqi, Morteza and Nasri, Mitra and Xu, Yang and Cervin, Anton and Årzén, KarlErik}, isbn = {9781450347877 }, language = {eng}, location = {Brest, France}, month = {10}, pages = {171180}, publisher = {ACM}, title = {On the Problem of Finding Optimal Harmonic Periods}, url = {http://dx.doi.org/10.1145/2997465.2997490}, year = {2016}, }