Schedulability analysis of deferrablescheduling algorithms for maintainingreal-time data freshness

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

25 Scopus Citations
View graph of relations

Author(s)

  • Song Han
  • Deji Chen
  • Ming Xiong
  • Aloysius K. Mok
  • Krithi Ramamritham

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number6338927
Pages (from-to)979-994
Journal / PublicationIEEE Transactions on Computers
Volume63
Issue number4
Online published24 Oct 2012
Publication statusPublished - Apr 2014

Abstract

Although the deferrable scheduling algorithm for fixed priority transactions (DS-FP) has been shown to provide a better performance compared with the More-Less (ML) method, there is still a lack of any comprehensive studies on the necessary and sufficient conditions for the schedulability of DS-FP. In this paper, we first analyze the necessary and sufficient schedulability conditions for DS-FP, and then propose a schedulability test algorithm for DS-FP by exploiting the fact that there always exists a repeating pattern in a DS-FP schedule. To resolve the limitation of fixed priority scheduling in DS-FP, we then extend the deferrable scheduling to a dynamic priority scheduling algorithm called DS-EDF by applying the earliest deadline first (EDF) policy to schedule update jobs. We also propose a schedulability test for DS-EDF and compare its performance with DS-FP and ML through extensive simulation experiments. The results show that the schedulability tests are effective. Although the schedulability of DS-EDF is lower than DS-FP and the repeating patterns in DS-EDF schedules are longer than those in DS-FP due to the use of dynamic priority scheduling, the performance of DS-EDF is better than both DS-FP and ML in terms of CPU utilization and impact on lower priority application transactions. © 1968-2012 IEEE.

Research Area(s)

  • real-time data, Real-time database, real-time scheduling, schedulability, temporal validity

Citation Format(s)

Schedulability analysis of deferrablescheduling algorithms for maintainingreal-time data freshness. / Han, Song; Chen, Deji; Xiong, Ming; Lam, Kam-Yiu; Mok, Aloysius K.; Ramamritham, Krithi.

In: IEEE Transactions on Computers, Vol. 63, No. 4, 6338927, 04.2014, p. 979-994.

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