Real-Time Scheduling with Fault-Tolerance in Heterogeneous Distributed Systems
Xiao Qin · Chinese Journal of Computers · 2002
Some real time fault tolerant scheduling algorithms have been studied in the literatures. These algorithms, however, are devised for homogeneous distributed systems, which have identical processors. The heterogeneous systems, on the other hand, consist of processors with various computation powers. Since the scheduling is a key factor in obtaining high performance in heterogeneous systems, scheduling algorithms play an important role in the efficiency of heterogeneous systems. This paper presents two real time scheduling algorithms, RTFTNO and RTFTRC, which are able to map tasks onto processors and order their execution so that tasks' real time requirements are satisfied and a minimum schedule length is abtained. We introduce the reliability cost into the scheduling algorithm in heterogeneous systems. The RTFTRC algorithm allocates each task to the processor, which gives rise to the minimum reliability cost. This scheme is able to enhance the reliability of the systems without any extra hardware. The RTFTNO algorithm, however, does not take reliability cost into account. Therefore, our simulation results indicate that under the same workload, the reliability cost generated by the RTFTRC is significantly less than that generated by the RTFTNO algorithm. In addition, we observe from the simulation results that the schedule length generated by the RTFTRC algorithm is shorter than that generated by the RTFTNO algorithm. This fact is the main reason that the RTFTRC algorithm has lower PMD(percentage of missing deadlines) than that of the RTFTNO algorithm. Further more, since the RTFTRC has a shorter schedule length, its schedulability is relatively higher than that of the RTFTNO algorithm. As the schedule threshold is a factor in our algorithms, this paper also discusses the impact of schedule threshold on systems performance. Our simulation experiments show that the schedule threshold has no effect on the RTFTNO algorithm. Schedule threshold has an unnoticeable impact, which is not meaningful, on the RTFTRC algorithm.