| As real-time requirements are becoming prevalent in industrial applications, there is an increasing demand for more complex, sophisticated, and dependable hard real-time computing systems, where periodic and aperiodic tasks generally co-exist. Both periodic tasks - for information acquisition, control loops, data communication, etc. -, and aperiodic tasks - arising from arbitrary critical events - must be completed within their deadlines. Meanwhile, a multiprocessor is necessary to deal with the complicated computations. Furthermore, timing constraints are essential for the correct execution of the system even if hardware or software faults occur. Therefore, real-time industrial computing requires jointly scheduling periodic and aperiodic tasks in multiprocessor systems, and needs fault-tolerance to behave correctly despite the presence of failures. In order to meet the requirements of real-time industrial computing, we present a variety of algorithms for scheduling multiple tasks in real-time industrial systems based on the analysis of existing algorithms. The schedulability and ability of fault-tolerance of each algorithm is analyzed, and the effectiveness and feasibility of each algorithm is demonstrated with simulation results. The main work and contributions in this dissertation are as follows.? Considering the characteristics of periodic and aperiodic tasks in real-time industrial systems, a Processing-Time Reservation algorithm (PTR) is proposed, in which periodic tasks are scheduled according to the Rate-Monotonic Scheduling (RMS) algorithm, while aperiodic tasks are scheduled by utilizing the reserved processing-time following the Earliest-Deadline-First (EDF) algorithm. The scheduling of aperiodic tasks does not lead to reallocation of periodic tasks, which greatly reduces the complexity of on-line computation.? Based on the analysis of exact execution time of periodic tasks at critical moments, the maximum processing-time to be reserved for the execution of aperiodic tasks without missing any periodic task deadline is derived by systematic analysis. Owing to the prior knowledge of periodic tasks, the allocation of periodic tasks and the derivation of reserved processing-time are implemented off-line. PTR can make full use of all the available processing time, which achieves high processor utilization without increment of on-line overhead.? Aiming at minimizing the number of required processors, a Fault-Tolerant Best-Fit algorithm for Scheduling periodic tasks (FTBFS) is proposed, which adopts the primary/backup approach and determines which tasks must use active duplication and which can use passive duplication,preferring passive duplication whenever possible. In order to tolerate many processor failures, spare processors are employed to replace failed processors on-line. Then, a generalized algorithm for scheduling periodic and aperiodic tasks is proposed by integrating PTR and fault-tolerant techniques. The allocation of primary and backup copies of periodic tasks and the derivation of maximum reserved processing-time arc performed statically, while the allocation of primary and backup copies of aperiodic tasks is performed dynamically once unexpected aperiodic tasks arrive in the system. Combining static and dynamic scheduling simplifies the online computation, and the combination of passive and active duplication of tasks efficiently reduces the number of required processors.? Based on the analysis of a system specification for a kind of embedded control system (ECS), it is addressed the problem of the multiprocessor priority inheritance protocol to control the access to shared-resources in an ECS, a nonpreemptive-critical-section protocol is extended to fault-tolerant multiprocessor systems, and the blocking time introduced by resource conflicts of cooperating tasks is computed. Then a fault-tolerant algorithm for scheduling cooperating tasks is presented, which bounds the blocking time, requires limited overhead on the number of processors, and still...
|
PDF Full Text Request