當我們使用?read()?和?write()?系統(tǒng)調(diào)用向內(nèi)核提交讀寫文件操作時，內(nèi)核并不會立刻向硬盤發(fā)送 I/O 請求，而是先將 I/O 請求交給 I/O 調(diào)度層進行排序和合并處理。經(jīng)過 I/O 調(diào)度層加工處理后，才會將 I/O 請求發(fā)送給塊設(shè)備驅(qū)動進行最終的 I/O 操作。

下圖是塊設(shè)備 I/O 棧的架構(gòu)圖：

在上圖中，紅色那一層便是 I/O 調(diào)度層。

I/O 調(diào)度層主要完成的工作如下：

• 對新提交的 I/O 請求進行排序。

• 如果新的 I/O 請求能與舊的 I/O 請求進行合并，那么將會把兩個 I/O 請求合并成一個 I/O 請求。

• 向塊設(shè)備驅(qū)動層發(fā)送 I/O 請求。

什么是 I/O 調(diào)度層

現(xiàn)實中塊設(shè)備的種類非常多，如磁盤、SSD（固態(tài)硬盤） 和 CD-ROM 等。由于不同種類的塊設(shè)備其物理結(jié)構(gòu)不同，所以優(yōu)化 I/O 效率的算法也不一樣。如：SSD 讀寫任意地址中的數(shù)據(jù)速度都一樣，所以就沒必要進行額外的優(yōu)化，只需要將用戶提交 I/O 操作直接發(fā)送給塊設(shè)備驅(qū)動即可。

但有些塊設(shè)備的物理結(jié)構(gòu)比較特殊，如磁盤，其讀寫速度與磁頭移動的距離（尋道）有關(guān)，所以磁頭移動的距離越遠，讀寫速度就越慢。

磁盤的物理結(jié)構(gòu)如下圖所示：

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

假如有3個進程先后向磁盤寫入數(shù)據(jù)，如下圖所示：

如上圖序號的順序所示：首先進程 A 向扇區(qū) A 寫入數(shù)據(jù)，然后進程 B 向扇區(qū) B 寫入數(shù)據(jù)，最后進程 C 向扇區(qū) C 寫入數(shù)據(jù)。

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

• 當進程 A 的數(shù)據(jù)寫入到扇區(qū) A 后，將磁頭移動到較遠的扇區(qū) B 處，并將進程 B 的數(shù)據(jù)寫入到扇區(qū) B。

• 當進程 B 的數(shù)據(jù)寫入到扇區(qū) B 后，將磁頭倒退回到扇區(qū) C 處，并將進程 C 的數(shù)據(jù)寫入到扇區(qū) C 中。

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

如上述例子中，將數(shù)據(jù)寫入到扇區(qū) A 后，應(yīng)該接著寫扇區(qū) C，最后才寫扇區(qū) B。因為這樣磁盤移動的距離最小，尋道所需的時間最小。

為了提高 I/O 操作的效率，Linux 內(nèi)核需要對用戶提交的 I/O 操作進行排序和合并，這個工作就是通過 I/O 調(diào)度層來完成。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ?

I/O 調(diào)度層工作原理

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

由于不同的場景或硬件所需的優(yōu)化手段不一樣，比如固態(tài)硬盤（SSD）就不需要對 I/O 請求進行排序。

Linux 內(nèi)核為了適配不同的場景或硬件，定義了一套統(tǒng)一的接口。不同的 I/O 調(diào)度算法，只需要實現(xiàn)這套接口即可無縫接入到 I/O 調(diào)度層。如下圖所示：

從上圖可知，Linux 內(nèi)核支持多種 I/O 調(diào)度算法，如：CFQ調(diào)度算法、Deadline調(diào)度算法?與?noop調(diào)度算法?等。我們可以根據(jù)不同的場景來選擇適當?shù)恼{(diào)度算法，從而提升 I/O 操作的效率。

I/O 調(diào)度層通過?elevator_ops?結(jié)構(gòu)體來適配不同的 I/O 調(diào)度算法，這個結(jié)構(gòu)體定義了一系列的接口。不同的 I/O 調(diào)度算法只需要實現(xiàn)這些接口，然后注冊到 I/O 調(diào)度層后，即可被 I/O 調(diào)度層識別。

elevator_ops?結(jié)構(gòu)體定義如下：

elevator_ops?結(jié)構(gòu)定義了很多接口，但 I/O 調(diào)度算法只需要按需實現(xiàn)其中部分重要的接口即可。

下面我們來介紹一下?elevator_ops?結(jié)構(gòu)幾個重要接口的作用：

• elevator_merge_fn：用于判斷新提交的 I/O 請求是否能夠與 I/O 調(diào)度器中的請求進行合并。

• elevator_merged_fn：用于對合并后的 I/O 請求進行重新排序。

• elevator_dispatch_fn：用于將 I/O 調(diào)度器中的 I/O 請求分發(fā)給塊設(shè)備驅(qū)動層。

• elevator_add_req_fn：用于向 I/O 調(diào)度器添加新的 I/O 請求。

由于內(nèi)核支持多種 I/O 調(diào)度算法，所以內(nèi)核通過鏈表把所有的 I/O 調(diào)度算法連接起來。如果用戶編寫了新的 I/O 調(diào)度算法，可以使用?elv_register()?函數(shù)將其注冊到內(nèi)核中。

Deadline 調(diào)度算法

上面介紹了 I/O 調(diào)度層的原理，現(xiàn)在我們通過?Deadline調(diào)度算法?來分析它是怎么提升 I/O 操作的效率的。

1. 排序隊列

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

當向設(shè)備驅(qū)動層分發(fā) I/O 請求時，Deadline 調(diào)度器會按照排序后的順序進行分發(fā)，這樣做的好處是：可以減少磁頭移動的距離。如下圖所示：

雖然這樣能夠減少磁頭移動的距離，但對 I/O 請求進行排序可能會導(dǎo)致某些 I/O 請求出現(xiàn)?饑餓?的情況，饑餓的意思是用戶指發(fā)送的 I/O 請求長時間得不到執(zhí)行。

試想一下以下場景：

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

如果用戶沒有提交新的 I/O 請的話，那么執(zhí)行完扇區(qū)號 100 處的 I/O 請求后，便會移動到扇區(qū)號 200 處執(zhí)行 I/O 請求。

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

執(zhí)行 I/O 請求時會按照排序后的順序進行操作，那么扇區(qū)號 200 處的 I/O 請求就很有可能出現(xiàn)饑餓的情況。

2. FIFO隊列

為避免 I/O 請求出現(xiàn)饑餓的情況，Deadline 調(diào)度器還使用 FIFO（Frist In Frist Out）隊列來管理 I/O 請求。

在新的 I/O 請求被提交到 Deadline 調(diào)度器時，Deadline 調(diào)度器會為 I/O 請求設(shè)置一個限期（Deadline），然后添加到 FIFO 隊列中。如下圖所示：

在向設(shè)備驅(qū)動層分發(fā) I/O 請求時，Deadline 調(diào)度器首先會查看 FIFO 隊列中的第一個 I/O 請求是否超時。如果超時了，那么將 FIFO 隊列的第一個 I/O 請求分發(fā)給設(shè)備驅(qū)動層。否則，將會從排序隊列中獲取下一個 I/O 請求分發(fā)給設(shè)備驅(qū)動層。

Deadline 調(diào)度器通過設(shè)置 I/O 請求的限期和 FIFO 隊列，來解決 I/O 請求出現(xiàn)饑餓的情況。

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

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

原文作者：Linux內(nèi)核那些事