07. 큐잉 이론 최소한

앞 글에서 단일 서버 대기열을 DES로 모델링하는 법을 보았다. 그런데 시뮬레이터를 만들고 나면 곧바로 의문이 생긴다. “내 코드가 정말 맞게 돌아가는 걸까?” 시뮬레이션 결과로 평균 대기 손님 수가 4.0이 나왔다 한들, 비교할 정답이 없으면 그것이 옳은지 알 수 없다.

다행히 충분히 단순한 대기열은 수식으로 정확한 답을 구할 수 있다. 그 분야가 큐잉 이론(queueing theory)이다. 이 글은 큐잉 이론을 깊이 파려는 것이 아니라, 시뮬레이터 검증의 기준선(sanity check)으로 쓸 최소한만 추린다. 다음 글에서 직접 만든 시뮬레이터의 결과를 여기 공식과 맞춰 볼 것이다.

대기열을 표기하는 법: Kendall 표기

대기열은 A/B/c 형태의 Kendall 표기로 나타낸다.

• A: 도착 과정(arrival)의 분포
• B: 서비스 시간(service)의 분포
• c: 서버의 개수

여기서 분포 자리에는 M(Markovian — 도착 간격/서비스 시간이 지수분포, 즉 포아송 과정), D(Deterministic — 일정), G(General — 임의 분포) 등이 들어간다. 그래서

• M/M/1: 지수 도착·지수 서비스·서버 1개 (가장 기본)
• M/M/c: 위와 같되 서버 $c$개
• M/G/1: 지수 도착·임의 서비스 분포·서버 1개

처럼 쓴다. 이 글은 가장 단순하고 닫힌 해가 깔끔한 M/M/1에 집중한다.

기본량과 안정 조건

세 가지 기본 비율로 시작한다.

• $\lambda$ — 도착률(arrival rate): 단위 시간당 평균 도착 수.
• $\mu$ — 서비스율(service rate): 서버가 쉬지 않을 때 단위 시간당 평균 처리 수. (평균 서비스 시간은 $1/\mu$.)
• $\rho$ — 이용률(utilization) 또는 traffic intensity: 서버가 바쁜 시간의 비율.

단일 서버에서는

$$\rho =\frac{\lambda }{\mu }$$

이다. 여기서 결정적으로 중요한 것이 안정 조건(stability condition) $\rho <1$, 즉 $\lambda <\mu$다. 도착이 처리 능력보다 빠르면($\rho \ge 1$) 큐는 무한히 길어져 정상상태(steady state)가 존재하지 않는다. 이 조건이 깨진 시스템을 시뮬레이션하면 큐 길이가 끝없이 증가하는데, 이는 버그가 아니라 시스템 자체의 성질이다.

모든 대기열을 잇는 법칙: Little’s Law

큐잉 이론에서 가장 아름답고 보편적인 결과가 Little’s law다.

$$L=\lambda W$$

• $L$: 시스템 안에 있는 평균 손님 수 (시간 평균)
• $W$: 손님 한 명이 시스템에 머무는 평균 시간 (체류시간)
• $\lambda$: 도착률

앞 글에서 구분한 시간 평균 $L$과 개체 평균 $W$를 도착률 하나로 잇는 식이다. 놀라운 점은 이 법칙이 분포에 대한 어떤 가정도 필요로 하지 않는다는 것이다. 도착이 포아송이든 아니든, 서비스가 어떤 분포든, 서버가 몇 개든 — 정상상태에 도달하는 안정적인 시스템이면 무조건 성립한다. 그래서 시뮬레이터 검증의 1차 점검 도구로 매우 유용하다. 큐만 떼어 보면 $L_q=\lambda W_q$도 똑같이 성립한다(아래 첨자 $q$는 “큐에서 기다리는” 부분).

M/M/1의 닫힌 해

M/M/1에 대해서는 모든 주요 지표가 깔끔한 공식으로 나온다($\rho <1$ 가정).

$$\begin{array}{rlrl}L& =\frac{\rho }{1-\rho }& & \text{시스템 내 평균 손님 수}\\ L_q& =\frac{{\rho }^2}{1-\rho }& & \text{큐에서 기다리는 평균 수}\\ W& =\frac{1}{\mu -\lambda }& & \text{평균 체류시간}\\ W_q& =\frac{\rho }{\mu -\lambda }& & \text{평균 대기시간}\end{array}$$

또한 시스템에 $n$명이 있을 정상상태 확률은 $P_n=(1-\rho ){\rho }^n$이고, 서버가 비어 있을 확률은 $P_0=1-\rho$다. 이 식들은 서로 Little’s law로 연결되어 있음을 확인할 수 있다($L=\lambda W$, $L_q=\lambda W_q$).

ρ가 1에 가까워지면: 비선형 폭발

이 공식들에서 가장 중요한 직관 하나를 꼭 가져가자. $L=\rho /(1-\rho )$를 보면, 이용률 $\rho$가 1에 가까워질수록 평균 손님 수가 폭발적으로 커진다.

이용률 $\rho$	평균 손님 수 $L$
0.5	1
0.8	4
0.9	9
0.95	19
0.99	99

이용률을 50%에서 90%로 올리면 손님 수는 1명에서 9명으로 9배가 된다. 직관적으로 “장비를 100% 가깝게 굴리면 효율적”일 것 같지만, 실제로는 이용률을 한계까지 밀어붙일수록 대기가 비선형으로 폭증한다. 이 혼잡의 비선형성은 대기열을 다루는 모든 분야 — 통신망, 공장, 서비스 — 의 근본 직관이며, 무작위성이 있는 한 피할 수 없다.

왜 그래도 시뮬레이션이 필요한가

큐잉 이론이 이렇게 깔끔한 답을 준다면 시뮬레이션은 왜 필요할까? 현실이 M/M/1처럼 단순한 경우가 거의 없기 때문이다. 서비스 시간이 지수분포가 아니고(M/G/1조차 공식이 훨씬 복잡해진다), 여러 대기열이 네트워크로 얽히고, 우선순위·배치 처리·서버 고장이 끼어들면 — 닫힌 해는 곧 손을 든다. 바로 그 지점이 1부에서 말한 “수식으로 풀 수 없을 때 시뮬레이션”의 영역이다.

그러므로 큐잉 이론과 시뮬레이션의 올바른 관계는 이렇다. 단순한 경우에 대해 큐잉 이론으로 시뮬레이터를 검증해 신뢰를 쌓고, 그 검증된 엔진을 복잡한 현실로 확장한다. 다음 글에서 정확히 이 일을 한다.

정리

• 대기열은 A/B/c(Kendall 표기)로 나타내며, M/M/1이 가장 단순하다.
• 핵심량은 도착률 $\lambda$, 서비스율 $\mu$, 이용률 $\rho =\lambda /\mu$이고, 안정 조건은 $\rho <1$이다.
• Little’s law ($L=\lambda W$)는 분포 가정 없이 성립하는 보편 법칙으로, 시뮬레이터 검증의 1차 도구다.
• M/M/1은 $L=\rho /(1-\rho )$ 등 닫힌 해를 가지며, $\rho \to 1$에서 대기가 비선형으로 폭발한다.
• 현실은 대부분 이 가정을 벗어나므로, 큐잉 이론으로 검증한 시뮬레이터를 복잡한 경우로 확장하는 것이 올바른 전략이다.

다음 글에서는 6번 글의 사건 중심 관점을 Python 코드로 옮겨 M/M/1을 바닥부터 구현하고, 그 결과를 위 공식과 비교해 본다.