Elevator Scheduling Algorithms: FCFS, SSTF, SCAN, and LOOK

Since I’ve been working with Go for quite some time, I thought it would be a fun challenge to implement a few classic low-level design solutions in it.

When designing an elevator system, one crucial aspect is how to decide which floor to service next, especially when the elevator has multiple requests. Go’s straightforward syntax and performance make it ideal for modeling such systems, so I set out to create basic implementations of FCFS (First Come First Serve), SSTF (Shortest Seek Time First), SCAN, and LOOK algorithms.

1. First Come First Serve (FCFS)

I started with the simplest approach: service requests in the order they’re received. It’s easy to implement but can be inefficient if the requests are spread out across floors, leading to more travel time.

func FCFS(currentFloor int, requests []int) []int {
    path := []int{}
    for _, floor := range requests {
        path = append(path, floor)
    }
    return path
}

In FCFS, the elevator simply moves to each requested floor in the given order.

2. Shortest Seek Time First (SSTF)

SSTF tries to minimize travel by choosing the closest requested floor next. This reduces travel time but can lead to "starvation" for far-off requests if new closer requests keep coming.

func SSTF(currentFloor int, requests []int) []int {
    path := []int{}
    remaining := append([]int{}, requests...)

    for len(remaining) > 0 {
        closestIdx := 0
        minDistance := abs(currentFloor - remaining[0])

        for i, floor := range remaining {
            distance := abs(currentFloor - floor)
            if distance < minDistance {
                closestIdx = i
                minDistance = distance
            }
        }

        currentFloor = remaining[closestIdx]
        path = append(path, currentFloor)
        remaining = append(remaining[:closestIdx], remaining[closestIdx+1:]...)
    }
    return path
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

This function finds the closest floor to the current floor each time, updating the elevator’s position after each move.

3. SCAN (Elevator Algorithm)

In SCAN, the elevator moves in one direction, servicing all requests in that direction until it reaches the end, then reverses. This approach is more fair than SSTF because it reduces starvation.

func SCAN(currentFloor, maxFloor int, requests []int) []int {
    path := []int{}
    up := []int{}
    down := []int{}

    for _, floor := range requests {
        if floor >= currentFloor {
            up = append(up, floor)
        } else {
            down = append(down, floor)
        }
    }

    sort.Ints(up)
    sort.Sort(sort.Reverse(sort.IntSlice(down)))

    path = append(path, up...)
    path = append(path, down...)
    return path
}

This function splits requests into floors above and below the current position. It serves all floors upwards, then downwards.

4. LOOK

LOOK is a slight variation of SCAN. Instead of going all the way to the end, the elevator reverses direction at the last request in each direction. It saves time by stopping where the requests end, not at the physical limits.

func LOOK(currentFloor int, requests []int) []int {
    path := []int{}
    up := []int{}
    down := []int{}

    for _, floor := range requests {
        if floor >= currentFloor {
            up = append(up, floor)
        } else {
            down = append(down, floor)
        }
    }

    sort.Ints(up)
    sort.Sort(sort.Reverse(sort.IntSlice(down)))

    path = append(path, up...)
    path = append(path, down...)
    return path
}

Similar to SCAN, this approach only moves as far as the last request in each direction.

Each algorithm has its trade-offs:

• FCFS: Simple but can be inefficient.
• SSTF: Optimizes for closest floors but can starve far-off requests.
• SCAN: Fairer and efficient, minimizing direction changes.
• LOOK: Saves additional time by stopping at the last request.

The right choice depends on the specific requirements for efficiency, fairness, and response time in the system.

For full implementation using LOOK algorithm, refer to my github repo:

thesaltree / low-level-design-golang

Low level system design problems solutions in Golang

Low-Level System Design in Go

Welcome to the Low-Level System Design in Go repository! This repository contains various low-level system design problems and their solutions implemented in Go. The primary aim is to demonstrate the design and architecture of systems through practical examples.

Table of Contents

• Overview
• Parking Lot System
• Elevator System

Overview

Low-level system design involves understanding the core concepts of system architecture and designing scalable, maintainable, and efficient systems. This repository will try to cover solutions of various problems and scenarios using Go.

Parking Lot System

The first project in this repository is a Parking Lot System. This system simulates a parking lot where vehicles can be parked and unparked. It demonstrates:

• Singleton design pattern for managing the parking lot instance.
• Handling different types of vehicles (e.g., cars, trucks).
• Parking space management across multiple floors.
• Payment processing for parked vehicles.

Features

• Add and remove vehicles from the…

View on GitHub

The above is the detailed content of Elevator Scheduling Algorithms: FCFS, SSTF, SCAN, and LOOK. For more information, please follow other related articles on the PHP Chinese website!