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:

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!