现代数据工程与实时计算实验室
 

论文发表

Workload-Efficient Deadline and Period Assignment for Maintaining Temporal Consistency under EDF


作者

Jianjun Li, Ming Xiong, Victor C. S. Lee, LihChyun Shu, Guohui Li

期刊

期刊名称:IEEE
出版日期:2013
所在页数:1255-1268

摘要

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 (GEEDF), for assigning periods and deadlines to EDF-scheduled update transactions. Phase 1 of GEEDF 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.

关键词

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

[pdf]

地址:湖北省武汉市洪山区珞瑜路1037号,华中科技大学南一楼西南501室 邮编:430074 电话:027-87556601
计算机科学与技术学院,现代数据工程与实时计算实验室 有问题和意见请与网站管理员联系:adelab@163.com

温馨提示:为保证能正常的浏览此网站,请用IE9.0以上版本查看!    访问人次: