Workload-efficient deadline and period assignment for maintaining temporal consistency under EDF

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

18 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number6171159
Pages (from-to)1255-1268
Journal / PublicationIEEE Transactions on Computers
Volume62
Issue number6
Online published7 Mar 2012
Publication statusPublished - Jun 2013

Abstract

Deriving deadlines and periods for update transactions so as to maintain timeliness and data freshness while minimizing imposed workload has long been recognized an important problem in real-time database research. Despite years of active research, the state-of-the-art still has much room for improvement, particularly for periodic transactions scheduled by the Earliest Deadline First (EDF) algorithm. In this paper, we propose a practical and efficient two-phase algorithm, GEneral EDF ((G EEDF)), for assigning periods and deadlines to EDF-scheduled update transactions. Phase 1 of (G EEDF) aims at finding solutions for most inputs in linear time, based on the observation that the execution times of update transactions are relatively small compared to the validity interval lengths of real-time data objects in many real-time applications. In the remaining cases for which Phase 1 fails to derive solutions, Phase 2 is invoked by employing an existing deadline-monotonic-based algorithm, which we show is also applicable to our problem. Meanwhile, we have devised several techniques which significantly reduce the cost of schedulability test, and hence greatly improve time efficiency. Our experimental results demonstrate that (GEEDF) outperforms existing approaches in terms of generated workloads. Although Phase 2 has a pseudopolynomial time complexity, our experimental study shows that it runs much faster than other solutions with comparable quality. © 1968-2012 IEEE.

Research Area(s)

  • earliest deadline first, periods and deadlines, Real-time databases, temporal consistency, update transaction

Citation Format(s)

Workload-efficient deadline and period assignment for maintaining temporal consistency under EDF. / Li, Jianjun; Xiong, Ming; Lee, Victor C.S.; Shu, Lihchyun; Li, Guohui.

In: IEEE Transactions on Computers, Vol. 62, No. 6, 6171159, 06.2013, p. 1255-1268.

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