電梯調度演算法：FCFS、SSTF、SCAN 和 LOOK

由於我使用 Go 已經有一段時間了，我認為在 Go 中實現一些經典的低階設計解決方案將是一個有趣的挑戰。

設計電梯系統時，一個關鍵的方面是如何決定下一步服務哪一層，尤其是當電梯有多個請求時。 Go 簡單的語法和效能使其非常適合對此類系統進行建模，因此我著手創建 FCFS（先來先服務）、SSTF（最短尋道時間優先）、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：針對最近的樓層進行最佳化，但可能會導致遠處的請求匱乏。
• SCAN：更公平、更有效率，盡量減少方向變化。
• 查看：透過在最後一個請求處停止來節省額外時間。

正確的選擇取決於系統對效率、公平性和回應時間的特定要求。

有關使用 LOOK 演算法的完整實現，請參閱我的 github 儲存庫：

主題樹 / 低級設計 golang

Golang 中的底層系統設計問題解決方案

Go 中的底層系統設計

歡迎來到Go 中的低階系統設計 儲存庫！此儲存庫包含各種低階系統設計問題及其在 Go 中實現的解決方案。主要目的是透過實際範例展示系統的設計和架構。

目錄

• 概述
• 停車場系統
• 電梯系統

概述

底層系統設計涉及理解系統架構的核心概念以及設計可擴展、可維護和高效的系統。該儲存庫將嘗試涵蓋使用 Go 的各種問題和場景的解決方案。

停車場系統

此儲存庫中的第一個項目是停車場系統。該系統模擬一個可以停放車輛和出庫車輛的停車場。它示範了：

• 用於管理停車場實例的單例設計模式。
• 處理不同類型的車輛（例如汽車、卡車）。
• 多個樓層的停車位管理。
• 停放車輛的付款處理。

特點

• 新增和刪除車輛......

在 GitHub 上查看

以上是電梯調度演算法：FCFS、SSTF、SCAN 和 LOOK的詳細內容。更多資訊請關注PHP中文網其他相關文章！