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