Decision-driven scheduling
Tóm tắt
This paper presents a scheduling model, called decision-driven scheduling, elaborates key optimality results for a fundamental scheduling model, and evaluates new heuristics solving more general versions of the problem. In the context of applications that need control and actuation, the traditional execution model has often been either time-driven or event-driven. In time-driven applications, sensors are sampled periodically, leading to the classical periodic task model. In event-driven applications, sensors are sampled when an event of interest occurs, such as motion-activated cameras, leading to an event-driven task activation model. In contrast, in decision-driven applications, sensors are sampled when a particular decision must be made. We offer a justification for why decision-driven scheduling might be of increasing interest to Internet-of-things applications, and explain why it leads to interesting new scheduling problems (unlike time-driven and event-driven scheduling), including the problems addressed in this paper.
Tài liệu tham khảo
Adelberg B, Garcia-Molina H, Kao B (1995) Applying update streams in a soft real-time database system. In: Proceedings of the ACM SIGMOD international conference on management of data, ser SIGMOD
Adelberg B, Kao B, Garcia-Molina H (1996) Database support for efficiently maintaining derived data. In: Proceedings of 5th international conference on extending database technology, vol 1057. Springer, New York
Cipar J, Ganger G, Keeton K, Morrey CB, III, Soules CA, Veitch A (2012) Lazybase: trading freshness for performance in a scalable database. In: Proceedings of the 7th ACM European conference on computer systems, ser EuroSys
Gustafsson T, Hansson J (2004) Data management in real-time systems: a case of on-demand updates in vehicle control systems. In: Proceedings of the IEEE real-time and embedded technology and applications symposium, ser RTAS
Gustafsson T, Hansson J (2004) Dynamic on-demand updating of data in real-time database systems. In: Proceedings of the ACM symposium on applied computing, ser SAC
Hu S, Yao S, Jin H, Zhao Y, Hu Y, Liu X, Naghibolhosseini N, Li S, Kapoor A, Dron W, Su L, Bar-Noy A, Szekely P, Govindan R, Hobbs R, Abdelzaher TF (2015) Data acquisition for real-time decision-making under freshness constraints. In: RTSS
Kang K-D, Son S, Stankovic J, Abdelzaher T (2002) A qos-sensitive approach for timeliness and freshness guarantees in real-time databases. In: Proceedings of the Euromicro conference on real-time systems, ser ECRTS
Kang K-D, Son S, Stankovic J (2002) Star: secure real-time transaction processing with timeliness guarantees. In: Proceedings of the IEEE real-time systems symposium, ser RTSS
Kang K-D, Son SH, Stankovic JA (2004) Managing deadline miss ratio and sensor data freshness in real-time databases. IEEE Trans Knowl Data Eng 16(10):1200–1216
Kao B, Lam K-Y, Adelberg B, Cheng R, Lee T (2003) Maintaining temporal consistency of discrete objects in soft real-time database systems. IEEE Trans Comput 52(3):373–389
Kim J-E (2017) Timing analysis in existing and emerging cyber physical systems. PhD dissertation, University of Illinois at Urbana-Champaign. http://hdl.handle.net/2142/97405
Kim J-E, Abdelzaher T, Sha L, Bar-Noy A, Hobbs R (2016) Sporadic decision-centric data scheduling with normally-off sensors. In: Proc of IEEE int’l real-time systems symposium (RTSS)
Kim J-E, Abdelzaher T, Sha L, Bar-Noy A, Hobbs R, Dron W (2016) On maximizing quality of information for the internet of things: a real-time scheduling perspective (Invited). In: Proc of IEEE int’l conference on embedded and real-time computing systems and applications
Lee C-G, Kim Y-K, Son SH, Min SL, Kim CS (1996) Efficiently supporting hard/soft deadline transactions in real-time database systems. In: Proceedings of the third international workshop on real-time computing systems application, ser RTCSA
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J ACM 20(1):46–61
Qu H, Labrinidis A (2007) Preference-aware query and update scheduling in web-databases. In: Proceedings of the 23rd IEEE international conference on data engineering
Ramamritham K (1993) Real-time databases. Distrib Parallel Databases 1(2):199–226
Röhm U, Böhm K, Schek H-J, Schuldt H (2002) Fas: a freshness-sensitive coordination middleware for a cluster of olap components. In: Proceedings of the 28th international conference on very large data bases, ser VLDB ’02
Song X, Liu JW-S (1995) Maintaining temporal consistency: pessimistic vs. optimitic concurrency control. IEEE Trans Knowl Data Eng 7(5):786–796
Xiong M, Ramamritham K (2004) Deriving deadlines and periods for real-time update transactions. IEEE Trans Comput 53(5):567–583
Xiong M, Han S, Lam K-Y (2005) A deferrable scheduling algorithm for real-time transactions maintaining data freshness. In: Proceedings of the IEEE international real-time systems symposium, ser RTSS
Xiong M, Wang Q, Ramamritham K (2008) On earliest deadline first scheduling for temporal consistency maintenance. Real Time Syst 40(2):208–237