DESH : Overhead reduction algorithms for deferrable scheduling

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

12 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1-25
Journal / PublicationReal-Time Systems
Volume44
Issue number1-3
Publication statusPublished - Mar 2010

Abstract

Although the deferrable scheduling algorithm for fixed priority transactions (DS-FP) has been shown to be a very effective approach for minimizing real-time update transaction workload, it suffers from its on-line scheduling overhead. In this work, we propose two extensions of DS-FP to minimize the on-line scheduling overhead. The proposed algorithms produce a hyperperiod from DS-FP so that the schedule generated by repeating the hyperperiod infinitely satisfies the temporal validity constraint of the real-time data. The first algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Construction (DESH-SC), searches the DS-FP schedule for a hyperperiod. The second algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Adjustment (DESH-SA), adjusts the DS-FP schedule in an interval to form a hyperperiod. Our experimental results demonstrate that while both DESH-SC and DESH-SA can reduce the scheduling overhead of DS-FP, DESH-SA outperforms DESH-SC by accommodating significantly more update transactions in the system. Moreover, DESH-SA can also achieve near-optimal update workload. © 2009 Springer Science+Business Media, LLC.

Research Area(s)

  • Deferrable scheduling, Fixed priority scheduling, Real-Time databases, Temporal validity constraint

Citation Format(s)

DESH : Overhead reduction algorithms for deferrable scheduling. / Xiong, Ming; Han, Song; Chen, Deji; Lam, Kam-Yiu; Feng, Shan.

In: Real-Time Systems, Vol. 44, No. 1-3, 03.2010, p. 1-25.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review