Real-time scheduling under fault bursts with multiple recovery strategy

In this paper, we consider the feasibility problem of a set of real-time jobs which may be subject to a fault burst during execution. A fault burst represents a time interval during which multiple jobs may incur faults; hence multiple recoveries may be needed. We show that determining the feasibility of a real-time system, which may be subject to a fault burst that may last at most Δ time units, is an NP-Hard problem even when the exact position of the fault burst is known a priori. However, in a practical system, the fault burst may occur at any arbitrary and unpredictable time. We develop feasibility analysis by assuming multiple recovery strategy where, in addition to the job at the end of which the fault is detected, all preempted tasks are also re-executed. We formally characterize the overhead that a scheduler incurs due to a fault burst and present a generic recovery strategy, called Δ-idling, that is shown to minimize the worst-case overhead for any priority-driven scheduling algorithm. Next, we analyze periodic task systems. We show that the preemptive EDF policy, when coupled with Δ-idling, provides the highest possible utilization bound ½ (1 - Δ over P_min), where P_min is the smallest task period. We also present an empirical evaluation of the EDF policy with Δ-idling over synthetically generated task sets, and show that it offers a clear improvement over the naive EDF policy that triggers the recovery tasks as soon as an error is detected.