×

Mathematical problems in the theory of processor-sharing queueing systems. (English. Russian original) Zbl 0735.68010

J. Sov. Math. 58, No. 2, 101-147 (1992); translation from Itogi Nauki Tekh., Ser. Teor. Veroyatn., Mat. Stat., Teor. Kibern. 29, 3-82 (1990).
This paper reviews problems and models of processor-shared queueing systems and their applications in computer networks. It concentrates on obtaining exact results to the main steady-state performance measures, such as mean sojourn times, average queue-lengths, etc. Some basic methods of investigation are also discussed with special attention to systems with Poisson-arrivals. Some heavy-traffic approximations, and different limit theorems are also treated.
Reviewer: J. Sytrik

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V. V. Anisimov, Random Processes with Discrete Components. Limit Theorems [in Russian], Vishcha Shkola, Kiev (1988). · Zbl 0686.60092
[2] G. P. Basharin and A. L. Tolmachev, ?The theory of queuing networks and applications to analysis of information processing systems,? Itogi Nauki Tekh., Mat. Stat., Teor. Kibernet.,21, 3?119 (1983). · Zbl 0562.60098
[3] Yu. K. Belyaev, B. V. Gnedenko, and I. A. Ushakov, ?Mathematical problems in queuing and reliability theory,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 6, 3?12 (1983).
[4] Yu. K. Belyaev and N. V. Chistyakova, ?Nonparametric estimates for service requirements in shared-processor systems,? in: Probabilistic Processes and Their Applications [in Russian], MIÉM, Moscow (1987), pp. 12?17.
[5] A. A. Borovkov, Asymptotic Methods in Queuing Theory [in Russian], Nauka, Moscow (1980). · Zbl 0479.60006
[6] V. A. Vatutin and A. M. Zubkov, ?Branching Processes. I,? Itogi Nauki Tekh., Teor. Veroyatn., Mat. Stat., Teor. Kibernet.,23, 3?67 (1985). · Zbl 0608.60076
[7] B. V. Gnedenko, É, A. Danielyan, B. N. Dimitrov, G. P. Klimov, and V. F. Matveev, Prioritized Queuing Systems [in Russian], Mosk. Gos. Univ., Moscow (1973).
[8] B. V. Gnedenko and I. N. Kovalenko, Introduction to Queuing Theory. Second ed. [in Russian], Nauka, Moscow (1987). · Zbl 0186.24502
[9] S. A. Grishechkin, ?Single-line shared-processor systems and branching processes,? Mat. Zametki,44, No. 4, 433?448 (1988). · Zbl 0715.60121
[10] N. K. Jaiswal, Priority Queues, Academic Press, New York (1968).
[11] M. Ts. Dimitrov, ?Single-line bulk-servicing system with group service in the shared-processor mode,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 4, 102?105 (1979).
[12] M. Ts. Dimitrov, ?Single-line M |M| 1 systems with generalized dynamic priorities,? Serdika. B’lg. Mat. Spisanie,6, No. 2, 143?152 (1980).
[13] M. Ts. Dimitrov, ?Bulk servicing systems with Markov arrivals and shared processors,? Pliska. B’lg. Mat. Stud., No. 7, 68?74 (1984).
[14] R. L. Dobrushin, M. Ya. Kel’bert, A. N. Rybko, and Yu. M. Sukhov, ?Qualitative methods for queuing networks,? Akad. Nauk SSSR, IPPI Preprint, Moscow (1986).
[15] A. A. Zamyatin and A. D. Solov’ev, ?Asymptotic behavior of the service process in single-line systems with critical loading,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 4, 115?119 (1981).
[16] V. A. Ivnitskii, ?Queuing networks and their application to computers,? Zarub. Radioélektr., No. 7, 33?70 (1977).
[17] G. I. Ivchenko, V. A. Kashtanov, and I. N. Kovalenko, Queuing Theory [in Russian], Vyssh. Shk., Moscow (1982).
[18] V. V. Kalashnikov and S. T. Rachev, Mathematical Methods for Construction of Stochastic Service Models [in Russian], Nauka, Moscow (1988). · Zbl 0714.60083
[19] F. I. Karpelevich and A. Yu. Kreinin, ?Two-phase GI |G| ? G? |1| ? systems under heavy load,? Teor. Veroyatn. Ee. Primen.,26, No. 2, 302?320 (1981).
[20] M. Ya. Kel’bert and Yu. M. Sukhov, ?Mathematical Problems in the Theory of Queuing Networks,? Itogi Nauki Tekh., Teor. Veroyatn., Mat. Stat., Teor. Kibernet.,26, 3?96 (1988).
[21] D. König, V. V. Rykov, and F. Shmidt, ?Stationary queueing systems with dependencies,? Itogi Nauki Tekh., Teor. Veroyatn., Mat. Stat, Teor. Kibernet.,18, 95?186 (1981).
[22] M. Yu. Kitaev and S. F. Yashkov, ?Distribution of the conditional sojourn time of requests in shared-processor systems,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 4, 211?215 (1978).
[23] M. Yu. Kitaev and S. F. Yashkov, ?Analysis of single-line shared-processor systems,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 6, 64?71 (1979).
[24] L. Kleinrock, Queueing Theory. Vol. 1. Theory, Wiley, New York (1975).
[25] L. Kleinrock, Queueing Theory. Vol. 2. Computer Applications, Wiley, New York (1975).
[26] G. P. Klimov, ?Time-sharing systems. I,? Teor. Veroyatn. Ee. Primen.,19, No. 3, 558?576 (1974). · Zbl 0378.60102
[27] G. P. Klimov, ?Time-sharing systems. II,? Teor. Veroyatn. Ee. Primen.,23, No. 2, 331?339 (1978). · Zbl 0388.60096
[28] G. P. Klimov, A. K. Lyakhu, and V. F. Matveev, Mathematical Models of Time-Shared Systems [in Russian], Shtiintsa, Kishinev (1983). · Zbl 0564.68027
[29] I. N. Kovalenko, N. Yu. Kuznetsov, and V. M. Shurenkov, Handbook of Random Processes [in Russian], Naukova Dumka, Kiev (1983). · Zbl 0525.60002
[30] V. S. Korolyuk, N. I. Portenko, A. V. Skorokhod, and A. F. Turbin, Handbook of Probability and Statistics. Second ed. [in Russian], Nauka, Moscow (1985). · Zbl 0608.60001
[31] A. I. Kostogryzov, ?Packet processing with EPS and interrupts,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 4, 88?93 (1987).
[32] A. I. Kostogryzov and L. V. Nazarov, ?Packet processing in systems with relative priorities,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 3, 194?198 (1981).
[33] J. Cohen and O. Boxma, Boundary-Value Problems in Queuing Theory, North Holland, Amsterdam (1983). · Zbl 0515.60092
[34] V. V. Lupaev and S. F. Yashkov, Efficient Computation in Automatic Control Systems [in Russian], Statistika, Moscow (1975).
[35] S. A. Maiorov, G. I. Novikov, T. I. Aliev, É. I. Makharev, and B. D. Timchenko, Fundamentals of Computer System Theory, Vyssh. Shk., Moscow (1978).
[36] V. A. Malyshev, ?Weiner-Hopf equations and their applications in probability theory,? Itogi Nauki Tekh., Teor. Veroyatn., Mat. Stat., Teor. Kibernet.,13, 5?35 (1976). · Zbl 0451.60047
[37] V. F. Matveev and V. G. Ushakov, Queueing Systems [in Russian], Mosk. Gos. Univ., Moscow (1984). · Zbl 0549.60087
[38] G. A. Medvedev and V. V. Matushevskii, ?Comparative analysis of time-sharing policies and productivity at switching nodes,? Avtomatika Vychisl. Tekh., No. 1, 52?53 (1989).
[39] V. A. Nagonenko and A. V. Pechinkin, ?Heavy loading in FBPS shared-processor systems,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 6, 62?67 (1980). · Zbl 0481.60096
[40] V. I. Neiman, ?Computer communications networks,? Itogi Nauki Tekh., Élektrosvyaz’,9, 5?119 (1978).
[41] A. V. Pechinkin, ?Stationary probabilities in FBPS shared-processor systems,? Izv. Akad. Nauk. SSSR, Tekh. Kibernet., No. 5, 73?77 (1980).
[42] A. V. Pechinkin and A. G. Tatashev, ?Generalized FBPS policies,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 4, 120?125 (1981).
[43] N. Prabhu, Stochastic Storage Processes, Springer, New York (1980). · Zbl 0453.60094
[44] B. A. Sevast’yanov, Branching Processes [in Russian], Nauka, Moscow (1971).
[45] D. S. Sil’vestrov, Semi-Markov Processes with Discrete State Sets. Principles of Computation of Functional and Reliability Characteristics of Stochastic Systems [in Russian], Sov. Radio, Moscow (1980).
[46] A. D. Solov’ev, ?Analysis of M |G|1| ? systems with various scheduling policies,? in: Queuing Theory. Proc. All-Union School-Seminar [in Russian], Moscow (1981), pp. 172?178.
[47] D. Ferrari, Computer Systems Performance Evaluation, Prentice-Hall, Englewood Cliffs (1978).
[48] P. Franken, D. Kënig, U. Arndt, and F. Shmidt, Queues and Point Processes, Wiley, New York (1982).
[49] D. Tsikritzis and F. Bernstein, Operating Systems [Russian translation], Mir, Moscow (1977).
[50] K. Chun and R. Williams, Introduction to Stochastic Integration [Russian translation], Mir, Moscow (1987).
[51] D. Shtoiyan, Qualitative Properties and Bounds for Stochastic Models [Russian translation], Mir, Moscow (1979).
[52] S. F. Yashkov, ?Distribution of conditional waiting time in time-shared systems,? Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 5, 88?94 (1977).
[53] S. F. Yashkov, ?Shared-processor systems,? in: Structural Adaptation of Multiprocessor Information Processing Systems [in Russian], Zinatne, Riga (1978), pp. 25?29.
[54] S. F. Yashkov, ?FBPS processor sharing for requests with minimum service requirements,? Tekh. Sredsv Svyazi, Ser. ASU, No. 2, 51?62 (1978).
[55] S. F. Yashkov, ?Invariance properties of probabilistic models of dispatching in multiprogramming systems,? Avtomat. Vychisl. Tekh, No. 6, 56?62 (1980). · Zbl 0479.68046
[56] S. F. Yashkov, ?Results of analysis of probabilistic models of teleprocessing systems,? Avtomat. Vychisl. Tekh., No. 4, 3?11 (1981).
[57] S. F. Yashkov, ?Ergodicity of systems with variable service rates,? Izv. Akad. Nauk SSSR., Tekh. Kibernet., No. 3, 83?90 (1981). · Zbl 0512.90047
[58] S. F. Yashkov, ?Analysis of systems with prioritized processor sharing,? Avtomat. Vychisl. Tekh, No. 3, 29?38 (1984). · Zbl 0572.68023
[59] S. F. Yashkov, ?Shared-processor system with limited number of requests,? in: Models of Information Distribution and Methods for Their Analysis: Annals of the Tenth All-Union School-Seminar on Teletraffic Theory [in Russian], Moscow (1988), pp. 68?74.
[60] S. F. Yashkov, Analysis of Queues in Computers [in Russian], Radio Svyaz’, Moscow (1989).
[61] S. F. Yashkov, ?Method for analyzing shared-processor systems,? in: Teletraffic Theory in Information Systems [in Russian], Nauka, Moscow (1989), pp. 38?45.
[62] S. F. Yashkov, ?Characteristics of nonclassical queue models with processor sharing,? in: Models and Methods for Information Networks [in Russian], Nauka, Moscow (1990), pp. 14?19. · Zbl 0764.60103
[63] J. Abate and W. Whitt, ?Transient behaviour of the M |M|1 queue via Laplace transforms,? Adv. Appl. Probab.,20, No. 1, 145?178 (1988). · Zbl 0638.60097 · doi:10.1017/S0001867800017985
[64] I. Adiri and B. Avi-Itzhak, ?A time-sharing queue,? Manag. Sci.,15, No. 11, 639?657 (1969). · Zbl 0179.23701 · doi:10.1287/mnsc.15.11.639
[65] B. K. Asare and F. G. Foster, ?Conditional response times in the M |G|1 processor-sharing system,? J. Appl. Probab.,20, No. 4, 910?915 (1983). · Zbl 0531.60088 · doi:10.1017/S0021900200024232
[66] S. Asmussen and H. Hering, Branching Processes, Birkhäuser, Basel (1983). · Zbl 0516.60095
[67] D. Assaf and M. Haviv, ?Reneging from processor-sharing systems and random queues,? Math. Oper. Res.,15, No. 1, 129?138 (1990). · Zbl 0797.68017 · doi:10.1287/moor.15.1.129
[68] B. Avi-Itzhak and S. Halfin, ?Server sharing with a limited number of service positions and symmetric queues,?J. Appl. Probab.,24, No. 4, 990?1000 (1987). · Zbl 0638.60098 · doi:10.1017/S0021900200116845
[69] B. Avi-Itzhak and S. Halfin, ?Response times in M |M|1 time-sharing schemes with limited number of service positions,? J. Appl. Probab.,25, No. 3, 579?595 (1988). · Zbl 0655.60085 · doi:10.1017/S0021900200041292
[70] F. Baccelli and D. Towsley, ?The customer reponse times in the processor sharing queue are associated,? unpublished paper. · Zbl 0736.60089
[71] A. D. Barbour, ?Networks of queues and the method of stages,? Adv. Appl. Probab.,8, No. 3, 584?591 (1976). · Zbl 0342.60065 · doi:10.1017/S0001867800042415
[72] J. A. Barnes, ?Traffic processes and sojourn times in finite Markovian queues,? Doct. Dissert., Virginia State Univ. Dept. of Industr. Eng. and Opr. Res., Blacksburg (1988).
[73] J. L. van den Berg, ?Simple approximations for second moment characteristics of the sojourn time in the M |G| 1 processor-sharing queue,? Rept. Cent. Math. Comput. Sci., No. BS-R8907, 1?19 (1989).
[74] J. L. van den Berg and O. J. Boxma, ?Sojourn times in feedback and processor sharing queues,? Rept. Cent. Math. Comput. Sci., No. OS-R8801, 1?9 (1988).
[75] J. L. van den Berg and O. J. Boxma, ?Sojourn times in feedback queues,? in: Proc. DGOR Conf., Springer, Berlin (1989). · Zbl 0668.60087
[76] J. L. van den Berg, O. J. Boxma, and W. P. Groenendijk, ?Sojourn times in the M|G|1 queue with deterministic feedback,? Commun. Statist. Stochastic Models,5, No. 1, 115?129 (1989). · Zbl 0668.60087 · doi:10.1080/15326348908807101
[77] J. P. C. Blanc, ?On the relaxation times of open queueing networks,? in: Queueing Theory and Its Applications (O. J. Boxma and R. Syski, eds.), North-Holland, Amsterdam (1988), pp. 235?239.
[78] O. J. Boxma, ?Models of two queues ?a few new views,? in: Teletraffic Anal. and Comput. Perform. Eval.: Proc. Int. Seminar, North-Holland, Amsterdam (1986), pp. 75?98.
[79] S. L. Brumelle, ?A generalization of Erlang’s loss system to state dependent arrivals and service rates,? Math. Oper. Res.,3, No. 1, 10?16 (1978). · Zbl 0397.60076 · doi:10.1287/moor.3.1.10
[80] K. M. Chandy, J. H. Howard, and D. E. Towsley, ?Product form and local balance in queueing networks,? JACM,24, No. 2, 250?263 (1977). · Zbl 0356.68074 · doi:10.1145/322003.322009
[81] K. M. Chandy and A. J. Martin, ?A characterization of product-form queueing networks,? JACM,30, No. 2, 286?299 (1983). · Zbl 0512.68030 · doi:10.1145/322374.322378
[82] Ji Chuanshu, ?Sequential scheduling of priority queues and arm-acquiring bandits,? J. Appl. Math. Simul.,1, No. 2, 115?135 (1987). · Zbl 0652.90044 · doi:10.1155/S1048953388000097
[83] E. G. Coffman and P. Denning, Operating Systems Theory, Prentice-Hall, Englewood Cliffs (1973).
[84] E. G. Coffman, G. Fayolle, and I. Mitrani, ?Sojourn time in a tandem queue with overtaking,? Commun. Statist. Stochastic Models,2, No. 1, 43?65 (1986). · Zbl 0595.60091 · doi:10.1080/15326348608807024
[85] E. G. Coffman, L. Flatto, I. Mitrani, L. A. Shepp, and C. Knessl, ?Stochastic models of queue storage,? Probab. Eng. and Inf. Sci.,2, No. 1, 75?93 (1988). · Zbl 1134.60391 · doi:10.1017/S0269964800000644
[86] E. G. Coffman, R. R. Muntz, and H. Trotter, ?Waiting time distributions for processor-sharing systems,? JACM,17, No. 1, 123?130 (1970). · Zbl 0197.15304 · doi:10.1145/321556.321568
[87] J. W. Cohen, ?The multiple phase service network with generalized processor sharing,? Acta Inform.,12, No. 3, 245?284 (1980).
[88] J. W. Cohen, ?Sensitivity and insensitivity,? Delft Progr. Rept. Ser. A,5, No. 3, 159?173 (1980).
[89] J. W. Cohen, The Single-Server Queues. Second Edition, North-Holland, Amsterdam (1982).
[90] J. W. Cohen, ?On processor sharing and random service,? J. Appl. Probab.,21, No. 4, 937 (1984). · Zbl 0562.60097 · doi:10.1017/S0021900200037657
[91] J. W. Cohen, ?Boundary value problems in queueing theory,? Queueing Syst.,3, No. 2, 97?128 (1988). · Zbl 0662.60098 · doi:10.1007/BF01189045
[92] R. B. Cooper, Introduction to Queueing Theory. Second Edition, North-Holland, New York (1981). · Zbl 0486.60002
[93] R. B. Cooper, ?Queueing theory,? in: Handbook in Oper. Res. and Manag. Sci., Vol. 2, D. Heyman and M. Sobel (eds.), North-Holland, New York (1990), pp. 469?518.
[94] R. B. Cooper and Niu Shun-Chen, ?Bene?’s formula for M|G|1-FIFO explained by preemptive-resume LIFO,? J. Appl. Probab.,23, No. 2, 550?554 (1986). · Zbl 0602.60085
[95] H. Daduna, ?The distribution of residence times and cycle times in a closed tandem of processor sharing queues,? in: Messung, Modellierung und Bewertung von Rechensystemen, H. Beilner (ed.), Springer, Berlin (1985), pp. 127?140.
[96] H. Daduna and R. Schassberger, ?A discrete-time round-robin queue with Bernoulli input and general arithmetic service time distributions,? Acta Inform.,15, No. 3, 251?263 (1981). · Zbl 0459.68004 · doi:10.1007/BF00289264
[97] D. J. Daley, ?Queueing output processes,? Adv. Appl. Probab.,8, No. 2, 395?415 (1976). · Zbl 0349.60097 · doi:10.1017/S0001867800042208
[98] R. L. Disney and P. Kiessler, Traffic Processes in Queueing Networks. A Markov Renewal Approach, The Johns Hopkins Univ. Press, Baltimore (1987). · Zbl 0713.90032
[99] R. L. Disney and D. König, ?Queueing networks: a survey of their random processes,? SIAM Rev.,27, No. 3, 335?403 (1985). · Zbl 0581.60075 · doi:10.1137/1027109
[100] D. Fakinos, ?On the single-server queue with the preemptive-resume last-come first-served queue discipline,? J. Appl. Probab.,23, No. 1, 243?248 (1986). · Zbl 0591.60091
[101] G. Fayolle, ?On functional equations of one and two complex variables arising in the analysis of stochastic models,? in: Math. Comput. Performance and Reliab., Amsterdam (1984), pp. 45?75.
[102] G. Fayolle, I. Mitrani, and R. Iasnogorodski, ?Sharing a processor among many job classes,? JACM,27, No. 3, 519?532 (1980). · Zbl 0475.68012 · doi:10.1145/322203.322212
[103] R. D. Foley and G. A. Klutke, ?Stationary increments in the accumulated work process in processor-sharing queues,? J. Appl. Probab.,26, No. 3, 671?677 (1989). · Zbl 0683.60071 · doi:10.1017/S0021900200038298
[104] D. P. Gaver and P. A. Jacobs, ?Processor-shared time-sharing models in heavy traffic,? SIAM J. Comput,15, No. 4 1085?1100 (1986). · Zbl 0621.68023 · doi:10.1137/0215078
[105] J. C. Gittins, Multi-Armed Bandit Allocation Indices, Wiley, New York (1989). · Zbl 0699.90068
[106] S. A Grishechkin, ?On connection between the theory of branching processes and queueuing theory,? in: Proc. Fifth Internat. Vilnius Conf. on Probab. Theory and Math. Stat., Vilnius (1989).
[107] G. Hooghiemstra, M. Keane, and S. van de Ree, ?Power series for stationary distribution of coupled processor models,? SIAM J. Appl. Math.,48, No. 5, 1159?1166 (1988). · Zbl 0652.60097 · doi:10.1137/0148069
[108] D. L. Jagerman and B. Sengupta, ?A functional equation arising in a queue with a gating mechanism,? Probab. Eng. and Inf. Sci.,3, No. 3, 417?433 (1989). · Zbl 1134.60398 · doi:10.1017/S0269964800001285
[109] P. Jagers, Branching Processes with Biological Applications, Wiley, London (1975). · Zbl 0356.60039
[110] N. K. Jaiswal, ?Performance evaluation studies for time-sharing computer systems,? Perform. Eval.,2, No. 4, 223?236 (1982). · Zbl 0494.68002 · doi:10.1016/0166-5316(82)90023-2
[111] U. Jansen, ?Conditional expected sojourn times in insensitive queueing systems and networks,? Adv. Appl. Probab.,16, No. 4, 906?919 (1984). · Zbl 0559.60074 · doi:10.1017/S0001867800022990
[112] J. Keilson and L. Servi, ?Dynamics of the M|G|1 vacation model,? Oper. Res.,35, No. 4, 575?582 (1987). · Zbl 0636.90033 · doi:10.1287/opre.35.4.575
[113] F. P. Kelly, Reversibility and Stochastic Networks, Wiley, New York (1979). · Zbl 0422.60001
[114] L. Kleinrock, ?Time-shared systems: a theoretical treatment,? JACM,14, No. 2, 242?251 (1967). · Zbl 0173.20001 · doi:10.1145/321386.321388
[115] G. A. Klutke, P. Kiessler, and R. Disney, ?Interoutput times in processor sharing queues with feedback,? Queueing Syst.,3, No. 4, 363?376 (1988). · Zbl 0661.68035 · doi:10.1007/BF01157856
[116] C. Knessl, B. Matkowsky, Z. Schuss, and C. Tier, ?Response times in prcessor-shared queues with state-dependent arrival rates,? Commun. Statist. Stochastic Models,5, No. 1, 83?113 (1989). · Zbl 0668.60086 · doi:10.1080/15326348908807100
[117] H. Kobayashi and A. G. Konheim, ?Queueing models of computer communications system analysis,? IEEE Trans. Commun.,25, No. 1, 2?28 (1977). · Zbl 0365.68064 · doi:10.1109/TCOM.1977.1093702
[118] V. G. Kulkarni, V. F. Nicola, and K. S. Trivedi, ?The completion time of a job on multimode systems,? Adv. Appl. Probab.,19, No. 4, 932?954 (1987). · Zbl 0632.60101 · doi:10.1017/S000186780001750X
[119] D. Mitra, ?Waiting time distributions from closed queueing network models of shared-processor systems,? in: Performance ’81: Proc. Eighth Int. Symp. Comput. Performance Modelling, Meas. and Eval., North-Holland, Amsterdam (1981), pp. 113?131.
[120] D. Mitra and J. A. Morrison, ?Asymptotic expansions of moments of the waiting time in closed and open processor-sharing systems with multiple job classes,? Adv. Appl. Probab.,15, No. 4, 813?839 (1983). · Zbl 0526.60085 · doi:10.1017/S0001867800021637
[121] D. Mitra and J. A. Morrison, ?Asymptotic expansions of moments of waiting time in a shared-processor of an interactive system,? SIAM J. Comput,12, No. 4, 789?802 (1983). · Zbl 0524.68022 · doi:10.1137/0212054
[122] I. Mitrani, ?Response time problems in communication networks,? J. Roy. Statist. Soc.,B47, No. 3, 396?406 (1986). · Zbl 0611.68011
[123] J. A. Morrison, ?Response-time distribution for a processor-sharing system,? SIAM J. Appl. Math.,45, No. 1, 152?167 (1985). · Zbl 0558.68031 · doi:10.1137/0145007
[124] J. A. Morrison, ?Asymptotic analysis of the waiting-time distribution for a large closed processor-sharing system,? SIAM J. Appl. Math.,46, No. 1, 140?170 (1986). · Zbl 0597.60095 · doi:10.1137/0146012
[125] J. A. Morrison, ?Conditioned response-time distribution for a large closed processor-sharing system with multiple classes in very heavy usage,? SIAM J. Appl. Math.,48, No. 6, 1493?1509 (1988). · Zbl 0674.60091 · doi:10.1137/0148093
[126] J. A. Morrison and D. Mitra, ?Heavy-usage asymptotic expansions for the waiting time in closed processor-sharing systems with multiple classes,? Adv. Appl. Probab.,17, No. 1, 163?185 (1985). · Zbl 0556.60038 · doi:10.1017/S0001867800014713
[127] Ph. Nain, P. Tsoucas, and J. Walrand, ?Interchange arguments in stochastic scheduling,? J. Appl. Probab.,26, No. 4, 815?826 (1989). · Zbl 0689.90030 · doi:10.1017/S0021900200027686
[128] M. F. Neuts, ?Matrix-analytic methods in queueing theory,? Eur. J. Oper. Res.,15, No. 1, 2?12 (1984). · Zbl 0525.90046 · doi:10.1016/0377-2217(84)90034-1
[129] T. M. O’Donovan, ?Direct solutions of M|G|1 processor-sharing models,? Oper. Res.,22, No. 6, 1232?1235 (1974). · Zbl 0294.60076 · doi:10.1287/opre.22.6.1232
[130] T. M. O’Donovan, ?The queue M|G|1 when jobs are scheduled within generations,? Oper. Res.,23, No. 4, 821?824 (1975). · Zbl 0307.90038 · doi:10.1287/opre.23.4.821
[131] T. M. O’Donovan, ?Conditional response times in M|M| 1 processor-sharing models,? Oper. Res.,24, No. 2, 382?385 (1976). · Zbl 0325.60092 · doi:10.1287/opre.24.2.382
[132] T. J. Ott, ?The sojourn-time distribution in the M|G|1 queue with processor-sharing,? J. Appl. Probab.,21, No. 2, 360?378 (1984). · Zbl 0544.60087
[133] A. Pósafalvi and J. Sztrik, ?On the \(\langle (m,n)(\overrightarrow M |\overrightarrow M )1\rangle\) priority queues and their applications,? Probl. Upr. Teorii Inf.,16, No. 3, 169?186 (1987). · Zbl 0637.90039
[134] V. Ramaswami, ?The sojourn time in the GI|M|1 queue with processor sharing,? J. Appl. Probab.,21, No. 2, 437?442 (1984). · Zbl 0543.60093
[135] K. M. Rege and B. Sengupta, ?Sojourn time distribution in a multiprogrammed computer system,? AT and T Tech. J.,64, No. 5, 1077?1090 (1985). · doi:10.1002/j.1538-7305.1985.tb00456.x
[136] K. M. Rege and B. Sengupta, ?Response time distribution in a multiprogrammed computer with terminal traffic,? Perform. Eval.,8, No. 1, 41?50 (1988). · doi:10.1016/0166-5316(88)90011-9
[137] K. M. Rege and B. Sengupta, ?A single server queue with gated processor-sharing discipline,? Queueing Syst.,4, No. 3, 249?261 (1989). · Zbl 0676.60089 · doi:10.1007/BF02100269
[138] M. I. Reiman, ?A multiclass feedback queue in heavy traffic,? Adv. Appl. Probab.,20, No. 1, 179?207 (1988). · Zbl 0647.60100 · doi:10.1017/S0001867800017997
[139] J. A. C. Resing, G. Hooghiemstra, and M. S. Keane, ?The M|G|1 processor sharing queue as the almost sure limit of feedback queues,? J. Appl. Probab., (to appear). · Zbl 0726.60093
[140] Ph. Robert and R. Schassberger, ?On the M|G|1 foreground?background processor-sharing queue,? Queueing Syst.,4, No. 3, 281?286 (1989). · Zbl 0684.60069 · doi:10.1007/BF02100271
[141] T. Rolski, ?Stationary random processes associated with point processes,? Lect. Notes. Statist.,5, Springer, New York (1981). · Zbl 0467.60002
[142] S. M. Ross, ?Multi-server queues,? in: Deterministic and Stochastic Scheduling: Proc. NATO Adv. Study and Res., Inst. Theor. Approaches Scheduling Probl., Reidel, Dordrecht (1982), pp. 197?209.
[143] M. Sakata, S. Noguchi, and J. Oizumi, ?An analysis of the M|G|1 queue under round-robin scheduling,? Oper. Res.,19, No. 2, 371?385 (1971). · Zbl 0247.60061 · doi:10.1287/opre.19.2.371
[144] C. L. Samelson and W. G. Bulgrein, ?A note on product form solutions for queueing networks with Poisson arrivals and general service-time distributions with finite means,? JACM,29, No. 3, 830?840 (1982). · Zbl 0484.90039 · doi:10.1145/322326.322338
[145] R. Schassberger, Warteschlangen, Springer, Vienna (1973).
[146] R. Schassberger, ?A new approach to the M|G|1 processor-sharing queue,? Adv. Appl. Probab.,16, No. 1, 202?213 (1984). · Zbl 0529.68015 · doi:10.1017/S0001867800022412
[147] R. Schassberger, ?A detailed steady-state analysis of the M|G|1 queue under various time sharing disciplines,? in: Appl. Math., Perform., Reliab. Models of Comp. Comm. Syst., G. Iazeolla (ed.), North-Holland, Amsterdam (1987).
[148] R. Schassberger, ?The steady-state distribution of spent service times present in the M|G|1 foreground?background processor-sharing queue,? J. Appl. Probab.,25, No. 1, 194?203 (1988). · Zbl 0642.60080
[149] L. E. Schrage, ?The queue M|G|1 with feedback to lower priority queues,? Manag. Sci.,13, No. 7, 466?474 (1967). · doi:10.1287/mnsc.13.7.466
[150] B. Sengupta, ?A perturbation method for solving some queues with processor sharing discipline,? J. Appl. Probab.,26, No. 1, 209?214 (1989). · Zbl 0672.60095 · doi:10.1017/S0021900200041966
[151] B. Sengupta and D. L. Jagerman, ?A conditional response time of the M|M|1 processor-sharing queue,? AT and T Tech. J.,64, No. 2, Pt. 1, 409?421 (1985). · Zbl 0587.68036 · doi:10.1002/j.1538-7305.1985.tb00440.x
[152] R. F. Serfozo, ?Recent developments in queueing theory and a review of ’Asymptotic Methods in Queueing Theory’ by A A. Borovkov,? SIAM Rev.,28, No. 2, 279?283 (1986). · doi:10.1137/1028095
[153] J. G. Shantikumar and U. Sumita, ?Convex ordering of sojourn times in single-server queues: extremal properties of FIFO and LIFO service disciplines,? J. Appl. Probab.,24, No. 3, 737?748 (1987). · Zbl 0631.60095 · doi:10.1017/S0021900200031442
[154] F. W. Steutel and K. van Harn, ?Discrete operator-self-decomposability and queueing networks0,? Commun. Statist. Stochastic Models,2, No. 2, 161?169 (1986). · Zbl 0603.60012 · doi:10.1080/15326348608807031
[155] R. Syski, ?Markovian models ?an essay,? in: Craft Probabilistic Modell., Springer, New York (1986), pp. 109?125.
[156] R. Syski, ?Markovian functionals in teletraffic analysis,? in: Teletraffic Anal. and Comput. Perform. Eval.: Proc Internat. Semin., North-Holland, Amsterdam (1986), pp. 303?317.
[157] L. Takács, ?Queues, random graphs and branching processes,? J. Appl. Math. and Simul.,1, No. 3, 223?243 (1988). · Zbl 0655.60088
[158] A. L. Tolmachev, ?Insensitivity in the queueing networks with generalized processor-sharing discipline,? in: Proc. First World Congress of the Bernoulli Soc., Vol. 1, VNU Sci. Press, Utrecht (1987). · Zbl 0694.60088
[159] S. K. Tripathi and A. Duda, ?A time-dependent analysis of queueing systems,? INFOR,24, No. 3, 199?220 (1986). · Zbl 0605.60088
[160] P. R. de Waal and N. M. van Dijk, ?Monotonicity of performance measures in a processor sharing queue,? Rept. Cent. Math. and Comput. Sci., No. BS-R8902, 1?11 (1989).
[161] W. Whitt, ?On the heavy-traffic limit theorems for GI|G|? queues,? Adv. Appl. Probab,14, No. 1, 171?190 (1982). · Zbl 0479.60090
[162] R. W. Wolff, ?Time-sharing with priorities,? SIAM J. Appl. Math.,19, No. 3, 566?574 (1970). · Zbl 0206.22401 · doi:10.1137/0119057
[163] G. Yamazaki and H. Sakasegawa, ?An optimal design problem for limited processor-sharing systems,? Manag. Sci.,33, No. 8, 1010?1019 (1987). · Zbl 0644.68047 · doi:10.1287/mnsc.33.8.1010
[164] S. F. Yashkov, ?A derivation of response time distribution for an M|G|1 processor-sharing queue,? Probl. Upr. Teor. Inf.,12, No. 2, 133?148 (1983). · Zbl 0519.68052
[165] S. F. Yashkov, ?New applications of random time change to analysis of processor-sharing queues,? in: Fourth Int. Vilnius Conf. on Probab. Theory and Math. Stat., Vol. 4, Vilnius (1985), pp. 343?345.
[166] S. F. Yashkov, ?Distribution of number of jobs in a feedback processor-sharing queue,? Math. Res.,27, 464?468 (1985). · Zbl 0582.90034
[167] S. F. Yashkov, ?A note on asymptotic estimates of the sojourn time variance in the M|G|1 queue with processor-sharing,? Syst. Anal. Modell. Simulat,3, No. 3, 267?269 (1986). · Zbl 0602.90059
[168] S. F. Yashkov, ?New solutions for processor-sharing queues,? in: Abstracts of the First World Congress of the Bernoulli Soc. for Math. Stat. and Prob. Theory [in Russian], Vol. 2, Nauka, Moscow (1986), p. 558.
[169] S. F. Yashkov, ?Processor-sharing queues: some progress in analysis,? (invited paper) Queueing Syst.,2, No. 1, 1?17 (1987). · Zbl 0648.68050 · doi:10.1007/BF01182931
[170] S. F. Yashkov, ?The nonstationary distribution of number of calls in the M|G|1 processor-sharing queue,? in: Adv. in Simulat.: Proc. Int. Symp., Vol. 2, R. Lukar and B. Schmidt (eds.), Springer (1988), pp. 158?162.
[171] S. F. Yashkov, ?The foreground-background processor-sharing queue: some developments in analysis,? in: Fifth Int. Vilnius Conf. on Probab. Theory and Math. Stat, Vol. 2, Vilnius (1989), pp. 236?237.
[172] A. Yassouridis and R. Koller, ?Mehrstufige Auswahldisziplin in einem M|G|1 Processor-Sharing System mit Prioritäten,? Computing,30, No. 1, 1?18 (1983). · Zbl 0489.60095 · doi:10.1007/BF02253292
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.