AN IMPROVED SCHEDULING STRATEGY FOR PROCESSOR UTILIZATION IN HARD-REAL-TIME SYSTEMS

Abstract

A hard-real-time system must be reliable as a failure to meet its timing specifications might endanger human life, damage equipment or waste resources. Applications that require remote operation, timing accuracy, and long periods of activity need mechanisms to support reliability. One approach to increase reliability is by employing fault-tolerance. One approach to achieve fault-tolerance is through redundancy. In order to tolerate failures, tasks are scheduled on two sets of processors, whenever a processor in one of these sets is failed then the results of the corresponding processor on the other set will be taken. This dissertation addresses the problem of maximizing the minimum achievable processor utilization in the fault-tolerant hard-real-time systems. A distributed system is considered where tasks are periodic and each task occurs in multiple copies which are periodically synchronized in order to handle failures. These tasks are preemptively scheduled on different processors such that the every occurrence of task has to be completely executed before the next occurrence of the same task. In this thesis the Slot Machine and Mixed Strategy algorithms, related to fault-tolerant hard-real-time system, have been implemented. Employing Mixed Strategy algorithm has resulted in a considerable improvement in the processor utilization. In this high frequency tasks are duplicated while the low frequency tasks are periodically checkpointed. Further modification has been suggested to the Mixed Strategy algorithm which resulted in an increase in the feasible task sets.