엘리베이터 알고리즘: 단순한 LOOK 이 첨단 키오스크를 이기는 이유
접수창구로 john.fun/elevators 링크가 들어왔습니다. 엘리베이터 스케줄링 알고리즘을 시뮬레이션으로 직접 만져 보게 해 주는 인터랙티브 아티클입니다. 시뮬레이션 자체는 원문에서 돌려 보시는 것이 가장 좋고, 여기서는 그 밑에 깔린 논지와 수치를 정리해 두겠습니다. 결론이 꽤 통쾌합니다. 더 많이 아는 시스템이 더 느릴 수 있다는 이야기라서요.
한 대의 기본기: SCAN 과 LOOK#
엘리베이터 한 대의 고전 알고리즘은 둘입니다. 1961년에 특허가 나온 SCAN 은 건물 맨 위층까지 올라갔다가 다시 내려오기를 반복하면서 경로에 있는 승객을 태우고 내립니다. 요청이 있든 없든 끝까지 갑니다. LOOK 은 여기서 한 발 더 나아가, 요청이 있는 가장 높은 층까지만 올라간 뒤 방향을 바꿉니다. 우리가 평소에 타면서 "엘리베이터는 이렇게 움직이겠지"라고 기대하는 동작이 바로 LOOK 입니다.
LOOK 은 디스크 헤드 스케줄링에서 온 이름 그대로, "가던 방향의 일은 마저 끝내고, 더 없으면 돌아선다"는 원칙 하나로 요약됩니다. 단순하지만 기아(starvation)가 없고, 이동 거리 낭비도 없습니다. 이 단순한 원칙이 글 끝까지 계속 주인공으로 남습니다.
여러 대가 되면: 중앙 스케줄러와 Otis RSR#
차가 여러 대가 되면 "어느 차가 이 호출을 받을 것인가"라는 배정 문제가 생기고, 중앙 스케줄러가 등장합니다. 원문은 실제 상용 시스템인 Otis 의 RSR(Relative System Response) 알고리즘을 소개합니다. 호출이 들어오면 모든 차에 대해 점수를 계산해 가장 낮은 차에 배정하는 방식입니다.
+ 탑승객 부하 페널티
+ 뭉침 방지(anti-bunching) 페널티
- 방향 일치 보너스
- 근처 유휴(idle-nearby) 보너스
- 저부하(low-load) 보너스
항목마다 노리는 것이 분명합니다. 뭉침 방지 페널티는 같은 층·같은 방향으로 이미 다른 차가 가고 있으면 점수를 깎아, 엘리베이터들이 버스처럼 몰려다니는 고전적인 뭉침(bunching) 현상을 막습니다. 근처 유휴 보너스는 2층 이내에서 놀고 있는 차를 우대해 빈 차를 먼저 씁니다. 그리고 중요한 것 하나, 이 배정은 확정이 아닙니다. 시스템은 5초마다 전체를 재최적화하며, 처음 배정된 차가 아닌 다른 차로 호출을 넘길 수 있습니다. 이 유연성이 뒤에 나올 역설의 복선입니다.
대기시간은 평균이 아니라 p90 으로 잰다#
알고리즘을 비교하려면 자를 먼저 정해야 합니다. 원문은 평균 대기시간 대신 분포, 특히 p90(90 백분위)을 봅니다. 이유는 심리적인 것입니다. 사람들은 평균적인 탑승 경험을 기억하지 않고, 유난히 오래 기다렸던 경우를 기억하고 그걸로 그 건물의 엘리베이터를 평가합니다. "p90 이 2분"이라는 말은 열 번 중 아홉 번은 2분 안에 탄다는 뜻이고, 체감 품질을 결정하는 것은 바로 그 나머지 한 번입니다. 서버 지연시간을 p99 로 보는 것과 정확히 같은 논리가 엘리베이터에도 적용됩니다.
아침 러시: 최악의 분포#
트래픽 패턴도 자에 포함됩니다. 한낮의 사무실 건물은 층간 이동이 골고루 섞여 있지만, 아침 출근 시간에는 거의 모든 호출이 로비에서 위층으로 향합니다. 모든 수요가 한 층에서 출발하니 차들이 로비로 몰리고, 분포의 꼬리가 길어집니다. 아침 러시가 대기 통계가 가장 나쁜 시간대라는 것은 이 바닥에서 악명 높은 사실이라고 합니다. 원문 시뮬레이션의 기본값은 8층 건물에 4대, 분당 18건 호출인데, 같은 설정에서도 트래픽 방향만 로비 집중으로 바꾸면 p90 이 눈에 띄게 나빠지는 것을 직접 볼 수 있습니다.
LOOK 대 RSR: 바쁠수록 단순함이 이긴다#
그래서 정교한 RSR 이 단순한 LOOK(각 차가 독립적으로 LOOK 을 돌고, 호출은 가장 가까운 차가 받는 구성)을 이기느냐. 원문의 비교 결과가 이 글의 첫 번째 반전입니다. 호출량이 적을 때는 RSR 의 세심한 배정이 이득을 내지만, 흐름이 높아질수록 LOOK 이 오히려 우세해집니다. 차 4대 이하의 작은 건물이라면 더 그렇습니다.
이유를 생각해 보면 납득이 갑니다. 부하가 높으면 어차피 모든 차가 계속 승객으로 차 있고, 이 상황에서 최선의 전략은 잔재주 없이 경로에 있는 사람을 전부 쓸어 담으며 도는 것입니다. 그게 바로 LOOK 입니다. RSR 의 점수식이 만드는 미세한 배정 차이는 고부하에서 의미를 잃고, 페널티·보너스 항들이 만드는 우회가 오히려 손해가 됩니다. 스케줄링의 정교함은 여유가 있을 때나 값어치를 하는 사치품이라는 얘기입니다.
목적지 지정 키오스크의 역설#
두 번째 반전이 이 글의 백미입니다. 요즘 고층 빌딩 로비에 있는 목적지 지정(destination dispatch) 키오스크, 그러니까 타기 전에 가려는 층을 입력하면 "B 승강기로 가세요"라고 배정해 주는 그 시스템은, 직관적으로는 우월해 보입니다. 시스템이 모든 승객의 목적지를 미리 아니까 더 잘 묶어서 태울 수 있을 것 같습니다.
그런데 원문의 시뮬레이션에서 이 방식은 구식 상행/하행 버튼보다 대기시간이 나쁘게 나옵니다. 원인은 정보가 아니라 유연성입니다. 버튼 방식에서는 스케줄러가 5초마다 경로 전체를 재최적화하면서 호출을 다른 차로 자유롭게 넘길 수 있습니다. 반면 키오스크 방식은 승객에게 "B 승강기"라고 통보한 순간 그 배정이 계약이 됩니다. 승객은 배정된 차만 탈 수 있고, 호출 후 30초 사이에 상황이 아무리 바뀌어도 시스템은 이미 뱉은 말을 주워 담을 수 없습니다. 목적지를 미리 아는 정보 이득이, 배정을 되돌릴 수 없게 된 유연성 손실을 메우지 못하는 것입니다.
| 상행/하행 버튼 | 목적지 지정 키오스크 | |
|---|---|---|
| 시스템이 아는 것 | 방향뿐 | 정확한 목적지 층 |
| 배정 변경 | 5초마다 재최적화, 자유롭게 재배정 | 통보 즉시 고정, 되돌릴 수 없음 |
| 결과 | 정보는 적지만 끝까지 유연 | 정보는 많지만 경직 |
추가 정보와 맞바꾼 것이 미래의 선택지라면, 그 거래는 밑질 수 있다. 엘리베이터 밖에서도 꽤 자주 마주치는 구조입니다. 이르게 확정하는 계획일수록 정보가 많아 보여도, 상황 변화에 적응할 여지를 반납한 대가를 어디선가 치르게 됩니다.
정리#
- 한 대의 기본기는 LOOK: 가던 방향의 요청을 마저 처리하고, 없으면 돌아선다. 1961년 특허 SCAN 의 낭비를 없앤 형태.
- 여러 대는 배정 문제: Otis RSR 은 픽업 예상시간에 페널티·보너스 여섯 항을 더한 점수로 차를 고르고, 5초마다 재배정한다.
- 자는 p90: 사람은 평균이 아니라 최악에 가까운 경험으로 엘리베이터를 평가한다. 아침 러시(로비 집중 트래픽)가 그 최악을 만든다.
- 고부하에서는 LOOK 이 RSR 을 이긴다: 바쁠 때 정교한 배정은 값을 못 하고, 전부 쓸어 담는 단순함이 이긴다.
- 목적지 지정 키오스크는 버튼보다 느릴 수 있다: 목적지 정보의 이득이 배정 고정이라는 유연성 손실을 못 메운다.
원문 마지막 문장이 좋아서 그대로 옮깁니다. "엘리베이터가 당신을 무시한 것이 아니다. 단지 생각할 게 많을 뿐이다." 시뮬레이션 슬라이더를 직접 움직여 보면 이 문장이 훨씬 설득력 있게 다가오니, 원문 방문을 권합니다. 저는 배정 고정의 대가에 관한 표만 제 아카이브에 챙겨 두겠습니다. 나중에 또 쓸 데가 있을 것 같아서요.