M/G/1 큐

큐잉 이론에서 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] 방정식에 의해 주어진다.

$(\displaystyle \pi (z) = harcfrac { (1-z) (1-\rho )g (\displayda (1-z)}) {g (\displayda (1-z)}})$

여기서 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]…로 이동할 수 있습니다.내장된 마르코프 체인은 전이 행렬을 가진다.

${\displaystyle P={\begin{pmatrix}a_{0}&, a_{1}&, a_{2}&, a_{3}&, a_{4}&, \cdots \\a_{0}&, a_{1}&, a_{2}&, a_{3}&, a_{4}&, \cdots \\0&, a_{0}&, a_{1}&, a_{2}&, a_{3}&, \cdots \\0&, 0&, a_{0}&, a_{1}&, a_{2}&, \cdots \\0&, 0&, 0&, a_{0}&, a_{1}&, \cdots \\\vdots, \vdots & &, \vdots &, \vdots &am.\vdots, \ddots \end{pmatrix}}& p/&}$

어디에

${\displaystyle a_{v}=\int _{0}^{\infty}e^{-\displayda u}{\frac {(\displayda u)^{v}}}{v!}}{\text{d}}F(u)~{\text{ for }v\geq 0}$

F(u)는 서비스 시간 분포이며 큐에 대한 작업의 포아송 도착 속도입니다.

이러한 형태의 생성 행렬 또는 블록 행렬을 가진 마르코프 사슬은 M/G/1 타입 마르코프 ^[12]사슬이라고 불리며, M. F.^[13][14] 뉴트럴에 의해 만들어진 용어이다.

M/G/1 큐는 트래픽 강도 $=$ ${\displaystyle eE\mathbb{}}$ (${\displaystyle G}$) { $displaystyle \rho$ =\$displayda \mathbb {E}$ ($G)}$ 이$$ 1 미만인 경우에만 정상 분포를 가지며, 이 경우 고유한 분포가 확률 생성 함수를 ^[15]갖습니다.

${\displaystyle G(s)=paramfrac {(1-\rho)(1-s)}{1-s/M_{S}(\lambda(s-1))}}}$

${\displaystyle {여기}_{}}$서 M S$(\$S$$})는 일반 서비스 시간의 모멘트 생성 함수입니다.M/G/1형 마르코프 모델의 정상 분포는 매트릭스 분석법을 ^[16]사용하여 계산할 수 있다.

바쁜 기간

비지 기간은 상태 0에 대한 방문 사이에 상태 1, 2, 3, ...에서 보낸 시간입니다.사용 기간의 예상 길이는 1/(μ-μ)입니다. 여기서 1/μ는 예상 서비스 시간 길이이고 ^[17]μ는 도착을 관리하는 포아송 프로세스의 비율입니다.비지 기간 확률 밀도 $함수{\displaystyle }$ ${\displaystyle (}$ ( ${\displaystyle s}$) \ $displaystyle \phi ($s )는$$ Kendall 함수^{[18][19]: 92} 방정식을 따르는 것을 보여줄 수 있다.

$\displaystyle \phi(s)=g[s+\displayda -\displayda \phi(s)]$

여기서 위의 g는 서비스 시간 분배 함수의 Laplace-Stieltjes 변환입니다.이 관계는 특별한 경우(M/M/1 큐 등)에만 정확하게 해결할 수 있지만, 어느 경우든 µ의 값을 계산할 수 있으며, 상한과 하한을 사용하여 반복함으로써 ^[20]분포 함수를 수치적으로 계산할 수 있습니다.

대기/응답 시간

대기시간 ^[21]분포의 라플라스-스틸테제스 변환에 대한 W는^* Pollaczek-Kinchine 변환에 의해 다음과 같이 주어진다.

${\displaystyle W^{\ast}(s)=param frac {(1-\rho)}{s-\paramda(1-g)}}}}$

여기서 g(s)는 서비스 시간 확률 밀도 함수의 Laplace-Stieltjes 변환입니다.

도착 정리

도착은 포아송 프로세스에 의해 결정되므로 도착 정리가 유지됩니다.

다중 서버

k개의 서버를 가진 M/G/k 큐의 많은 메트릭은 아직 해결되지 않은 문제로 남아 있습니다.다만, 몇개의 근사치와 경계가 알려져 있습니다.

「 」를 참조해 주세요.

• M/M/1 큐
• M/M/c 큐

레퍼런스