IO調度發生在Linux內核的IO調度層。這個層次是針對Linux的整體IO層次的。從read()或write()系統調用的角度來看，Linux的整體IO系統可以分為七層，分別是:
VFS層:虛擬文件系統層。由於內核要處理多種文件系統，每個文件系統實現的數據結構和相關方法可能不同，所以內核抽象了這壹層，專門用來適應各種文件系統，提供統壹的操作接口。
文件系統層:不同的文件系統實現各自的操作流程，提供各自獨特的功能。這件事我不需要多說。如果妳願意，妳可以自己讀代碼。
頁面緩存層:負責緩存頁面。
通用塊層:因為大部分io操作都是處理塊設備，所以Linux提供了壹個類似於vfs層的塊設備操作抽象層。下層為各種不同屬性的塊設備提供統壹的塊IO請求標準。
IO調度層:由於大部分塊設備都是磁盤之類的設備，所以需要根據這類設備的特點和應用的不同特點，設置壹些不同的調度算法和隊列。為了提高磁盤在不同應用環境下的讀寫效率，這就是著名的Linux電梯發揮作用的地方。這裏實現了機械硬盤的各種調度方式。
塊設備驅動層:驅動層提供了壹個相對高級的設備操作接口，往往是C語言，而下層則接口設備本身的操作方法和規範。
塊設備層:這壹層是具體的物理設備，定義了真實設備的各種操作方法和規範。
有壹個有條理的【Linux IO結構圖】，非常經典，壹圖勝千言:
我們今天要研究的主要是IO調度層。
要解決的核心問題是如何提高塊設備IO的整體性能。這壹層也主要是針對機械硬盤的結構而設計的。
眾所周知，機械硬盤的存儲介質是磁盤，磁頭在磁盤上移動尋址磁道，類似於放唱片。
這種結構的特點是順序訪問時吞吐量高，但如果存在隨機訪問磁盤的情況，會在磁頭的移動上浪費大量時間，導致每次IO的響應時間更長，大大降低IO的響應速度。
磁盤上磁頭的尋道操作類似於電梯調度。事實上，在最開始，Linux把這種算法命名為Linux電梯算法，即:
如果能夠在尋道過程中“順便”處理所有依次經過的相關磁道的數據請求，那麽就可以在對響應速度影響不大的情況下提高整體IO的吞吐量。
這就是為什麽我們要設計IO調度算法的原因。
目前內核默認開啟三種算法/模式:noop、cfq和deadline。嚴格來說，應該有兩種:
因為第壹種叫noop，是空操作調度算法，即沒有調度操作，io請求不排序，只有壹個fifo隊列進行適當的io合並。
目前內核默認的調度算法應該是cfq，也就是所謂的完全公平隊列調度。顧名思義，這種調度算法試圖為所有進程提供壹個完全公平的IO操作環境。
註:請記住這個詞，cfq，完全公平隊列調度，否則看不下去。
Cfq為每個進程創建壹個同步的IO調度隊列，以時間片和請求數限制的方式默認分配IO資源，保證每個進程的IO資源占用是公平的。cfq還實現了進程級的優先級調度，我們將在後面詳細解釋。
查看和修改IO調度算法是:
Cfq是通用服務器更好的IO調度算法選擇，對於桌面用戶也是更好的選擇。
但是對於很多IO壓力大的場景，尤其是IO壓力集中在某些進程上的場景，就不是很適合了。
因為這種場景，我們需要更多地滿足壹個或幾個進程的io響應速度，而不是讓所有進程都公平地使用IO，比如數據庫應用。
截止時間調度(Deadline scheduling)是更適合上述場景的解決方案。截止日期實現了四個隊列:
其中兩個分別處理正常讀寫，按扇區號排序，合並正常io提高吞吐量。因為io請求可能集中在某些磁盤位置，新的請求會壹直合並，其他磁盤位置的IO請求可能會餓死。
另外兩個處理超時讀寫的隊列是按照請求創建時間排序的，如果超時請求出現，就放入這兩個隊列中。調度算法確保隊列中超過截止時間的請求將被首先處理，以防止請求被餓死。
不久前內核還默認標配了四種算法，還有壹種算法叫as(predictive scheduler)，預測調度算法。壹個高大上的名字讓我覺得Linux內核會算命。
結果表明，基於截止期算法的io調度無非是等待壹小段時間。如果這段時間內有可以合並的io請求，可以合並，提高順序讀寫情況下截止期調度的數據吞吐量。
其實這根本不是預測。我覺得還是叫大運調度算法比較好。當然，這種策略在某些特定場景下並不有效。
但在大多數場景下，這種調度不僅沒有提高吞吐量，還降低了響應速度，所以內核幹脆將其從默認配置中刪除。畢竟Linux的目的是實用，我們不會在這個調度算法上浪費口舌。
1，cfq:完全公平隊列調度
Cfq是內核選擇的默認IO調度隊列，在桌面應用場景和最常見的應用場景都是不錯的選擇。
如何實現壹個所謂的完全公平排隊？
首先，我們要明白對誰公平？從操作系統的角度來看，產生操作行為的主體是進程，所以這裏的公平是針對每個進程的，要盡量讓進程公平地占用IO資源。
那麽如何讓進程公平地占用IO資源呢？我們首先要了解什麽是IO資源。我們在衡量壹個IO資源時，壹般喜歡用兩個單位，壹個是數據讀寫的帶寬，壹個是數據讀寫的IOPS。
帶寬是以時間為單位的數據讀寫量，例如100兆字節/秒。IOPS是以時間為單位的讀寫次數。在不同的讀寫情況下，這兩個單元的性能可能會有所不同，但可以肯定的是，兩個單元中的任何壹個達到性能極限，都會成為IO的瓶頸。
考慮到機械硬盤的結構，如果讀寫是順序讀寫，IO的性能就是可以用較少的IOPS實現較大的帶寬，因為可以合並很多IO，通過預讀的方式可以加快數據讀取效率。
當io的性能偏向隨機讀寫時，IOPS會變大，合並IO請求的可能性會降低。每次IO請求的數據越少，帶寬性能就越低。
由此我們可以理解，壹個進程的IO資源主要有兩種表現形式:單位時間內進程提交的IO請求數量和進程占用的帶寬。
其實不管是哪壹種，都和進程分配的IO處理時間長短密切相關。
有時候服務可以占用更大的帶寬，IOPS更少，而其他服務可能占用更小的帶寬，IOPS更大，所以調度壹個進程占用IO的時間相對來說是最公平的。
也就是說，我不在乎妳的IOPS高還是妳的帶寬高。到時候我們再切換到下壹個流程，隨便妳。
因此，cfq試圖為所有進程分配相同的時間片。在時間片期間，進程可以將生成的IO請求提交給塊設備進行處理。在時間片結束時，進程的請求將在其自己的隊列中排隊，以便在下壹個調度時間進行處理。這是cfq的基本原理。
當然，現實生活中不可能有真正的“公平”。在常見的應用場景中，我們願意手動給壹個進程的IO占用分配優先級，就像給壹個進程的CPU占用設置優先級壹樣。
因此，除了時間片的公平隊列調度，cfq還提供了優先級支持。每個進程可以設置壹個IO優先級，cfq會把這個優先級的設置作為調度的重要參考因素。
優先級首先分為RT、BE和IDLE三類，分別是實時、盡力而為和空閑，並采用不同的策略來處理每壹類的IO和cfq。此外，在RT和BE類別中，劃分了八個子優先級以實現更詳細的QOS要求，而IDLE只有壹個子優先級。
此外，我們都知道，默認情況下，內核讀寫緩沖區/緩存中的存儲。在這種情況下，cfq無法區分當前處理的請求來自哪個進程。
只有當進程使用同步模式(sync read或sync wirte)或直接IO模式讀寫時，cfq才能區分IO請求來自哪個進程。
因此，除了為每個進程實現的IO隊列之外，還實現了壹個公共隊列來處理異步請求。
目前內核已經實現了對IO資源的cgroup資源隔離，所以在上述系統的基礎上，cfq還實現了對cgroup的調度支持。
壹般來說，cfq使用壹系列數據結構來支持上述所有復雜功能。可以通過源代碼看到相關的實現。該文件位於Block/CFQ-IOSched的源代碼目錄中。C.
1.1 cfq的設計原理
在這裏，我們對整體數據結構做壹個簡單的描述:首先，cfq通過壹個名為cfq_data的數據結構來維護整個調度程序進程。在支持cgroup功能的cfq中，所有進程被分成幾個控制組進行管理。
每個cgroup用cfq的cfq _ group結構描述，所有cgroup作為調度對象放入壹棵紅黑樹中，以vdisktime為關鍵字排序。
vdisktime的時間記錄了當前cgroup占用的io時間。每次調度cgroup時，總是通過紅黑樹選擇當前vdisktime最少的cgroup進行處理，以保證所有cgroup之間IO資源占用的“公平性”。
當然我們知道，cgroup可以按比例分配資源給blkio，其工作原理是分配比例大的cgroup占用的時間增長緩慢，而分配比例小的vdisktime占用的時間增長迅速，速度與分配比例成正比。
這樣不同的cgroup分配的IO比例是不壹樣的，從cfq的角度看還是“公平”的。
在選擇了要處理的cgroup(cfq_group)之後，調度器需要決定選擇下壹個service_tree。
數據結構service_tree對應壹系列紅黑樹，主要目的是實現請求優先級的分類，即RT、BE、IDLE的分類。每個cfq_group維護七個服務樹，定義如下:
其中，service_tree_IDLE是壹棵紅黑樹，用於對空閑請求進行排隊。
在上面的二維數組中，首先第壹維分別為RT和BE實現壹個數組，每個數組維護三棵紅黑樹，分別對應三種不同的請求子類型，即SYNC、SYNC_NOIDLE和ASYC。
我們可以認為SYNC等同於SYNC_IDLE，對應於sync _ noiidle。空閑是cfq為了盡可能多的組合連續IO請求以提高吞吐量而添加的機制。我們可以把它理解為壹種“閑置”的等待機制。
空閑意味著當壹個隊列處理完壹個請求時，它將在調度之前等待壹段時間。如果下壹個請求到來，它可以減少頭尋址並繼續處理順序IO請求。
為了實現這個功能，cfq在service_tree的數據結構中實現了同步隊列。如果請求是同步順序請求，它將在此服務樹中排隊。如果請求是同步隨機請求，將在SYNC_NOIDLE隊列中排隊，判斷下壹個請求是否是順序請求。
所有異步寫請求將在async的服務樹中排隊，這個隊列沒有空閑等待機制。
此外，cfq還對ssd等硬盤進行了特殊的調整。當cfq發現存儲設備是SSD硬盤等隊列更深的設備時，所有針對單個隊列的空閑都不會生效，所有IO請求都會排隊到SYNC_NOIDLE的服務樹中。
每個服務樹對應幾個cfq_queue隊列，每個cfq_queue隊列對應壹個進程，我們後面會詳細解釋。
Cfq_group還維護壹個異步IO請求隊列，該隊列為cgroup中的所有進程所共有。其結構如下:
異步請求也分為三類:RT、BE和IDLE，每壹類都排隊壹個cfq_queue。
BE和RT也支持優先級。每種類型都有多個優先級，比如IOPRIO_BE_NR。這個值被定義為8，數組下標為0-7。
我們目前分析的內核代碼版本是Linux 4.4。可以看出，從cfq的角度來看，已經實現了對異步IO的cgroup支持。我們這裏需要定義壹下異步IO的含義，異步IO僅指將數據從內存中的緩沖區/緩存同步到硬盤的IO請求。而不是aio(man 7 aio)或者linux的原生異步io和libaio機制，其實這些所謂的“異步”io機制都是在內核中同步實現的(馮諾依曼計算機本質上並沒有真正的“異步”機制)。
正如我們上面所解釋的，由於進程通常首先將數據寫入緩沖區/緩存，這種異步IO由cfq_group中的異步請求隊列統壹處理。
那麽為什麽要在上面的service_tree中實現和壹個異步類型呢？
當然，這是為了支持區分進程的異步IO，並為“完全公平”做好準備。
其實在最新的cgroup v2的blkio系統中，內核已經支持cgroup對buffer IO的限速支持，這些可能容易混淆的類型都是新系統中需要用到的類型標簽。
新系統更復雜，功能更強大，不過不用擔心，正式的cgroup v2系統會在Linux 4.5發布時正式看到。
我們繼續選擇service_tree的過程。service_tree的三種優先級類型的選擇是根據類型的優先級進行的，RT優先級最高，BE次之，IDLE最低。也就是說，RT中有壹個，就壹直處理RT，沒有RT，就處理BE。
每個service_tree對應壹棵元素為cfq_queue的紅黑樹，每個cfq_queue是內核為壹個進程(線程)創建的請求隊列。
每個cfq_queue維護壹個變量rb_key，實際上就是這個隊列的IO服務時間。
這裏通過紅黑樹找到服務時間最短的cfq_queue，保證“完全公平”。
選擇cfq_queue之後，就該開始處理這個隊列中的IO請求了。這裏的調度方式基本類似於deadline。
Cfq_queue將每個進入隊列的請求排隊兩次，壹次在fifo中，另壹次在紅黑樹中，以訪問扇區順序為關鍵字。
默認情況下，請求是從紅黑樹中提取出來進行處理的。當請求的延遲時間達到deadline時，從紅黑樹中取出等待時間最長的請求進行處理，保證請求不會餓死。
這就是整個cfq調度過程，當然還有很多細節沒有解釋，比如合並處理和順序處理。
1.2 cfq的參數調整
了解整個調度過程有助於我們決定如何調整cfq的相關參數。cfq的所有可調參數都可以在目錄/sys/class/block/sda/queue/io sched/中找到。當然，在妳的系統上，請用相應的磁盤名替換SDA。讓我們看看我們有什麽:
其中壹些參數與機械硬盤磁頭的尋道模式有關。如果顯示看不懂，請先補充相關知識:
Back_seek_max:磁頭可以向後尋址的最大範圍，默認值為16M。
Back_seek_penalty:反向尋址的懲罰系數。該值與正向尋址進行比較。
以上兩個設置是為了防止磁頭尋道抖動導致尋址緩慢。基本思想是，當壹個io請求到達時，cfq將根據它的尋址位置估計它的磁頭尋道成本。
設置back_seek_max的最大值。只要尋址範圍不超過該值，cfq就會將其視為向前尋址的請求。
當設置壹個系數back_seek_penalty來評估代價，相對於頭向前尋址，向後尋址的距離為1/2(1/back _ seek _ penalty)時，cfq認為這兩個請求的代價是壹樣的。
這兩個參數實際上是cfq判斷請求合並處理的條件限制，在這個請求處理過程中所有結合這個條件的請求都會盡量合並在壹起。
Fifo_expire_async:設置異步請求超時。
同步請求和異步請求在不同的隊列中處理。壹般來說，在調度時，cfq會優先處理同步請求，然後處理異步請求，除非異步請求滿足上述合並的條件和限制。
當這個進程的隊列被調度時，cfq會先檢查是否有異步請求超時，即超過fifo_expire_async參數的限制。如果有，將首先發送壹個超時請求，其余請求仍將根據優先級和扇區號進行處理。
Fifo_expire_sync:這個參數和上面的類似，只是用來設置同步請求的超時。
Slice_idle:該參數設置等待時間。這就使得cfq在切換cfq_queue或者服務樹的時候要等待壹段時間，以提高機械硬盤的吞吐量。
通常，來自同壹cfq_queue或服務樹的IO請求具有更好的尋址局部性，因此這可以減少磁盤尋址的數量。該值在機械硬盤上默認為非零值。
當然，在SSD或者硬盤RAID設備上設置這個值為非零會降低存儲效率，因為SSD沒有頭尋址的概念，所以在這類設備上應該設置為0，並且關閉這個功能。
Group_idle:這個參數和前面的類似，只是cfq在切換cfq_group的時候會等待壹段時間。
在cgroup的場景中，如果按照slice_idle的方式，cgroup中的每個進程在切換cfq_queue時都可能出現空閑等待。
這樣，如果該進程壹直有請求要處理，則同壹組中的其他進程可能不會被調度，直到該cgroup的配額用盡。這會造成同組其他進程餓死，造成IO性能瓶頸。
在這種情況下，我們可以設置slice _ idle = 0，group _ idle = 8。為了防止上述問題，這種空閑等待是在cgroup中進行的，而不是在cfq_queue的進程中。
Low_latency:該開關用於開啟或關閉cfq的低延遲模式。
當這個開關打開時，cfq會根據target_latency的參數設置重新計算每個進程的切片時間。
這將有利於吞吐量的公平性(默認為時間片分配的公平性)。
關閉此參數(設置為0)將忽略target_latency的值。這將使系統中的進程能夠完全根據時間片方法分配IO資源。默認情況下，此開關是打開的。
我們已經知道，cfq設計中有壹個“空轉”的概念，為了合並盡可能多的連續讀寫操作，為了增加吞吐量而減少磁頭的尋址操作。
如果壹個進程總是順序快速讀寫，會因為cfq的空閑等待命中率高而拖慢其他需要處理IO的進程的響應速度。如果另壹個需要調度的進程沒有發出大量的順序IO行為，那麽系統中不同進程的IO吞吐量性能會非常不均衡。
例如，當系統內存的緩存中有許多臟頁要寫回時，桌面必須打開瀏覽器進行操作。這時候臟頁回寫的後臺行為很可能大量命中空閑時間，導致瀏覽器的少量IO壹直等待，讓用戶感覺瀏覽器響應速度慢。
這種低延遲主要是優化這種情況的壹種選擇。開啟時，系統會根據target_latency的配置，限制因hit idling占用大量IO吞吐量的進程，以達到不同進程IO占用吞吐量的相對平衡。這個開關更適合在類似桌面應用的場景下開啟。
Target_latency:當low_latency的值為on時，cfq會根據這個值重新計算每個進程分配的IO槽長。
Quantum:該參數用於設置壹次從cfq_queue處理多少個IO請求。在隊列處理事件周期中，超過此數量的IO請求將不會被處理。此參數僅對同步請求有效。
Slice_sync:當調度cfq_queue隊列進行處理時，可以分配給它的總處理時間由該值作為計算參數指定。公式為:time _ slice = slice _ sync+(slice _ sync/5 *(4-prio))。此參數對同步請求有效。
Slice_async:這個值與前壹個值類似，只是它對異步請求有效。
Slice_async_rq:該參數用於限制壹個隊列在壹個時間片範圍內可以處理的異步請求的最大數量。要處理的最大請求數也與相關進程設置的io優先級有關。
1.3 cfq的IOPS模式
我們已經知道，默認情況下，cfq是由時間片支持的優先級調度，以保證IO資源占用的公平性。
高優先級的進程將獲得更長的時間片長度，而低優先級的進程將獲得更短的時間片。
當我們的存儲是支持NCQ (Native Instruction Queue，原生指令隊列)的高速設備時，為了提高NCQ的利用率，我們最好讓它處理來自多個cfq隊列的多個請求。
這時候用時間片分配來分配資源就不合適了，因為基於時間片分配，同壹時間最多只能處理壹個請求隊列。
此時，我們需要將cfq模式切換到IOPS模式。切換模式很簡單，即slice_idle=0。內核會自動檢測妳的存儲設備是否支持NCQ，如果支持，cfq會自動切換到IOPS模式。
此外，在默認的基於優先級的時間片模式下，我們可以使用ionice命令來調整進程的IO優先級。進程分配的默認IO優先級是根據進程的nice值計算的，計算方法可以在Manionics看到，這裏就不廢話了。
2.截止日期:截止日期計劃
截止期調度算法比cfq簡單得多。其設計目標是:
在確保請求按照設備扇區的順序被訪問的同時，其他請求不應該被餓死，應該在截止日期之前被調度。
我們知道，磁頭對磁盤的尋道可以順序和隨機訪問。由於尋道的延遲時間，IO的吞吐量在順序訪問中較大，在隨機訪問中較小。
如果我們要優化壹個機械硬盤的吞吐量，那麽我們可以讓調度器盡可能的將訪問的IO請求按照復合順序排序，然後請求按照這個順序發送到硬盤，這樣可以讓IO吞吐量變大。
但是這樣做還有壹個問題，就是如果此時出現請求，它要訪問的磁道距離當前磁頭所在的磁道較遠，大量的應用請求集中在當前磁道附近。
因此，大量的請求總是會被合並並排隊等待處理，而訪問相對較遠的磁道的請求會因為從未被調度而餓死。
Deadline就是這樣壹個調度器，既能保證IO的最大吞吐量，又能盡量讓遠程請求在限定的時間內被調度，而不至於餓死。