圖解 I-O 調度層

當我們使用 read() 和 write() 系統調用向內核提交讀寫文件操作時，內核並不會立刻向硬盤發送 I/O 請求，而是先將 I/O 請求交給 I/O 調度層進行排序和合並處理。經過 I/O 調度層加工處理後，纔會將 I/O 請求發送給塊設備驅動進行最終的 I/O 操作。

下圖是塊設備 I/O 棧的架構圖：

在上圖中，紅色那一層便是 I/O 調度層。

I/O 調度層主要完成的工作如下：

什麼是 I/O 調度層

現實中塊設備的種類非常多，如磁盤、SSD（固態硬盤） 和 CD-ROM 等。由於不同種類的塊設備其物理結構不同，所以優化 I/O 效率的算法也不一樣。如：SSD 讀寫任意地址中的數據速度都一樣，所以就沒必要進行額外的優化，只需要將用戶提交 I/O 操作直接發送給塊設備驅動即可。

但有些塊設備的物理結構比較特殊，如磁盤，其讀寫速度與磁頭移動的距離（尋道）有關，所以磁頭移動的距離越遠，讀寫速度就越慢。

磁盤的物理結構如下圖所示：

對於磁盤來說，順序讀寫的速度是最快的。這是由於順序讀寫時，磁頭移動的距離最小。所以，避免隨機讀寫是加速磁盤 I/O 效率最有效的辦法。

假如有 3 個進程先後向磁盤寫入數據，如下圖所示：

如上圖序號的順序所示：首先進程 A 向扇區 A 寫入數據，然後進程 B 向扇區 B 寫入數據，最後進程 C 向扇區 C 寫入數據。

如上圖所示，扇區 A 到扇區 B 的距離要比扇區 A 到扇區 C 的距離遠。如果按照 I/O 提交的順序進行操作，那麼步驟如下：

聰明的讀者可以發現，其實上面的過程可以進行優化。而優化的方案是：進行 I/O 操作時，按照磁盤的移動方向的順序進行 I/O 操作，而不是按照提交的順序進行 I/O 操作。

如上述例子中，將數據寫入到扇區 A 後，應該接着寫扇區 C，最後才寫扇區 B。因爲這樣磁盤移動的距離最小，尋道所需的時間最小。

爲了提高 I/O 操作的效率，Linux 內核需要對用戶提交的 I/O 操作進行排序和合並，這個工作就是通過 I/O 調度層來完成。

I/O 調度層工作原理

通過前面的分析可知，I/O 調度層的主要工作是合併和排序用戶提交的 I/O 操作，從而達到提升 I/O 效率的作用。

由於不同的場景或硬件所需的優化手段不一樣，比如固態硬盤（SSD）就不需要對 I/O 請求進行排序。

Linux 內核爲了適配不同的場景或硬件，定義了一套統一的接口。不同的 I/O 調度算法，只需要實現這套接口即可無縫接入到 I/O 調度層。如下圖所示：

從上圖可知，Linux 內核支持多種 I/O 調度算法，如：CFQ調度算法、Deadline調度算法 與 noop調度算法 等。我們可以根據不同的場景來選擇適當的調度算法，從而提升 I/O 操作的效率。

I/O 調度層通過 elevator_ops 結構體來適配不同的 I/O 調度算法，這個結構體定義了一系列的接口。不同的 I/O 調度算法只需要實現這些接口，然後註冊到 I/O 調度層後，即可被 I/O 調度層識別。

elevator_ops 結構體定義如下：

struct elevator_ops
{
    elevator_merge_fn *elevator_merge_fn;
    elevator_merged_fn *elevator_merged_fn;
    ...
    elevator_dispatch_fn *elevator_dispatch_fn;
    elevator_add_req_fn *elevator_add_req_fn;
    ...
};

elevator_ops 結構定義了很多接口，但 I/O 調度算法只需要按需實現其中部分重要的接口即可。

下面我們來介紹一下 elevator_ops 結構幾個重要接口的作用：

由於內核支持多種 I/O 調度算法，所以內核通過鏈表把所有的 I/O 調度算法連接起來。如果用戶編寫了新的 I/O 調度算法，可以使用 elv_register() 函數將其註冊到內核中。

Deadline 調度算法

上面介紹了 I/O 調度層的原理，現在我們通過 Deadline調度算法 來分析它是怎麼提升 I/O 操作的效率的。

1. 排序隊列

Deadline 調度算法通過使用紅黑樹（一種平衡二叉樹）來 I/O 請求進行排序，節點的鍵爲 I/O 請求的開始扇區號，值爲 I/O 請求實體。如下圖所示：

當向設備驅動層分發 I/O 請求時，Deadline 調度器會按照排序後的順序進行分發，這樣做的好處是：可以減少磁頭移動的距離。如下圖所示：

雖然這樣能夠減少磁頭移動的距離，但對 I/O 請求進行排序可能會導致某些 I/O 請求出現 飢餓 的情況，飢餓的意思是用戶指發送的 I/O 請求長時間得不到執行。

試想一下以下場景：

磁盤正在扇區號 100 處執行 I/O 操作，這時用戶提交一個新的 I/O 請求，此 I/O 請求的起始扇區號爲 200，如下圖所示：

如果用戶沒有提交新的 I/O 請的話，那麼執行完扇區號 100 處的 I/O 請求後，便會移動到扇區號 200 處執行 I/O 請求。

此時如果用戶連續在扇區號 110、120、130 處提交了新的 I/O 請求，由於 Deadline 調度器會以 I/O 請求的起始扇區號進行排序，所以 I/O 隊列將會變成如下圖所示情況：

執行 I/O 請求時會按照排序後的順序進行操作，那麼扇區號 200 處的 I/O 請求就很有可能出現飢餓的情況。

2. FIFO 隊列

爲避免 I/O 請求出現飢餓的情況，Deadline 調度器還使用 FIFO（Frist In Frist Out）隊列來管理 I/O 請求。

在新的 I/O 請求被提交到 Deadline 調度器時，Deadline 調度器會爲 I/O 請求設置一個限期（Deadline），然後添加到 FIFO 隊列中。如下圖所示：

在向設備驅動層分發 I/O 請求時，Deadline 調度器首先會查看 FIFO 隊列中的第一個 I/O 請求是否超時。如果超時了，那麼將 FIFO 隊列的第一個 I/O 請求分發給設備驅動層。否則，將會從排序隊列中獲取下一個 I/O 請求分發給設備驅動層。

Deadline 調度器通過設置 I/O 請求的限期和 FIFO 隊列，來解決 I/O 請求出現飢餓的情況。

另外，Deadline 調度器爲 讀/寫 操作分別各分配一個排序隊列和 FIFO 隊列，所以在 Deadline 調度器中維護了 4 個隊列：讀排序隊列、寫排序隊列、讀FIFO隊列 和 寫FIFO隊列。

這是因爲在 I/O 操作中，讀操作比寫操作需要的實時性更高，所以會優先處理讀操作。如果將讀寫操作放在同一個隊列進行管理，那麼就不能優先處理讀操作了。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/blzg9BEBSV8vyGiUFfUgNQ

猜你喜歡