M/G/1 대기행렬(폴라첵–힌친) 계산기

도착이 포아송(M), 처리 시간은 아무 분포(G), 창구가 하나(1)인 대기행렬입니다. M/M/1이 «처리 시간이 지수분포»라는 강한 가정을 깔고 있는 것과 달리, M/G/1은 평균과 분산만 알면 평균 대기시간을 정확히 계산할 수 있습니다. 실제 시스템의 처리 시간이 지수분포인 경우는 드물기 때문에 더 널리 쓰입니다.

폴라첵–힌친 공식 Wq = λE[S²]/(2(1−ρ))에 처리 시간의 2차 적률 E[S²]가 들어가고, E[S²] = 분산 + 평균²이라 분산이 그대로 반영되기 때문입니다. 변동계수 Cv로 다시 쓰면 대기가 (1 + Cv²)/2에 정비례하므로, Cv = 0(언제나 같은 시간)이면 지수분포의 절반, Cv = 2면 2.5배가 됩니다.

처리 시간을 고르게 만드는 것이 서버를 늘리는 것보다 값이 쌀 때가 많습니다. 편차를 완전히 없애면 대기가 절반으로 떨어지기 때문입니다. 요청 크기 제한, 타임아웃, 무거운 작업을 별도 큐로 분리하기, 배치 크기 통일이 그 방법입니다. 물론 이용률이 이미 90%를 넘었다면 처리 능력 자체를 늘려야 합니다.

처리 시간 로그를 모아 표준편차를 평균으로 나눕니다. 웹 요청처럼 대부분 빠르고 가끔 아주 느린 작업이 섞이면 Cv가 2~3을 넘기도 합니다. p50과 p99의 차이가 클수록 Cv도 크다고 보면 대략 맞습니다.

아무 때나 도착하면 긴 작업 도중에 끼어들 확률이 그만큼 높기 때문입니다. 이것을 검사 역설이라 하며, 남은 시간의 평균이 E[S]/2가 아니라 E[S²]/(2E[S])가 됩니다. 처리 시간이 일정하면 정확히 절반이지만, 지수분포면 «기억이 없어» 남은 시간의 평균이 평균 처리 시간 그대로입니다.

보통 70~80%를 넘기지 않습니다. 공식의 분모가 (1 − ρ)라 ρ가 0.8에서 0.9로 가면 대기가 두 배, 0.9에서 0.95로 가면 다시 두 배가 됩니다. 이용률이 1에 닿으면 평균 대기시간 자체가 존재하지 않고 줄이 끝없이 길어집니다.

M/G/c에는 닫힌 식이 없고 근사식만 있어 이 계산기로는 다룰 수 없습니다. 처리 시간이 지수분포인 창구 여럿은 얼랑 C 공식으로, 창구 하나에 지수분포는 M/M/1 계산기로 풀 수 있습니다.

평균 대기시간은 달라지지 않습니다. 우선순위를 주든 무작위로 뽑든, 창구가 노는 일 없이 계속 일한다면 전체 평균은 같습니다. 달라지는 것은 «누가 오래 기다리는가»의 분포이며, 짧은 작업을 먼저 처리하면 평균 체감은 좋아지지만 긴 작업은 더 오래 기다립니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지며 입력한 값은 이 기기에만 남습니다.