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

저는 꽤 오랫동안 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과 유사하게 이 접근 방식은 각 방향의 마지막 요청까지만 이동합니다.

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

• FCFS: 간단하지만 비효율적일 수 있습니다.
• SSTF: 가장 가까운 층에 최적화되지만 멀리 있는 요청은 부족할 수 있습니다.
• 스캔: 공정하고 효율적이며 방향 변경을 최소화합니다.
• LOOK: 마지막 요청에서 중지하여 추가 시간을 절약합니다.

올바른 선택은 시스템의 효율성, 공정성, 응답 시간에 대한 구체적인 요구 사항에 따라 달라집니다.

LOOK 알고리즘을 사용하여 전체 구현을 보려면 내 github 저장소를 참조하세요.

thesaltree / 로우레벨 디자인 골랑

Golang의 낮은 수준 시스템 설계 문제 솔루션

Go에서의 저수준 시스템 설계

Go의 하위 수준 시스템 설계 저장소에 오신 것을 환영합니다! 이 저장소에는 다양한 하위 수준 시스템 설계 문제와 Go로 구현된 솔루션이 포함되어 있습니다. 주요 목표는 실제 사례를 통해 시스템의 설계와 아키텍처를 보여주는 것입니다.

목차

• 개요
• 주차장 시스템
• 엘리베이터 시스템

개요

낮은 수준의 시스템 설계에는 시스템 아키텍처의 핵심 개념을 이해하고 확장 가능하고 유지 관리가 가능하며 효율적인 시스템을 설계하는 작업이 포함됩니다. 이 저장소에서는 Go를 사용하여 다양한 문제와 시나리오에 대한 솔루션을 다루려고 합니다.

주차장 시스템

이 저장소의 첫 번째 프로젝트는 주차장 시스템입니다. 이 시스템은 차량을 주차하고 주차 해제할 수 있는 주차장을 시뮬레이션합니다. 다음을 보여줍니다.

• 주차장 인스턴스 관리를 위한 싱글톤 디자인 패턴
• 다양한 유형의 차량(예: 승용차, 트럭)을 취급합니다.
• 다층에 걸쳐 주차공간을 관리합니다.
• 주차차량 결제 처리

특징

• 차량 추가 및 제거...

GitHub에서 보기

위 내용은 엘리베이터 스케줄링 알고리즘: FCFS, SSTF, SCAN 및 LOOK의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!