電梯算法（也稱為 SCAN）是一種磁盤調度算法，用于確定磁盤臂和磁頭在處理讀寫請求時的運動。該算法以建筑物電梯的行為命名，其中電梯繼續沿其當前方向（向上或向下）運行，直到空無一人，停止僅讓人員離開或接載朝同一方向行駛的新人員。從實現的角度來看，驅動器維護一個緩沖區，其中包含掛起的讀/寫請求，以及請求的相關柱面號。 （氣缸數越小一般表示氣缸離主軸越近，數值越大表示氣缸離主軸越遠。） 本文內容包含以下： 1 說明 2 變化 3 示例 4 分析 5 另見 1.描述 當驅動器空閑時新請求到達時，初始臂/磁頭移動將沿存儲數據的柱面方向進行，無論是進還是出。 當額外的請求到達時，請求僅在當前手臂移動方向上得到服務，直到手臂到達磁盤邊緣。 發生這種情況時，臂的方向會反轉，而保留在相反方向上的請求將得到服務，依此類推。 2.變化 這種方法的一種變體確保所有請求都只在一個方向上得到服務，也就是說，一旦磁頭到達磁盤的外邊緣，它就會返回到開頭，只在這個方向上為新請求提供服務（反之亦然） ）。 這被稱為“環形電梯算法”或 C-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 所做的那樣）。 對于這兩種方法，都采用下一個軌道請求和當前軌道之間的幅度（即絕對值）差異。
此時兩者都達到了最高（結束）track request。 SCAN 只會反轉方向并為下一個最近的磁盤請求（在本例中為 20）提供服務，而 C-SCAN 將始終返回到軌道 0 并開始處理更高的軌道請求。
盡管使用 C-SCAN 算法執行了 6 次尋道，但實際上只完成了 5 次 I/O。 4.分析： 因此，對于兩種版本的升降舵算法，手臂運動總是小于總氣缸數的兩倍。 該變化的優點是響應時間的變化較小。 算法也比較簡單。然而，電梯算法并不總是比最短搜索優先好，后者稍微接近最優，但是當新請求在現有請求之前不斷得到服務時，會導致響應時間的很大差異，甚至會導致饑餓?？桂囸I技術可以應用于最短尋道時間優先算法，以保證最佳響應時間。 5.另見
FCFS 也是 FIFO 操作系統調度算法的行話術語，它按照要求的順序為每個進程的中央處理單元 (CPU) 分配時間。 [1] FIFO 的對立面是 LIFO，后進先出，其中最年輕的條目或“棧頂”首先被處理。 [2] 優先級隊列既不是 FIFO 也不是 LIFO，但可以臨時或默認采用類似的行為。 排隊論包括這些處理數據結構的方法，以及嚴格先進先出隊列之間的交互。
具有入隊和出隊操作的 FIFO 隊列的表示。 |
