Deferrable Scheduling for Temporal Consistency: Schedulability Analysis and Overhead Reduction

The deferrable scheduling algorithm for fixed priority transactions (DS-FP) is demonstrated to be a very effective approach for minimizing real-time update transaction workload while maintaining temporal validity of real-time data. This paper examines the schedulability of deferrable scheduling and presents a sufficient condition. While its online scheduling overhead is a concern, we propose a hyperperiod based DS-FP approach satisfying the temporal validity constraint with low overhead. The algorithm, namely DEferrable Scheduling with Hyperperiod by Schedule Adjustment (DESH-SA), adjusts the DS-FP schedule in an interval so that the adjusted schedule in the interval can be repeated infinitely. Our experiments demonstrate that DESH-SA can reduce scheduling overhead of DS-FP and also achieve update workload near optimal