A sensor transaction scheduling algorithm for maintaining real-time data temporal validity

Abstract

A new scheduling algorithm called deferrable scheduling with time slice exchange (DS-EXC) was proposed to maintain the temporal validity of real-time data. In DS-EXC, the time slice exchange method was designed to further defer the release time of transaction instances derived by the deferrable scheduling algorithm (DS-FP). In this way, more CPU time would be left for lower priority transactions and other transactions. In order to minimize the scheduling overhead, an off-line scheme was designed. In particular, the schedule for a transaction set is generated off-line until a repeating pattern is found, and then the pattern is used to construct the schedule on-line. The performance of DS-EXC was evaluated by sets of experiments. The results show that DS-EXC outperforms DS-FP in terms of increasing schedulable ratio. It also provides better performance under mixed workloads.

Keywords

temporal validity / real-time database / sensor transaction

References

[1] GoudG., SharmaN., RamamrithamK., MalewarS.. Efficient real-time support for automotive applications: A case study [C]. Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, 2006, Washington, DC, IEEE Computer Society: 335-341

[2] HoS.-j., KuoT.-w., MokA. K.. Similarity-based load adjustment for real-time data-intensive applications [C]. Proceedings of the 18th IEEE Real-Time Systems Symposium, 1997, Washington, DC, IEEE Computer Society: 144-153

[3] RamamrithamK.. Real-time databases [J]. Distributed and Parallel Databases, 1993, 1(2): 199-226

[4] StankovicJ. A., SonS., HanssonJ.. Misconception about real-time databases [J]. Computer, 1999, 32(6): 29-36

[5] XiongM., HanS., LamK.-y., ChenD.-ji.. Deferrable scheduling for maintaining real-time data freshness: Algorithms, analysis, and results [J]. IEEE Transactions on Computers, 2008, 57(7): 952-964

[6] AmirijooM., HanssonJ., SonS. H.. Specification and management of QoS in real-time databases supporting imprecise computations [J]. IEEE Transactions on Computers, 2006, 55(3): 304-319

[7] XiongM., SivasankaranR., StankovicJ. A., RamamrithamK., TowsleyD.. Scheduling transactions with temporal constraints: exploiting data semantics [J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(5): 1155-1166

[8] KangK. D., SonS. H., StankovicJ. A.. Managing deadline miss ratio and sensor data freshness in real-time databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(10): 1200-1216

[9] SongX.-h., LiuJ. W. S.. Maintaining temporal consistency: Pessimistic versus optimistic concurrency control [J]. IEEE Transactions on Knowledge and Data Engineering, 1995, 7(5): 786-796

[10] GustafssonT., HanssonJ.. Dynamic on-demand updating of data in real-time database systems [C]. Proceedings of the 2004 ACM Symposium on Applied Computing, 2004, New York, ACM: 846-853

[11] LundbergL.. Utilization based schedulability bounds for age constraint process sets in real-time system [J]. Real-Time Systems, 2002, 23(3): 273-295

[12] XiongM., LiangB.-y., LamK.-Y., GuoYang.. Quality of service guarantee for temporal consistency of real-time transactions [J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(8): 1097-1110

[13] XiongM., RamamrithamK.. Deriving deadlines and periods for real-time update transactions [J]. IEEE Transactions on Computers, 2004, 53(5): 567-583

[14] HanS., ChenD.-j., XiongM., MokA. K.. A schedulability analysis of deferrable scheduling using patterns [C]. Proceedings of the 2008 Euromicro Conference on Real-Time Systems, 2008, Washington D C, IEEE Computer Society: 45-57

[15] BiniE., ButtazzoG.. Measuring the performance of schedulability tests [J]. Real-Time Systems, 2005, 30(1/2): 129-154