A Heterogeneous Fork-Join Queueing System in Which EachJob Occupy All Free Servers

Cover Page

Cite item

Full Text

Abstract

In this paper, we consider a multiserver queueing system with heterogeneous servers in whicheach job is split to be serviced into a number of tasks, one for each free server. The tasks areserviced independently, but service time depends on weight of the tasks. A job is considered tobe complete only when all the tasks associated with the job have been executed to completion.Applying a matrix-geometric approach, we obtain the exact expression for the stationarydistribution of the number of jobs in the system under exponential assumptions. Using thedistribution, we derive other important performance measures. Special attention is paid to thesojourn time in the queueing system (the time to complete a job). Finally, some numericalexamples and a section of conclusions commenting the main research contributions of thispaper are presented.The results can be used for the performance analysis of multiprocessor systems and othermodern distributed systems.

About the authors

O A Osipov

Saratov State University (SSU)

Author for correspondence.
Email: oleg.alex.osipov@gmail.com

Osipov O. A. - assistant of Department of System Analysis and Automatic Control of Saratov State University (SSU)

83 Astrahanskaya St., Saratov, 410012, Russian Federation

References

  1. R. Corrˆea, I. Dutra, M. Fiallos, F. Gomes (Eds.), Models for Parallel and Distributed Computation, Springer US, 2002. doi: 10.1007/978-1-4757-3609-0.
  2. Y. Narahari, P. Sundarrajan, Performability Analysis of Fork-join Queueing Systems, Journal of the Operational Research Society 46 (10) (1995) 1237–1249. doi: 10.1057/jors.1995.171.
  3. L. Flatto, S. Hahn, Two Parallel Queues Created by Arrivals with Two Demands I, SIAM Journal on Applied Mathematics 44 (5) (1984) 1041–1053. doi: 10.1137/0144074.
  4. R. Nelson, A. N. Tantawi, Approximate Analysis of Fork/Join Synchronization in Parallel Queues, IEEE Transactions on Computers 37 (6) (1988) 739–743. doi: 10.1109/12.2213.
  5. S.-S. Ko, R. F. Serfozo, Response Times in
  6. A. V. Gorbunova, I. S. Zaryadov, S. I. Matyushenko, K. E. Samouylov, S. Ya. Shorgin, The Approximation of Response Time of a Cloud Computing System, Informatics and applications 9 (2015) 32–38, in Russian. doi: 10.14357/19922264150304.
  7. M. S. Squillante, Y. Zhang, A. Sivasubramaniam, N. Gautam, Generalized Parallel- Server Fork-Join Queues with Dynamic Task Scheduling, Annals of Operations Research 160 (1) (2008) 227–255. doi: 10.1007/s10479-008-0312-7.
  8. S. V. Vyshenski, P. V. Grigoriev, Yu. Yu. Dubenskaya, Ideal Synchronizer for Marked Pairs in Fork-Join Network, Review of applied and industrial mathematics 15 (3) (2008) 385–399, in Russian.
  9. L. Green, A Queueing System in Which Customers Require a Random Number of Servers, Operations Research 28 (6) (1980) 1335–1346.
  10. A. Rumyantsev, E. Morozov, Stability Criterion of a Multiserver Model with Simultaneous Service, Annals of Operations Research 252 (1) (2015) 29–39. doi: 10.1007/s10479-015-1917-2.
  11. K. Omahen, L. Schrage, A Queueing Analysis of a Multiprocessor System with Shared Memory, in: Proceedings of the Symposium on Computer Communication Networks and Teletraffic, 1972, pp. 77–88.
  12. A. Kumar, R. Shorey, Performance Analysis and Scheduling of Stochastic Fork-Join Jobs in a Multicomputer System, IEEE Transactions on Parallel and Distributed Systems 10 (4) (1993) 1147–1164.
  13. T. Javidi, Cooperative and Non-Cooperative Resource Sharing in Networks: A Delay Perspective, IEEE Transactions on Automatic Control 53 (9) (2008) 2134–2142. doi: 10.1109/TAC.2008.930186.
  14. A. Thomasian, Analysis of Fork/Join and Related Queueing Systems, ACM Computing Surveys 47 (2) (2014) 17:1–17:71. doi: 10.1145/2628913.
  15. A. V. Gorbunova, I. S. Zaryadov, K. E. Samouylov, E. S. Sopin, A Survey on Queuing Systems with Parallel Serving of Customers, RUDN Journal of Mathematics, Information Sciences and Physics 25 (2017) 350–362, in Russian. doi: 10.22363/2312- 9735-2017-25-4-350-362.
  16. Q.-M. He, Fundamentals of Matrix-Analytic Methods, Springer, New York, 2014. doi: 10.1007/978-1-4614-7330-5.
  17. M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, The Johns Hopkins University Press, Baltimore, 1981.
  18. H. A. David, H. N. Nagaraja, Order Statistics, John Wiley & Sons, Inc., 2003. doi: 10.1002/0471722162.
  19. F. R. Gantmacher, The Theory of Matrices, Chelsea Publishing Company, 1959.
  20. P. Lancaster, M. Tismenetsky, The Theory of Matrices, 2d edition, Academic Press, 1985, in Russian.

Copyright (c) 2018 Osipov O.A.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies