Abstract
Response times are arguably the most representative and important metric for measuring the performance of modern computer systems. Further, service level agreements (SLAs), ranging from data centres to smartphone users, demand quick and, equally important, predictable response times. Hence, it is necessary to calculate moments, at least, and ideally response time distributions, which is not straightforward. A new moment-generating algorithm for calculating response times analytically is obtained, based on M/M/1 processor sharing (PS) queueing models. This algorithm is compared against existing work on response times in M/M/1-PS queues and extended to M/M/1 discriminatory PS queues. Two real-world case studies are evaluated.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Response Time
- Service Level Agreement
- Response Time Distribution
- Sojourn Time Distribution
- General Lambda Distribution
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Curtis, J.: 10 top cloud computing providers for 2014. http://tinyurl.com/top-10-cloud-providers-2014
Velazco, C.: Google gives students unlimited cloud storage. http://www.engadget.com/2014/09/30/google-drive-for-education/
Huria, T., Ceraolo, M., Gazzarri, J., Jackey, R.: High fidelity electrical model with thermal dependence for characterization and simulation of high power lithium battery cells. In: Proc. IEEE IEVC, Greenville, pp. 1–8 (2012)
Coffman Jr., E.G., Muntz, R.R., Trotter, H.: Waiting Time Distributions for Processor-Sharing Systems. Journal ACM 17, 123–130 (1970)
Prabhu, B.J., Chockalingam, A., Sharma, V.: Performance analysis of battery power management schemes in wireless mobile devices. In: Proc. IEEE WCNC, Orlando, vol. 2, pp. 825–831 (2002)
Open Battery. http://www.doc.ic.ac.uk/~gljones/openbattery/index.php
Harrison, P.G., Patel, N.M.: Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley (1993)
Stewart, W.J.: Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Performance Modeling, p. 409. Princeton University Press (2009)
Kjaer, M.A., Kihl, M., Robertsson, A.: Response-time control of a processor-sharing system using virtualised server environments. In: Proc. IFAC, Korea, vol. 17, p. 3612–3618 (2008)
Rohner, C., Feeney, L.M., Gunningberg, P.: Evaluating battery models in wireless sensor networks. In: Tsaoussidis, V., Kassler, A.J., Koucheryavy, Y., Mellouk, A. (eds.) WWIC 2013. LNCS, vol. 7889, pp. 29–42. Springer, Heidelberg (2013)
Au-Yeung, S.W.M., Dingle, N.J., Knottenbelt, W.J.: Efficient approximation of response time densities and quantiles in stochastic models. In: Proc. ACM WOSP, Redwood Shores, vol. 4, pp. 151–155 (2004)
Shye, A., Scholbrock, B., Memik, G., Dinda, P.A.: Characterizing and Modeling User Activity on Smartphones, Technical Report, Northwest University (2010)
Rao, V., Singhal, G., Kumar, A., Navet, N.: Battery model for embedded systems. In: Proc. IEEE VLSID, Washington, DC, vol. 18, pp. 105–110 (2005)
Gao, P.X., Curtis, A.R., Wong, B., Keshav, S.: It’s not easy being green. In: Proc. ACM SIGCOMM, Helsinki, vol. 44, pp. 211–222 (2012)
Wray, J.: Where’s The Rub: Cloud Computing’s Hidden Costs. http://tinyurl.com/cloud-computing-hidden-costs
Alawnah, R.Y., Ahmad, I., Alrashed, E.A.: Green and Fair Workload Distribution in Geographically Distributed Data. Journal Green Eng. 4, 69–98 (2014)
Massoulie, L., Roberts, J.W.: Bandwidth sharing and admission control for elastic traffic. Telecomm. Systems 15, 185–201 (2000)
AISO.net. http://www.aiso.net/index.html
Ott, T.J.: The Sojourn-Time Distribution in the M/G/1 Queue with Processor Sharing. Journal of Applied Probability 21, 360–378 (1984)
Wierman, A.: Scheduling for Today’s Computer Systems: Bridging Theory and Practice, PhD Thesis, School of Computer Science, Carnegie Mellon University (2007)
Kim, J., Kim, B.: Sojourn time distribution in the M/M/1 queue with discriminatory processor-sharing. Performance Evaluation 58, 341–365 (2004)
Yashkov, S.F.: Processor-Sharing Queues: Some Progress In Analysis. Queueing Systems 2, 1–17 (1987)
Wierman, A., Harchol-Balter, M.: Classifying scheduling policies with respect to higher moments of conditional response time. In: Proc. ACM SIGMETRICS (2005)
Zwart, A.P., Boxma, O.J.: Sojourn time asymptotics in the M/G/1 processor sharing queue. Queueing Systems 35, 141–166 (2000)
Lakhany, A., Mausser, H.: Estimating the parameters of the General Lambda Distribution. Algo. Research Quarterly 3, 47–58 (2000)
Roberts, J.W.: A survey on statistical bandwidth sharing. Computer Networks 45, 319–332 (2004)
Lohr, S.: For Impatient Web Users, an Eye Blink Is Just Too Long to Wait. New York Times. http://tinyurl.com/eye-blink-too-long-to-wait
Jones, G.L., Harrison, P.G., Harder, U., Field, T.: Fluid queue models of battery life. In: Proc. IEEE MASCOTS, vol. 19, pp. 278–285 (2011)
Wierman, A., Andrew, L.L.H., Tang, A.: Power-aware speed scaling in processor sharing systems: Optimality and robustness. Performance Evaluation 69(12), 601–622 (2012)
Casale, G., Harrison, P.G.: AutoCAT: automated product-form solution of stochastic models. In: Matrix-Analytic Methods in Stochastic Models, vol. 27, pp. 57–85 (2013)
Queija, R.N.: Sojourn times in non-homogeneous QBD processes with processor sharing. Stochastic Models 17, 61–92 (2001)
Masuyama, H., Takine, T.: Sojourn time distribution in a MAP/M/1 processor-sharing queue. Op. Res. Letters 31, 406–412 (2003)
Bansal, N.: Analysis of the M/G/1 processor-sharing queue with bulk arrivals. Op. Res. Letters 31, 401–405 (2003)
Lebrecht, A.: Queueing network models of Zoned RAID system performance, PhD Thesis, Department of Computing, Imperial College London (2009)
Ramberg, J., Schmeiser, B.: An approximate method for generating asymmetrics random variables. Comm. ACM 17, 78–82 (1974)
Ward, A.R., Whitt, W.: Predicting reponse times in processor-sharing queues. In: Proc. of Fields Institute Conference on Communication Networks (2000)
Fayolle, G., Iasnogorodski, R., Mitrani, I.: Sharing a Processor Among Many Job Classes. Journal ACM 27(3), 519–532 (1980)
Kelly, F.: Stochastic Networks and Reversibility, vol. 1. Wiley (1979)
Embedded Microprocessor Benchmark Consortium (EEMBC). http://eembc.org/
Ramberg, J., Dudewicz, E., Tadikamalla, P., Mykytka, E.: A probability distribution and its uses in fitting data. Technometrics 21, 201–214 (1979)
AndEBench-Pro. http://eembc.org/andebench/index_pro.php
Freimer, M., Mudholkar, G., Kollia, G., Lin, C.: A study of the generalized Tukey Lambda family. Comm. in Statistics 17, 3547–3567 (1988)
Aalto, S., Ayesta, U., Borst, S., Misra, V., Nunez-Queija, R.: Beyond Processor Sharing. ACM SIGMETRICS Perform. Eval. Rev. 34, 36–43 (2007)
Kherani, A.A., Kumar, A.: On processor sharing as a model for TCP controlled HTTP-like transfers. In: Proc. IEEE ICC, Paris, vol. 4, pp. 2256–2260 (2004)
Dukkipati, N., Kobayashi, M., Zhang-Shen, R., McKeown, N.: Processor sharing flows in the internet. In: de Meer, H., Bhatti, N. (eds.) IWQoS 2005. LNCS, vol. 3552, pp. 271–285. Springer, Heidelberg (2005)
Harrison, P.G.: Response time distributions in queueing network models. In: Donatiello, L., Nelson, R. (eds.) SIGMETRICS 1993 and Performance 1993. LNCS, vol. 729, pp. 147–164. Springer, Heidelberg (1993)
Huilgol, M.: Xiaomi aims to sell 100 million smartphones in 2015. http://tinyurl.com/xiaomi-100-million-smartphones
Moore, M.: Huawei Looks To Shift 100 Million Smartphones in 2015. http://tinyurl.com/huawei-100-million-smartphones
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Chis, T., Harrison, P. (2015). Moment-Generating Algorithm for Response Time in Processor Sharing Queueing Systems. In: Beltrán, M., Knottenbelt, W., Bradley, J. (eds) Computer Performance Engineering. EPEW 2015. Lecture Notes in Computer Science(), vol 9272. Springer, Cham. https://doi.org/10.1007/978-3-319-23267-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-23267-6_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23266-9
Online ISBN: 978-3-319-23267-6
eBook Packages: Computer ScienceComputer Science (R0)