The Rate Monotonic Scheduling (RMS) policy is a widely accepted scheduling strategy for real-time systems due to strong theoretical foundations and features attractive to practical uses. For a periodic task set of n tasks with deadlines at the end of task periods, it guarantees a feasible schedule on a single processor as long as the utilization factor of the task set is below n(2/sup 1/n/-1) which converges to 0.69 for large n. We analyze the schedulability of a set of periodic tasks that is scheduled by the RMS policy and is susceptible to a single fault. The recovery action is the reexecution of all uncompleted tasks. The priority of the RMS policy is maintained even during recovery. Under these conditions, we guarantee that no task will miss a single deadline, even in the presence of a fault, if the utilization factor on the processor does not exceed 0.5. Thus, 0.5 is the minimum achievable utilization that permits recovery from faults before the expiration of the deadlines of the tasks. This bound is better than the trivial bound of 0.6912=0.345 that would be obtained if computation times were doubled to provide for reexecutions in the RMS analysis. Our result provides scheduling guarantees for tolerating a variety of intermittent and transient hardware and software faults that can be handled simply by reexecution. In addition, we demonstrate how permanent faults can be tolerated efficiently by maintaining common spares among a set of processors that are independently executing periodic tasks.

Topological testing is introduced and its applications are presented. Topological testing uses graph-theoretic optimization methods such as the traveling salesman problem, the Chinese postman problem, coloring, path covering, and partitioning to minimize the test time. The topological testing techniques can be applied to test a system's behavior and its organization at each level of the system's hierarchy, namely, circuit, logic, register transfer, instruction, and processor-memory-switch levels. Specifically, the topological testing approach is demonstrated by developing tests for the multistage interconnection network and the hypercube network. Time optimization for the testing of these networks gives very promising results by taking advantage of inherent parallelism and removing test redundancy. Three-orders-of-magnitude improvement is achieved by applying topological testing techniques to the testing of an existing multistage interconnection network.>