대기행렬 이론

대기행렬 이론(Queueing Theory)은 고객이 서비스를 받으려고 줄을 서는 시스템을 확률 모형으로 나타내어, 대기 길이·대기 시간·서버 이용률 같은 성능을 분석하는 이론이다.

개요

1909년 덴마크의 얼랑(A. K. Erlang)이 전화 교환기의 회선 수를 정하려고 연구한 데서 시작했다. 고객의 도착과 서비스 시간이 무작위이면 서버가 평균적으로 여유가 있어도 순간적으로 대기열이 생긴다. 대기행렬 이론은 도착과 서비스를 확률 분포로 모형화해 서비스 수준과 자원 비용의 균형점을 찾게 해 준다.

IT 에서는 웹 서버·DB 의 용량 산정, 스레드 풀과 연결 풀 크기 결정, 라우터 버퍼와 큐잉 지연 분석, CPU·디스크 스케줄링, 콜센터 상담원 수 산정 등에 쓴다.

구성 요소

구성 요소	내용
고객 모집단	서비스를 요청할 수 있는 대상. 무한(웹 사용자) 또는 유한(공장 기계 몇 대)
도착 과정	고객이 오는 방식. 평균 도착률 λ. 무작위 도착은 포아송 과정(도착 간격은 지수 분포)으로 본다
대기열	대기 공간의 용량(무한/유한). 유한하면 넘친 고객은 거절(손실)된다
대기 규칙	대기열에서 다음 고객을 고르는 규칙(아래 처리 기법)
서비스 시설	서버 수와 배치, 서비스 시간 분포. 평균 서비스율 μ
이탈	서비스를 마치고 시스템을 떠남

켄달 표기법

대기 시스템을 A/B/c/K/N/D 로 나타낸다. 뒤의 세 항목은 생략하면 K=∞, N=∞, D=FCFS 로 본다.

A: 도착 간격 분포, B: 서비스 시간 분포 — M(지수 분포, 마르코프), D(일정), E_k(얼랑), G(일반 분포)
c: 서버 수, K: 시스템 수용 한도, N: 고객 모집단 크기, D: 대기 규칙
예: M/M/1 — 포아송 도착, 지수 서비스, 서버 1개 / M/M/c — 서버 c 개 / M/D/1 — 서비스 시간 일정

성능 척도

기호	의미
ρ	서버 이용률(트래픽 강도) = λ / (cμ). 1보다 작아야 대기열이 무한히 늘지 않는 안정 상태가 된다
L	시스템 안의 평균 고객 수(대기 + 서비스 중)
L_q	대기열의 평균 고객 수
W	시스템 안의 평균 체류 시간
W_q	평균 대기 시간
P_n	시스템에 고객이 n 명 있을 확률

척도들은 리틀의 법칙 L = λW, L_q = λW_q 와 W = W_q + 1/μ 로 서로 연결된다. 분포의 종류와 관계없이 성립하므로 하나를 알면 나머지를 구할 수 있다.

주요 모형

M/M/1

척도	식
이용률	ρ = λ / μ
빈 시스템 확률	P₀ = 1 − ρ
n 명 있을 확률	P_n = (1 − ρ)ρⁿ
L	ρ / (1 − ρ) = λ / (μ − λ)
L_q	ρ² / (1 − ρ)
W	1 / (μ − λ)
W_q	ρ / (μ − λ)

계산 예 — 시간당 평균 8건 요청(λ = 8)이 오고 서버가 시간당 평균 10건(μ = 10)을 처리하면

ρ = 0.8, L = 0.8/0.2 = 4건, L_q = 0.64/0.2 = 3.2건
W = 1/(10 − 8) = 0.5시간, W_q = 0.8/2 = 0.4시간 (리틀의 법칙 L = λW = 8 × 0.5 = 4 와 일치)

이용률이 1에 가까워질수록 L = ρ/(1 − ρ) 은 비선형으로 폭증한다. ρ 가 0.5 → 0.8 → 0.9 → 0.95 일 때 L 은 1 → 4 → 9 → 19 다. 서버 이용률을 70~80% 이하로 계획하는 근거다.

그 밖의 모형

M/M/c — 서버 c 개가 하나의 대기열을 공유한다. 대기 확률은 얼랑 C 공식으로 구한다. 같은 총 처리 능력이면 대기열 하나를 공유하는 편이 서버별로 줄을 따로 세우는 것보다 평균 대기가 짧다.
M/M/c/c — 대기 공간 없이 서버가 다 차면 거절되는 손실 시스템. 얼랑 B 공식으로 호손실률을 구해 전화 회선 수를 정한다.
M/D/1 — 서비스 시간이 일정하면 L_q = ρ² / [2(1 − ρ)] 로 M/M/1 의 절반이다. 서비스 시간의 변동이 대기를 늘린다.
M/G/1 — 서비스 시간이 일반 분포이면 폴라체크-힌친 공식 L_q = (λ²σ² + ρ²) / [2(1 − ρ)] 을 쓴다(σ: 서비스 시간 표준편차).
대기 네트워크(Jackson Network) — 웹 서버 → WAS → DB 처럼 여러 대기 시스템이 이어진 경우

처리 기법

대기 규칙(서비스 순서)

기법	내용	예
FCFS / FIFO	먼저 온 고객부터 처리	은행 창구, 프린터 스풀
LCFS / LIFO	나중에 온 고객부터 처리	스택, 창고 적재물
SIRO	무작위로 선택	경합 기반 매체 접근
우선순위(Priority)	등급이 높은 고객 먼저. 선점형·비선점형	응급실, QoS 의 우선순위 큐잉
SPT / SJF	서비스 시간이 짧은 고객 먼저. 평균 대기 시간 최소	CPU 스케줄링
라운드 로빈	정해진 시간만큼 번갈아 서비스	시분할 CPU 스케줄링
가중 공정 큐잉	흐름별 큐에 가중치에 비례해 대역폭 배분	WFQ

서비스 시설 배치

단일 경로·단일 단계 — 서버 1개를 한 번 거친다(M/M/1).
다중 경로·단일 단계 — 병렬 서버 여러 개 중 하나에서 처리(M/M/c). 로드 밸런서 뒤의 서버 팜
단일 경로·다중 단계 — 여러 서버를 차례로 거친다. 웹 → WAS → DB
다중 경로·다중 단계 — 단계마다 병렬 서버가 있다.

고객 행동

포기(Balking) — 줄이 길어 처음부터 들어오지 않는다.
이탈(Reneging) — 기다리다 떠난다(웹 요청 타임아웃).
이동(Jockeying) — 더 짧은 줄로 옮겨 간다.

분석 방법

해석적 방법 — 위의 공식으로 정상 상태 성능을 계산한다. 가정(포아송 도착, 지수 서비스)이 맞을 때 쓴다.
시뮬레이션 — 도착·서비스를 난수로 발생시켜 성능을 추정한다(몬테카를로 시뮬레이션). 복잡한 다단계 시스템에 쓴다.
측정 기반 검증 — 성능 테스트로 측정한 처리량·응답 시간과 모형을 비교해 용량 계획을 세운다.

같이 보기