Research On Hybrid Real-time Fault-tolerant Task Scheduling Algorithm Based On Multiprocessor

The real-time systems are made strict demands on because of their wide application in industry, such as finishing information acquisition, control loops, data communication within their deadlines, responding to aperiodic tasks arising from arbitrary critical events in time, and making real-time task satisfy the timing constraints even if hardware or software faults occur. Meanwhile, as the applications are getting complex gradually, the multiprocessor becomes a kind of effective way to deal with the complicated computations. Therefore, real-time industrial computing is required to handle periodic and aperiodic hybrid scheduling tasks in multiprocessor systems based on the premise of fault tolerance. In order to meet the existing problems in real-time industrial computing, the paper proposes a hybrid schedule algorithm through summarizing the characteristics of real-time task schedule and analyzing the existing algorithms, and the effectiveness and feasibility of the algorithm is verified with simulation test. The following researches and contributions are carried out:Considering the characteristics of periodic and aperiodic tasks in real-time industrial systems, a hybrid reservation processing-time task scheduling algorithm is proposed, in which periodic tasks are scheduled according to the Rate-Monotonic Scheduling (RMS) algorithm in the reserved processing time, while aperiodic tasks are scheduled according to the Earliest-Deadline-First (EDF) algorithm. The scheduling of aperiodic tasks does not cost the reserved processing time, which avoids reallocation of periodic tasks and reduces the complexity of on-line schedule greatly.Based on the analysis of exact execution time of periodic tasks at critical instant, the minimum reserved processing time of periodic tasks is derived systematically. According to the determinability of periodic task parameters, the allocation of periodic tasks and the derivation of reserved processing time are implemented off-line. The algorithm can make full use of the available processing time of processor without increase of on-line cost.An integrating fault-tolerant scheduling algorithm is introduced to implement periodic and aperiodic tasks schedule. The primary-backup allocation of periodic tasks and the derivation of minimum reserved processing time are performed statically, while the primary-backup allocation of aperiodic tasks is performed dynamically once unexpected aperiodic tasks arrive in the system. The combination between static and dynamic scheduling decreases the on-line cost to a great extent.