Simulation of Utility Accrual Scheduling and Recovery Algorithm in Multiprocessor Environment

Authors: A. Idawaty, O. Mohamed, A. Z. Zuriati

Abstract:

This paper presents the development of an event based Discrete Event Simulation (DES) for a recovery algorithm known Backward Recovery Global Preemptive Utility Accrual Scheduling (BR_GPUAS). This algorithm implements the Backward Recovery (BR) mechanism as a fault recovery solution under the existing Time/Utility Function/ Utility Accrual (TUF/UA) scheduling domain for multiprocessor environment. The BR mechanism attempts to take the faulty tasks back to its initial safe state and then proceeds to re-execute the affected section of the faulty tasks to enable recovery. Considering that faults may occur in the components of any system; a fault tolerance system that can nullify the erroneous effect is necessary to be developed. Current TUF/UA scheduling algorithm uses the abortion recovery mechanism and it simply aborts the erroneous task as their fault recovery solution. None of the existing algorithm in TUF/UA scheduling domain in multiprocessor scheduling environment have considered the transient fault and implement the BR mechanism as a fault recovery mechanism to nullify the erroneous effect and solve the recovery problem in this domain. The developed BR_GPUAS simulator has derived the set of parameter, events and performance metrics according to a detailed analysis of the base model. Simulation results revealed that BR_GPUAS algorithm can saved almost 20-30% of the accumulated utilities making it reliable and efficient for the real-time application in the multiprocessor scheduling environment.

Keywords: Time Utility Function/ Utility Accrual (TUF/UA) scheduling, Real-time system (RTS), Backward Recovery, Multiprocessor, Discrete Event Simulation (DES).

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1340314

References:

[1] S. Punnekat, A. Burns, and R. Davis, “Analysis of checkpointing for real time systems,” Real Time System, vol. 20, no. 1, pp. 83–102, 2001.
[2] P. Alvarez, “Scheduling fault recovery operations in real time systems,” Journal of Computer System, vol. 6, no. 1, pp. 51–61, 2002.
[3] P. Alvarez and D. Mosse, “A responsiveness for scheduling fault recovery in real time systems,” in Proc. 5th IEEE Real Time Technology and Application Symposium, Vancouver, 1999, pp. 4–13.
[4] R. Pathan, Scheduling Algorithms for Fault Tolerant Real Time Systems. PhD Thesis, Chalmers University of Technology, 2010.
[5] G.A. Lima, Fault Tolerance in Fixed Priority Hard Real Time Systems. PhD Thesis, University of York, 2003.
[6] B. Sahoo and A. Ekka, “Backward fault recovery in real time distributed systems of periodic tasks with timing and precedence constraint,” in Proc. of International Conference on Emerging Trends in High Performance Architecture, Algorithms and Computing (HiPAAC’07), Chennai, 2007, pp. 124–130.
[7] F. Zhang, and A. Burns, “Schedulability analysis for real time systems with EDF scheduling,” IEEE Trans on Computers, vol. 58, no. 9, pp. 1250–1258, 2009.
[8] H. Aydin, R. Mosse, and P. Alvarez, “Optimal reward-based scheduling for periodic real time tasks,” IEEE Journal of Computer, vol. 50, no. 2, pp. 111–130, 2001.
[9] S. Punnekat, Schedulability Analysis for Fault Tolerant Real Time Systems. PhD Thesis, University of York, 1997.
[10] K. Han, B. Ravindran, and E. Jensen, “RTG-L: Dependably scheduling real time distributed threads in large scale, unreliable networks,” in Proc. 13th IEEE Pacific Rim International Symposium on Dependable Computing (PDRC’07), Melbourne, 2007, pp. 314–321.
[11] H. Cho, B. Ravindran, and E. Jensen, “Garbage collector scheduling in dynamic, multiprocessor real time system,” IEEE Transactions on Parallel and Distributed System, vol. 20, no. 6, pp. 845–856, 2009.
[12] S. Fahmy, B. Ravindran, and E. Jensen, “On collaborative scheduling of distributable real time threads in dynamic, networked embedded systems,” in Proc. 11th IEEE Symposium on Object Oriented Real Time Distributed Computing(ISORC’08), Orlando, 2008, pp. 485–491.
[13] B. Ravindran, B. Anderson and E. Jensen, “On distributed real-time scheduling in networked embedded systems in the presence of crash failures,” in Lecture Notes in Computer Science, 4761/2007, Springer Berlin/Heidelberg, 2007, pp. 67–81.
[14] E. Curley, Recovering From Distributable Thread Failures with Assured Timeliness in Real Time Distributed System. Master Thesis, Virginia Polytechnic Institute and State University, 2007.
[15] E. Jensen, E. Locke, and H. Tokuda, “A time driven scheduling model for real time system,” in Proc. 6th IEEE Real Time Symposium, San Diego, California, 1985, pp. 112–212.
[16] P. Li, Utility Accrual Real Time Scheduling: Models and Algorithms. PhD Thesis, Virginia Polytechnic Institute and State University, 2004.
[17] A. Idawaty, O. Mohamed, and A.Z. Zuriati, “Enhanced preemptive global utility accrual real time scheduling algorithms in multicore environment,” Journal of Computer Sciences, vol. 11, no. 12, pp. 1009–1107, 2015.
[18] J. Banks, J. Carson, B. Nelson, and D. Nicol, Discrete Event System Simulation. 3rd edition, Prentice Hall, 2000.
[19] A. Idawaty, S. Shamala, O. Mohamed, and A.Z. Zuriati, “A Discrete Event Simulation Framework for Utility Accrual Scheduling Algorithm in Uniprocessor Environment,” Journal of Computer Sciences, vol. 7, no. 8, pp. 1133–1140, 2011.