Optimal harmonic period assignment : complexity results and approximation algorithms
(2018) In RealTime Systems 54(4). p.830860 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. As a result, all instances of a task are interfered by the same amount of workload. This property decreases the jitters that 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 and the task set is required to be feasible. We study two variants of this problem.... (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. As a result, all instances of a task are interfered by the same amount of workload. This property decreases the jitters that 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 and the task set is required to be feasible. We study two variants of this problem. In the first one, the objective is to maximize the system utilization, while in the second one, the goal is to minimize the total weighted sum of the periods. First, we assume that an interval is determined a priori for each task from which its period can be selected. We show that both variants of the problem are (at least) weakly NPhard. This is shown by reducing the NPcomplete number partitioning problem to the mentioned harmonic period assignment problems. Afterwards, we consider a variant of the second problem in which the periods are not restricted to a special interval. We present two approximation algorithms with polynomialtime complexity for this problem and show that the maximum relative error of these algorithms is bounded by a factor of 1.125. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution.
(Less)
 author
 Mohaqeqi, Morteza; Nasri, Mitra; Xu, Yang ^{LU} ; Cervin, Anton ^{LU} and Årzén, Karl Erik ^{LU}
 organization
 publishing date
 20180406
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Hard realtime, Harmonic tasks, Period assignment, Realtime schedulability
 in
 RealTime Systems
 volume
 54
 issue
 4
 pages
 830  860
 publisher
 Kluwer
 external identifiers

 scopus:85045043554
 ISSN
 09226443
 DOI
 10.1007/s1124101893040
 language
 English
 LU publication?
 yes
 id
 c7ed77c4b33a43e9b8208d47e860c4d9
 date added to LUP
 20180417 15:05:00
 date last changed
 20190114 17:16:18
@article{c7ed77c4b33a43e9b8208d47e860c4d9, abstract = {<p>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. As a result, all instances of a task are interfered by the same amount of workload. This property decreases the jitters that 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 and the task set is required to be feasible. We study two variants of this problem. In the first one, the objective is to maximize the system utilization, while in the second one, the goal is to minimize the total weighted sum of the periods. First, we assume that an interval is determined a priori for each task from which its period can be selected. We show that both variants of the problem are (at least) weakly NPhard. This is shown by reducing the NPcomplete number partitioning problem to the mentioned harmonic period assignment problems. Afterwards, we consider a variant of the second problem in which the periods are not restricted to a special interval. We present two approximation algorithms with polynomialtime complexity for this problem and show that the maximum relative error of these algorithms is bounded by a factor of 1.125. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution.</p>}, author = {Mohaqeqi, Morteza and Nasri, Mitra and Xu, Yang and Cervin, Anton and Årzén, Karl Erik}, issn = {09226443}, keyword = {Hard realtime,Harmonic tasks,Period assignment,Realtime schedulability}, language = {eng}, month = {04}, number = {4}, pages = {830860}, publisher = {Kluwer}, series = {RealTime Systems}, title = {Optimal harmonic period assignment : complexity results and approximation algorithms}, url = {http://dx.doi.org/10.1007/s1124101893040}, volume = {54}, year = {2018}, }