M/G/1 큐
M/G/1 queue큐잉 이론에서 M/G/1 큐는 확률의 수학적 이론에서 도착이 마르코프(포아송 프로세스에 의해 변조됨)이고 서비스 시간은 일반 분포를 가지며 단일 [1]서버가 있는 큐 모델입니다.모델명은 Kendall 표기법으로 작성되며 서비스 시간이 기하급수적으로 분산되어야 하는 M/M/1 큐의 확장입니다.M/G/1 큐는 고정 헤드 하드 [2]디스크의 성능을 모델링하는 데 사용됩니다.
모델 정의
M/G/1 큐로 표현되는 큐는 상태공간이 설정된 {0,1,2,3...}인 확률적 프로세스이며, 여기서 값은 서비스되는 큐의 고객 수에 대응한다.상태 i에서 상태 i + 1로의 이행은 신규 고객의 도착을 나타냅니다.이러한 도착 사이의 시간은 모수 θ로 지수 분포를 가집니다.상태 i에서 상태 i - 1로의 전환은 서비스를 받고 서비스를 마치고 출발한 고객을 나타냅니다. 개별 고객에게 서비스를 제공하는 데 필요한 시간은 일반적인 분배 기능을 가집니다.도착과 서비스 기간 사이의 시간은 통계적으로 독립적이라고 가정되는 무작위 변수이다.
스케줄링 정책
고객은 일반적으로 선착순으로 제공됩니다.그 밖에 널리 사용되는 스케줄 정책에는 다음과 같은 것이 있습니다.
- 큐 내의 모든 작업이 동등하게 서비스 용량을 공유하는 프로세서 공유
- 선착순, 선착순, 서비스 중인 업무를 중단할 수 없는 경우
- 선착순 선착순으로 서비스 중인 일이 후착순으로 인해 중단되지만 일은 보호되는[3] 경우
- Generalized Foreground-Background(FB; 범용 전경 백그라운드) 스케줄링으로, 지금까지 최소 처리 시간을 받은 작업이 먼저 처리되고 프로세서[3] 공유를 사용하여 동일한 서비스 시간을 받은 작업이 서비스 용량을 공유합니다.
- 가장 작은 크기의 작업이 서비스를 받고 서비스가 완료될 때까지 중단될 수 없는 SJF(Sortest Job first without Preemption)
- 가장 작은 원래 크기의 작업이 어느 순간에나 서비스되는[4] 선제적 최단 작업
- Shortest remaining processing time(SRPT; 최단 남은 처리시간) 다음 서비스 작업은 남은 처리요건이[5] 최소인 경우
대부분의 경우 서비스 정책은 큐 내의 평균 체류시간을 비교하여 평가됩니다.작업에 필요한 서비스 시간을 도착 시 알 수 있는 경우 최적의 스케줄링 정책은 SRPT입니다.[6]: 296
정책은 공정성의 [7]척도를 사용하여 평가할 수도 있습니다.
큐 길이
폴라체크-킨친법
정상 큐 길이 분포의 확률 생성 함수는 Pollaczek-Kinchine 변환[2] 방정식에 의해 주어진다.
여기서 g(s)는 서비스 시간 확률 밀도 [8]함수의 라플라스 변환입니다.M/M/1 큐의 경우 파라미터 μ, g(s) = μ/(μ+s)가 기하급수적으로 분포한다.
이것은 직접 계산 또는 보충 변수 방법을 사용하여 개별 상태 확률에 대해 해결할 수 있다.Pollaczek-Kinchine 공식은 시스템의 [9][10]평균 큐 길이와 평균 대기 시간을 나타냅니다.
매트릭스 분석법
M/G/1 큐의 내장된 마르코프 체인을 고려하며, 여기서 선택한 시점은 출발 순간 직후이다.서비스를 받고 있는 고객(있는 경우)에게는 0초의 서비스가 제공되고 있습니다.출발 사이에는 0, 1, 2, 3, ...의 도착이 있을 수 있습니다.따라서 체인은 상태 i에서 상태 i – 1, i, i + 1, i + 2, [11]…로 이동할 수 있습니다.내장된 마르코프 체인은 전이 행렬을 가진다.
어디에
F(u)는 서비스 시간 분포이며 큐에 대한 작업의 포아송 도착 속도입니다.
이러한 형태의 생성 행렬 또는 블록 행렬을 가진 마르코프 사슬은 M/G/1 타입 마르코프 [12]사슬이라고 불리며, M. F.[13][14] 뉴트럴에 의해 만들어진 용어이다.
M/G/1 큐는 트래픽 강도 () { =\ ( 이 1 미만인 경우에만 정상 분포를 가지며, 이 경우 고유한 분포가 확률 생성 함수를 [15]갖습니다.
서 M SS})는 일반 서비스 시간의 모멘트 생성 함수입니다.M/G/1형 마르코프 모델의 정상 분포는 매트릭스 분석법을 [16]사용하여 계산할 수 있다.
바쁜 기간
비지 기간은 상태 0에 대한 방문 사이에 상태 1, 2, 3, ...에서 보낸 시간입니다.사용 기간의 예상 길이는 1/(μ-μ)입니다. 여기서 1/μ는 예상 서비스 시간 길이이고 [17]μ는 도착을 관리하는 포아송 프로세스의 비율입니다.비지 기간 확률 밀도 ( ) \ s )는 Kendall 함수[18][19]: 92 방정식을 따르는 것을 보여줄 수 있다.
여기서 위의 g는 서비스 시간 분배 함수의 Laplace-Stieltjes 변환입니다.이 관계는 특별한 경우(M/M/1 큐 등)에만 정확하게 해결할 수 있지만, 어느 경우든 µ의 값을 계산할 수 있으며, 상한과 하한을 사용하여 반복함으로써 [20]분포 함수를 수치적으로 계산할 수 있습니다.
대기/응답 시간
대기시간 [21]분포의 라플라스-스틸테제스 변환에 대한 W는* Pollaczek-Kinchine 변환에 의해 다음과 같이 주어진다.
여기서 g(s)는 서비스 시간 확률 밀도 함수의 Laplace-Stieltjes 변환입니다.
도착 정리
도착은 포아송 프로세스에 의해 결정되므로 도착 정리가 유지됩니다.
다중 서버
k개의 서버를 가진 M/G/k 큐의 많은 메트릭은 아직 해결되지 않은 문제로 남아 있습니다.다만, 몇개의 근사치와 경계가 알려져 있습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ Gittins, John C. (1989). Multi-armed Bandit Allocation Indices. John Wiley & Sons. p. 77. ISBN 0471920592.
- ^ a b Harrison, Peter; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison–Wesley.
- ^ a b Harchol-Balter, M. (2012). "Scheduling: Preemptive, Non-Size-Based Policies". Performance Modeling and Design of Computer Systems. pp. 482–498. doi:10.1017/CBO9781139226424.038. ISBN 9781139226424.
- ^ Harchol-Balter, M. (2012). "Scheduling: Preemptive, Size-Based Policies". Performance Modeling and Design of Computer Systems. pp. 508–517. doi:10.1017/CBO9781139226424.040. ISBN 9781139226424.
- ^ Harchol-Balter, M. (2012). "Scheduling: SRPT and Fairness". Performance Modeling and Design of Computer Systems. pp. 518–530. doi:10.1017/CBO9781139226424.041. ISBN 9781139226424.
- ^ Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press. ISBN 9781439806586.
- ^ Wierman, A.; Harchol-Balter, M. (2003). "Classifying scheduling policies with respect to unfairness in an M/GI/1" (PDF). ACM SIGMETRICS Performance Evaluation Review. 31: 238–249. doi:10.1145/885651.781057.
- ^ Peterson, G. D.; Chamberlain, R. D. (1996). "Parallel application performance in a shared resource environment". Distributed Systems Engineering. 3: 9–19. doi:10.1088/0967-1846/3/1/003.
- ^ Pollaczek, F. (1930). "Über eine Aufgabe der Wahrscheinlichkeitstheorie". Mathematische Zeitschrift. 32: 64–75. doi:10.1007/BF01194620. S2CID 125053340.
- ^ Khintchine, A. Y (1932). "Mathematical theory of a stationary queue". Matematicheskii Sbornik. 39 (4): 73–84. Retrieved 2011-07-14.
- ^ Stewart, William J. (2009). Probability, Markov chains, queues, and simulation. Princeton University Press. p. 510. ISBN 978-0-691-14062-9.
- ^ Neuts, Marcel F. (1981). Matrix-geometric solutions in stochastic models: an algorithmic approach (Johns Hopkins Studies in Mathematical Sciences). Johns Hopkins University Press. p. 2. ISBN 0-486-68342-7.
- ^ Neuts, M. F . (1989). "Structured Stochastic Matrices of M/G/1 Type and Their Applications". New York: Marcel Dekk.
{{cite journal}}
:Cite 저널 요구 사항journal=
(도움말) - ^ Meini, B. (1998). "Solving m/g/l type markov chains: Recent advances and applications". Communications in Statistics. Stochastic Models. 14 (1–2): 479–496. doi:10.1080/15326349808807483.
- ^ Grimmett, G. R.; Stirzaker, D. R. (1992). Probability and Random Processes (second ed.). Oxford University Press. p. 422. ISBN 0198572220.
- ^ Bini, D. A.; Latouche, G.; Meini, B. (2005). Numerical Methods for Structured Markov Chains. doi:10.1093/acprof:oso/9780198527688.001.0001. ISBN 9780198527688.
- ^ Ross, Sheldon M.; Seshadri, Sridhar (1999). "Hitting time in an M/G/1 queue" (PDF). Journal of Applied Probability. 36 (3): 934–940. doi:10.1239/jap/1029349991. JSTOR 3215453.
- ^ Abate, J.; Choudhury, G. L.; Whitt, W. (1995). "Calculating the M/G/1 busy-period density and LIFO waiting-time distribution by direct numerical transform inversion" (PDF). Operations Research Letters. 18 (3): 113–119. doi:10.1016/0167-6377(95)00049-6.
- ^ Mitrani, I. (1997). "Queueing systems: average performance". Probabilistic Modelling. Cambridge University Press. pp. 74–121. doi:10.1017/CBO9781139173087.004. ISBN 9781139173087.
- ^ Abate, J.; Whitt, W. (1992). "Solving probability transform functional equations for numerical inversion" (PDF). Operations Research Letters. 12 (5): 275–281. doi:10.1016/0167-6377(92)90085-H.
- ^ Daigle, John N. (2005). "The Basic M/G/1 Queueing System". Queueing Theory with Applications to Packet Telecommunication. pp. 159–223. doi:10.1007/0-387-22859-4_5. ISBN 0-387-22857-8.