On Co-Scheduling of Update and Control Transactions in Real-Time Sensing and Control Systems: Algorithms, Analysis, and Performance

摘要

Maintaining sensor data validity while exercising timely control is crucial in real-time sensing and control systems. The goal of scheduling algorithms deployed in such systems is to maintain the validity of real-time sensor data so as to maximize the schedulability of update transactions with minimum update workload so that control actions occur on time. In this paper, we first propose a dynamic scheduling algorithm, called Deferrable Scheduling with Least Actual Laxity First (DS-LALF). DS-LALF is designed by extending the deferrable scheduling algorithm, DS-FP which is designed for fixed priority systems. We develop a schedulability test algorithm for DS-LALF based on pattern analysis and a pattern search algorithm to find the shortest and earliest pattern in the schedule. Then, based on DS-LALF, a co-scheduling algorithm called Co-LALF--to schedule update transactions and control transactions in a real-time sensing and control system together--is developed 1) to meet the deadlines of all the control transactions and 2) to maximize the quality of data (QoD) utilized by the control transactions. Co-LALF schedules the jobs in the ascending order of their actual laxities and defers the release times of update jobs as long as the corresponding sensor data are maintained within the required quality. Experimental results show that DS-LALF incurs lower update workload compared with DS-FP and ML, and its schedulability is close to DS-FP but is much better than ML and DS-EDF. The experimental results also show that Co-LALF is effective in improving the overall performance by ensuring better QoD for the real-time data while meeting the deadline constraints of all the control transactions.