On the Problem of Finding Optimal Harmonic Periods

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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. 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.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • Max Planck Institute for Software Systems
  • Uppsala universitet
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Reglerteknik
Originalspråkengelska
Titel på värdpublikationProceedings of the 24rd International Conference on Real Time and Networks Systems
FörlagAssociation for Computing Machinery (ACM)
Sidor171-180
Antal sidor10
ISBN (elektroniskt)978-1-4503-4787-7
StatusPublished - 2016 okt 20
PublikationskategoriForskning
Peer review utfördJa
EvenemangInternational Conference on Real-Time Networks and Systems - Brest, Frankrike
Varaktighet: 2016 okt 192016 okt 21
Konferensnummer: 24
http://rtns16.univ-brest.fr

Konferens

KonferensInternational Conference on Real-Time Networks and Systems
Förkortad titelRTNS
LandFrankrike
OrtBrest
Period2016/10/192016/10/21
Internetadress

Related projects

Anton Cervin, Yang Xu & Karl-Erik Årzén

2010/01/012017/12/31

Projekt: Forskning

Anton Cervin, Karl-Erik Årzén, Martina Maggio, Nils Vreman, Yang Xu, Enrico Bini, Gautham Nayak Seetanadi, Marcus Thelander Andrén, Paolo Pazzaglia, Zebo Peng, Petru Eles, Rouhollah Mahfouzi, Soheil Samii & Amir Aminifar

2010/01/01 → …

Projekt: Forskning

Visa alla (2)

Anton Cervin (Mottagare), Yang Xu (Mottagare), Karl-Erik Årzén (Mottagare), Morteza Mohaqeqi (Mottagare) & Mitra Nasri (Mottagare), 2016 okt 20

Priser och utmärkelser: Priser pch utmärkelserPris (inklusive medaljer och utmärkelser)

Visa alla (1)