電梯算法（也稱為 SCAN）是一種磁盤調度算法，用于確定磁盤臂和磁頭在處理讀寫請求時的運動。該算法以建筑物電梯的行為命名，其中電梯繼續沿其當前方向（向上或向下）運行，直到空無一人，停止僅讓人員離開或接載朝同一方向行駛的新人員。從實現的角度來看，驅動器維護一個緩沖區，其中包含掛起的讀/寫請求，以及請求的相關柱面號。 （氣缸數越小一般表示氣缸離主軸越近，數值越大表示氣缸離主軸越遠。）
本文內容包含以下：
1 說明
2 變化
3 示例
4 分析
5 另見
1.描述
當驅動器空閑時新請求到達時，初始臂/磁頭移動將沿存儲數據的柱面方向進行，無論是進還是出。 當額外的請求到達時，請求僅在當前手臂移動方向上得到服務，直到手臂到達磁盤邊緣。 發生這種情況時，臂的方向會反轉，而保留在相反方向上的請求將得到服務，依此類推。
2.變化
這種方法的一種變體確保所有請求都只在一個方向上得到服務，也就是說，一旦磁頭到達磁盤的外邊緣，它就會返回到開頭，只在這個方向上為新請求提供服務（反之亦然） ）。 這被稱為“環形電梯算法”或 C-SCAN。 盡管浪費了返回尋道的時間，但這會導致所有磁頭位置的性能更加平等，因為與磁頭的預期距離始終是最大距離的一半，這與標準升降機算法不同，其中中間的圓柱將作為 是最里面或最外面的圓柱體的兩倍。
其他變體包括：
- FSCAN
- LOOK (and C-LOOK)
- N-Step-SCAN
FScan 是一種磁盤調度算法，用于確定磁盤臂和磁頭在服務讀寫請求時的運動。 它使用兩個子隊列。 在掃描期間，所有請求都在第一個隊列中，所有新請求都放入第二個隊列中。 因此，新請求的服務被推遲，直到所有舊請求都已處理完畢。 當掃描結束時，手臂被帶到第一個隊列條目并重新開始。
LOOK 算法與 SCAN 算法相同，因為它也接受磁盤磁頭的兩個掃描方向上的請求，但是，該算法“向前看”以查看在磁頭移動方向上是否有任何未決請求。如果在磁頭移動方向上沒有待處理的請求，則磁盤磁頭遍歷將反轉到相反方向，并且可以服務另一個方向上的請求。在 LOOK 調度中，arm 只運行到每個方向的最終請求，然后反轉方向，而不會一直走到最后。考慮一個例子，給定一個有 200 個柱面 (0-199) 的磁盤，假設我們有 8 個待處理的請求：98、183、37、122、14、124、65、67 并且讀/寫頭當前在柱面 53 . 為了完成這些請求，手臂會先升序移動，到達終點后再降序移動。因此，它將執行的順序是 65, 67, 98, 122, 124, 183, 37, 14。 [1]
LOOK 的行為與最短尋道時間優先 (SSTF) 幾乎相同，但避免了 SSTF 的饑餓問題。這是因為 LOOK 偏向于最近穿過的區域，并且非常傾向于聚集在盤片最外和最內邊緣的軌道。 LOOK 也偏向于最近到達的工作（平均而言）。
N-Step-SCAN（也稱為 N-Step LOOK）是一種磁盤調度算法，用于確定磁盤臂和磁頭在服務讀寫請求時的運動。 它將請求隊列分成長度為 N 的子隊列。將隊列分成 N 個請求的段使服務保證成為可能。 進入請求隊列的后續請求不會被推送到 N 大小的子隊列中，這些子隊列已經被電梯算法填滿。 因此，饑餓被消除并且在 N 個請求內保證服務是可能的。
查看 N 步 SCAN 的另一種方法是：保留 N 個請求的緩沖區。 此緩沖區中的所有請求都在任何特定掃描中得到服務。 在此期間的所有傳入請求都不會添加到此緩沖區中，而是保存在單獨的緩沖區中。 當這些前 N 個請求得到服務時，IO 調度程序會選擇接下來的 N 個請求并且這個過程繼續。 這允許更好的吞吐量并避免饑餓。
3.示例：
以下是如何計算 SCAN 和 C-SCAN 算法的平均磁盤尋道時間的示例。
待處理磁盤請求的示例列表（按軌道編號列出）：100、50、10、20、75。
示例的起始曲目編號為 35。
該列表需要按升序排序：10、20、50、75、100。
SCAN 和 C-SCAN 都以相同的方式運行，直到它們到達排隊的最后一個軌道。 為了這個例子，讓我們假設 SCAN 算法當前正在從較低的軌道編號轉到較高的軌道編號（就像 C-SCAN 所做的那樣）。 對于這兩種方法，都采用下一個軌道請求和當前軌道之間的幅度（即絕對值）差異。
- Seek 1: 50 ? 35 = 15
- Seek 2: 75 ? 50 = 25
- Seek 3: 100 ? 75 = 25
此時兩者都達到了最高（結束）track request。 SCAN 只會反轉方向并為下一個最近的磁盤請求（在本例中為 20）提供服務，而 C-SCAN 將始終返回到軌道 0 并開始處理更高的軌道請求。
- Seek 4 (SCAN): 20 ? 100 = 80
- Seek 5 (SCAN): 10 ? 20 = 10
- Total (SCAN): 155
- Average (SCAN): 155 ÷ 5 = 31
- Seek 4 (C-SCAN): 0 ? 100 = 0 head movement as cylinders are treated as a circular list (C-SCAN always goes back to the first track)
- Seek 5 (C-SCAN): 10 ? 0 = 10
- Seek 6 (C-SCAN): 20 ? 10 = 10
- Total (C-SCAN): 85
- Average (C-SCAN): 85 ÷ 5 = 17
盡管使用 C-SCAN 算法執行了 6 次尋道，但實際上只完成了 5 次 I/O。
4.分析：
因此，對于兩種版本的升降舵算法，手臂運動總是小于總氣缸數的兩倍。 該變化的優點是響應時間的變化較小。 算法也比較簡單。然而，電梯算法并不總是比最短搜索優先好，后者稍微接近最優，但是當新請求在現有請求之前不斷得到服務時，會導致響應時間的很大差異，甚至會導致饑餓。抗饑餓技術可以應用于最短尋道時間優先算法，以保證最佳響應時間。
5.另見
FCFS 也是 FIFO 操作系統調度算法的行話術語，它按照要求的順序為每個進程的中央處理單元 (CPU) 分配時間。 [1] FIFO 的對立面是 LIFO，后進先出，其中最年輕的條目或“棧頂”首先被處理。 [2] 優先級隊列既不是 FIFO 也不是 LIFO，但可以臨時或默認采用類似的行為。 排隊論包括這些處理數據結構的方法，以及嚴格先進先出隊列之間的交互。
具有入隊和出隊操作的 FIFO 隊列的表示。
