어제, 엘리베이터의 운행 방식과 작동 원리를 다룬 인터랙티브 해설 기사가 세계 최대 개발자 커뮤니티인 Hacker News의 1위를 차지했습니다. 771개의 추천과 198개의 댓글이 달릴 만큼, 개발자들은 하루 종일 엘리베이터 알고리즘을 두고 뜨거운 토론을 벌였습니다.
이 논의의 출발점은 직관에 반하는 한 가지 사실이었습니다. 최근 신축 오피스 빌딩에서는 엘리베이터 내부의 층수 버튼을 없애고, 로비에서 먼저 목적지를 입력하면 탑승할 엘리베이터를 지정해 주는 ‘목적층 사전 지정 시스템(Destination Dispatch)‘을 도입하고 있습니다. 하지만 수많은 시뮬레이션 환경에서 이 최신 시스템이 기존의 단순한 위/아래 버튼보다 오히려 느리다는 결과가 나왔습니다. 댓글창에는 엘리베이터 엔지니어, 디스크 드라이버 개발자, 호텔 시설 관리자 등이 모여 각자의 경험과 관점을 공유했습니다.
엘리베이터는 누구나 매일 이용하는 장치지만, 그 이면에 숨겨진 제어 알고리즘을 잘 아는 사람은 많지 않습니다. 원문 기사는 속도를 조절할 수 있는 애니메이션과 직접 층수 및 엘리베이터 수를 추가할 수 있는 인터랙티브 시뮬레이션을 통해 각 알고리즘에 따른 대기 시간 분포의 변화를 시각적으로 보여줍니다. 여기에 Hacker News 커뮤니티에서 공유된 현실 세계의 흥미로운 상세 정보들을 종합하여 정리했습니다.
엘리베이터 스케줄링이 어려운 이유
먼저 물리적인 제약 조건을 살펴보아야 합니다. 엘리베이터 한 대는 한 번에 한 방향으로만 이동할 수 있고, 탑승 인원에 제한이 있으며, 층수가 높아질수록 선택지가 폭발적으로 늘어납니다. 여러 대의 엘리베이터가 동시에 작동할 때 누구를 먼저 태우고 어떤 순서로 정차할 결정하는 문제는 고도의 스케줄링 과제가 됩니다.
승객의 이동 흐름 또한 심한 비대칭성을 보입니다. 오피스 빌딩의 출근 시간에는 거의 모든 사람이 로비에서 고층으로 이동하고, 퇴근 시간에는 반대로 내려옵니다. 점심시간에는 양방향 혼잡이 복합적으로 발생합니다. 동일한 제어 규칙이라도 시간대에 따라 성능이 극명하게 달라지며, 특히 출근 시간대의 대기 시간 최적화는 가장 해결하기 어려운 문제입니다.
군관리(Group Control) 제어 역시 난이도를 높이는 요인입니다. 오피스 빌딩에서는 보통 5~6대의 엘리베이터가 하나의 호출 버튼 패널을 공유합니다. 승객이 상향 버튼을 누르면 시스템은 어떤 엘리베이터를 보낼지 결정해야 합니다. 이 결정은 엘리베이터의 이동, 승객의 탑승, 새로운 요청의 발생에 따라 매 순간 재계산됩니다. 단일 엘리베이터의 제어 규칙은 단순하지만, 여러 대의 엘리베이터를 협조 제어하는 것은 매우 까다롭습니다.
전통적인 엘리베이터의 작동 방식
가장 널리 쓰이는 표준 알고리즘은 1961년에 이미 특허가 출원된 ‘SCAN’ 알고리즘입니다. 엘리베이터가 로비에서 최상층까지 일직선으로 운행하면서 경로 상에 요청이 있는 층마다 정차하여 승객을 태우고, 최상층에 도달하면 방향을 바꾸어 내려옵니다. 노선버스가 길을 따라 승객을 태우는 방식과 유사합니다. 컴퓨터 과학자들은 하드디스크의 헤드가 데이터 블록을 읽는 방식이 엘리베이터와 완전히 동일하다는 점을 발견하고 이 명칭을 그대로 빌려와 ‘엘리베이터 알고리즘’이라고 불렀습니다.
하지만 모든 승객이 최상층까지 가는 것은 아닙니다. 이에 따라 개선된 ‘LOOK’ 알고리즘이 등장했습니다. LOOK 방식은 현재 진행 방향으로 요청된 가장 먼 층까지만 운행한 뒤 곧바로 방향을 전환합니다. 이는 사람들이 익숙하게 경험하는 방식으로, 한 방향으로 끝까지 가면서 중간 요청을 처리하고 앞서 남아있는 요청이 없으면 방향을 바꾸는 단순하고 명확한 원칙을 따릅니다.
그림: John.fun 인터랙티브 해설의 엘리베이터 시뮬레이션 데모. 출처: john.fun/elevators
엘리베이터의 성능을 평가하는 핵심 기준은 대기 시간입니다. 구체적으로는 대기 시간의 분포를 확인합니다. p50은 승객의 절반이 기다리는 시간이며, p90은 90%의 승객이 대기하는 시간의 상한선입니다. 평균 대기 시간을 기억하는 사람은 거의 없으며, 사람들의 기억에 남는 것은 ‘한참 동안 기다렸던’ 몇 번의 불쾌한 경험입니다. 따라서 알고리즘 최적화의 주된 목표는 p90의 극단적인 대기 시간을 줄이는 데 맞춰집니다.
그림: John.fun 인터랙티브 해설의 대기 시간 분포 시뮬레이션. 출처: john.fun/elevators
여기에는 명확한 트레이드오프가 존재합니다. 대기 시간이 짧다고 해서 실제 탑승 시간이 짧아지는 것은 아닙니다. 더 많은 사람을 중간에 태우기 위해 자주 정차할수록 카 내부에 탑승해 있는 시간은 길어집니다. 대기 시간과 탑승 시간 중 하나를 최적화하면 다른 하나가 희생되는 경우가 많으며, 스케줄링 알고리즘은 이 둘 사이에서 균형을 잡는 역할을 합니다.
더 똑똑하다고 해서 반드시 더 나은 것은 아니다
여러 대의 엘리베이터를 제어할 때 가장 기본적인 방법은 중앙 중앙 제어로, 새로운 요청이 들어오면 가장 가까운 엘리베이터를 배정하는 것입니다. 하지만 엔지니어들은 이에 만족하지 않았습니다. 오티스(Otis)가 개발한 RSR(Relative System Response) 알고리즘은 예상 도착 시간, 현재 탑승 인원, 다른 엘리베이터와의 뭉침 현상, 방향 일치 여부, 인근 빈 차량 유무 등을 종합하여 각 엘리베이터에 실시간 점수를 부여합니다. 점수가 가장 뛰어난 엘리베이터가 승객을 태우러 이동합니다. 이 시스템은 5초마다 배정을 재최적화하므로, A 엘리베이터가 지연되면 B 엘리베이터로 작업이 자동으로 전환될 수 있습니다.
RSR에는 뭉침 방지 규칙이 포함되어 있습니다. 이미 다른 엘리베이터가 해당 층으로 이동 중이라면 추가로 배정하지 않습니다. 오피스 빌딩에서 두 대의 엘리베이터가 동시에 도착해 문이 열리는 현상은 이 뭉침 방지 알고리즘이 제대로 작동하지 않은 결과입니다. 실시간으로 점수가 계산되며, 엘리베이터가 한 층을 이동할 때마다 각 카의 평가 점수가 변경됩니다.
그러나 시뮬레이션 결과는 뜻밖이었습니다. 교통량이 많아질수록 복잡한 RSR보다 단순한 LOOK 알고리즘이 오히려 뛰어난 성과를 보였습니다. 소형 건물이나 엘리베이터 대수가 적은 환경에서도 LOOK 알고리즘이 우위를 점하는 경우가 많았습니다. 규칙이 많아진다고 해서 반드시 속도가 빨라지는 것은 아니며, 때로는 단순함을 유지하는 것이 정답입니다. 이는 엔지니어링 측면에서 알고리즘의 복잡성과 성능 향상 사이에 실제 사용 환경이라는 변수가 존재함을 시사합니다.
신형 목적층 지정 시스템을 둘러싼 논란
목적층 사전 지정 시스템(Destination Dispatch)의 논리는 매우 간결합니다. 승객 개개인이 가고자 하는 층을 시스템이 미리 파악한다면, 같은 층으로 가는 승객들을 동일한 엘리베이터에 탑승시켜 중간 정차 횟수를 줄일 수 있습니다. 정보가 사전에 완벽하게 제공되므로 이론적으로는 훨씬 효율적이어야 합니다. 실제로 호텔, 병원, 초고층 오피스 빌딩에서 이러한 키오스크 방식이 광범위하게 적용되고 있습니다.
하지만 기사의 시뮬레이션은 반대의 결론을 보여주었습니다. 대부분의 경우 목적층 지정 시스템이 기존의 위/아래 버튼 방식보다 느렸습니다. 원인은 ‘유연성의 상실’에 있었습니다. 기존 엘리베이터는 5초마다 운행 경로를 재최적화할 수 있지만, 목적층 지정 시스템은 키오스크에서 버튼을 누르는 순간 승객을 특정 엘리베이터에 고정시킵니다. 30초 뒤 상황이 완전히 바뀌더라도 시스템은 배정을 변경할 수 없습니다. 사전 정보 습득으로 얻는 이점이 유연성 상실로 인한 손실을 상쇄하지 못하는 것입니다.
댓글창에서는 이에 대한 반론이 제기되었습니다. 현장 엔지니어들은 실제 오피스 빌딩의 점심시간에는 대규모 인원이 동시에 식당 층으로 이동하기 때문에, 일괄 처리 방식에 특화된 목적층 지정 시스템이 매우 유리하다고 지적했습니다. 또한 호텔의 아침 피크 타임에는 시스템이 조식 전용 모드로 전환되기도 합니다. 시뮬레이션이 이러한 특수 트레이크 패턴을 반영하지 않았기 때문에 기존 알고리즘에 유리한 결과가 나왔다는 설명입니다. 두 주장 모두 타당하며, 목적층 지정 시스템의 효율성은 승객의 이동 패턴에 따라 달라집니다. “새로운 시스템이 항상 더 빠르다”는 명제는 절대적이지 않습니다.
그림: John.fun 인터랙티브 해설의 목적층 지정 시스템 데모. 출처: john.fun/elevators
하드디스크는 말아놓은 엘리베이터다
댓글에서 눈길을 끈 흥미로운 사실은 SCAN 알고리즘이 컴퓨터 하드디스크의 헤드 스케줄링 알고리즘과 완전히 동일하다는 점입니다. 위키백과에서도 이 알고리즘은 ‘엘리베이터 알고리즘’과 ‘SCAN’이라는 두 가지 이름으로 등재되어 있습니다. SCAN 알고리즘은 본래 디스크 읽기/쓰기 요청을 스케줄링하기 위해 개발되었습니다.
기계식 하드디스크 내부에서 헤드는 엘리베이터가 층 사이를 이동하며 승객을 태우듯 플래터의 트랙 사이를 탐색하며 데이터를 읽고 씁니다. 디스크 표면에 흩어진 요청에 대해 헤드는 한 방향으로 이동하며 경로상의 요청을 처리하고, 끝에 도달하면 반대 방향으로 이동합니다. 하드디스크의 헤드 탐색(Seek) 동작은 컴퓨터 전체에서 가장 느린 기계적 동작 중 하나이며, 스케줄링을 통해 아끼는 것은 바로 이 물리적인 이동 시간입니다. 한 개발자는 이를 가리켜 “하드디스크는 둥글게 말아놓은 엘리베이터에 불과하다”고 비유했습니다.
컴퓨터 과학 교재에서 SCAN 알고리즘은 디스크 I/O 스케줄링의 고전적인 장으로 다뤄집니다. 1961년 엘리베이터 특허와 운영체제 교과서는 동일한 개념적 뿌리를 공유합니다. 도널드 커누스(Donald Knuth) 역시 《컴퓨터 프로그래밍의 예술(TAOCP)》에서 코루틴을 설명할 때 엘리베이터 시뮬레이션을 대표 예시로 들었습니다. 하나는 사람을 옮기고 다른 하나는 데이터를 옮기지만, 제어 스케줄링의 논리는 완전히 일치합니다.
오늘날 이 알고리즘은 탐색 시간이 거의 0에 가까운 솔리드 스테이트 드라이브(SSD)의 보급으로 하드디스크 분야에서는 점차 퇴장하고 있습니다. 하지만 엘리베이터 내부에서는 지금 이 순간에도 매일 작동하고 있습니다. 1961년 특허에서 시작된 동일한 아이디어가 기계 공학과 컴퓨터 과학이라는 두 분야를 넘나들며 생명력을 이어가고 있습니다.
마치며
엘리베이터가 빨리 오지 않을 때, 그것은 승객을 무시하는 것이 아니라 내부적으로 수많은 변수를 계산하느라 분주히 작동하고 있는 것입니다. 다음에 엘리베이터를 기다리며 지루함을 느낄 때, 버튼 뒤편에서 수많은 엔지니어들이 더 빠른 알고리즘을 만들기 위해 치열하게 고민해 왔다는 사실을 떠올려 보는 것도 흥미로울 것입니다. 그리고 그 고민 중 일부는 여전히 현재진행형입니다.
참고 링크:
- John.fun: Elevators 인터랙티브 해설
- HN 토론 (item?id=49124218)
