On the problem of finding optimal harmonic periods

Morteza Mohaqeqi, Mitra Nasri, Yang Xu, Anton Cervin, Karl Erik Årzén

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

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

Original languageEnglish
Title of host publicationProceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS 2016
PublisherAssociation for Computing Machinery, Inc
Pages171-180
Number of pages10
ISBN (Electronic)978-1-4503-4787-7
DOIs
Publication statusPublished - Oct 2016
Externally publishedYes
Event24th International Conference on Real-Time Networks and Systems, RTNS 2016 - Brest, France
Duration: 19 Oct 201621 Oct 2016
Conference number: 24

Conference

Conference24th International Conference on Real-Time Networks and Systems, RTNS 2016
Abbreviated titleRTNS 2016
Country/TerritoryFrance
CityBrest
Period19/10/1621/10/16

Fingerprint

Dive into the research topics of 'On the problem of finding optimal harmonic periods'. Together they form a unique fingerprint.
  • Best Paper Award - RTNS 2016

    Nasri, M. (Recipient), 2016

    Prize: OtherCareer, activity or publication related prizes (lifetime, best paper, poster etc.)Scientific

Cite this