This paper introduces an integrated framework for the scheduling of non-deterministic workloads, demanded on time-critical recovery operations triggered by the detection of errors in a real-time system. The framework will be developed within the context of fixed- priority preemptive systems. A dynamic analysis for recovery workloads is introduced by developing a criterion for responsiveness of fault recovery operations. This is motivated by the need to verify the timing correctness of real-time workloads under transient recovery workloads and provide graceful degradation to the real-time workload during recovery.We hypothesize that a scheduler suited to this environment should dispatch tasks using only response time and slack as an admission control mechanism for recovery requests, as long as all deadlines can be met, and that in the presence of transient recovery overloads, the best the scheduler can do is criticality-driven load shedding. By temporarily eliminating less important tasks, the responsive algorithm developed in this paper is expected to service the more important tasks without harming less critical tasks unnecessarily. The performance of the responsive algorithm is measured quantitatively with simulations using synthetic task sets.