A Novel Slack-Stealing Scheduling Algorithm for Hard-Real-Time Multiple-Processors System

When a permanent fault occurs in real-time system with multiple-processors, the slack distribution for different instances of the same task is unfair. The task instance under fault-occurred period (called urgent instance) is usually more urgent than its subsequent ones (called normal instance). In order to resolve the problem, the paper presents a novel slack-stealing strategy (referred to as NSS), which delays the execution of normal instance as late as possible. NSS strategy can reserve the slack time for the urgent instance with low priority potentially, thus it has more chance to complete its execution in time. Moreover, we present the corresponding schedulability test and accurate computation of delaying time based on NSS strategy. Extensive simulations reveal that NSS can achieve a remarkable saving on the number of processors required with respect to several well-known fault-tolerant scheduling algorithms.