Beyond Implicit-Deadline Optimality: A Multiprocessor Scheduling Framework for Constrained-Deadline Tasks

Hyeongboo Baek, Hoon Sung Chwa, Jinkyu Lee

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

3 Scopus citations


In the real-time systems community, many studies have addressed how to efficiently utilize a multiprocessor platform so as to accommodate as many periodic/sporadic real-time tasks as possible without violating any timing constraints. The scheduling theory has sufficiently matured for a set of implicit-deadline tasks (the relative deadline equal to the period), yielding a class of optimal scheduling algorithms. However, the same does not hold for a set of constrained-deadline tasks (the relative deadline no larger than the period) in that those task sets have been fully covered by neither existing implicit-deadline optimal scheduling algorithms nor heuristic scheduling algorithms., In this paper, we propose a scheduling framework that not only takes advantage of both existing implicit-deadline optimal and heuristic algorithms, but also surpasses both in finding schedulable constrained-deadline task sets. The proposed framework logically divides a given task set into the higher- and lower-priority classes and schedules the classes using an implicit-deadline optimal algorithm and a heuristic algorithm, respectively. Then, while the proposed framework guarantees schedulability of tasks in the higher-priority class by the target implicit-deadline optimal algorithm, we need to address the following technical issues for enabling tasks in the lower-priority class to efficiently reclaim remaining processor capacity while guaranteeing their schedulability: (i) division of a given task set into the two classes, (ii) selection/development of scheduling algorithms for the two classes, and (iii) development of a schedulability test for the framework with given (i) and (ii). We present a general case showing how to address (i)-(iii), and then a specific case addressing how to further improve schedulability by utilizing characteristics of the specific case. Our simulation results demonstrate that the proposed framework outperforms all existing scheduling algorithms in covering schedulable task sets; in particular, if we focus on task sets with the system density larger than the number of processors, the framework finds up to 446.3% additional schedulable task sets, compared to task sets covered by at least one of existing scheduling algorithms.

Original languageEnglish
Title of host publicationProceedings - 2017 IEEE Real-Time Systems Symposium, RTSS 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages12
ISBN (Electronic)9781538614143
StatePublished - 2 Jul 2017
Event38th IEEE Real-Time Systems Symposium, RTSS 2017 - Paris, France
Duration: 5 Oct 20178 Oct 2017

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Conference38th IEEE Real-Time Systems Symposium, RTSS 2017


  • constrained-deadline
  • existing-implicit-deadline-optimal-scheduling-algorithm
  • real-time-system
  • schedulability-analysis


Dive into the research topics of 'Beyond Implicit-Deadline Optimality: A Multiprocessor Scheduling Framework for Constrained-Deadline Tasks'. Together they form a unique fingerprint.

Cite this