DESH

DESH: Overhead reduction algorithms for deferrable scheduling Although the deferrable scheduling algorithm for fixed priority transactions $(DS-FP)$ has been shown to be a very effective approach for minimizing real-time update transaction workload, it suffers from its on-line scheduling overhead. In this work, we propose two extensions of $DS-FP$ to minimize the on-line scheduling overhead. The proposed algorithms produce a hyperperiod from $DS-FP$ so that the schedule generated by repeating the hyperperiod infinitely satisfies the temporal validity constraint of the real-time data. The first algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Construction $(DESH-SC)$, searches the $DS-FP$ schedule for a hyperperiod. The second algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Adjustment $(DESH-SA)$, adjusts the $DS-FP$ schedule in an interval to form a hyperperiod. Our experimental results demonstrate that while both $DESH-SC$ and $DESH-SA$ can reduce the scheduling overhead of $DS-FP, DESH-SA$ outperforms $DESH-SC$ by accommodating significantly more update transactions in the system. Moreover, $DESH-SA$ can also achieve near-optimal update workload.