The equivalence between processor sharing and service in random order. (English) Zbl 1041.90009
Summary: We explore a useful equivalence relation for the delay distribution in the \(G/M/1\) queue under two different service disciplines: (i) processor sharing (PS); and (ii) random order of service (ROS). We provide a direct probabilistic argument to show that the sojourn time under PS is equal (in distribution) to the waiting time under ROS of a customer arriving to a non-empty system. We thus conclude that the sojourn time distribution for PS is related to the waiting-time distribution for ROS through a simple multiplicative factor, which corresponds to the probability of a non-empty system at an arrival instant. We verify that previously derived expressions for the sojourn time distribution in the \(M/M/1\) PS queue and the waiting-time distribution in the \(M/M/1\) ROS queue are indeed identical, up to a multiplicative constant. The probabilistic nature of the argument enables us to extend the equivalence result to more general models, such as the \(M/M/1/K\) queue and \(\cdot/M/1\) nodes in product-form networks.
MSC:
| 90B22 | Queues and service in operations research |
| 60K25 | Queueing theory (aspects of probability theory) |
References:
| [1] | Barbour, A. D., Networks of queues and the method of stages, Adv. Appl. Probab., 8, 584-591 (1976) · Zbl 0342.60065 |
| [2] | Baskett, F.; Chandy, K. M.; Muntz, R. R.; Palacios, F. G., Open, closed, and mixed networks of queues with different classes of customers, J. ACM, 22, 248-260 (1975) · Zbl 0313.68055 |
| [3] | Boxma, O. J.; Denteneer, D.; Resing, J. A.C., Some models for contention resolution in cable networks, (Gregori, E.; etal., Networking 2002. Networking 2002, Lecture Notes in Computer Science, Vol. 2345 (2002), Springer: Springer Berlin), 117-128 · Zbl 1046.68686 |
| [4] | Coffman, E. G.; Muntz, R. R.; Trotter, H., Waiting time distribution for processor-sharing systems, J. ACM, 17, 123-130 (1970) · Zbl 0197.15304 |
| [5] | Cohen, J. W., The multiple phase service network with generalised processor sharing, Acta Inform., 12, 245-284 (1979) · Zbl 0396.68038 |
| [6] | Cohen, J. W., The Single Server Queue (1982), North-Holland: North-Holland Amsterdam · Zbl 0481.60003 |
| [7] | Cohen, J. W., On processor sharing and random service (Letter to the editor), J. Appl. Probab., 21, 937-937 (1984) · Zbl 0562.60097 |
| [8] | Flatto, L., The waiting time distribution for the random order service M/M/1 queue, Ann. Appl. Probab., 7, 382-409 (1997) · Zbl 0883.60086 |
| [9] | Jagerman, D. L.; Sengupta, B., The GI/M/1 processor-sharing queue and its heavy traffic analysis, Comm. Statist. Stochastic Models, 7, 379-395 (1991) · Zbl 0736.60092 |
| [10] | Kelly, F. P., Reversibility and Stochastic Networks (1979), Wiley: Wiley Chichester · Zbl 0422.60001 |
| [11] | Kendall, D. G., Stochastic processes occurring in the theory of queues and their analysis by the method of the embedded Markov chain, Ann. Math. Statist., 24, 338-354 (1953) · Zbl 0051.10505 |
| [12] | Kleinrock, L., Analysis of a time-shared processor, Naval Res. Logist. Quart., 11, 59-73 (1964) · Zbl 0129.30902 |
| [13] | Kleinrock, L., Time-shared systemsa theoretical treatment, J. ACM, 14, 242-261 (1967) · Zbl 0173.20001 |
| [14] | L. Massoulié, J.W. Roberts, Bandwidth sharing: objectives and algorithms, in: Proceedings of the IEEE INFOCOM ’99, 1999, pp. 1395-1403.; L. Massoulié, J.W. Roberts, Bandwidth sharing: objectives and algorithms, in: Proceedings of the IEEE INFOCOM ’99, 1999, pp. 1395-1403. |
| [15] | Mitra, D., Waiting time distributions from closed queueing network models of shared-processor systems, (Kylstra, F. J., Proceedings of Performance ’81 (1981), North-Holland: North-Holland Amsterdam), 113-131 |
| [16] | Mitra, D.; Morrison, J. A., Asymptotic expansions of moments of the waiting time in closed and open processor-sharing systems with multiple job classes, Adv. Appl. Probab., 15, 813-839 (1983) · Zbl 0526.60085 |
| [17] | Morrison, J. A., Response-time distribution for a processor-sharing system, SIAM J. Appl. Math., 45, 152-167 (1985) · Zbl 0558.68031 |
| [18] | Morrison, J. A.; Mitra, D., Heavy-usage asymptotic expansions for the waiting time in closed processor-sharing systems with multiple classes, Adv. Appl. Probab., 17, 163-185 (1985) · Zbl 0556.60038 |
| [19] | R. Núñez Queija, Processor-sharing models for integrated-services networks, Ph.D. Thesis, Eindhoven University of Technology, 2000, ISBN 90-646-4667-8 (http://www.cwi.nl/ sindo; R. Núñez Queija, Processor-sharing models for integrated-services networks, Ph.D. Thesis, Eindhoven University of Technology, 2000, ISBN 90-646-4667-8 (http://www.cwi.nl/ sindo · Zbl 0953.68016 |
| [20] | Núñez Queija, R., Note on the GI/GI/1 queue with LCFS-PR observed at arbitrary times, Probab. Eng. Inf. Sci., 15, 179-187 (2001) · Zbl 0982.60093 |
| [21] | Ott, T. J., The sojourn time distributions in the M/G/1 queue with processor sharing, J. Appl. Probab., 21, 360-378 (1984) · Zbl 0544.60087 |
| [22] | Ramaswami, V., The sojourn time in the GI/M/1 queue with processor sharing, J. Appl. Probab., 21, 437-442 (1984) · Zbl 0543.60093 |
| [23] | M. Sakata, S. Noguchi, J. Oizumi, Analysis of a processor-shared queueing model for time-sharing systems, in: Proceedings of the Second Hawaii International Conference on System Sciences, 1969, pp. 625-628.; M. Sakata, S. Noguchi, J. Oizumi, Analysis of a processor-shared queueing model for time-sharing systems, in: Proceedings of the Second Hawaii International Conference on System Sciences, 1969, pp. 625-628. |
| [24] | Sakata, M.; Noguchi, S.; Oizumi, J., An analysis of the M/G/1 queue under round-robin scheduling, Oper. Res., 19, 371-385 (1971) · Zbl 0247.60061 |
| [25] | Sengupta, B.; Jagerman, D. L., A conditional response time of the M/M/1 processor-sharing queue, AT&T Tech. J., 64, 409-421 (1985) · Zbl 0587.68036 |
| [26] | Sevcik, K. C.; Mitrani, I., The distribution of queuing network states at input and output instants, J. ACM, 28, 358-371 (1981) · Zbl 0456.68035 |
| [27] | Yashkov, S. F., Processor-sharing queuessome progress in analysis, Queueing Systems, 2, 1-17 (1987) · Zbl 0648.68050 |
| [28] | Yashkov, S. F., Mathematical problems in the theory of processor-sharing queueing systems, J. Soviet Math., 58, 101-147 (1992) · Zbl 0735.68010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
