Advanced

Optimal harmonic period assignment : complexity results and approximation algorithms

Mohaqeqi, Morteza; Nasri, Mitra; Xu, Yang LU ; Cervin, Anton LU and Årzén, Karl Erik LU (2018) In Real-Time Systems 54(4). p.830-860
Abstract

Harmonic periods have wide applicability in industrial real-time 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 real-time 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 NP-hard. This is shown by reducing the NP-complete 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 polynomial-time 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)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Hard real-time, Harmonic tasks, Period assignment, Real-time schedulability
in
Real-Time Systems
volume
54
issue
4
pages
830 - 860
publisher
Kluwer
external identifiers
  • scopus:85045043554
ISSN
0922-6443
DOI
10.1007/s11241-018-9304-0
language
English
LU publication?
yes
id
c7ed77c4-b33a-43e9-b820-8d47e860c4d9
date added to LUP
2018-04-17 15:05:00
date last changed
2019-01-14 17:16:18
@article{c7ed77c4-b33a-43e9-b820-8d47e860c4d9,
  abstract     = {<p>Harmonic periods have wide applicability in industrial real-time 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 NP-hard. This is shown by reducing the NP-complete 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 polynomial-time 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         = {0922-6443},
  keyword      = {Hard real-time,Harmonic tasks,Period assignment,Real-time schedulability},
  language     = {eng},
  month        = {04},
  number       = {4},
  pages        = {830--860},
  publisher    = {Kluwer},
  series       = {Real-Time Systems},
  title        = {Optimal harmonic period assignment : complexity results and approximation algorithms},
  url          = {http://dx.doi.org/10.1007/s11241-018-9304-0},
  volume       = {54},
  year         = {2018},
}