엘리베이터 스케줄링 알고리즘: FCFS, SSTF, SCAN 및 LOOK

Linda Hamilton

풀어 주다： 2024-10-27 20:31:02

원래의

809명이 탐색했습니다.

저는 꽤 오랫동안 Go를 사용했기 때문에 몇 가지 고전적인 하위 수준 디자인 솔루션을 Go에 구현하는 것이 재미있는 도전이 될 것이라고 생각했습니다.

엘리베이터 시스템을 설계할 때 중요한 측면 중 하나는 특히 엘리베이터에 여러 요청이 있는 경우 다음 서비스 층을 결정하는 방법입니다. Go의 간단한 구문과 성능은 이러한 시스템을 모델링하는 데 이상적입니다. 그래서 저는 FCFS(First Come First Serve), SSTF(Shortest Seek Time First), SCAN 및 LOOK 알고리즘의 기본 구현을 만들기 시작했습니다.

1. 선착순 서비스(FCFS)

저는 가장 간단한 접근 방식인 서비스 요청을 받은 순서대로 시작했습니다. 구현하기는 쉽지만 요청이 여러 층에 분산되어 이동 시간이 늘어나면 비효율적일 수 있습니다.

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

로그인 후 복사

FCFS에서는 엘리베이터가 지정된 순서대로 요청한 층으로 이동합니다.

2. SSTF(최단 탐색 시간 우선)

SSTF는 다음으로 가장 가까운 요청 층을 선택하여 이동을 최소화하려고 합니다. 이렇게 하면 이동 시간이 줄어들지만 새로운 가까운 요청이 계속해서 오면 멀리 있는 요청에 대한 "기아"가 발생할 수 있습니다.

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
}

로그인 후 복사

이 기능은 매번 현재 층과 가장 가까운 층을 찾아 이동 후 엘리베이터의 위치를 업데이트합니다.

3. SCAN(엘리베이터 알고리즘)

SCAN에서는 엘리베이터가 한 방향으로 이동하여 끝에 도달할 때까지 해당 방향의 모든 요청을 처리한 다음 반대 방향으로 이동합니다. 이 접근 방식은 기아를 줄이기 때문에 SSTF보다 더 공정합니다.

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
}

로그인 후 복사

현재 위치보다 높은 층과 낮은 층으로 요청을 분할하는 기능입니다. 모든 층을 위쪽으로, 그 다음 아래쪽으로 서비스합니다.

4. 보세요

LOOK은 SCAN의 약간의 변형입니다. 엘리베이터는 끝까지 가는 대신 각 방향의 마지막 요청에 따라 방향을 바꿉니다. 물리적 한계가 아닌 요청이 끝나는 지점에서 중지하여 시간을 절약합니다.

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
}

로그인 후 복사

SCAN과 유사하게 이 접근 방식은 각 방향의 마지막 요청까지만 이동합니다.

각 알고리즘에는 장단점이 있습니다.