창구나 서버에 처리 요청이 도착하여, 비기를 기다렸다가 처리를 받는 모습을 확률 모델로 나타내어 대기 시간이나 행렬의 길이를 구하는 이론. 도착 분포, 서비스 시간 분포, 창구 수를 'M/M/1'처럼 늘어놓는 켄달 기호로 나타낸다. M/M/1 모델에서는 사용률 ρ = 도착률 λ × 평균 서비스 시간 Ts를 사용하여, 평균 대기 시간을 ρ/(1 − ρ) × Ts로 구한다. 컴퓨터의 성능 평가, 네트워크 지연, 공장의 재공품 분석 등에 사용된다.
일본어 명칭: 待ち行列理論
대기행렬 이론(Queueing Theory)은(는) 확률·통계와 대기행렬 등 1개 분야의 연습 문제 6개에 나와요.
분야: 확률·통계와 대기행렬
대기행렬 모델은 '도착 분포/서비스 시간 분포/창구 수'의 형태로 나타냅니다. M은 마르코프성을 나타내며, 도착이라면 푸아송 도착(간격이 지수 분포), 서비스 시간이라면 지수 분포를 의미합니다. D는 일정한 시간, G는 일반 분포입니다. M/M/1은 무작위 도착과 무작위 서비스 시간의 창구가 1개인 모델로, 기다리는 장소에 제한이 없고, 선착순으로 처리하며, 충분한 시간이 지난 정상 상태를 생각하는 것이 기본 전제입니다.
사용률은 ρ = λ × Ts로, 창구가 바쁜 시간의 비율입니다. M/M/1에서는 평균 대기 시간 Wq = ρ/(1 − ρ) × Ts, 평균 응답 시간 W = Wq + Ts = Ts/(1 − ρ), 시스템 안에 있는 평균 개수 L = ρ/(1 − ρ)입니다. 이들은 리틀의 법칙 L = λW로 연결되어 있으며, 예를 들어 λ = 3건/분, Ts = 15초라면 ρ = 0.75, Wq = 45초, W = 60초, L = 3건이 됩니다.
Wq ÷ Ts = ρ/(1 − ρ)는 사용률 0.5에서 1배, 0.8에서 4배, 0.9에서 9배, 0.95에서 19배로, 사용률이 1에 가까워질수록 급격히 커집니다. 우연히 도착이 겹쳐서 생긴 행렬을 해소하기 위한 빈 시간 1 − ρ가 적어지기 때문입니다. 그래서 응답 시간이 중요한 시스템에서는 사용률에 여유를 두고 설계합니다.
정답: A. 0.8
사용률 ρ는 도착률 λ와 평균 서비스 시간 Ts의 곱으로, 창구가 바쁜 시간의 비율을 나타냅니다. 단위를 맞추면 4분 = 1/15시간이므로 ρ = 12 × 1/15 = 0.8입니다. 서비스율 μ = 15건/시간을 사용하여 ρ = λ/μ = 12/15로 구해도 같습니다.
정답: C. 60초
사용률은 ρ = 3건/분 × 15초 ÷ 60초 = 0.75입니다. 평균 대기 시간은 Wq = ρ/(1 − ρ) × Ts = 0.75/0.25 × 15 = 45초이고, 여기에 처리 시간 15초를 더하면 평균 응답 시간은 45 + 15 = 60초입니다. Ts/(1 − ρ) = 15/0.25 = 60초로 구해도 같습니다.
서비스 시간이 일정하다면 M/D/1처럼, 실제에 가까운 모델을 사용합니다. M/D/1의 평균 대기 시간은 M/M/1의 정확히 절반이 되며, 서비스 시간의 흩어짐이 작을수록 대기 시간은 짧아집니다. 복잡한 시스템에서는 시뮬레이션으로 확인하는 경우도 많으며, 어느 경우든 리틀의 법칙은 성립합니다.
전체 처리 능력이 같다면, 2배 빠른 창구 1개 쪽이 창구 2개(1개의 행렬을 공유하는 M/M/2)보다 평균 응답 시간이 짧아집니다. 한편 행렬에서 기다리는 시간만 비교하면 창구 2개 쪽이 짧아집니다. 창구가 2개라도 창구마다 따로따로 행렬을 만들면, 한쪽이 비어 있는데 다른 쪽에서 기다리는 일이 생기므로, 1개의 행렬을 공유하는 방식보다 대기 시간이 길어집니다.
대기행렬의 M/M/1 모델의 첫 번째 M은 이러한 도착을 나타냅니다.
서버에 대한 요청이 1분당 평균 6건의 푸아송 도착(서로 독립적인 무작위 도착)으로 도착한다. 도착 간격이…방식 A는 도착률이 절반인 M/M/1이 2개 나란히 있는 것으로 볼 수 있습니다.
같은 속도의 창구가 2개 있다. 방식 A에서는 이용자가 도착했을 때 어느 한 창구를 같은 확률로 골라, 창…지수 분포(Exponential Distribution) 가설 검정(Hypothesis Testing) 기댓값(Expected Value) 베이즈 정리(Bayes' Theorem) 사분위수(Quartile) 상관 계수(Correlation Coefficient) 순열과 조합(Permutations and Combinations) 신뢰 구간(Confidence Interval) 이항 분포(Binomial Distribution) 정규 분포(Normal Distribution)