A Backward Recovery Mechanism in Preemptive Utility Accrual Real Time Scheduling Algorithm

Abstract

Problem statement: This study proposed a robust algorithm named as Backward Recovery Preemptive Utility Accrual Scheduling (BRPUAS) algorithm that implements the Backward Recovery (BR) mechanism as a fault recovery solution under the existing utility accrual scheduling environment. The problem identified in the TUF/UA scheduling domain is that the existing algorithms only considers the Abortion Recovery (AR) as their fault recovery solution in which all faulty tasks are simply aborted to nullify the erroneous effect. The decision to immediately abort the affected tasks is inefficient because aborted tasks produce zero utility causes the system to accrue lower utility. Approach: The proposed BRPUAS algorithm enabled the re-execution of the affected tasks rather than abortion to reduce the number of aborted task in the existing algorithm known as Abortion Recovery Preemptive Utility Accrual Scheduling (ARPUAS) algorithm that employed the AR mechanism. The BRPUAS ensure the correctness of the executed tasks in the best effort basis in such a way that the infeasible tasks are aborted and produced zero utility, while the feasible tasks are re-executed to produce positive utility and consequently maximized the total accrued utility to the system. The performances of these algorithms are measured by using discrete event simulation. Results: The proposed BRPUAS algorithm achieved higher accrued utility compared to ARPUAS for the entire load range. Conclusion: Simulation results revealed that the BR mechanism is more efficient than the existing AR mechanism, producing higher accrued utility ratio and less abortion ratio making it more reliable and efficient for adaptive real time application domain.