TY - JOUR
T1 - The Deferrable Server Algorithm for Enhanced Aperiodic Responsiveness in Hard Real-Time Environments
AU - Strosnider, Jay K.
AU - Lehoczky, John P.
AU - Sha, Lui
N1 - Funding Information:
Manuscript received July 19, 1989; revised May 7, 1990, October 12. 1991, March 1, 1992. This work was supported in part from a grant lrom the Office of Naval Research and in part from a grant from Naval Ocean Systems Center. J. K. Strosnider is with the Department of Electrical and Computer Engineering, Camegie Mellon University, Pittsburgh, PA 152 I3 USA; E-mail: [email protected]. J. P. Lehoczky is with the Department of Statistics, Camegie Mellon University, Pittsburgh, PA 15213 USA. L. Sha is with the Software Engineering Institute and School of Computer Science, Camegie Mellon University, Pittsburgh, PA 15213 USA. IEEE Log Number 94071 13.
PY - 1995/1
Y1 - 1995/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0029230309&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0029230309&partnerID=8YFLogxK
U2 - 10.1109/12.368008
DO - 10.1109/12.368008
M3 - Article
AN - SCOPUS:0029230309
SN - 0018-9340
VL - 44
SP - 73
EP - 91
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
IS - 1
ER -