A deferrable scheduling algorithm for real-time transactions maintaining data freshness

Periodic update transaction model has been used to maintain freshness (or temporal validity) of real-time data. Period and deadline assignment has been the main focus in the past studies such as the more-less scheme by Xiong and Ramamrithan (2004) in which update transactions are guaranteed by the deadline monotonic scheduling algorithm by Leung and Whitehead (1982) to complete by their deadlines. In this paper, we propose a novel algorithm, namely deferrable scheduling, for minimizing imposed workload while maintaining temporal validity of real-time data. In contrast to previous work, update transactions scheduled by the deferrable scheduling algorithm follow a sporadic task model. The deferrable scheduling algorithm exploits the semantics of temporal validity constraint of real-time data by judiciously deferring the sampling times of update transaction jobs as late as possible. We present a theoretical analysis of its processor utilization, which is verified in our experiments. Our experimental results also demonstrate that the deferrable scheduling algorithm is a very effective approach, and it significantly outperforms the more-less scheme in terms of reducing processor workload. © 2005 IEEE.