Paper title:

Prediction of Ready Queue Processing Time in Multiprocessor Environment Using Lottery Scheduling (ULS)

Published in: Issue 2, (Vol. 5) / 2011
Publishing date: 2011-10-28
Pages: 58-63
Author(s): SHUKLA Diwakar, JAIN Anjali, CHOUDHARY Amita
Abstract. While in multi-user environment, CPU has to manage lot of requests generated over the same time. Waiting queue of processes generates a problem of scheduling for processors. Designers and hardware architects have suggested system of multiprocessors to overcome the queue length. Lottery scheduling is one such method where processes in waiting queue are selected through a chance manner. This opens a way to use probability models to get estimates of system parameters. This paper is an application where the processing time of jobs in ready queue is predicted using the sampling method under the k-processors environment (k>1). The random selection of one process by each of k processors through without replacement method is a sample data set which helps in the prediction of possible ready queue processing time. Some theorems are established and proved to get desired results in terms of confidence intervals.
Keywords: Scheduling, Lottery Scheduling, Bias, Variance, Confidence Interval Lottery Scheduling (ULS), Estimator, Sampling

1. Carl A. Waldspurger William E. Weihl: Lottery Scheduling a flexible proportional-share resource management, Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI),pp.1-11, 1994.

2. Cochran, W.G: Sampling Technique, Wiley Eastern Publication, New Delhi 2005.

3. David Petrou, Garth A. Gibson, and John W. Milford: Implementing Lottery Scheduling: Matching the specializations in Traditional Schedulers, Proceedings of the USENIX Annual Technical Conference USA, pp.66-80, 1999.

4. Raz, D., B. Itzahak, H. Levy: Classes, Priorities and Fairness in Queuing Systems, Research report, Rutgers University, 2004.

5. Shukla, D. and Jain, Saurabh. : A Markov chain model for multilevel queue scheduler in operating system, Proceedings of International Conference on Mathematics and Computer Science, ICMCS-07, pp. 522-526, 2007.

6. Shukla, D. and Jain, Saurabh: Deadlock state study in security based multilevel queue scheduling scheme in operating system, Proceedings of National Conference on Network Security and Management, NCNSM-07, pp. 166-175, 2007.

7. Shukla,D.and Jain, Anjali, Choduary Amita: Estimation of ready queue processing time under SL scheduling scheme in multiprocessor environment, International Journal of Computer Science and Secucity (IJCSS),4(1) pp. 74-81, 2010.

8. Shukla,D.and Jain, Anjali, Choduary Amita: Estimation of ready queue processing time under Usual Group Lottery Scheduling(GLS) in Multiprocessor Environment, International Journal of Computer and Applications(IJCA),Vol 8 no. 14 pp. 39-45, 2010.

9. Silberschatz, A. and Galvin, P.: Operating System Concepts, Ed.5, John Wiley and Sons (Asia), Inc. 1999.

10. Singh, Daroga and Choudhary F.S.: Theory and Analysis of Sample Survey and Designs, Wiley Eastern Limited, New Delhi, 1986.

11. Stalling, W.: Operating System, Ed.5, Pearson Education, Singapore, Indian Edition, New Delhi, 2004.

12. Tanenbaum, A.: Operating system, Ed. 8, Prentice Hall of India, New Delhi, 2000.

Back to the journal content
Creative Commons License
This article is licensed under a
Creative Commons Attribution-ShareAlike 4.0 International License.
Home | Editorial Board | Author info | Archive | Contact
Copyright JACSM 2007-2023