M/M/1 큐

M/M/1 queue
M/M/1 queue diagram
M/M/1 큐잉 노드

큐잉 이론에서 M/M/1 큐는 확률수학적 이론 내의 한 분야로, 단일 서버를 가진 시스템에서 큐 길이를 나타내며, 여기서 도착은 포아송 프로세스에 의해 결정되며, 작업 서비스 시간은 지수 분포를 가진다.모델명은 Kendall 표기법으로 기재되어 있습니다.이 모델은 큐잉[1] 모델 중 가장 기초적인 모델이며 이 모델에서 관심 있는 많은 메트릭에 대해 폐쇄형 표현식을 얻을 수 있기 때문에 매력적인 연구 대상이다.여러 서버를 가진 이 모델의 확장은 M/M/c 큐입니다.

모델 정의

M/M/1 큐는 상태 공간이 집합 {0,1,2,3,...인 확률 프로세스입니다.}: 이 값은 현재 서비스 중인 고객 수를 포함하여 시스템의 고객 수에 해당합니다.

  • 도착은 포아송 공정에 따라 θ 비율로 발생하며 공정이 상태 i에서 i + 1로 이동합니다.
  • 서비스 시간은 M/M/1 큐에 레이트 파라미터 μ를 갖는 지수 분포를 가지며 1/μ는 평균 서비스 시간입니다.
  • 모든 도착 시간과 서비스 시간은 (보통) 서로 [2]독립적이라고 가정한다.
  • 1대의 서버가, 선착순의 순서에 따라서, 큐의 선두로부터 1대씩 고객에게 서비스를 제공합니다.서비스가 완료되면 고객은 큐에서 탈퇴하고 시스템 내 고객 수는 1명 감소합니다.
  • 버퍼의 크기는 무한하기 때문에 포함할 수 있는 고객 수에 제한이 없습니다.

모델은 전이율 매트릭스를 가진 연속 시간 마르코프 체인으로 설명할 수 있다.

상태 공간 {0,1,2,3,...}에 있습니다. 이것은 출생-사망 과정과 동일한 연속 시간 마르코프 사슬입니다. 체인의 상태 공간도는 다음과 같습니다.

MM1 queue state space.svg

일시적인 솔루션

t에 의존하는 확률 질량 함수를 작성하여 특정 시간에 M/M/1 큐가 특정 상태에 있을 확률을 설명할 수 있습니다.큐는 처음에 상태 i에 있다고 가정하고 시간 t에 상태 k가 될 가능성에 대해 p(t)를k 씁니다.그럼[2][3].

서 ii}는 ({t = / μ / \/ \ { a={ displayda }}}, { 기능은 변경되었습니다.과도 솔루션의 모멘트는 두 가지 단조 [4]함수의 합으로 표현할 수 있습니다.

정상 분석

이 모델은 μ 미만인 경우에만 안정적이라고 간주됩니다.평균적으로 서비스 완료보다 빨리 도착하는 경우 큐는 무한히 길어지고 시스템은 고정 분포를 갖지 않습니다.고정 분포는 t 이 큰 경우의 제한 분포입니다.

M/M/1 큐에 대해 다양한 성능 측정값을 명시적으로 계산할 수 있습니다.버퍼의 활용도는 the = / / μ로 쓰고, 큐가 안정되려면 < < 1이 필요합니다.repres 、 서버가 점유하고 있는 시간의 평균 비율을 나타냅니다.

시스템 평균 고객 수

정지 프로세스가 상태 i(서비스 중인 고객 포함 i 고객 포함)일[5]: 172–173 확률은 다음과 같습니다.

시스템 내 고객 수는 파라미터 1 - ρ의해 기하학적으로 분포되어 있음을 알 수 있습니다.따라서 시스템 내 평균 고객 수는 /(1 - )이고 시스템 내 고객 수의 분산은 /(1 - 2)입니다.이 결과는 프로세서 [6]공유와 같은 작업 절약형 서비스 시스템에 적용됩니다.

서버 사용 기간

비지 기간은 고객이 빈 시스템에 도착하는 순간부터 고객이 빈 시스템을 두고 떠나는 순간까지 측정되는 시간입니다.바쁜 기간은 확률 밀도[7][8][9][10] 함수를 가집니다.

여기1 I는 Laplace 변환을 사용하고 [12]용액을 반전시켜 얻은 첫 [11]번째 종류의 변형 베셀 함수이다.

M/M/1 비지 기간의 Laplace 트랜스폼은 다음과[13][14][15]: 215 같습니다.

이것은 특히 평균은 1/(μ - δ)이고 분산은 다음과 같이 주어진다.

응답시간

평균 응답 시간 또는 체류 시간(고객이 시스템에서 보내는 총 시간)은 스케줄링 분야에 의존하지 않으며 리틀의 법칙을 사용하여 1/(μ - λ)로 계산할 수 있습니다.평균 대기시간은 1/(μ - )) - 1/μ = //(μ - λ)이다.경험한 응답 시간의 분포는 스케줄링 분야에 따라 달라집니다.

선착순 훈련

큐에 도착하여 정지된 프로세스로 큐를 찾는 고객의 경우, 그들이 경험하는 응답 시간(대기 시간과 서비스 시간의 합)은 변환(μ - ))/(s + μ - [16]))되므로 확률 밀도[17] 함수가 된다.

프로세서 공유 규율

