Temporal consistency maintenance on multiprocessor platforms with instance skipping

Abstract

Maintaining temporal consistency of real-time data is important for cyber-physical systems. Most of the previous studies focus on uniprocessor systems. In this paper, the problem of temporal consistency maintenance on multiprocessor platforms with instance skipping was formulated based on the (m,k)-constrained model. A partitioned scheduling method SC-AD was proposed to solve the problem. SC-AD uses a derived sufficient schedulability condition to calculate the initial value of m for each sensor transaction. It then partitions the transactions among the processors in a balanced way. To further reduce the average relative invalid time of real-time data, SC-AD judiciously increases the values of m for transactions assigned to each processor. Experiment results show that SC-AD outperforms the baseline methods in terms of the average relative invalid time and the average valid ratio under different system workloads.

Keywords

cyber-physical systems / sensor transactions / multiprocessor scheduling / temporal consistency

References

[1] CintugluM H, MohammedO A, AkkayaK, UluagacAS. A survey on smart grid cyber physical system testbeds [J]. IEEE Communications Surveys & Tutorials, 2017, 19(1): 446-464

[2] CañizoM, CondeA, CharramendietaS, MiñónR, Cid-FuentesR G, OnievaE. Implementation of a large-scale platform for cyber-physical system real-time monitoring [J]. IEEE Access, 2019, 7: 52455-52466

[3] CaiX. Collaborative prediction for bus arrival time based on CPS [J]. Journal of Central South University, 2014, 21(3): 1242-1248

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

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

[6] HanS, ChenD J, XiongM, LamK Y, MokA K, RamamrithamK. Schedulability analysis of deferrable scheduling algorithms for maintaining real-time data freshness [J]. IEEE Transactions on Computers, 2014, 63(4): 979-994

[7] XiongM, WangQ, RamamrithamK. On earliest deadline first scheduling for temporal consistency maintenance [J]. Real-Time Systems, 2008, 40(2): 208-237

[8] LiJ J, XiongM, LeeV C S, ShuL C, LiG. Workload-efficient deadline and period assignment for maintaining temporal consistency under EDF [J]. IEEE Transactions on Computers, 2013, 62(6): 1255-1268

[9] HanS, LamK Y, ChenD, XiongM, WangJ, RamamrithamK, MokA K. Online mode switch algorithms for maintaining data freshness in dynamic cyber-physical systems [J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(3): 756-769

[10] LiJ, ChenJ, XiongM, LiG, WeiW. Temporal consistency maintenance upon partitioned multiprocessor platforms [J]. IEEE Transactions on Computers, 2016, 65(5): 1632-1645

[11] ZhouC, LiG, LiJ, GuoB. Energy-aware real-time data processing for IoT systems [J]. IEEE Access, 2019, 7: 171776-171789

[12] DengC, LiG, ZhouQ, LiJ. Co-scheduling of hybrid transactions on multiprocessor real-time database systems [J]. IEEE Access, 2019, 7: 109506-109517

[13] KangK D. Enhancing timeliness and saving power in real-time databases [J]. Real-Time Systems, 2018, 54: 484-513

[14] 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(7): 1200-1216

[15] 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

[16] ZhouY, KangK D. Deadline assignment and feedback control for differentiated real-time data services [J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(12): 3245-3257

[17] KangW, SonS H, StankovicJ A. Design, implementation, and evaluation of a QoS-aware real-time embedded database [J]. IEEE Transactions on Computers, 2012, 61(1): 45-59

[18] AMIRIJOO M, CHAUFETTE N, HANSSON J, SON S H, GUNNARSSON S. Generalized performance management of multi-class real-time imprecise data services [C]//26th IEEE International Real-Time Systems Symposium. Miami, FL, USA, 2005: 38–49. DOI: https://doi.org/10.1109/RTSS.2005.23.

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

[20] WangJ, LamK Y, HanS, SonS H, MokA K. An effective fixed priority co-scheduling algorithm for periodic update and application transactions [J]. Computing, 2013, 95(1011): 993-1018

[21] HanS, LamK Y, WangJ, SonS H, MokA K. Adaptive co-scheduling for periodic application and update transactions in real-time database systems [J]. Journal of Systems and Software, 2012, 85(8): 1729-1743

[22] HanS, LamK Y, WangJ T, RamamrithamK, MokA K. On co-scheduling of update and control transactions in real-time sensing and control systems: Algorithms, analysis, and performance [J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(10): 2325-2342

[23] KANG K D. Reducing deadline misses and power consumption in real-time databases [C]//IEEE Real-Time Systems Symposium. Porto, Portugal, 2016: 257–268. DOI: https://doi.org/10.1109/RTSS.2016.033.

[24] RobertI D, AlanB. A survey of hard real-time scheduling for multiprocessor systems [J]. ACM Computing Surveys, 2011, 43(4): 1-44

[25] WEST R, POELLABAUER C. Analysis of a window constrained scheduler for real-time and best-effort packet streams [C]//IEEE Real-Time Systems Symposium. Orlando, FL, USA, 2000: 239–248. DOI: https://doi.org/10.1109/REAL.2000.896013.

[26] RamanathanP. Overload management in real-time control applications using (m,k)-firm guarantee [J]. IEEE Transactions on Parallel and Distributed Systems, 1999, 10(6): 549-559