The Design and Analysis of Scheduling Algorithms for Real-Time and Fault-Tolerant Computer Systems

Many applications are not feasible without the support of real-time and fault-tolerant computer systems. Timeliness and dependability are properties that predominantly distinguish a real-time system and a fault-tolerant system from other computer systems. In this thesis we address the issue of supporting timeliness and dependability by studying four fundamental scheduling problems that are inherent to these systems.
The real-time systems we consider are the ones in which tasks are executed periodically; each task has an infinite number of requests and there are multiple tasks being executed. There arises a problem of scheduling all requests of the tasks on as few processors as possible such that not a single deadline is missed. This problem has optimal solutions for a single processor system when tasks are preemptive; the Rate-Monotonic (RM) algorithm is optimal for fixed-priority assignment and the Earliest Deadline First (EDF) is optimal for dynamic priority assignment. However, the problem is intractable for a multiprocessor system. The main goal of this thesis is to design and analyze algorithms for the problem of scheduling a set of periodic, preemptive tasks on as few processors as possible such that task deadlines are met on each processor by the RM algorithm. We give the best on-line and off-line scheduling algorithms for this problem to date with regard to worst case performance and average case performance. The worst case performance
of the algorithms is shown to have constant tight bounds through complex analysis and the average case performance is assessed by conducting simulation experiments. Several new schedulability conditions are also obtained for the RM scheduling.
The second problem is defined the same way as the first one except that instead of one version, a task has a number of versions that must be executed on different processors for fault-tolerance purposes. We propose a solution to this problem with its worst case performance analyzed and average case performance simulated.
The third problem is defined the same way as the second one except that instead of the RM algorithm, the EDF algorithm is used to guarantee task deadlines on each processor. This problem is equivalent to the problem of packing a list of colorful items into as few bins as possible without violating the constraint that no two items having the same colors are packed into a bin. An algorithm is proposed to solve this problem, with its worst case performance shown to be tightly bounded by 1.7.
Finally we address the fundamental question of scheduling non-preemptive tasks on a multiprocessor system for tolerance of processor failures or task errors. We show that this problem is intractable even for three processors with the tolerance of one arbitrary processor failure. Two heuristic algorithms are then proposed to solve a restricted case of the problem. By solving these problems, the thesis contributes to the establishment of a firm theoretical foundation for guaranteeing task deadlines in real-time and fault-tolerant computer systems.