Packing sporadic real-time tasks on identical multiprocessor systems

Jian Jia Chen, Nikhil Bansal, Samarjit Chakraborty, Georg Von Der Brüggen

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

19 Downloads (Pure)

Abstract

In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling is widely used in real-time systems, i.e., the tasks are statically assigned onto processors while ensuring that all timing constraints are met. The decision version of the problem, which is to check whether the deadline constraints of tasks can be satisfied on a given number of identical processors, has been known NP-complete in the strong sense. Several studies on this problem are based on approximations involving resource augmentation, i.e., speeding up individual processors. This paper studies another type of resource augmentation by allocating additional processors, a topic that has not been explored until recently. We provide polynomial-time algorithms and analysis, in which the approximation factors are dependent upon the input instances. Specifically, the factors are related to the maximum ratio of the period to the relative deadline of a task in the given task set. We also show that these algorithms unfortunately cannot achieve a constant approximation factor for general cases. Furthermore, we prove that the problem does not admit any asymptotic polynomial-time approximation scheme (APTAS) unless P = NP when the task set has constrained deadlines, i.e., the relative deadline of a task is no more than the period of the task.

Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation, ISAAC 2018
EditorsWen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages14
ISBN (Electronic)978-3-95977-094-1
DOIs
Publication statusPublished - 1 Dec 2018
Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Hotel Royal Chiaohsi, Jiaoxi, Yilan, Taiwan
Duration: 16 Dec 201819 Dec 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume123

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
CountryTaiwan
CityJiaoxi, Yilan
Period16/12/1819/12/18

Keywords

  • Approximation factors
  • Multiprocessor partitioned scheduling

Fingerprint Dive into the research topics of 'Packing sporadic real-time tasks on identical multiprocessor systems'. Together they form a unique fingerprint.

Cite this