A new fault-tolerant technique for improving schedulability in multiprocessor real-time systems

In real-time systems, tasks have deadlines to be met despite the presence of faults. Primary-Backup (PB) scheme is one of the most common schemes that has been employed for fault-tolerant scheduling of real-time tasks, wherein each task has two versions and the versions are scheduled on two different processors with time exclusion. There have been techniques proposed for improving schedulability of the PB-based scheduling. One of the more popular ones include Backup-Backup (BB) overloading, wherein two or more backups can share/overlap in time on a processor. In this paper we propose a new schedulability enhancing technique, called primary-backup (PB) overloading, in which the primary of a task can share/overlap in time with the backup of another task an a processor. The intuition is that, for both primary and backup of a task, the PB-overloading can assign an earlier start time than that of the BB-overloading, thereby increasing the schedulability. We conduct schedulability and reliability analysis of PB- and BB-overloading techniques through simulation and analytical studies. Our studies show that PB-overloading offers better schedulability (25% increase in the guarantee ratio) than that of BB-overloading, and offers reliability comparable to that of BB-overloading. The proposed PB-overloading is a general technique that can be employed in any static or dynamic fault-tolerant scheduling algorithm.