Abstract
This article considers new approaches in queuing theory associated with mathematical modelling and analysis of contemporary computer systems and networks using shared processors. Emphasis is placed on results concerning exact determination of probability distributions for such characteristics as sojourn times and waiting times. Various methods of analyzing shared-processor systems are considered, their characteristics analyzed, and special attention is devoted to the broad class of M ¦GI¦1 queuing disciplines that result in Poisson throughput. Several limit theorems for heavyload conditions are described.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Literature cited
V. V. Anisimov, Random Processes with Discrete Components. Limit Theorems [in Russian], Vishcha Shkola, Kiev (1988).
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).
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).
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.
A. A. Borovkov, Asymptotic Methods in Queuing Theory [in Russian], Nauka, Moscow (1980).
V. A. Vatutin and A. M. Zubkov, “Branching Processes. I,” Itogi Nauki Tekh., Teor. Veroyatn., Mat. Stat., Teor. Kibernet.,23, 3–67 (1985).
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).
B. V. Gnedenko and I. N. Kovalenko, Introduction to Queuing Theory. Second ed. [in Russian], Nauka, Moscow (1987).
S. A. Grishechkin, “Single-line shared-processor systems and branching processes,” Mat. Zametki,44, No. 4, 433–448 (1988).
N. K. Jaiswal, Priority Queues, Academic Press, New York (1968).
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).
M. Ts. Dimitrov, “Single-line M ¦M¦ 1 systems with generalized dynamic priorities,” Serdika. B'lg. Mat. Spisanie,6, No. 2, 143–152 (1980).
M. Ts. Dimitrov, “Bulk servicing systems with Markov arrivals and shared processors,” Pliska. B'lg. Mat. Stud., No. 7, 68–74 (1984).
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).
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).
V. A. Ivnitskii, “Queuing networks and their application to computers,” Zarub. Radioélektr., No. 7, 33–70 (1977).
G. I. Ivchenko, V. A. Kashtanov, and I. N. Kovalenko, Queuing Theory [in Russian], Vyssh. Shk., Moscow (1982).
V. V. Kalashnikov and S. T. Rachev, Mathematical Methods for Construction of Stochastic Service Models [in Russian], Nauka, Moscow (1988).
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).
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).
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).
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).
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).
L. Kleinrock, Queueing Theory. Vol. 1. Theory, Wiley, New York (1975).
L. Kleinrock, Queueing Theory. Vol. 2. Computer Applications, Wiley, New York (1975).
G. P. Klimov, “Time-sharing systems. I,” Teor. Veroyatn. Ee. Primen.,19, No. 3, 558–576 (1974).
G. P. Klimov, “Time-sharing systems. II,” Teor. Veroyatn. Ee. Primen.,23, No. 2, 331–339 (1978).
G. P. Klimov, A. K. Lyakhu, and V. F. Matveev, Mathematical Models of Time-Shared Systems [in Russian], Shtiintsa, Kishinev (1983).
I. N. Kovalenko, N. Yu. Kuznetsov, and V. M. Shurenkov, Handbook of Random Processes [in Russian], Naukova Dumka, Kiev (1983).
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).
A. I. Kostogryzov, “Packet processing with EPS and interrupts,” Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 4, 88–93 (1987).
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).
J. Cohen and O. Boxma, Boundary-Value Problems in Queuing Theory, North Holland, Amsterdam (1983).
V. V. Lupaev and S. F. Yashkov, Efficient Computation in Automatic Control Systems [in Russian], Statistika, Moscow (1975).
S. A. Maiorov, G. I. Novikov, T. I. Aliev, É. I. Makharev, and B. D. Timchenko, Fundamentals of Computer System Theory, Vyssh. Shk., Moscow (1978).
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).
V. F. Matveev and V. G. Ushakov, Queueing Systems [in Russian], Mosk. Gos. Univ., Moscow (1984).
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).
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).
V. I. Neiman, “Computer communications networks,” Itogi Nauki Tekh., Élektrosvyaz',9, 5–119 (1978).
A. V. Pechinkin, “Stationary probabilities in FBPS shared-processor systems,” Izv. Akad. Nauk. SSSR, Tekh. Kibernet., No. 5, 73–77 (1980).
A. V. Pechinkin and A. G. Tatashev, “Generalized FBPS policies,” Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 4, 120–125 (1981).
N. Prabhu, Stochastic Storage Processes, Springer, New York (1980).
B. A. Sevast'yanov, Branching Processes [in Russian], Nauka, Moscow (1971).
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).
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.
D. Ferrari, Computer Systems Performance Evaluation, Prentice-Hall, Englewood Cliffs (1978).
P. Franken, D. Kënig, U. Arndt, and F. Shmidt, Queues and Point Processes, Wiley, New York (1982).
D. Tsikritzis and F. Bernstein, Operating Systems [Russian translation], Mir, Moscow (1977).
K. Chun and R. Williams, Introduction to Stochastic Integration [Russian translation], Mir, Moscow (1987).
D. Shtoiyan, Qualitative Properties and Bounds for Stochastic Models [Russian translation], Mir, Moscow (1979).
S. F. Yashkov, “Distribution of conditional waiting time in time-shared systems,” Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 5, 88–94 (1977).
S. F. Yashkov, “Shared-processor systems,” in: Structural Adaptation of Multiprocessor Information Processing Systems [in Russian], Zinatne, Riga (1978), pp. 25–29.
S. F. Yashkov, “FBPS processor sharing for requests with minimum service requirements,” Tekh. Sredsv Svyazi, Ser. ASU, No. 2, 51–62 (1978).
S. F. Yashkov, “Invariance properties of probabilistic models of dispatching in multiprogramming systems,” Avtomat. Vychisl. Tekh, No. 6, 56–62 (1980).
S. F. Yashkov, “Results of analysis of probabilistic models of teleprocessing systems,” Avtomat. Vychisl. Tekh., No. 4, 3–11 (1981).
S. F. Yashkov, “Ergodicity of systems with variable service rates,” Izv. Akad. Nauk SSSR., Tekh. Kibernet., No. 3, 83–90 (1981).
S. F. Yashkov, “Analysis of systems with prioritized processor sharing,” Avtomat. Vychisl. Tekh, No. 3, 29–38 (1984).
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.
S. F. Yashkov, Analysis of Queues in Computers [in Russian], Radio Svyaz', Moscow (1989).
S. F. Yashkov, “Method for analyzing shared-processor systems,” in: Teletraffic Theory in Information Systems [in Russian], Nauka, Moscow (1989), pp. 38–45.
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.
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).
I. Adiri and B. Avi-Itzhak, “A time-sharing queue,” Manag. Sci.,15, No. 11, 639–657 (1969).
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).
S. Asmussen and H. Hering, Branching Processes, Birkhäuser, Basel (1983).
D. Assaf and M. Haviv, “Reneging from processor-sharing systems and random queues,” Math. Oper. Res.,15, No. 1, 129–138 (1990).
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).
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).
F. Baccelli and D. Towsley, “The customer reponse times in the processor sharing queue are associated,” unpublished paper.
A. D. Barbour, “Networks of queues and the method of stages,” Adv. Appl. Probab.,8, No. 3, 584–591 (1976).
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).
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).
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).
J. L. van den Berg and O. J. Boxma, “Sojourn times in feedback queues,” in: Proc. DGOR Conf., Springer, Berlin (1989).
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).
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.
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.
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).
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).
K. M. Chandy and A. J. Martin, “A characterization of product-form queueing networks,” JACM,30, No. 2, 286–299 (1983).
Ji Chuanshu, “Sequential scheduling of priority queues and arm-acquiring bandits,” J. Appl. Math. Simul.,1, No. 2, 115–135 (1987).
E. G. Coffman and P. Denning, Operating Systems Theory, Prentice-Hall, Englewood Cliffs (1973).
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).
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).
E. G. Coffman, R. R. Muntz, and H. Trotter, “Waiting time distributions for processor-sharing systems,” JACM,17, No. 1, 123–130 (1970).
J. W. Cohen, “The multiple phase service network with generalized processor sharing,” Acta Inform.,12, No. 3, 245–284 (1980).
J. W. Cohen, “Sensitivity and insensitivity,” Delft Progr. Rept. Ser. A,5, No. 3, 159–173 (1980).
J. W. Cohen, The Single-Server Queues. Second Edition, North-Holland, Amsterdam (1982).
J. W. Cohen, “On processor sharing and random service,” J. Appl. Probab.,21, No. 4, 937 (1984).
J. W. Cohen, “Boundary value problems in queueing theory,” Queueing Syst.,3, No. 2, 97–128 (1988).
R. B. Cooper, Introduction to Queueing Theory. Second Edition, North-Holland, New York (1981).
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.
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).
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.
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).
D. J. Daley, “Queueing output processes,” Adv. Appl. Probab.,8, No. 2, 395–415 (1976).
R. L. Disney and P. Kiessler, Traffic Processes in Queueing Networks. A Markov Renewal Approach, The Johns Hopkins Univ. Press, Baltimore (1987).
R. L. Disney and D. König, “Queueing networks: a survey of their random processes,” SIAM Rev.,27, No. 3, 335–403 (1985).
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).
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.
G. Fayolle, I. Mitrani, and R. Iasnogorodski, “Sharing a processor among many job classes,” JACM,27, No. 3, 519–532 (1980).
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).
D. P. Gaver and P. A. Jacobs, “Processor-shared time-sharing models in heavy traffic,” SIAM J. Comput,15, No. 4 1085–1100 (1986).
J. C. Gittins, Multi-Armed Bandit Allocation Indices, Wiley, New York (1989).
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).
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).
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).
P. Jagers, Branching Processes with Biological Applications, Wiley, London (1975).
N. K. Jaiswal, “Performance evaluation studies for time-sharing computer systems,” Perform. Eval.,2, No. 4, 223–236 (1982).
U. Jansen, “Conditional expected sojourn times in insensitive queueing systems and networks,” Adv. Appl. Probab.,16, No. 4, 906–919 (1984).
J. Keilson and L. Servi, “Dynamics of the M¦G¦1 vacation model,” Oper. Res.,35, No. 4, 575–582 (1987).
F. P. Kelly, Reversibility and Stochastic Networks, Wiley, New York (1979).
L. Kleinrock, “Time-shared systems: a theoretical treatment,” JACM,14, No. 2, 242–251 (1967).
G. A. Klutke, P. Kiessler, and R. Disney, “Interoutput times in processor sharing queues with feedback,” Queueing Syst.,3, No. 4, 363–376 (1988).
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).
H. Kobayashi and A. G. Konheim, “Queueing models of computer communications system analysis,” IEEE Trans. Commun.,25, No. 1, 2–28 (1977).
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).
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.
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).
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).
I. Mitrani, “Response time problems in communication networks,” J. Roy. Statist. Soc.,B47, No. 3, 396–406 (1986).
J. A. Morrison, “Response-time distribution for a processor-sharing system,” SIAM J. Appl. Math.,45, No. 1, 152–167 (1985).
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).
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).
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).
Ph. Nain, P. Tsoucas, and J. Walrand, “Interchange arguments in stochastic scheduling,” J. Appl. Probab.,26, No. 4, 815–826 (1989).
M. F. Neuts, “Matrix-analytic methods in queueing theory,” Eur. J. Oper. Res.,15, No. 1, 2–12 (1984).
T. M. O'Donovan, “Direct solutions of M¦G¦1 processor-sharing models,” Oper. Res.,22, No. 6, 1232–1235 (1974).
T. M. O'Donovan, “The queue M¦G¦1 when jobs are scheduled within generations,” Oper. Res.,23, No. 4, 821–824 (1975).
T. M. O'Donovan, “Conditional response times in M¦M¦ 1 processor-sharing models,” Oper. Res.,24, No. 2, 382–385 (1976).
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).
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).
V. Ramaswami, “The sojourn time in the GI¦M¦1 queue with processor sharing,” J. Appl. Probab.,21, No. 2, 437–442 (1984).
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).
K. M. Rege and B. Sengupta, “Response time distribution in a multiprogrammed computer with terminal traffic,” Perform. Eval.,8, No. 1, 41–50 (1988).
K. M. Rege and B. Sengupta, “A single server queue with gated processor-sharing discipline,” Queueing Syst.,4, No. 3, 249–261 (1989).
M. I. Reiman, “A multiclass feedback queue in heavy traffic,” Adv. Appl. Probab.,20, No. 1, 179–207 (1988).
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).
Ph. Robert and R. Schassberger, “On the M¦G¦1 foreground—background processor-sharing queue,” Queueing Syst.,4, No. 3, 281–286 (1989).
T. Rolski, “Stationary random processes associated with point processes,” Lect. Notes. Statist.,5, Springer, New York (1981).
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.
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).
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).
R. Schassberger, Warteschlangen, Springer, Vienna (1973).
R. Schassberger, “A new approach to the M¦G¦1 processor-sharing queue,” Adv. Appl. Probab.,16, No. 1, 202–213 (1984).
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).
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).
L. E. Schrage, “The queue M¦G¦1 with feedback to lower priority queues,” Manag. Sci.,13, No. 7, 466–474 (1967).
B. Sengupta, “A perturbation method for solving some queues with processor sharing discipline,” J. Appl. Probab.,26, No. 1, 209–214 (1989).
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).
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).
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).
F. W. Steutel and K. van Harn, “Discrete operator-self-decomposability and queueing networks0,” Commun. Statist. Stochastic Models,2, No. 2, 161–169 (1986).
R. Syski, “Markovian models —an essay,” in: Craft Probabilistic Modell., Springer, New York (1986), pp. 109–125.
R. Syski, “Markovian functionals in teletraffic analysis,” in: Teletraffic Anal. and Comput. Perform. Eval.: Proc Internat. Semin., North-Holland, Amsterdam (1986), pp. 303–317.
L. Takács, “Queues, random graphs and branching processes,” J. Appl. Math. and Simul.,1, No. 3, 223–243 (1988).
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).
S. K. Tripathi and A. Duda, “A time-dependent analysis of queueing systems,” INFOR,24, No. 3, 199–220 (1986).
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).
W. Whitt, “On the heavy-traffic limit theorems for GI¦G¦∞ queues,” Adv. Appl. Probab,14, No. 1, 171–190 (1982).
R. W. Wolff, “Time-sharing with priorities,” SIAM J. Appl. Math.,19, No. 3, 566–574 (1970).
G. Yamazaki and H. Sakasegawa, “An optimal design problem for limited processor-sharing systems,” Manag. Sci.,33, No. 8, 1010–1019 (1987).
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).
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.
S. F. Yashkov, “Distribution of number of jobs in a feedback processor-sharing queue,” Math. Res.,27, 464–468 (1985).
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).
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.
S. F. Yashkov, “Processor-sharing queues: some progress in analysis,” (invited paper) Queueing Syst.,2, No. 1, 1–17 (1987).
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.
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.
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).
Additional literature cited
T. A. Azlarov and Kh. T. Tashmanov, “Transient processes in bulk servicing systems,” in: Queueing theory: Annals of All-Union School-Seminar, Moscow (1981), pp. 154–157.
G. P. Basharin, P. P. Bocharov, and Ya. A. Kogan, Analysis of Queues in Computer Networks [in Russian], Nauka, Moscow (1989).
A. A. Borovkov, “Limit theorems for serving networks. I, II,” Teor. Veroyatn. Primen.,31, No. 3, 474–490 (1987);32, No. 2, 282–298 (1987).
O. I. Bronshtein and I. M. Dukhovnyi, Models for Prioritized Service in Data Processing Systems [in Russian], Nauka, Moscow (1976).
I. I. Gikhman and A. V. Skorokhod, The Theory of Random Processes [in Russian], Vol. 2, Nauka, Moscow (1973).
B. Grigelionis and R. Mikulyavichyus, “Limit theorems for functionals in heavily loaded queueing systems. I,” Lit. Mat. Sb.,27, No. 3, 441–454 (1987).
V. M. Zolotarev, Modern Theory of Summation for Independent Random Variables [in Russian], Nauka, Moscow (1986).
V. A. Ivnitskii, “Conditions for invariance of stationary probabilities for queueing networks,” Teor. Veroyatn. Ee. Primen.,27, No. 1, 188–192 (1982).
Yu. M. Kabanov, R. Sh., Liptser, and A. N. Shiryaev, “Martingale methods in the theory of point processes,” in: Proc. School-Seminar on the Theory of Random Processes [in Russian], Part. 2, Vilnius (1975), pp. 269–354.
M. Ya. Kel'bert and Yu. M. Sukhov, “Poisson limit theorem for hybrid star networks: approximation of mean field,” Probl. Peredachi Inf.,25, No. 1, 78–87 (1989).
D. Kënig and F. Shmidt, “Limit theorems for single-line serving systems with feedback controlled by a general class of Markov point processes,” Teor. Veroyatn. Ee Primen.,30, No. 4, 671–678 (1985).
M. Yu. Kitaev, “Serving systems with Poisson departure streams,” Avtomat. Telemekh., No. 11, 40–45 (1980).
V. V. Kozlov, “Optimal service policy for bulk servicing,” in: Probabilistic Processes and Control: Scientific Annals of Kubanskii State University [in Russian], No. 247, Krasnodar (1977), pp. 33–37.
R. Conway, W. Maxwell, and L. Miller, Scheduling Theory [Russian translation], Nauka, Moscow (1975).
Yu. V. Malinkovskii, “Multiplicativeness of the stationary distribution of the state for one class of bulk-servicing network,” Avtomat. Telemekh., No. 2, 108–118 (1988).
A. V. Pavlov, “System with Schräge scheduling under heavy load,” Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 6, 59–66 (1983).
A. V. Pechinkin, “Analysis of single-line queueing systems with different service policies,” Doctoral Dissertation [in Russian], Mosk. Gos. Univ., Moscow (1986).
A. V. Pechinkin, A. D. Solov'ev, and S. F. Yashkov, “A system with policy of serving requests with minimal remaining service requirement,” Izv. Akad. Nauk SSSR, Tekh. Kibernet., No. 5, 51–58 (1979).
V. V. Rykov, “Decomposable multiregenerative processes and their application to problems in queueing theory,” Doctoral Dissertation [in Russian], Mosk. Gos. Univ., Moscow (1989).
S. F. Yashkov, “One class of service policies for models of computer networks,” in: Networks of Information Processing Computers [in Russian], Moscow (1980), pp. 112–117.
S. F. Yashkov, “Nonstationary characteristics of systems with FBPS,” in: Proc. Int. Seminar on Teletraffic Theory and Computer Modelling, Jusautor, Sofia (1988), pp. 41–46.
B. Avi-Itzhak and S. Halfin, “Expected response times in a nonsymmetric time-sharing queue with a limited number of service positions,” in: Proc. Twelfth Int. Teletraffic Congress, Vol. 5, Session 5.4B.2, Torino (1988), pp. 1–7.
M. V. Altamirano and B. Fontana, “Models to evaluate response times in single-processor systems and their applications to a multiprocessor system,” Proc. Twelfth Int. Teletraffic Congress, Vol. 4, Session 4.3A.5, Torino (1988), pp. 1–10.
F. Baccelli and P. Brémaud, “Palm probabilities and stationary queues,” in: Lect. Notes Statist., No. 41, Springer, New York (1987).
P. Brémaud, Point Processes and Queues: Martingale Dynamics, Springer, New York (1981).
R. Blumenthal and R. Getoor, Markov Processes and Potential Theory, Acad. Press, New York (1968).
P. J. Burke, “Output processes and tandem queues,” in: Proc. Twenty Second Int. Symp. on Cornputer-Commun. Networks and Teletraffic, J. Fox (ed.), Brooklyn Polytechnic Institute, New York (1972), pp. 419–428.
F. Kelly, “Networks of quasi-reversible nodes,” in: Applied Probability—Computer Science: The Interface, R. Disney and T. Ott (eds.), Birkhäuser, Boston (1982), pp. 3–26.
A. G. Konheim, I. Meilijson, and A. Melkman, “Processor sharing of two parallel lines,” J. Appl. Probab.,18, No. 4, 952–956 (1981).
A. J. Lemoine, “Networks of queues: a survey of weak convergence results,” Manag. Sci.,24, No. 11, 1175–1193 (1978).
W. Massey, “Open networks of queues: their algebraic structure and estimating their transient behaviour,” Adv. Appl. Probab.,16, No. 1, 167–201 (1984).
B. Melamed, “Characterization of Poisson traffic streams in Jackson queueing networks,” Adv. Appl. Probab,11, No. 2, 422–438 (1979).
D. Oakes, “Random overlapping intervals —a generalization of Erlang's loss formula,” Ann. Probab.,4, No. 6, 940–946 (1976).
G. Oliver, “Kostenminimale Prioritäten in Wartesystemen vom Typ M¦G¦1,” Elektron. Rechenanlagen,14, No. 6 262–271 (1972).
E. Reich, “Departure processes,” in: Proc. Symp. on Congestion Theory, W. Smith and W. E. Wilkinson (eds.), Univ. North Carolina Press, Chapel Hill (1965), pp. 439–457.
L. A. Schrage, “A proof of the optimality of the shortest remaining processing time discipline,” Oper. Res.,16, No. 4, 687–690 (1968).
L. A. Schrage and L. Miller, “The queue M¦G¦1 with the shortest remaining processing time discipline,” Oper. Res.,14, No. 4, 670–684 (1966).
K. C. Sevcik, “Scheduling for minimum total loss using service time distributions,” JACM,21, No. 1, 66–75 (1974).
J. Walrand, “A probabilistic look at networks of quasi-reversible queues,” IEEE Trans. Inf. Theory,29, No. 6, 825–831 (1983).
J. Walrand, An Introduction to Queueing Networks, Prentice-Hall, Englewood Cliffs (1989).
J. Walrand and P. Varaiya, “Flows in queueing networks: a martingale approach,” Math. Oper. Res.,6, No. 3, 387–404 (1981).
W. Whitt, “Heavy traffic limit theorems for queues: a survey,” Lect. Notes in Econ. and Math. Syst.98, A. B. Clark (ed.), Springer, New York (1974), pp. 307–350.
Additional information
Translated from Itogi Nauki i Tekhniki, Seriya Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 29, pp. 3–82, 1990.
The author would like to thank M. Ya. Kelbert for helpful comments.
Rights and permissions
About this article
Cite this article
Yashkov, S.F. Mathematical problems in the theory of shared-processor systems. J Math Sci 58, 101–147 (1992). https://doi.org/10.1007/BF01097426
Issue Date:
DOI: https://doi.org/10.1007/BF01097426