IMLFQ Scheduling Algorithm with Combinational Fault Tolerant Method

Authors: MohammadReza EffatParvar, Akbar Bemana, Mehdi EffatParvar

Abstract:

Scheduling algorithms are used in operating systems to optimize the usage of processors. One of the most efficient algorithms for scheduling is Multi-Layer Feedback Queue (MLFQ) algorithm which uses several queues with different quanta. The most important weakness of this method is the inability to define the optimized the number of the queues and quantum of each queue. This weakness has been improved in IMLFQ scheduling algorithm. Number of the queues and quantum of each queue affect the response time directly. In this paper, we review the IMLFQ algorithm for solving these problems and minimizing the response time. In this algorithm Recurrent Neural Network has been utilized to find both the number of queues and the optimized quantum of each queue. Also in order to prevent any probable faults in processes' response time computation, a new fault tolerant approach has been presented. In this approach we use combinational software redundancy to prevent the any probable faults. The experimental results show that using the IMLFQ algorithm results in better response time in comparison with other scheduling algorithms also by using fault tolerant mechanism we improve IMLFQ performance.

Keywords: IMLFQ, Fault Tolerant, Scheduling, Queue, Recurrent Neural Network.

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

References:

[1] M. R. EffatParvar, M. EffatParvar, A. T. Haghoghat, R. Mahini, and M. Zarei, "An Intelligent MLFQ Scheduling Algorithm (IMLFQ)," Real-Time Computing Systems & Applications (RTCOMP), Jun 2006.
[2] K. U. Herath, and Sh. Hashimoto, "Automated trend diagnosis using neural networks," 0-7803-6583- IEEE, 1186-1191, 2000.
[3] C. Molter, U. Salihoglu, and H. Bersini, "Introduction of an hebbian unsupervised learning algorithm to boost the encoding capacity of Hopfield networks," Proceedings of the IJCNN, 2005.
[4] Ma. Sheng, and Ji. Chuanyi, "Fast Training of Recurrent Networks Based on the EM Algorithm. Transactions on Neural Networks," IEEE, Vol. 9, No.1, Jan 1998.
[5] N. K. Kasabov, Foundations of Neural Networks, Fuzzy Systems, and Knowledge Engineering, A Bradford Book The MIT Press Cambridge, Massachusetts London, England, 1996, Massachusetts Institute of Technology, 1998.
[6] F. A. Gers, and J. Schmidhuber, "LSTM recurrent networks learn simple context free and context sensitive languages," Transactions on Neural Networks, IEEE, 12(6):1333-1340, 2001.
[7] J. Guynes, "Impact of System Response Time on Stat Anxiety," Communications of the ACM, 1988.
[8] A. Memon, A. Porter, C. Yilmaz, A. Nagarajan, D. C. Schmidt, and B. Natarajan, "Skoll: Distributed Continuous Quality Assurance," Proc, Int-l Conf, Software Eng, (ICSE), pp. 459- 468, 2004.
[9] S. Ghosh, R. Melhem, and D. Mosse, "Fault-tolerance through scheduling of aperiodic tasks in hard real-time mul-tiprocessor systems," IEEE Trans, Parallel and Distributed Systems, vol.8, no.3, pp.272-183, Mar 1997.
[10] G. Manimaran, and C. Siva Ram Murthy, "A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis," IEEE Trans, Parallel and Distributed Systems, vol.9, no.11, Nov 1998.