LLD: Elevator System
1. Introduction
The design of an enterprise Elevator Dispatch & Controller System is an exceptional test of real-time distributed engineering, hardware-software abstraction, concurrent state management, and algorithmic scheduling optimization.
In a towering high-rise skyscraper with 50 floors and a bank of 8 elevator cars, simply answering "which elevator should serve floor 24?" requires solving complex operational trade-offs:
- Throughput vs. Latency: Do you prioritize minimizing the waiting time of an individual passenger standing in a chilly hallway (p99 tail latency), or do you maximize total system carrying throughput during morning rush-hour traffic?
- Concurrency & Race Conditions: When two distinct passengers press the "UP" hall call buttons simultaneously on floors 4 and 12, how do you prevent competing elevator cars from racing toward the same target, wasting electrical power and mechanical endurance?
- Hardware-Software Interface Abstraction: How does programmatic software code interact safely with analog physical hardware components like infrared door obstruction sensors, weight overload load cells, and emergency mechanical brake interlocks?
2. System Requirements & Architectural Boundaries
Functional Requirements
- Building Topology: Support a customizable vertical building architecture containing elevators serving distinct physical floors.
- Button Call Panels (Internal & External):
- External Hall Call Panels (Up/Down Buttons): Placed across every floor hallway; initiates generalized direction requests without declaring final destination.
- Internal Car Call Panels (Floor Selection Buttons): Located inside each specific car; registers exact target destination stop requests.
- Dispatch Optimization Engine: An automated central scheduling dispatcher that receives external hall calls and assigns the most economically optimal car based on heuristic calculations of direction, distance, and current load.
- Real-Time State Mechanics: Continuous stateful monitoring of car direction (
IDLE,MOVING_UP,MOVING_DOWN), operational mode (NORMAL,MAINTENANCE,EMERGENCY), and door positions (OPENING,CLOSED,OBSTRUCTED). - Hardware Sensor Integrations: Immediate interrupt-driven responses to weight limit violations and optical door obstruction sensors.
Non-Functional Requirements
- Thread Safety & High Concurrency: Multi-threaded asynchronous event execution without deadlocks or race conditions on shared target assignment registers.
- Starvation Freedom: Guarantee that no external hall call goes unanswered indefinitely due to continuous algorithmic preemption by nearer traffic bursts.
- Graceful Degradation & Fault Tolerance: If an individual car suffers mechanical failure or network disconnects, the central dispatcher must immediately drop it from circulation and reroute pending assignments to healthy peers.
3. Structural Object-Oriented Design & Abstraction Topology
To achieve high cohesion and modular decoupling, we divide the design into three layers: Physical Domain Entities (ElevatorCar, Door, Floor), Input Event Interfaces (HallButton, CarButton), and the Control & Dispatch Layer (ElevatorController, DispatchStrategy).
Complete UML Class Diagram
classDiagram
class Building {
-String name
-List~Floor~ floors
-ElevatorController controller
+getFloor(int floorNum) Floor
}
class ElevatorController {
-List~ElevatorCar~ cars
-DispatchStrategy dispatcher
+submitHallCall(int floor, Direction dir) void
+submitCarCall(int carId, int targetFloor) void
+stepExecution() void
-assignOptimalCar(HallCallRequest req) void
}
class DispatchStrategy {
<<interface>>
+selectOptimalCar(List~ElevatorCar~ cars, int floor, Direction dir) ElevatorCar
}
class SCANLookStrategy {
+selectOptimalCar(List~ElevatorCar~ cars, int floor, Direction dir) ElevatorCar
-calculateCost(ElevatorCar car, int targetFloor, Direction targetDir) int
}
class ElevatorCar {
-int id
-int currentFloor
-Direction currentDirection
-CarState state
-Door door
-Set~Integer~ targetDestinations
-int maxCapacityKg
-int currentWeightKg
+move() void
+openDoors() void
+closeDoors() void
+addDestination(int floor) void
+isOverloaded() boolean
}
class Door {
-DoorState state
-boolean isObstructed
+open() void
+close() void
+triggerObstructionSensor() void
}
class Button {
<<abstract>>
-boolean isPressed
+press()* void
+reset() void
}
class HallButton {
-int floorNumber
-Direction callDirection
+press() void
}
class CarButton {
-int targetFloor
-int elevatorId
+press() void
}
class Direction {
<<enumeration>>
UP
DOWN
IDLE
}
class CarState {
<<enumeration>>
IDLE
MOVING
STOPPED
OUT_OF_SERVICE
EMERGENCY_OVERRIDE
}
Building "1" *-- "1" ElevatorController
Building "1" *-- "*" Floor
ElevatorController "1" o-- "*" ElevatorCar
ElevatorController "1" --> "1" DispatchStrategy
DispatchStrategy <|-- SCANLookStrategy
ElevatorCar "1" *-- "1" Door
ElevatorCar "1" --> "1" Direction
ElevatorCar "1" --> "1" CarState
Button <|-- HallButton
Button <|-- CarButton
4. Elevator Car Finite State Machine (FSM)
An elevator car must never attempt physical vertical movement while doors remain open or mechanical interlocks are compromised. Modeling car operations via a formal Finite State Machine (FSM) prevents catastrophic mechanical instructions.
stateDiagram-v2
[*] --> IDLE : Power Initialized
IDLE --> MOVING_UP : Destination Assigned (Target > Current)
IDLE --> MOVING_DOWN : Destination Assigned (Target < Current)
MOVING_UP --> STOPPING : Approaching Target Floor
MOVING_DOWN --> STOPPING : Approaching Target Floor
STOPPING --> DOORS_OPENING : Zero Velocity Reached
DOORS_OPENING --> DOORS_OPEN_WAITING : Doors Fully Retracted
DOORS_OPEN_WAITING --> DOORS_CLOSING : Timer Expired (5s)
DOORS_CLOSING --> DOORS_OPEN_WAITING : Optical Sensor Obstructed / Door Open Button
DOORS_CLOSING --> IDLE : Doors Locked & No Targets Pending
DOORS_CLOSING --> MOVING_UP : Doors Locked & Pending Up Targets
DOORS_CLOSING --> MOVING_DOWN : Doors Locked & Pending Down Targets
IDLE --> EMERGENCY_STOP : Overload Sensor / Power Interrupt
MOVING_UP --> EMERGENCY_STOP : Safety Brake Triggered
MOVING_DOWN --> EMERGENCY_STOP : Safety Brake Triggered
DOORS_OPEN_WAITING --> EMERGENCY_STOP : Weight Overload Alarm
EMERGENCY_STOP --> IDLE : Alarm Cleared & Reset Validated
5. Scheduling Algorithms & Mathematical Modeling
The central architectural bottleneck of an elevator control system is the Dispatch Strategy Engine. Selecting which elevator to dispatch to an exterior hall call directly governs user tail latency (waiting time) and building transport throughput.
1. FIFO / First-Come-First-Served (Naive Architecture)
- Requests are placed in a simple synchronized queue and assigned sequentially to the first car terminating its active run.
- Why it Fails in Practice: Horrific physical inefficiencies. If Car A is on floor 2 heading down to floor 1, and a call arrives on floor 50 followed immediately by a call on floor 3, the naive system forces Car A all the way up to floor 50 before returning to floor 3. Energy expenditures and waiting times scale to catastrophic levels.
2. SSTF / Shortest Seek Time First (Greedy Heuristics)
- Assigns the incoming call to whichever elevator is spatially closest in scalar floor distance: .
- Why it Fails: Introduces severe Starvation. During peak lunchtime hours, cars constantly oscillate between the lobby and lower cafeteria floors (floors 1-5). A passenger waiting up on floor 48 will be continuously bypassed by nearer traffic bursts, leaving their call unserviced for arbitrary durations.
3. The SCAN / LOOK Strategy (The Elevator Algorithm)
- Widely implemented in modern commercial architecture and disk hard-drive controller head routing.
- The Mechanic: An elevator maintains its current directional vector (e.g.,
UP). It sweeps up the building, stopping sequentially at all requested floors located ahead of it in that direction (both car button targets and matching directional hall calls). When no further targets exist ahead in that direction, the car reverses vector (DOWN) and sweeps down.
4. Mathematical Cost Function Optimization (Modern Adaptive Control)
Advanced industrial dispatchers (e.g., Otis, Schindler) quantify car suitability using an explicit algorithmic Cost Optimization Function . When hall call arrives, the central controller computes a predictive penalty cost across every available car , selecting the candidate with the minimum algorithmic cost:
The evaluation cost function is formally defined as:
Where:
- = Estimated structural distance in floors to target.
- If car is moving toward target in matching direction: .
- If car is moving away from target or in opposing direction: (accounts for turnaround penalty).
- = Current operational capacity load ratio (). If , cost diverges to (bypass full car).
- = Directional penalty multiplier ( if direction matches request vector, if opposing).
- = Number of intermediate scheduled stops currently registered ahead of the arriving hall call.
- = Configurable weight parameters adjusted for morning up-peak vs. evening down-peak traffic profiles.
6. Production-Grade Reference Implementation
Below is a complete, well-structured, thread-safe Python implementation demonstrating an interactive Elevator Controller utilizing an adaptive LOOK Algorithm, priority direction set routing, and automated state machine step processing.
import time
from enum import Enum, auto
from typing import List, Set, Dict, Optional
import threading
class Direction(Enum):
UP = auto()
DOWN = auto()
IDLE = auto()
class CarState(Enum):
IDLE = auto()
MOVING = auto()
DOORS_OPEN = auto()
MAINTENANCE = auto()
class ElevatorCar:
"""Represents an individual physical elevator car unit and its local destination memory."""
def __init__(self, car_id: int, max_floor: int, capacity_kg: int = 1000):
self.id = car_id
self.max_floor = max_floor
self.capacity_kg = capacity_kg
self.current_weight = 0
# State registers
self.current_floor = 1
self.direction = Direction.IDLE
self.state = CarState.IDLE
# Dual directional sets allow continuous O(1) LOOK algorithm routing
self.up_targets: Set[int] = set()
self.down_targets: Set[int] = set()
self.lock = threading.Lock()
def is_overloaded(self) -> bool:
return self.current_weight > self.capacity_kg
def add_target(self, target_floor: int):
with self.lock:
if target_floor > self.current_floor:
self.up_targets.add(target_floor)
elif target_floor < self.current_floor:
self.down_targets.add(target_floor)
else:
# Target is existing floor; instantly open doors if moving stops
if self.state == CarState.IDLE:
self.state = CarState.DOORS_OPEN
self._update_direction()
def _update_direction(self):
"""Re-evaluates movement vector based on active destinations (LOOK mechanic)."""
if self.direction == Direction.UP:
if not self.up_targets and not self.down_targets:
self.direction = Direction.IDLE
self.state = CarState.IDLE
elif not self.up_targets and self.down_targets:
self.direction = Direction.DOWN
elif self.direction == Direction.DOWN:
if not self.down_targets and not self.up_targets:
self.direction = Direction.IDLE
self.state = CarState.IDLE
elif not self.down_targets and self.up_targets:
self.direction = Direction.UP
elif self.direction == Direction.IDLE:
if self.up_targets:
self.direction = Direction.UP
self.state = CarState.MOVING
elif self.down_targets:
self.direction = Direction.DOWN
self.state = CarState.MOVING
def step_simulation(self):
"""Executes a single structural simulation unit representing real-time progression."""
with self.lock:
if self.state == CarState.MAINTENANCE:
return
if self.is_overloaded():
print(f"[Car {self.id}] ALARM: Overload! Doors immobilized at Floor {self.current_floor}.")
self.state = CarState.DOORS_OPEN
return
if self.state == CarState.DOORS_OPEN:
# Simulate passenger boarding completion and close doors
print(f"[Car {self.id}] Doors closing at Floor {self.current_floor}.")
self.state = CarState.MOVING if (self.up_targets or self.down_targets) else CarState.IDLE
self._update_direction()
return
if self.direction == Direction.UP:
self.current_floor += 1
print(f"[Car {self.id}] Moving UP -> Floor {self.current_floor}")
if self.current_floor in self.up_targets:
self._arrive_at_floor(self.up_targets)
elif self.direction == Direction.DOWN:
self.current_floor -= 1
print(f"[Car {self.id}] Moving DOWN -> Floor {self.current_floor}")
if self.current_floor in self.down_targets:
self._arrive_at_floor(self.down_targets)
def _arrive_at_floor(self, target_set: Set[int]):
print(f"[Car {self.id}] ARRIVAL: Stopping at Floor {self.current_floor}. Doors OPENING.")
target_set.remove(self.current_floor)
self.state = CarState.DOORS_OPEN
self._update_direction()
class ElevatorController:
"""Centralized high-performance dispatch engine orchestrating car selection and assignments."""
def __init__(self, num_cars: int, total_floors: int):
self.total_floors = total_floors
self.cars: List[ElevatorCar] = [ElevatorCar(i + 1, total_floors) for i in range(num_cars)]
self.lock = threading.Lock()
def dispatch_hall_call(self, floor: int, direction: Direction):
"""Evaluates Cost Optimization Heuristics to allocate best available car."""
if not (1 <= floor <= self.total_floors):
raise ValueError(f"Invalid call requested for Floor {floor}")
best_car: Optional[ElevatorCar] = None
min_cost = float('inf')
with self.lock:
for car in self.cars:
cost = self._calculate_dispatch_cost(car, floor, direction)
if cost < min_cost:
min_cost = cost
best_car = car
if best_car is not None:
print(f"[Dispatcher] Hall Call (Floor {floor}, {direction.name}) assigned to Car {best_car.id} (Cost: {min_cost})")
best_car.add_target(floor)
else:
print("[Dispatcher] ALERT: All cars unavailable or out of circulation!")
def _calculate_dispatch_cost(self, car: ElevatorCar, target_floor: int, call_dir: Direction) -> int:
"""Cost Function computation balancing distance, direction, and starvation prevention."""
if car.state == CarState.MAINTENANCE:
return 999999
if car.is_overloaded():
return 888888
distance = abs(car.current_floor - target_floor)
if car.direction == Direction.IDLE:
# Idle car incurs low penalty (just distance)
return distance
# If car is moving toward target floor and directional intent matches
if car.direction == Direction.UP and target_floor >= car.current_floor and call_dir == Direction.UP:
return distance
if car.direction == Direction.DOWN and target_floor <= car.current_floor and call_dir == Direction.DOWN:
return distance
# Penalty condition: car moving away or going opposing direction requires full sweep turnaround
turnaround_penalty = 20
return distance + turnaround_penalty
def submit_car_call(self, car_id: int, destination_floor: int):
"""Directly registers an internal cabin selection button press."""
for car in self.cars:
if car.id == car_id:
print(f"[Internal Cabin] Passenger in Car {car_id} selected destination Floor {destination_floor}")
car.add_target(destination_floor)
return
print(f"[Error] Car {car_id} does not exist.")
def run_system_step(self):
"""Advances operational state machine ticks across all elevator pods simultaneously."""
for car in self.cars:
car.step_simulation()
# --- Verification Simulation Script ---
if __name__ == "__main__":
# Initialize high-rise skyscraper with 2 elevators serving 20 floors
controller = ElevatorController(num_cars=2, total_floors=20)
print("\n--- System Bootstrapper Initialized ---")
# Car 1 moves toward floor 5
controller.submit_car_call(car_id=1, destination_floor=5)
# Hall call initiated from floor 3 wanting to go UP
controller.dispatch_hall_call(floor=3, direction=Direction.UP)
# Hall call initiated from floor 12 wanting to go DOWN
controller.dispatch_hall_call(floor=12, direction=Direction.DOWN)
print("\n--- Running Real-Time Step Engine ---")
for cycle in range(1, 8):
print(f"\n[Time Step {cycle}]")
controller.run_system_step()
time.sleep(0.1) # Brief pause for visual output progression
7. Hardware-Software Edge Cases & Resilience
In distributed cyber-physical infrastructures, software controllers must handle analog component anomalies cleanly without locking up operations:
1. The Optical Sensor Obstruction Loop
- Problem: An obstinate passenger holds their arm across the elevator doors to block departure, interrupting the optical infrared door sensor beam. A naive loop repeatedly commands
door.close(), which triggers an instant interrupt back todoor.open(), causing an infinite state machine freeze and burning out the door motor drive. - Resilient Solution: Implement an exponential timeout counter and audible mechanical alarm fallback:
class Door: def __init__(self): self.obstruction_count = 0 self.max_obstruction_attempts = 3 def attempt_close(self) -> bool: if self.is_sensor_blocked(): self.obstruction_count += 1 if self.obstruction_count >= self.max_obstruction_attempts: # Enter Forced Nudge Mode: sound buzzer, close slowly with reduced torque self.activate_audible_alarm() self.force_slow_nudge_close() self.obstruction_count = 0 return True return False self.obstruction_count = 0 self.close() return True
2. Network Partitions Between Hall Panels & Central Dispatcher
- Problem: In modern CAN-bus or Ethernet-wired buildings, a physical network severance may isolate floors 15 through 20 from the primary roof-mounted Central Elevator Controller server.
- Resilient Solution: Implement decentralized Fallback Emergency Routing. Every individual
ElevatorCarlocal controller processor continuously listens for central controller heartbeats (PING/PONGpackets). If heartbeats fail for , individual elevator pods fall back to Autonomous Sweep Mode (continually sweeping between Floor 1 Lobby and Top Floor, stopping at every single landing regardless of hall button signal reception) to guarantee evacuation capabilities.
3. Ghost Occupancy & Weight Cell Calibration Failure
- Problem: All interior floor call buttons are selected by a mischievous passenger who immediately exits at the lobby. The car ascends, making 30 useless stops facing empty hallways, destroying building efficiency.
- Resilient Solution: Integrate digital load cell readings (
current_weight). When the doors lock and the cabin prepares to depart, ifcurrent_weight < 45 kg(indicating zero human passengers inside the car), the internal software register immediately clears and overrides all pending internal car call destinations (self.up_targets.clear()), instantly shifting the car back toIDLE.
8. Senior Technical Interview Q&A
Q1: Why is First-Come, First-Served (FCFS) an inappropriate scheduling algorithm for a commercial high-rise elevator bank, and how does the SCAN/LOOK algorithm resolve its limitations?
Answer: FCFS evaluates traffic purely based on chronological arrival order, completely ignoring physical vertical topology. If an elevator is at floor 2 and receives consecutive requests for floor 45, floor 4, floor 39, and floor 6, FCFS forces the mechanical car into catastrophic vertical oscillations (2 45 4 39 6). This causes unacceptable energy consumption, mechanical friction wear, and immense average passenger waiting times (high p50 and p99 latency).
The SCAN/LOOK Algorithm (Elevator Algorithm) establishes strict directional momentum. An ascending elevator prioritizes all requested floors lying ahead of its current trajectory vector, picking up matching hall calls and unloading cabin passengers sequentially on its way up. It only reverses directional vector when zero outstanding target demands remain above it. This minimizes total traveled physical distance, reduces motor braking wear, and ensures high systemic throughput.
Q2: In an elevator system architecture, how do you prevent race conditions when two different threads execute an automated dispatch assignment to the exact same elevator car concurrently?
Answer: To eliminate concurrency race conditions:
- Avoid Global Shared Locks: Do not utilize a coarse-grained synchronized lock over the entire
ElevatorController, as this forces sequential bottleneck delays during peak traffic hours when hundreds of call buttons fire simultaneously. - Fine-Grained Optimistic Concurrency & Actor Models: Implement an Actor Model Architecture (or use isolated concurrent queues per elevator pod). The central dispatch evaluator acts as a read-only router that assesses car snapshots and submits an immutable command instruction (
AddTargetCommand) into a lightweight, concurrent multi-producer single-consumer FIFO message queue affixed directly to the targetElevatorCarinstance. - Thread-Safe Mutation Execution: Each individual elevator runs on its own isolated worker execution loop (or thread), consuming tasks sequentially from its private mailbox queue and updating its target sets safely without thread contention or external locking overhead.
Q3: How would you design the system to handle an explicit "Emergency Fireman Overlay Mode" initiated from an external ground-floor hardware switch?
Answer: An Emergency Overlay requires immediate preemption over normal algorithmic scheduling:
- State Machine Override Transition: Upon reception of the structural hardware interrupt (
FireAlarmEvent), the central controller broadcasts an high-priority interrupt signal to every activeElevatorCar. - Immediate Destination Cleansing: All elevators immediately erase their existing internal cabin destination memory sets (
up_targets.clear(),down_targets.clear()) and ignore all newly arriving external Hall Calls. - Safety Descent Rule: If a car is traveling away from the designated evacuation level (usually Floor 1 Lobby), it decelerates, stops safely at the very next immediate mechanical floor landing without opening passenger doors, reverses its directional vector, and navigates straight down to the Floor 1 evacuation landing. Upon arrival at Floor 1, doors open fully, exit access is locked open, and internal control transits to manual key-operated
EMERGENCY_OVERRIDEmode exclusively reserved for firefighting personnel.
Q4: Describe how you would implement a "Destination Dispatch" system (such as Schindler IDO / Otis Compass), where users select their destination floor directly on kiosk screens before boarding, rather than pressing inside a cabin.
Answer: In traditional systems, passengers merely declare UP or DOWN in the hall, hiding their final destination until after they board. Destination Dispatch radically transforms computational grouping efficiency by revealing the passenger's actual target upfront:
- Interface Revision: Replace simple
HallButtonpanels with interactive touchpad kiosks (KioskPanel). When a user approaches floor 1 and inputs destination floor 34, the dispatcher immediately evaluates both origin () and destination (). - Mathematical Trip Grouping & Zone Routing: The algorithm groups passengers traveling to identical or adjacent vertical floor sectors into the same dedicated elevator car before they even board. For example, Car A is assigned exclusively to passengers traveling to floors 30-40, while Car B takes floors 10-20.
- Elimination of Internal Buttons: Internal car selection buttons (
CarButton) are totally stripped out of the physical car cabins. Passengers stand inside a minimalist pod that autonomously executes a tightly minimized sequence of pre-assigned, highly clustered sector stops, slashing total elevator stop counts by up to 50% during morning up-peak rushes.
Q5: How would you structure database logging and analytical telemetry across an elevator network to predict preventative mechanical maintenance failures?
Answer: We architect an asynchronous IoT ingestion data pipeline to prevent diagnostic IO loops from impacting the real-time embedded control engine:
- Asynchronous Edge Metric Emission: Every elevator microcontroller continuously publishes low-overhead structured telemetry datagrams (via MQTT or gRPC over UDP) to a centralized IoT gateway server. Emitted metrics include: door cycle transit times, mechanical motor current amperage draw, hydraulic valve pressure levels, acceleration/deceleration smoothness curves (Jerk calculations via inertial accelerometers), and optical door obstruction trigger frequency.
- Time-Series Storage: Stream these events into a horizontally scalable Time-Series Database (TSDB such as InfluxDB, Prometheus, or AWS Timestream) indexed by
car_idand timestamp. - Anomalous Drift Detection for Predictive Maintenance: Implement automated statistical outlier monitoring. If the historical normal duration for an elevator door to close is , and over a 30-day trailing window the closing duration gradually slips to alongside an upward spike in motor amperage draw, the analytics engine automatically fires an automated preventative maintenance work-order ticket to engineers before mechanical door drive gears fail completely during operating hours.
9. Summary & Quick Reference
| Dimension | Standard Architectural Solution | Advanced Industrial Implementation | | :--- | :--- | :--- | | Primary Dispatch Model | LOOK / SCAN Strategy (Directional sweeping) | Mathematical Heuristic Cost Optimization Function | | Peak Throughput Solution | Dual-button Hall Calls (Up/Down) | Destination Dispatch Kiosks (Grouped sector routing) | | Concurrency Mechanics | Mutex / Monitor synchronization locks on state sets | Actor Model with individual message queues per car | | Fault Resilience | Centralized Controller failover routing | Decentralized Local Heartbeat Timeout & Evacuate-to-Lobby mode | | Sensor Overloading | Simple timeout counters | Forced Nudge audible closing & automated weight-cell override | | Design Patterns Used | State Pattern (FSM), Strategy Pattern, Observer | Command Pattern (Events), Factory Pattern (Sensors), Actor Model |