Real-Time Scheduling And Load Balancing Algorithms In Fault Tolerant Systems

Fault-tolerant systems currently take over the safety-critical role in many areas such as defense, airplane, nucleus control, communication, industry process control, medical. Fault-tolerant computing also becomes an important subject of the computer science. These years according to the real-time computing and distributed computing rapid developing, a new trend of fault-tolerant systems is to ensure crtical tasks be executed timely and acquire load balancing in both absence and presence of faults, hence to expand the fault-tolerant applications in the real-time and distributed computing areas and to improve fault-tolerant systems resource utilization and performance.Therefore, this dissertation considers the real-time scheduling and load balancing algorithms in fault tolerant systems. Almost all fault-tolerant scheduling algorithms in real-time systems so far are designed to deal with hardware faults, less of them take possible software faults into account hence this dissertation proposes two partial-preemptive algorithms in the deadline mechanism which provides software fault-tolerance in hard real-time systems. Moreover, none of the previous proposed fault-tolerant scheduling algorithms have good scheduling performance for all the cases when the task set has different upper bound for the task load hence this dissertation proposes an efficient scheduling algorithm which extends the uniprocessor RM algorithm to primary-backup model to provide fault tolerance. In addition, this dissertation proposes a universal load-balancing algorithm for primary-backup based fault tolerant systems. At last, this dissertation reports a global equity crossing fault-tolerant system as a case study to demonstrate the load-balancing algorithm benefits in reality.The contributions of this dissertation are summarized as below:1) Two partial-preemptive scheduling algorithms called EDFPPA and RMPPA are proposed in the deadline mechanism which provides software fault-tolerance in hard real-time periodic task systems. Extensive simulations results show that both EDFPPA and RMPPA can obtain the similar scheduling performance as well as the well-known algorithms so far. Moreover, EDFPPA and RMPPA reduce the preemption dramatically than previous algorithms, thus reduce the negative impact introduced by preemption such as overhead runtime computation time.2) An efficient scheduling algorithm called TPFTRM is proposed in primary-backup based fault-tolerant systems. Compared with previous scheduling algorithms in this area, TPFTRM maximizes the backup over-booking and deallocation, thus reduces the hardware redundancy. Moreover, TPFTRM proposes the task partitioning and processors grouping technique, which reduce the scheduling computation time and also make an easy way to understand and implement it.3) A load-balancing algorithm called RSA is proposed in primary-backup based fault-tolerant systems. Compared with previous work of this area, RSA algorithm has the load better balanced no matter how many backup processes each primary process owns.4) A global equity crossing fault-tolerant system is described as a case study which integrates RSA algorithm and the other mechanisms to demonstrate the load-balancing algorithm benefits in reality.