Please use this identifier to cite or link to this item: http://hdl.handle.net/11717/4375
Title: A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis
Authors: Manimaran, G.
Siva Ram Murthy, C.
Keywords: Algorithms
Benchmarking
Computer simulation
Fault tolerant computer systems
Queueing theory
Real time systems
Response time (computer systems)
Storage allocation (computer)
Fault-tolerant dynamic scheduling algorithms
Multiprocessing systems
Issue Date: 1998
Citation: IEEE Transactions on Parallel and Distributed Systems, 9(11), 1137-1152
Abstract: Many time-critical applications require dynamic scheduling with predictable performance. Tasks corresponding to these applications have deadlines to be met despite the presence of faults. In this paper, we propose an algorithm to dynamically schedule arriving real-time tasks with resource and fault-tolerant requirements on to multiprocessor systems. The tasks are assumed to be nonpreemptable and each task has two copies (versions) which are mutually excluded in space, as well as in time in the schedule, to handle permanent processor failures and to obtain better performance, respectively. Our algorithm can tolerate more than one fault at a time, and employs performance improving techniques such as 1) distance concept which decides the relative position of the two copies of a task in the task queue, 2) flexible backup overloading, which introduces a trade-off between degree of fault tolerance and performance, and 3) resource reclaiming, which reclaims resources both from deallocated backups and early completing tasks. We quantify, through simulation studies, the effectiveness of each of these techniques in improving the guarantee ratio, which is defined as the percentage of total tasks, arrived in the system, whose deadlines are met. Also, we compare through simulation studies the performance our algorithm with a best known algorithm for the problem, and show analytically the importance of distance parameter in fault-tolerant dynamic scheduling in multiprocessor real-time systems. ? 1998 IEEE.
URI: http://dx.doi.org/10.1109/71.735960
http://hdl.handle.net/11717/4375
ISSN: 10459219
Appears in Collections:Articles

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.