Global EDF-based scheduling with laxity-driven priority promotion

Shinpei Kato, Nobuyuki Yamasaki

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


This paper presents an algorithm, called Earliest Deadline Critical Laxity (EDCL), for scheduling sporadic task systems on multiprocessors. EDCL is a derivative of the Earliest Deadline Zero Laxity (EDZL) algorithm. Each job is assigned a priority based on the well-known Global Earliest Deadline First (G-EDF) algorithm, as long as its laxity - the amount of time from the earliest possible time of job completion to the deadline of job - is above a certain value. The priority is however promoted to the highest level once the laxity falls below this certain value in order to meet the deadline. Priority promotions are aligned with arrivals and completions of jobs under EDCL to avoid additional scheduler invocations, while EDZL can promote priorities arbitrarily. As compared with EDZL, EDCL reduces runtime overhead and implementation cost, but still strictly dominates G-EDF in schedulability. Schedulability tests for EDCL are derived through theoretical analysis, and sustainability properties are also considered. Our simulation results demonstrate that EDCL is competitive to EDZL in schedulability with a smaller number of scheduler invocations, and it also outperforms traditional EDF-based algorithms.

Original languageEnglish
Pages (from-to)498-517
Number of pages20
JournalJournal of Systems Architecture
Issue number5
Publication statusPublished - 2011 May 1


  • Earliest Deadline First
  • Multiprocessor scheduling
  • Real-time systems
  • Schedulability analysis
  • Sustainability analysis

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture


Dive into the research topics of 'Global EDF-based scheduling with laxity-driven priority promotion'. Together they form a unique fingerprint.

Cite this