電梯算法(也稱為 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 隊列的表示。 |