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. 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 Rate-Monotonic (RM) algorithm. The thesis further considers three problems that are variations on the main question; in one, a task has multiple versions which must be executed on different processors for fault-tolerance purposes; in another, instead of the RM algorithm, the Earliest Deadline First (EDF) algorithm is used to guarantee task deadlines; and finally, the problem of scheduling non-preemptive tasks for fault-tolerance is considered. The thesis offers solutions to these problems. In doing so, it gives the best on-line and off-line scheduling algorithms for the main 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. 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.
展开▼
