Elevator Dispatch Algorithms Explained: The Scheduling Problem Hiding in Every Building

Stand in the lobby of an office building and press the up button. Somewhere above you, a piece of software just made a scheduling decision, and the algorithm it used is a close relative of the one your kernel uses to decide which disk block to read next. That’s not a coincidence or a stretch of an analogy. The algorithm most operating systems books call “the elevator algorithm” was named that because it was originally, literally, an elevator algorithm.

Why the obvious approach doesn’t work

The naive way to dispatch an elevator is to send whichever idle car is physically closest to the person who just pressed a button. It’s simple, and it’s wrong in a way that gets worse as a building fills up.

The problem is direction. Imagine a car on floor 9, descending, with three people already inside heading to floors 3, 2, and 1. Someone on floor 7 presses “up.” A nearest-car algorithm sees an idle-ish car close by and sends it there, ignoring the fact that it’s already committed to a downward trip with passengers who now have to sit through a detour to floor 7 and back before continuing down. Do this across a whole building under real traffic and you get long, unpredictable waits and passengers who never quite trust the “up” and “down” arrows again.

The elevator algorithm: commit to a direction

The classic fix, and the one that gives the algorithm family its name, is called SCAN. Instead of reacting to whichever request just arrived, a car commits to a direction and serves every pending call along the way, in order, until it reaches the top or bottom of its range. Only then does it reverse and sweep back down, again picking up everything in its path.

This is exactly how a disk head works in the SCAN disk-scheduling algorithm: it moves across the platter in one direction, servicing every pending read or write request it passes, then reverses at the end rather than jumping back and forth to whichever request came in most recently. Early Linux kernels shipped an I/O scheduler literally called “Linus Elevator” for this reason, and the elevator naming has stuck in operating systems curricula ever since, even as the scheduling has moved on to deadline-based and multi-queue approaches.

SCAN has one obvious inefficiency: it travels all the way to the physical end of the range, floor 1 or the top floor, even if nothing is waiting out there. LOOK fixes that by only traveling as far as the last pending request in the current direction, then reversing immediately, “looking ahead” instead of committing blindly to the extreme. C-LOOK goes one step further: rather than reversing at the last request, it jumps straight back to the lowest pending request and sweeps in the same direction again. That keeps the wait-time distribution more even across floors, at the cost of that one non-servicing jump.

Algorithm	Behavior	Tradeoff
FCFS / nearest car	Serve requests in arrival order or by proximity	Simple, but ignores direction; causes unnecessary reversals
SCAN	Sweep to the physical end of the range, then reverse	No starvation, but wastes travel past the last real request
LOOK	Sweep only as far as the last pending request, then reverse	Less wasted travel than SCAN, still direction-committed
C-LOOK	Sweep to the last request, jump back to the lowest, repeat	More uniform wait times, one non-servicing jump per cycle

None of these are elevator-specific. They’re general answers to the same question: given a stream of requests that each have a cost related to your current position, in what order do you serve them to minimize total movement or wait time, without starving requests at the far end?

Destination dispatch: changing the input, not just the algorithm

Modern high-rises mostly don’t use hallway up/down buttons anymore. You’ve probably used destination dispatch without knowing its name: a keypad or touchscreen in the lobby where you enter your destination floor before you board, and the system tells you which car to take, sometimes labeled by letter rather than “up” or “down.”

This is a bigger change than swapping SCAN for LOOK. It changes what information the scheduler has before it commits anyone to a car. A conventional system doesn’t know where you’re going until you’re already inside and have pressed a floor button, by which point the car’s route is partly locked in. Destination dispatch knows every passenger’s destination before assignment, which lets the controller group people heading to nearby floors into the same car and route that car with far fewer total stops. Industry data on destination dispatch systems shows real trip-time reductions and effective capacity gains large enough that some buildings can serve the same traffic with fewer elevator cars, which is why it’s become standard in new high-rise construction despite the added cost of the lobby hardware.

The lesson generalizes past elevators: sometimes the biggest improvement to a scheduler isn’t a smarter algorithm operating on the same inputs, it’s collecting better information earlier so the scheduler has less to guess about.

Where this actually shows up in software you build

If you’ve done load balancing algorithm design, you’ve already seen a cousin of this problem: round robin is the FCFS-equivalent, blind to real load; least-connections routing is closer to a reactive, state-aware assignment; and consistent hashing is closer to destination dispatch, deciding placement based on a stable key rather than reacting purely to whoever asks first.

Background job schedulers face the identical direction-commitment tradeoff. A worker that grabs the newest job in the queue behaves like the naive nearest-car dispatcher, cheap to reason about, prone to reversals and starvation under bursty load. A worker pool that batches jobs by some shared property, tenant, priority tier, or downstream dependency, before dispatching behaves more like destination dispatch: more setup cost, meaningfully less wasted movement.

None of this means you should reach for SCAN by name in your next scheduler. It means the next time you’re deciding how a queue picks its next item, the question worth asking is the same one a building’s elevator controller has to answer dozens of times a minute: are you reacting to whatever just arrived, or do you know enough about what’s coming to batch it intelligently first? Real elevators answered that question with better hardware and more upfront information. Most software schedulers have the same option available and don’t take it.