IMLFQ Scheduling Algorithm with Combinational Fault Tolerant Method

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.

Authors:

• MohammadReza EffatParvar
• Akbar Bemana
• Mehdi EffatParvar

Keywords:

• IMLFQ
• Fault Tolerant
• Scheduling
• Queue
• Recurrent Neural Network.

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.