Linux IO排程器1、Linus電梯2、DeadLine3、Anticipatory4、CFQ(Complete Fair Queuing)5、Noop

在現代計算機體系中，機械硬碟仍然作為大部分情況下的儲存設備使用，而機械硬碟的通路相對記憶體差了多個數量級，主要原因在于機械臂轉動的尋道時間太長，機械操作沒法跟上電子信号的傳遞，是以OS不可能對每次I/O請求都直接作尋道處理，而是需要額外的工作。

在Linux中，這部分工作主要由I/O排程器完成。

既然時間消耗主要花費在尋道上，那麼減少尋道時間就成為I/O排程算法的核心，這主要是通過對I/O請求實施合并和排序完成的。I/O排程器的主要工作是管理像磁盤這種塊裝置的請求隊列，并配置設定I/O資源給請求。目标是提升全局吞吐量，注意，這意味着I/O請求并不是按照FIFO來處理，而是存在不公平的現象，原理類似于公平鎖和非公平鎖。

I/O排程器通過合并和排序完成排程任務。

合并是指将兩個或多個請求結合成一個新的請求，例如當新來的請求和目前請求隊列中的某個請求需要通路的是相同或相鄰扇區時，那麼就可以把兩個請求合并為對同一或多個相鄰扇區的請求，這樣隻需要一次尋道即可。通過合并的做法，多個I/O請求被壓縮為一次I/O，最後發送給磁盤的隻需要一條尋址指令，就能完成多次尋址同樣的效果。顯然，合并請求能減少系統開銷和磁盤尋址次數。

解決了對相鄰扇區的通路，那麼對于非相鄰扇區呢？我們知道機械臂的轉動是朝着扇區增長的方向的，類似于電梯，那麼如果我們把I/O請求按照扇區增長排列，一次旋轉就可以通路更多的扇區，就可以縮短所有請求的實際尋道時間。這便是I/O排程器的另一項任務：排序。

上面說到排序操作導緻的結果和電梯類似，是以早期Linux的I/O排程算法被稱為電梯算法，在2.4核心中，被稱作Linus電梯。 Linus電梯實作了向前合并和向後合并，對應扇區的增長和減少，而排序操作則如同上面所說的，通過将新請求插入到已有請求隊列中合适的位置去實作。那麼這裡就有一個問題了，如果一個請求比較倒黴，老是被插隊怎麼辦？Linus電梯解決這個問題的辦法是當一段時間後檢測到隊列中有長期沒有被處理的請求，那麼就暫時中止插入，将新請求直接放到隊列尾部，寄希望于順序處理目前隊列中現有的請求來保證響應。但這種做法的缺點在于，I/O排程器并沒有真正去處理饑餓的請求，而是采取了一種間接的方式，是以很有可能饑餓的請求仍然饑餓，并沒有解決實質的問題。

為了解決Linus電梯的饑餓問題，DeadLine在全局吞吐量和延遲方面取了權衡。在DeadLine算法中，每個I/O請求都有一個逾時時間，預設讀請求是500ms，寫請求是5s。 DeadLine除了和Linus電梯一樣維護了一個擁有合并和排序功能的請求隊列以外，額外維護了兩個隊列，分别是讀請求隊列和寫請求隊列，它們都是帶有逾時的FIFO隊列。當新來一個I/O請求時，會被同時插入普通隊列和讀/寫隊列，然後處理普通隊列中的請求。當排程器發現讀/寫請求隊列中的請求逾時的時候，會優先處理這些請求，保證盡可能不産生請求饑餓。當然，這裡會犧牲一定的全局吞吐量。

DeadLine解決了饑餓問題，但是降低了全局吞吐量，當系統大量存在順序請求時，可能導緻請求無法被很好地排序，引發頻繁尋道。 Anticipatory是基于預測的I/O算法，大體上它和DeadLine很類似，也維護了三個請求隊列。差別在于，當它處理完一個I/O請求以後并不會直接傳回處理下一個請求，而是會等待片刻，預設為6ms。如果這時候有新來的針對目前扇區相鄰扇區的請求，那麼會直接處理它，當等待時間結束後，排程器才傳回處理下一個隊列請求。 試想一下，如果系統有頻繁的針對鄰近扇區的I/O請求，那麼這種預測算法必然大幅提高整體的吞吐量，畢竟節約了那麼多尋道時間。Anticipatory也是目前Linux核心預設的I/O排程器。 更新：在Linux Kernel 2.6.28 的Anticipatory/CFS算法中，對于塊裝置增加了QUEUE_FLAG_NONROT的标志位，标記随機通路裝置以消除等待時間的開銷。感謝 @fbcon 的提醒：）

CFQ把I/O請求按照程序分别放入程序對應的隊列中，是以A程序和B程序發出的I/O請求會在兩個隊列中。而各個隊列内部仍然采用合并和排序的方法，差別僅在于，每一個送出I/O請求的程序都有自己的I/O隊列。 CFQ的“公平”是針對程序而言的，它以時間片算法為前提，輪轉排程隊列，預設從目前隊列中取4個請求處理，然後處理下一個隊列的4個請求。這樣就可以確定每個程序享有的I/O資源是均衡的。

Noop做的事情非常簡單，它不會對I/O請求排序也不會進行任何其它優化（除了合并）。Noop除了對請求合并以外，不再進行任何處理，直接以類似FIFO的順序送出I/O請求。 那麼為什麼我們需要這種排程器呢？因為Noop面向的不是普通的塊裝置，而是随機通路裝置（例如SSD），對于這種裝置，不存在傳統的尋道時間，那麼就沒有必要去做那些多餘的為了減少尋道時間而采取的事情了。

從上面的算法中我們可以看到，對于不同的場景，選擇不同的I/O排程器是十分有必要的。例如對于資料庫這種随機通路特别明顯的場景，如果使用預設的Anticipatory，就會犧牲大量不必要的等待時間，這時候使用DeadLine通常是更好的選擇。對于SSD這種裝置，采用Noop或者DeadLine也通常能獲得比預設排程器更好的性能。