uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
On the problem of finding optimal harmonic periods
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
Max Planck Inst Software Syst MPI SWS, Kaiserslautern, Germany.
Lund Univ, Dept Automat Control, S-22100 Lund, Sweden.
Lund Univ, Dept Automat Control, S-22100 Lund, Sweden.
Show others and affiliations
2016 (English)In: Proc. 24th International Conference on Real-Time Networks and Systems, New York: ACM Press, 2016, 171-180 p.Conference paper (Refereed)
Abstract [en]

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 NP hard. This is shown by reducing the NP-complete 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.

Place, publisher, year, edition, pages
New York: ACM Press, 2016. 171-180 p.
National Category
Embedded Systems
URN: urn:nbn:se:uu:diva-305974DOI: 10.1145/2997465.2997490ISI: 000391255400017ISBN: 9781450347877 (print)OAI: oai:DiVA.org:uu-305974DiVA: diva2:1039464
RTNS 2016, October 19–21, Brest, France

Best Paper Award

Available from: 2016-10-19 Created: 2016-10-24 Last updated: 2017-02-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Mohaqeqi, Morteza
By organisation
Computer Systems
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 107 hits
ReferencesLink to record
Permanent link

Direct link