Title :
A new scheduling algorithm and a compensation strategy for imprecise computation
Author :
Cheng, Albert M K ; Wang, Rong
Author_Institution :
Dept. of Comput. Sci., Houston Univ.
Abstract :
The periodic multiframe task models and the imprecise computation techniques have been developed for scheduling real-time tasks. We introduce the imprecise computation concept into the periodic multiframe task model and derive a novel scheduling algorithm and an error compensation strategy. The paper also pays attention to the imprecise computation input error, which was often neglected in previous studies. The scheduling algorithm employs an error compensation strategy that based on the traditional largest-weight-first algorithm (LWF). The LWF algorithm guarantees that the largest weighted task executes first, thus minimizing the weighted total error in the task set. Our error compensation strategy enhances the error tolerance during the scheduling and takes maximum advantage of the processor idle time to improve the processor utilization. The experimental results show that the new task model and the new compensation strategy are practical in improving the schedulability and the processor utilization. The high error tolerance results in high schedulability and 100% processor utilization can be achieved in our algorithm. Moreover,, the scheduling algorithm is able to deal with tasks whose laxities are loose or light. Using both the error tolerance coefficient and the error compensation strategy leads to a good tradeoff between the result qualities (QoS) and the available processor time
Keywords :
processor scheduling; real-time systems; software fault tolerance; QoS; error compensation strategy; error tolerance; imprecise computation; largest-weight-first algorithm; periodic multiframe task models; processor idle time; processor utilization; real-time task scheduling algorithm; schedulability; Computer errors; Computer science; Degradation; Error compensation; Laboratories; Optimal scheduling; Processor scheduling; Real time systems; Scheduling algorithm; Timing;
Conference_Titel :
Computer Software and Applications Conference, 2004. COMPSAC 2004. Proceedings of the 28th Annual International
Conference_Location :
Hong Kong
Print_ISBN :
0-7695-2209-2
DOI :
10.1109/CMPSAC.2004.1342822