Schedulability issues for EDZL scheduling on real-time multiprocessor systems

Yi Hsiung Chao, Shun-Shii Lin, Kwei Jay Lin

Research output: Contribution to journalArticle

17 Citations (Scopus)

Abstract

EDZL (Earliest Deadline first until Zero Laxity) is an efficient and practical scheduling algorithm on multiprocessor systems. It has a comparable number of context switch to EDF (Earliest Deadline First) and its schedulable utilization seems to be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3 m / 4 = 0.75 m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m (1 - 1 / e) ≈ 0.6321 m, where e ≈ 2.718 is the Euler's number.

Original languageEnglish
Pages (from-to)158-164
Number of pages7
JournalInformation Processing Letters
Volume107
Issue number5
DOIs
Publication statusPublished - 2008 Aug 16

    Fingerprint

Keywords

  • EDF
  • EDZL
  • LLF
  • Real-time scheduling
  • Schedulability analysis
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this