A Fault-tolerant Dynamic Task Scheduling Algorithm for Real-time Systems on Heterogeneous Multiprocessor

Abstract

Real-time Systems are being increasingly used in several applications which are time critical. Tasks corresponding to these applications have deadlines to be met. Fault-tolerance is an important requirement of such systems, due to the catastrophic consequences of not tolerating faults. In this paper, we propose density first with minimum non-overlap scheduling algorithm (DNA), which schedule real-time tasks dynamically with primary/backup (PB) scheme on heterogeneous multiprocessor. In DNA we define a heuristic function density to prioritize tasks. Besides, we also propose minimum non-overlap (MNO) mechanism for backup scheduling. According to our simulations, DNA can achieve higher guarantee ratio in any environment compared with related methods.