A Comparative Study of Single-Queue Multiprocessor Scheduling (SQMS) and Multiple-Queue Multiprocessor Scheduling (MQMS) Based on Stochastic Modeling

Authors(2) :-Shweta Jain, Saurabh Jain

Multiprocessor systems have multiple processors which are basically challenging for managing resources and processor time. There is no system which can be completely deterministic whether the system has enough capacity to handle all requests and loads within the requisite time. Multiprocessor system scheduling are having two types of queue based scheduling: Single-Queue Multiprocessor Scheduling (SQMS) and Multiple Queue Multiprocessor Scheduling (MQMS). This paper analyzes both these multiprocessor scheduling schemes and their transition behaviour of processes over queues for balancing the load of a system. We have also applied stochastic modeling for simulation study and compared their performance.

Authors and Affiliations

Shweta Jain
Research Scholar, Faculty of Computer Science, Pacific Academy of Higher Education and Research University, Udaipur,Rajasthan, India
Saurabh Jain
Professor, Shri Vaishnav Institute of Computer Applications, Shri Vaishnav Vidyapeeth Vishwavidyalaya, Indore, Madhya Pradesh, India

Multiprocessor systems, MQMS, Markov Chain model, Process migration, SQMS, Scheduling, Stochastic process, Transition Probability Matrix, Affinity.

  1. Heidari H. and Chalechale A.: "Scheduling in Multiprocessor System using Genetic Algorithm", International Journal of Advanced Science and Technology, Vol. 43, June, 2012, pp 81-94. 
  2. Dhingra S., Gupta S.B. and Biswas R.: “Genetic Algorithm Parameters Optimization for Bi-Criteria Multiprocessor Task Scheduling using Design of Experiments”, International Journal of Computer, Information, Systems and Control Engineering, Vol. 8, No. 4, 2014, pp. 600-606.
  3. Kwong Y. and Ahmad I.: “Static Scheduling Algorithms for allocating directed task graphs to multiprocessors”, ACM Computing Surveys, Vol. 31, No. 4, December 1999, pp. 407-427.
  4. Arya S. and Dhingra S.: "Duplication Based Simulated Annealing Algorithm For Multiprocessor Task Scheduling: An Overview", International Journal of scientific Research, Vol. 4, Issue  9 ,Sept 2015, pp 325-327.
  5. Caprita B., Chan W. C., Nieh J., Stein C., and Zheng H.: "Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems", USENIX Association- USENIX Annual Technical Conference, 2005, pp 337-352.
  6. Gupta S., Rajak R., Singh G. K., and Jain S.: " Review of Task Duplication Based (TDB) Scheduling Algorithms", Smart Computing Review, Vol. 5, No. 1, January 2015, pp 67-75.
  7. Jain S. and Makkar S.: "Multiprocessor Environment using Genetic Algorithm", International Journal of Advanced Research in Computer Science and Software Engineering, Vol. 2, Issue 5, May 2012, pp 131-134.
  8. Pradhan S. R., Sharma S., Konar D. and Sharma K.: "A Comparative Study on Dynamic Scheduling of Real-Time Tasks in Multiprocessor System using Genetic Algorithms", International Journal of Computer Applications, Vol. 120, No.20, June 2015, pp 1-6.
  9. Edwin S.H and Ansari N.: “A Genetic Algorithm for Multiprocessor Scheduling”, IEEE Transaction on parallel and Distributed System, Vol. 5, No. 2, Feb. 1994.
  10. Ahmad I. and Ghafoor A.: “Semi-distributed load balancing for massively parallel multicomputer systems,” IEEE Transactions. on  Software. Engineering, Vol. 17, Issue 10, 1991, pp. 987–1004.
  11. Kaur R. and Kaur R.: “Multiprocessor Scheduling using Task Duplication Based Scheduling Algorithms: A Review Paper”, International Journal of Application or Innovation in Engineering and Management, Vol. 2, Issue 4, April. 2013, pp. 311-317.
  12. R. Rajak: “A Novel Approach for Task Scheduling in Multiprocessor System”, International Journal of Computer Application, Vol. 44, No. 11, April 2012, pp. 12-14.
  13. Halabian H., Lambadaris I. and Lung C. H.: "On the Stability Region of Multi-Queue Multi-Server Queueing Systems with Stationary Channel Distribution", Proceedings of IEEE International Symposium on Information Theory (ISIT’11), 31 July-5 Aug. 2011, pp 1801-1805.
  14. Halabian H., Lambadaris I. and Lung C. H.: "Optimal Server Assignment in Multi-Server Queuing Systems with Random Connectivities", IEEE International Conference on Communications (ICC 2012), 10-15 June 2012, pp. 1219-1224.
  15. Kittipiyakul S. and Javidi T.: “Delay-optimal server allocation in multi-queue multi-server systems with time-varying connectivities,” IEEE Transactions on Information Theory, Vol. 55, No. 5, pp. 2319–2333, May 2009.
  16. Shukla, D. and Jain, S.: "A Markov Chain Model for Multilevel Queue Scheduler in Operating System", Proceedings of International Conference on Mathematics and Computer Science, ICMCS-07, 2007, pp. 522-526.
  17. Shukla, D. and Jain, S.: "Deadlock State Study in Security Based Multilevel Queue Scheduling Scheme in Operating System", Proceedings of National Conference on Network Security and Management, NCNSM-07, 2007, pp. 166-175.
  18. Shukla, D., Jain, S., Singhai, R. and Agarwal, R. K.: "A Markov Chain Model for the Analysis of Round-Robin Scheduling Scheme", International Journal of Advanced Networking and Applications (IJANA), Vol. 1, Issue 1, 2009, pp. 1-7.
  19. Jain, S. and Jain, S.: "A Research Survey and Analysis for CPU Scheduling Algorithms using Probability-Based Study", International Journal of Engineering and Management Research, Vol. 6, Issue 5, December 2015, pp. 628-633.
  20. Jain, S. and Jain, S.: "Analysis of Multi Level Feedback Queue Scheduling Using Markov Chain Model with Data Model Approach", International Journal Advanced Networking and Applications(IJANA), Vol. 07 Issue 06, 2016, pp. 2915-2924.
  21. Jain, S. and Jain, S.: "Probability-Based Analysis to Determine the Performance of Multilevel Feedback Queue Scheduling", International Journal Advanced Networking and Applications(IJANA), Vol. 08 Issue 03, 2016, pp. 3044-3069.
  22. Jain, S. and Jain, S: "A Review Study on the CPU Scheduling Algorithms", International Journal of Advanced Research in Computer and Communication Engineering, Vol. 5, Issue 8, August 2016, pp. 22-31.
  23. Ross S. M.: "Stochastic Processes", 2nd ed. New York: J. Wiley and Sons, 1996.
  24. Silberschatz A., and Galvin P.: "Operating system concept", Ed.8, John Wiley and Sons, Asia, 2010.
  25. W. Stalling, "Operating systems", Ed.5, Pearson Eduaction, Singopore, Indian Edition, New Delhi,2004.
  26. A. Tanenbaum, and A.S. Woodhull, "Operating System", Ed. 8, Prentice Hall of India, NewDelhi, 2000.
  27. J. Medhi, "Stochastic processes", Ed. 4, Wiley Limited (Fourth Reprint), New Delhi, 1991.

Publication Details

Published in : Volume 2 | Issue 5 | September-October 2017
Date of Publication : 2017-10-31
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 361-369
Manuscript Number : CSEIT172531
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

Shweta Jain, Saurabh Jain, "A Comparative Study of Single-Queue Multiprocessor Scheduling (SQMS) and Multiple-Queue Multiprocessor Scheduling (MQMS) Based on Stochastic Modeling", International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 5, pp.361-369, September-October-2017.
Journal URL : http://ijsrcseit.com/CSEIT172531

Article Preview

Follow Us

Contact Us