엘리베이터가 늦는 이유, 버튼 뒤에서 돌아가는 배차 알고리듬

엘리베이터가 늦는 이유, 버튼 뒤에서 돌아가는 배차 알고리듬

AI 뉴스 썸네일

버튼을 눌렀는데 가까운 엘리베이터가 지나가 버릴 때가 있어요. 고장처럼 보이지만, 여러 대를 운용하는 시스템은 현재 거리만 보지 않아요. 진행 방향과 탑승 인원, 앞으로 생길 정차, 차량끼리 한곳에 몰릴 위험까지 계산해요. 1

핵심 요약

구분	핵심	왜 볼 만한가요
한 대 운행	SCAN은 끝까지 훑고, LOOK은 마지막 요청 층에서 방향을 바꿔요	운영체제의 디스크 스케줄링과 닮은 문제를 생활 속 사례로 볼 수 있어요
여러 대 배차	RSR은 도착 시간과 혼잡도, 방향, 차량 간 몰림을 점수로 계산해요	단순한 최단 거리보다 시스템 전체 상태가 중요하다는 점을 보여 줘요
성능 측정	평균뿐 아니라 p50과 p90 같은 대기 시간 분포를 함께 봐야 해요	드물지만 긴 지연이 사용자 경험을 크게 해칠 수 있어요
복잡성의 한계	교통량이 매우 많거나 차량 수가 적으면 LOOK이 더 나을 수 있어요	복잡한 알고리듬이 모든 환경에서 우수하다는 가정을 경계하게 해요

1. 엘리베이터 배차는 가까운 차를 고르는 문제가 아니에요

한 대만 움직일 때는 규칙이 비교적 단순해요. SCAN은 한 방향으로 요청을 처리한 뒤 끝에서 방향을 바꿔요. LOOK은 실제 요청이 있는 가장 먼 층까지만 갔다가 돌아와 불필요한 이동을 줄여요. 이 방식은 디스크 헤드가 트랙 요청을 순서대로 처리하는 엘리베이터 알고리듬과도 닮았어요. 2

여러 대가 들어오면 판단 항목이 급격히 늘어요. 눈앞에서 가장 가까운 차량이 곧 반대 방향으로 움직이거나, 이미 많은 승객을 태우고 여러 층에 설 예정일 수 있어요. 이 차에 새 호출을 배정하면 당장은 가까워 보여도 실제 도착은 늦어져요. 다른 차량과 같은 층으로 몰리면 이후 호출을 처리할 여유도 줄어요.

728x90

원문이 소개한 RSR(Relative System Response)은 각 차량이 새 호출을 맡았을 때의 비용을 점수로 계산해요. 예상 도착 시간이 짧으면 유리하고, 탑승 인원이 많거나 같은 방향의 다른 차량과 겹치면 불리해요. 호출 층 가까이 쉬고 있는 차량이나 진행 방향이 맞는 차량에는 가점을 줘요. 배정은 한 번으로 끝나지 않아요. 차량 위치와 혼잡 상태가 달라지면 일정 간격으로 호출을 다른 차량에 넘길 수 있어요. 2

성능도 평균 대기 시간 하나로 설명하기 어려워요. 절반이 몇 초 안에 탔는지를 보여 주는 p50과, 90%가 어느 시간 안에 탔는지를 보여 주는 p90을 함께 보면 긴 지연이 얼마나 자주 생기는지 알 수 있어요. 평균이 짧아도 일부 승객이 2분 넘게 기다린다면 체감 품질은 나쁠 수 있어요. 서비스 지연 시간을 평균과 꼬리 지연으로 나눠 보는 이유와 같아요.

시간대에 따라 입력 패턴도 달라져요. 출근 시간에는 로비에서 위층으로 향하는 호출이 몰려요. 퇴근 시간에는 반대 흐름이 커지고, 점심에는 상행과 하행이 섞여요. 좋은 배차 규칙은 특정 시점의 차량 위치뿐 아니라 이런 교통 패턴까지 견뎌야 해요.

복잡한 방식이 항상 이기는 건 아니에요. 모든 차량이 붐비고 거의 모든 층에 서는 상황에서는 정교한 점수 계산이 선택지를 크게 바꾸지 못해요. 차량이 적은 소형 건물에서도 단순한 LOOK이 더 짧은 대기 시간을 낼 수 있어요. 목적층을 미리 입력하는 Destination Dispatch도 정보를 더 받지만, 처음 안내한 차량을 쉽게 바꾸지 못하면 재배정의 유연성이 줄어요. 원문의 시뮬레이션 결과는 건물 규모와 승객 흐름에 따라 결과가 달라질 수 있다는 점까지 함께 보여 줘요. 2

왜 중요한가요

이 사례는 실시간 스케줄러를 설계할 때 자주 만나는 세 가지 문제를 한꺼번에 보여 줘요. 첫째, 지금 가장 가까운 선택이 전체 시스템에서 가장 빠른 선택은 아닐 수 있어요. 둘째, 입력 상태가 계속 바뀌면 최초 결정을 고정하기보다 재평가 비용과 재배정 이익을 비교해야 해요. 셋째, 평균값만으로는 사용자가 기억하는 긴 지연을 놓칠 수 있어요. 2

같은 관점은 서버 요청 분산, 작업 큐, 배달 배차, 디스크 입출력에도 적용할 수 있어요. 처리 시간을 줄이는 것만큼 차량이나 서버가 한곳에 몰리지 않게 하는 규칙이 필요해요. 다만 규칙을 많이 넣을수록 좋다고 볼 수는 없어요. 실제 부하 분포와 자원 수를 바꿔 가며 p50, p90, 최대 지연을 함께 측정해야 해요. 엘리베이터가 늦게 오는 평범한 경험이 스케줄링과 성능 평가를 이해하기 좋은 실험이 되는 이유예요.

참고 자료

1. 엘리베이터는 왜 바로 오지 않을까? — GeekNews
2. Elevators — john.fun