Data Model Approach And Markov Chain Based Analysis Of Multi-Level Queue Scheduling
|Published in:||Issue 2, (Vol. 4) / 2010|
|Author(s):||SHUKLA Diwakar, OJHA Shweta, JAIN Saurabh|
|Abstract.||There are many CPU scheduling algorithms in literature like FIFO, Round Robin, Shortest-Job-First and so on. The Multilevel-Queue-Scheduling is superior to these due to its better management of a variety of processes. In this paper, a Markov chain model is used for a general setup of Multilevelqueue-scheduling and the scheduler is assumed to perform random movement on queue over the quantum of time. Performance of scheduling is examined through a row dependent data model. It is found that with increasing value of α and d, the chance of system going over the waiting state reduces. At some of the interesting combinations of α and d, it diminishes to zero, thereby, provides us some clue regarding better choice of queues over others for high priority jobs. It is found that if queue priorities are added in the scheduling intelligently then better performance could be obtained. Data model helps choosing appropriate preferences.|
|Keywords:||Process Scheduling, Markov Chain Model, Mathematical Model, State Of The System, Rest State, Process Queue, Multilevel Queue Scheduling, Transition Probability Matrix, Central Processing Unit (CPU), Row Dependent Data Model.|
1. Cobb, J. Gouda, M. and EL-Nahas, A. (June, 1998): Time-Shift Fair Scheduling of Flaros in High-Speed Networks, IEEE/ACM Transactions of Networking, pp. 274-285
2. David B. Goub, (1994): Operating System Support for Coexistence of Real-Time and Conventional Scheduling, Carneqie Mellon University, PiHsburg W. PA.
3. Sun, Weiwei, Shi, Weibin, Shi, Bole and Yu, Yijun (2003). A cost-efficient scheduling algorithm of ondemand broadcasts. Wireless Networks, 9(3), pp. 239– 247.
4. Goyal, P. Guo., X. and Vin, H.M.(Oct., 1996): A Hierarchical CPU Scheduler for Multimedia Operating Systems, In Proceedings of the Second Symposium on Operating Systems Design and Implementation (OSDI’ 90), Secattle, WA, pp. 107-122.
5. Cong Chen; Yang Yu; Jinfan Lei; Youming Lin; Wenpeng Li: Research on Scheduling Algorithm for Workflow-Based Grid Resource, In proceedings of the Grid and Pervasive Computing Workshops, 2008. GPC Workshops apos;08. The 3rd International Conference on Volume , Issue , 25-28 May 2008 Page(s):37 – 42
6. Hieh, J. and Lam, M.S.(May, 2003): A SMART Scheduler for Multimedia Application, ACM Transactions on Computer System (TOCS), 21(2), pp. 117-163.
7. Jain, Saurabh(2008):Probability Based Model For CPU Scheduling,an unpublished thesis submitted to Dr H.S.Gour Central University, Sagar, M.P.
8. Lei Yingchun, Zhang Song, Li Guojie(Mar. 2003): Analyzing the relationship between scheduling algorithm and the performance of Web cluster servers, Journal of Computer Research and Development, 40(3): 483-492.
9. Jonathan A. Winter and David H. Albonesi (2008):The Scalability of Scheduling Algorithms for Unpredictably Heterogeneous CMP Architectures, Computer Systems Laboratory, Cornell University.
10. D. Liu, X. Sharon Hu, M. Lemmon and Q. Ling (2005) Scheduling Tasks with Markov-Chain Based constraints, in the proceedings of 17th Euromicro Conference on Real-Time Systems (ECRTS2005).
11. Naldi, M. (2002): Internet access traffic sharing in a multi-user environment, Computer Networks, Vol. 38, pp. 809-824.
12. Silberschatz, A., Galvin, P. (1999): Operating system concept, Ed.5, John Wiley and Sons (Asia), Inc.
13. Shukla, D., Gadewar, Surendra. Pathak, R.K. (2007): A Stochastic model for space-division switches in computer networks, Applied Mathematics and Computation (Elsevier Journal), Vol. 184, Issue 2, pp. 235-269.
14. Shukla, D. and Jain, Saurabh. (2007): A Markov chain model for multi-level queue scheduler in operating system, Proceedings of the International Conference on Mathematics and Computer Science, ICMCS-07, pp. 522-526.
15. Tanenbaum, A.S. and Woodhull, A.S. (2000): Operating System: Design and Implementation, Ed. 8, Prentice Hall of India Private Limited, New Delhi.
|Back to the journal content|
This article is licensed under a
Creative Commons Attribution-ShareAlike 4.0 International License.