A scheduling algorithm for hybrid tasks based on Imprecise Computation-Rotational Scheduling scheme

摘要

A fault-tolerant scheduling algorithm for hybrid tasks is presented, which combines the Imprecise Computation-Rotational Scheduling (IC-RS) scheduling strategy and the Alternate Primary Recovery-Space and Time Redundancy (APR-STR) fault-tolerant allocate scheduling. APR-STR fault-tolerant allocate strategy is adopted to divide periodic tasks with fault-tolerant requirement into two parts: high frequency tasks set and low frequency tasks set, then adopts space redundancy and time redundancy to scheduling sub-tasks set respectively. The periodic tasks without fault-tolerant requirement are treated as task which has backup only, by this way, periodic tasks are able to schedule together. The aperiodic tasks without fault-tolerant requirement are divided into two sequences: waiting sequence and preempted sequence. The aperiodic tasks' priority is based on their waiting time, and they are scheduled in the idle time of processors. The proposed algorithm is able to schedule the hybrid tasks effectively, and to improve process's utilization. An example shows this algorithm can deduce the overhead of communication time between processors and improve utilization of system resources.