An approximation analysis of nonpreemptive EDF scheduling

Masaki Hanada*, Hidenori Nakazato

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Due to recent advances in multimedia technology, a real-time capability is needed to a certain extent even in information systems, in addition to control systems. In general, information systems are classified as soft real-time systems, which keep operating even if a deadline is missed. In soft real-time systems, it is more important to provide statistical guarantees (probabilistic analysis) than absolute guarantees (deadline guarantees). In current real-time systems, real-time scheduling such as EDF (Earliest Deadline First) is used to meet timing constraints. EDF scheduling simply assigns higher priorities in the order of earlier deadlines. It can be applied to aperiodic tasks without prior knowledge of their starting times. In this paper, it is assumed that each attribute of the task follows a probabilistic distribution. The system performance when a nonpreemptive EDF scheduling is applied is then mathematically analyzed.

Original languageEnglish
Pages (from-to)13-23
Number of pages11
JournalElectronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi)
Issue number2
Publication statusPublished - 2006 Feb 1


  • Aperiodic task
  • EDF scheduling
  • Non-preemptive
  • Soft real time

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'An approximation analysis of nonpreemptive EDF scheduling'. Together they form a unique fingerprint.

Cite this