R-EDF: A reservation-based EDF scheduling algorithm for multiple multimedia task classes

Wanghong Yuan, Klara Nahrstedt, Kihun Kim

Research output: Contribution to journalArticlepeer-review


Multimedia applications became an integral part of the ubiquitous computing environment in general-purpose systems. However, current general-purpose operating systems cannot effectively support their soft real-time requirements. This paper presents a reservation-based preemptive earliest deadline first (R-EDF) algorithm to provide a predictable scheduling framework in an open shared environment. The major contributions of R-EDF are: (1) it delivers timing guarantees to four soft real-time task classes such as period class with constant and various processing time, aperiodic class and event-based class; (2) it provides starvation protection for best-effort tasks; (3) it provides overrun protection and handling so that an overrun task will not cause other tasks to miss deadlines and will finish its work within an acceptable and predictable time bound; and (4) it allows optimistic reservation and incurs low overhead cost for reservation and admission control. Our experimental results show the low overhead and correctness of R-EDF even when there is resource contention.

Original languageEnglish (US)
Pages (from-to)149-154
Number of pages6
JournalReal-Time Technology and Applications - Proceedings
StatePublished - Jan 1 2001

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Software

Fingerprint Dive into the research topics of 'R-EDF: A reservation-based EDF scheduling algorithm for multiple multimedia task classes'. Together they form a unique fingerprint.

Cite this