The Deferrable Server Algorithm for Enhanced Aperiodic Responsiveness in Hard Real-Time Environments

Jay K. Strosnider, John P. Lehoczky, Lui Sha

Research output: Contribution to journalArticlepeer-review

Abstract

Most existing scheduling algorithms for hard realtime systems apply either to periodic tasks or aperiodic tasks but not to both. In practice, real-time systems require an integrated, consistent approach to scheduling that is able to simultaneously meet the timing requirements of hard deadline periodic tasks, hard deadline aperiodic (alert-class) tasks, and soft deadline aperiodic tasks. This paper introduces the Deferrable Server (DS) algorithm which will be shown to provide improved aperiodic response time performance over traditional background and polling approaches. Taking advantage of the fact that, typically, there is no benefit in early completion of the periodic tasks, the Deferrable Server (DS) algorithm assigns higher priority to the aperiodic tasks up until the point where the periodic tasks would start to miss their deadlines. Guaranteed alert-class aperiodic service and greatly reduced response times for soft deadline aperiodic tasks are important features of the DS algorithm, and both are obtained with the hard deadlines of the periodic tasks still being guaranteed. The results of a simulation study performed to evaluate the response time performance of the new algorithm against traditional background and polling approaches are presented. In all cases, the response times of aperiodic tasks are significantly reduced (often by an order of magnitude) while still maintaining guaranteed periodic task deadlines.

Original languageEnglish (US)
Pages (from-to)73-91
Number of pages19
JournalIEEE Transactions on Computers
Volume44
Issue number1
DOIs
StatePublished - Jan 1995
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The Deferrable Server Algorithm for Enhanced Aperiodic Responsiveness in Hard Real-Time Environments'. Together they form a unique fingerprint.

Cite this