Scheduling Real-Time Tasks for Dependability

@article{1997, abstract = {Real-time systems are increasingly used in applications whose failure may result in large economic and human costs. Since many such systems operate in environments that are non-deterministic, and possibly hazardous, it is extremely important that the systems be dependable, namely the deadlines of tasks must be met even in the presence of particular failures. In order to enhance the dependability of a real-time system, we study the problem of scheduling a set of real-time tasks to meet their deadlines in the presence of processor failures. We first prove that the problem of scheduling a set of non-preemptive tasks on more than two processors to tolerate one arbitrary processor failure is NP-complete even when the tasks share a common deadline. Heuristic algorithms are then proposed to solve this problem. The schedules generated by the heuristic algorithms can tolerate one arbitrary processor failure in the worst case. The analysis and experimental data show that the performance of the algorithms is near-optimal.}, author = {Oh, Y. and Son, S. H. }, citeulike-article-id = {2789429}, journal = {The Journal of the Operational Research Society}, keywords = {fault-tolerance, real-time, scheduling}, number = {6}, pages = {629--639}, posted-at = {2008-05-12 14:12:07}, priority = {2}, publisher = {Palgrave Macmillan Journals on behalf of the Operational Research Society}, title = {Scheduling Real-Time Tasks for Dependability}, url = {http://www.jstor.org/stable/3010227}, volume = {48}, year = {1997} }

TY - JOUR ID - 1997 L3 - citeulike-article-id:2789429 TI - Scheduling Real-Time Tasks for Dependability JF - The Journal of the Operational Research Society VL - 48 IS - 6 SP - 629 EP - 639 PB - Palgrave Macmillan Journals on behalf of the Operational Research Society N2 - Real-time systems are increasingly used in applications whose failure may result in large economic and human costs. Since many such systems operate in environments that are non-deterministic, and possibly hazardous, it is extremely important that the systems be dependable, namely the deadlines of tasks must be met even in the presence of particular failures. In order to enhance the dependability of a real-time system, we study the problem of scheduling a set of real-time tasks to meet their deadlines in the presence of processor failures. We first prove that the problem of scheduling a set of non-preemptive tasks on more than two processors to tolerate one arbitrary processor failure is NP-complete even when the tasks share a common deadline. Heuristic algorithms are then proposed to solve this problem. The schedules generated by the heuristic algorithms can tolerate one arbitrary processor failure in the worst case. The analysis and experimental data show that the performance of the algorithms is near-optimal. KW - fault-tolerance KW - real-time KW - scheduling AU - Oh, Y AU - Son, SH PY - 1997/// UR - http://www.jstor.org/stable/3010227 ER -