Abstract
We consider a queueing system with capacity 1 and subject to a Poisson arrival process. Jobs consists of a random number of tasks and at each arrival, the system will continue to work on the current job if the number of its tasks is higher or equal than the number of tasks of the job just arrived, otherwise the job in the queue leaves the system and the one just arrived begins its service. The service time of each task is independent and exponentially distributed with the same parameter.
We give an explicit solution for the stationary distribution of the queue by resorting to time-reversed analysis and we observe that this approach gives a much more elegant and constructive way to obtain the result than the traditional approach based on the verification of the system of global balance equations. For geometric distribution of the number of tasks, we use the q-algebra to make the results numerically tractable. The queueing system finds applications in contexts in which the size of jobs is known or partially known and schedulers or dispatchers can take decisions based on this information to improve the overall performance (e.g., reducing the mean response time).
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsReferences
The on-line encyclopedia of integer sequences. https://oeis.org/A008289. Accessed 30 Aug 2019
Aalto, S., Ayesta, U., Nyberg-Oksanen, E.: Two-level processor-sharing scheduling disciplines: mean delay analysis. ACM SIGMETRICS Perform. Eval. Rev. 32(1), 97–105 (2004). Proceedings of ACM Sigmetrics/Performance
Balsamo, S., Harrison, P., Marin, A.: A unifying approach to product-forms in networks with finite capacity constraints. ACM SIGMETRICS Perform. Eval. Review 38(1), 25–36 (2010). Proceedings of ACM Sigmetrics/Performance
Comtet, L.: Advanced Combinatorics, The Art of Finite and Infinite Expansion. D. Reidel Publishing Company, Dordrecht (1974)
Grosof, I., Scully, Z., Harchol-Balter, M.: SRPT for multiserver systems. Perform. Eval. 127–128, 154–175 (2018)
Harrison, P.: Turning back time in Markovian process algebra. Theor. Comput. Sci. 290(3), 1947–1986 (2003)
Harrison, P., Marin, A.: Product-forms in multi-way synchronizations. Comput. J. 57(11), 1693–1710 (2014)
Kelly, F.P.: Reversibility and Stochastic Networks. Wiley, Hoboken (1979)
Marin, A., Balsamo, S., Fourneau, J.M.: LB-networks: a model for dynamic load balancing in queueing networks. Perform. Eval. 115, 38–53 (2017)
Marin, A., Mitrani, I., Elahi, M., Williamson, C.: Control and optimization of the SRPT service policy by frequency scaling. In: McIver, A., Horvath, A. (eds.) QEST 2018. LNCS, vol. 11024, pp. 257–272. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99154-2_16
McIntosh, I.J.: Some asymptotic formulae for q-shifted factorials. Ramanujan J. 3, 205–214 (1999)
Pittel, B.G.: Closed exponential networks of queues with saturation: the Jackson-type stationary distribution and its asymptotic analysis. Math. Oper. Res. 4(4), 357–378 (1979)
Pradhan, S., Gupta, U.C.: Modeling and analysis of an infinite-buffer batch-arrival queue with batch-size-dependent service. Perform. Eval. 108, 16–31 (2017)
Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16, 678–690 (1968)
Schroeder, B., Harchol-Balter, M.: Web servers under overload: how scheduling can help. ACM Trans. Internet Technol. 6(1), 20–52 (2006)
Acknowledgements
We would like to thank prof. Michael Somos for his invaluable suggestions on the relations between the q-series considered in this paper and number theory.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Marin, A., Rossi, S. (2020). A Queueing Model that Works Only on the Biggest Jobs. In: Gribaudo, M., Iacono, M., Phung-Duc, T., Razumchik, R. (eds) Computer Performance Engineering. EPEW 2019. Lecture Notes in Computer Science(), vol 12039. Springer, Cham. https://doi.org/10.1007/978-3-030-44411-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-44411-2_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-44410-5
Online ISBN: 978-3-030-44411-2
eBook Packages: Computer ScienceComputer Science (R0)