磁碟排程演算法

---

磁碟排程是作業系統中一項重要的程序，它決定了磁碟訪問請求的執行順序。磁碟排程的目的是最小化訪問磁碟資料所需的時間，並最小化完成磁碟訪問請求所需的時間。磁碟訪問時間由兩個因素決定：尋道時間和旋轉延遲。尋道時間是指磁碟磁頭移動到磁碟上所需位置所需的時間，而旋轉延遲是指磁碟將所需資料扇區旋轉到磁碟磁頭下方所需的時間。磁碟排程演算法是現代作業系統的一個重要組成部分，負責決定磁碟訪問請求的執行順序。這些演算法的主要目標是最小化磁碟訪問時間並改進整體系統效能。

先到先服務

先到先服務 (FCFS) 磁碟排程演算法是現代作業系統中最簡單、最直接的磁碟排程演算法之一。它的工作原理是按照接收請求的順序來處理磁碟訪問請求。在 FCFS 演算法中，磁碟頭定位在佇列中的第一個請求上，並處理該請求。然後磁碟頭移動到佇列中的下一個請求並處理該請求。此過程持續到所有請求得到處理為止。

示例

假設我們有如下順序的磁碟訪問請求：20 150 90 70 30 60。磁碟頭目前

位於 50 磁軌。

總尋道時間 = (50-20) + (150-20) + (150-90) + (90-70) + (70-30) + (60-30) = 310

最近鄰尋道優先

最近鄰尋道優先 (SSTF) 是作業系統中用來有效管理磁碟 I/O 操作的磁碟排程演算法。SSTF 的目標是最大限度地減少處理所有磁碟訪問請求所需的總尋道時間。在 SSTF 中，磁碟頭從其當前位置移動到尋道時間最短的請求處，處理該請求，然後重複此過程，直到處理所有請求。該演算法根據磁碟頭當前位置的接近程度對磁碟訪問請求進行優先排序，確保磁碟頭在處理每個請求時移動的最短距離。

示例

在這種情況下，對於相同的成功請求順序，總尋道時間 = (60-50) + (70-60) + (90-70) + (90-30) + (30-20) + (150-20) = 240

掃描

掃描 (SCAN) 是作業系統中用來管理磁碟 I/O 操作的磁碟排程演算法。SCAN 演算法在一個方向移動磁碟頭，處理所有請求，直到到達磁碟末尾，然後反轉方向處理所有剩餘請求。在 SCAN 中，磁碟頭從磁碟的一端開始，向另一端移動，處理其路徑中的所有請求。一旦磁碟頭到達另一端，它將反轉方向並處理途中錯過的所有請求。此操作會持續到處理完所有請求為止。

示例

如果我們認為在 SCAN 中的磁頭方向是向左，則總尋道時間 = (50-30) + (30-20) + (20-0) + (60-0) + (60-70) + (90-70) + (90-150) = 200

迴圈掃描

迴圈掃描 (C-SCAN) 演算法的操作類似於 SCAN 演算法，但它在磁碟末尾不會反轉方向。相反，磁碟頭繞到磁碟的另一端並繼續處理請求。此演算法可以減少磁碟頭必須移動的總距離，從而縮短磁碟訪問時間。然而，此演算法可能導致位於磁碟末尾附近進行的請求等待時間較長，因為這些請求必須等到磁碟頭繞到磁碟的另一端才能得到處理。迴圈掃描演算法通常用於現代作業系統，因為它可以減少磁碟訪問時間並提高整體系統效能。

示例

對於迴圈掃描，總尋道時間 = (60-50) + (70-60) + (90-70) + (150-90) + (199-150) + (199-0) + (20-0) + (30-20) = 378

先來後到

LOOK 演算法與 SCAN 演算法類似，但它會在到達磁碟末尾時停止服務請求。此演算法可以縮短磁碟磁頭必須移動的總距離，進而縮短磁碟訪問時間。然而，對於在磁碟末尾附近發出的請求，此演算法可能會導致長時間的等待時間，因為請求必須等待磁碟磁頭繞磁碟另一端迴繞，然後才能得到服務。由於 LOOK 演算法能夠縮短磁碟訪問時間並提高系統整體效能，因此常用於現代作業系統。

示例

考慮到磁頭朝向右側，此時，總尋道時間 = (60-50) + (70-60) + (90-70) + (150-90) + (150-30) + (30-20) = 230

C-LOOK

C-LOOK 與 C-SCAN 磁碟排程演算法類似。在此演算法中，不管磁碟臂是否到達末端，它只處理磁頭前面的最後一個待服務請求，然後從那裡轉到另一端的最後一個請求。因此，它也可以防止磁碟末端的非必要遍歷可能導致的額外延遲。

示例

對於 C-LOOK 演算法，總尋道時間 = (60-50) + (70-60) + (90-70) + (150-90) + (150-20) + (30-20) = 240

結論

近年來，為了解決傳統磁碟排程演算法存在的侷限性，已經開發出了多種混合磁碟排程演算法。這些演算法結合了多種演算法的優點，以提高系統整體效能。混合演算法的一個示例是掃描-SSTF 演算法，此演算法的操作方式與 SCAN 演算法類似，但它也考慮請求與磁碟磁頭當前位置的距離。此演算法縮短了磁碟訪問時間，同時還可以縮短距離磁碟磁頭較遠的請求的等待時間。預測排程演算法使用預測演算法來預測未來的磁碟訪問請求，並提前安排它們。透過預測未來的請求並相應地定位磁碟磁頭，此演算法可以減少磁碟訪問時間。

磁碟排程演算法在現代作業系統中發揮著至關重要的作用，負責確定磁碟訪問請求得到服務的順序。選擇哪種演算法通常取決於工作負載和磁碟訪問模式，有若干種不同的演算法可供選擇，每種演算法都有自己的一套優點和缺點。磁碟排程演算法的最終目標是最大限度地縮短磁碟訪問時間並提高系統整體效能，而實現這一目標的方法是使用先進的演算法和高階計算技術。