Dynamic Scheduling Real-Time Task Using Primary-Backup Overloading Strategy for Multiprocessor Systems

Wei SUN  Chen YU  Xavier DEFAGO  Yasushi INOGUCHI  

IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.3   pp.796-806
Publication Date: 2008/03/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.3.796
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Dependable Computing
real-time,  multiprocessor,  fault tolerance,  dynamic task scheduling,  

Full Text: PDF(949KB)>>
Buy this Article

The scheduling of real-time tasks with fault-tolerant requirements has been an important problem in multiprocessor systems. The primary-backup (PB) approach is often used as a fault-tolerant technique to guarantee the deadlines of tasks despite the presence of faults. In this paper we propose a dynamic PB-based task scheduling approach, wherein an allocation parameter is used to search the available time slots for a newly arriving task, and the previously scheduled tasks can be re-scheduled when there is no available time slot for the newly arriving task. In order to improve the schedulability we also propose an overloading strategy for PB-overloading and Backup-backup (BB) overloading. Our proposed task scheduling algorithm is compared with some existing scheduling algorithms in the literature through simulation studies. The results have shown that the task rejection ratio of our real-time task scheduling algorithm is almost 50% lower than the compared algorithms.