M/M/1-PS 큐에는 대기 회선이 없으며 모든 작업이 서비스 [18]용량의 동일한 비율을 받습니다.단일 서버가 16의 비율로 작동하고 시스템에 4개의 작업이 있다고 가정하면 각 작업은 4의 속도로 서비스를 받습니다.작업이 시스템에 [18]도착하거나 시스템에서 출발할 때마다 작업을 받는 속도가 변경됩니다.

큐를 정지 프로세스로 찾기 위해 도착한 고객을 위해 고객이 경험한 응답 시간의 분포에 대한 Laplace 변환이 [18]1970년에 발표되었으며, 이에 대해 필수적인 표현이 [19]알려져 있습니다.x개의 서비스를 필요로 하는 고객의 대기시간 분포(응답시간 감소 서비스 시간)가 변화하고[5]: 356 있다.

여기서 r은 방정식의 작은 루트입니다.

따라서 작업 도착 및 요구량 x의 평균 응답 시간은 x μ/(μ - θ)로 계산될 수 있습니다.대체 접근방식은 스펙트럼 확장 [6]방법을 사용하여 동일한 결과를 계산한다.

확산 근사

이용률 θ가 1에 가까우면 드리프트 파라미터 θ – μ와 분산 파라미터 θ + μ를 사용하여 반사된 브라운 운동을 통해 공정을 근사할 수 있다.이 과도한 교통 제한은 존 킹먼[20]의해 처음 도입되었다.

레퍼런스

  1. ^ Sturgul, John R. (2000). Mine design: examples using simulation. SME. p. vi. ISBN 0-87335-181-9.
  2. ^ a b Kleinrock, Leonard (1975). Queueing Systems Volume 1: Theory. p. 77. ISBN 0471491101.
  3. ^ Robertazzi, Thomas G. (2000). Computer Networks and Systems. New York, NY: Springer New York. p. 72. doi:10.1007/978-1-4612-1164-8. ISBN 978-1-4612-7029-4.
  4. ^ Abate, J.; Whitt, W. (1987). "Transient behavior of the M/M/l queue: Starting at the origin" (PDF). Queueing Systems. 2: 41–65. doi:10.1007/BF01182933.
  5. ^ a b Harrison, Peter; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison–Wesley.
  6. ^ a b Guillemin, F.; Boyer, J. (2001). "Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory" (PDF). Queueing Systems. 39 (4): 377. doi:10.1023/A:1013913827667. Archived from the original (PDF) on 2006-11-29.
  7. ^ Abate, J.; Whitt, W. (1988). "Simple spectral representations for the M/M/1 queue" (PDF). Queueing Systems. 3 (4): 321. doi:10.1007/BF01157854.
  8. ^ Keilson, J.; Kooharian, A. (1960). "On Time Dependent Queuing Processes". The Annals of Mathematical Statistics. 31 (1): 104–112. doi:10.1214/aoms/1177705991. JSTOR 2237497.
  9. ^ Karlin, Samuel; McGregor, James (1958). "Many server queueing processes with Poisson input and exponential service times" (PDF). Pacific J. Math. 8 (1): 87–118. doi:10.2140/pjm.1958.8.87. MR 0097132.
  10. ^ Gross, Donald; Shortle, John F.; Thompson, James M.; Harris, Carl M. (2011-09-23). "2.12 Busy-Period Analysis". Fundamentals of Queueing Theory. Wiley. ISBN 1118211642.
  11. ^ Adan, Ivo. "Course QUE: Queueing Theory, Fall 2003: The M/M/1 system" (PDF). Retrieved 2012-08-06.
  12. ^ Stewart, William J. (2009). Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. Princeton University Press. p. 530. ISBN 978-0-691-14062-9.
  13. ^ Asmussen, S. R. (2003). "Queueing Theory at the Markovian Level". Applied Probability and Queues. Stochastic Modelling and Applied Probability. Vol. 51. pp. 60–31. doi:10.1007/0-387-21525-5_3. ISBN 978-0-387-00211-8.
  14. ^ Adan, I.; Resing, J. (1996). "Simple analysis of a fluid queue driven by an M/M/1 queue". Queueing Systems. 22 (1–2): 171–174. doi:10.1007/BF01159399.
  15. ^ Kleinrock, Leonard (1975). Queueing Systems: Theory, Volume 1. Wiley. ISBN 0471491101.
  16. ^ Harrison, P. G. (1993). "Response time distributions in queueing network models". Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science. Vol. 729. pp. 147–164. doi:10.1007/BFb0013852. ISBN 3-540-57297-X.
  17. ^ Stewart, William J. (2009). Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. Princeton University Press. p. 409. ISBN 978-0-691-14062-9.
  18. ^ a b c Coffman, E. G.; Muntz, R. R.; Trotter, H. (1970). "Waiting Time Distributions for Processor-Sharing Systems". Journal of the ACM. 17: 123–130. doi:10.1145/321556.321568.
  19. ^ Morrison, J. A. (1985). "Response-Time Distribution for a Processor-Sharing System". SIAM Journal on Applied Mathematics. 45 (1): 152–167. doi:10.1137/0145007. JSTOR 2101088.
  20. ^ Kingman, J. F. C.; Atiyah (October 1961). "The single server queue in heavy traffic". Mathematical Proceedings of the Cambridge Philosophical Society. 57 (4): 902. doi:10.1017/S0305004100036094. JSTOR 2984229.