deadline 簡介

deadline 是linux內核通用塊層中自帶的四個IO電梯調度器之一，其他的三個分別為noop(no operation)、cfq(completely fair queuing)、as(anticipatory scheduling)，其中noop是個空的調度器，僅僅直接轉發IO請求，不提供排序和合并的功能，適合ssd和nvme等快速存儲設備。deadline 調度器由通用塊層的maintainer Jens Axboe在2002年首次寫出并于同期合并進內核，此后幾乎沒經過大的修改，歷久彌堅，現在已是通用塊層單隊列的默認IO調度器。deadline相對與其他電梯調度器綜合考慮IO請求的吞吐量和時延性，最要體現在以下三個方面：

ü電梯性

ü饑餓性

ü超時性

各個性質的解析后面會具體介紹。測試數據表明，deadline在大多數多線程應用場景和數據庫應用場景下表現的性能要優于cfq和as。

通用塊層調度器框架

內核通用塊層自帶四種IO調度器，每個塊設備在注冊的時候都會為其指定一種調度器，塊設備在運行的時候可以通過/sys接口動態調整當前塊設備使用的調度器，當然如果你喜歡，也可以自己實現一種滿足自己需求的IO調度器，并按照接口標準注冊到通用塊層。通用塊層為了滿足調度器的擴充，方便管理各式各樣的調度器，提煉出了一個統一的框架，稱之為電梯框架。每個調度器只需要需按照框架的標準實現自己調度策略的鉤子函數，然后向電梯框架注冊自己，后續的塊設備就可以使用該注冊的調度器。內核中大量使用了設計與實現分離的編程手法，熟悉內核md(multi device)子系統的開發人員應該很了解這種手法，md子系統規范出一個統一的接口，然后各個特性化的raid實現這些接口，并向md層注冊自己。電梯調度器框架所包含的接口由內核源碼下的include/linux/elevator.h中的struct elevator_ops結構體定義，每個調度器根據自己的特性只需要實現其中部分接口即可。其中最基本的接口有四個：

lelevator_init_fn：調度器初始化接口，注冊時被調用，用于初始化調度器的私有數據結構;

lelevator_exit_fn：調度器退出接口，解注冊時被調用，用于釋放申請的數據結構;

lelevator_add_req_fn：調度器入口函數，用于向調度器中添加IO請求;

lelevator_dispatch_fn：調度器出口函數，用于將調度器內的IO請求派發給設備驅動;

deadline 實現原理

deadline調度器實現的接口有：

static struct elevator_type iosched_deadline = {

.ops.sq = {

.elevator_merge_fn = deadline_merge,

.elevator_merged_fn= deadline_merged_request,

.elevator_merge_req_fn = deadline_merged_requests,

.elevator_dispatch_fn = deadline_dispatch_requests,

.elevator_add_req_fn = deadline_add_request,

.elevator_former_req_fn = elv_rb_former_request,

.elevator_latter_req_fn = elv_rb_latter_request,

.elevator_init_fn = deadline_init_queue,

.elevator_exit_fn = deadline_exit_queue,

},

.elevator_attrs = deadline_attrs,

.elevator_name = "deadline",

.elevator_owner = THIS_MODULE,

};

這些接口在調度器注冊的時候告訴調度器框架本調度器對外暴露的方法，除了對外暴露的接口以外，deadline內部還有一些數據結構，用于快速的保存和操作IO請求，如紅黑樹，鏈表等。這些數據結構是deadline內部使用的，可以統稱為調度器的調度隊列，對外不可見，需要調度器的接口才能操作。

struct deadline_data {

struct rb_root sort_list[2];

struct list_head fifo_list[2];

struct request *next_rq[2];

unsigned int batching; /* number of sequential requests made */

unsigned int starved; /* times reads have starved writes */

int fifo_expire[2];

int fifo_batch;

int writes_starved;

int front_merges;

};

從面向對象的角度來理解deadline調度器的話，可以將deadline看作一個封裝好的類，上面介紹的接口就是這個類的方法，上面介紹的數據結構就是這個類的數據成員。deadline_init_queue是這個類的構造函數，在給塊設備隊列分配調度器的時候被調用，用戶初始化類的數據成員。deadline_exit_queue相當于析構函數，用于釋放調度器實例化時申請的資源。其他的接口包括將IO請求加入到調度器內部數據結構中，將IO請求從調度器內部派發出去，將一個bio合并到調度器內部的一個request中等。deadline內調度隊列中最重要的兩個成員為：

lstruct rb_root sort_list[2];

lstruct list_head fifo_list[2];

sort_list是兩顆紅黑樹，用于對io請求按起始扇區編號進行排序，deadline的電梯掃描就是基于這兩個紅黑樹進行的，這里有兩顆樹，一顆讀請求樹，一顆寫請求樹，分別作用于讀和寫。 fifo_list是普通的先進先出鏈表，也有兩個，分別對應讀和寫。每個IO請求在進入調度器的時候都會根據當前系統時間和超時時間給它賦上一個時間厝，然后根據IO方向添加到讀或者寫fifo_list，fifo_list頭部保存即將超時的IO請求，調度器在派發IO請求的時候會檢測fifo_list中是否有已經超時的IO請求，如果有則必須進行派發處理，這就是deadline的字面意思，每個IO請求都有一個死亡線的截至時間，讀和寫的超時時間由fifo_expire成員定義，默認讀為500ms，寫為5s，因此讀的優先級比寫要高，因為讀請求大部分情況下是同步的，需要盡快得到滿足。

deadline調度器的工作過程就是： 通用塊層通過deadline注冊的操作接口將IO請求提交給deadline，deadline在收到請求之后根據請求的扇區編號將請求在sort_list中排好序，同時給每個請求添加超時時間厝，并插入到fifo_list尾部。一個IO請求同時掛接在sort_list和fifo_list中。通用塊層需要派發IO請求（瀉流或者direct IO）的時候也是調用deadline注冊的電梯派發接口，deadline在派發一個IO請求時會基于電梯算法綜合考慮IO請求是否超時、寫饑餓是否觸發、是否滿足批量條件來決定到底派發哪個IO請求，派發之后會將該IO請求同時從sort_list和fifo_list中刪除。deadline服務的整個過程都是由通用塊層驅動的，換言之deadline是被動的，在內核中不提供工作隊列或工作線程。

deadline IO請求的添加

deadline 的調度隊列(數據結構)容納的是request請求，本系列文章的《Linux通用塊層介紹（part1: bio層）》、《Linux通用塊層介紹（part2: request層）》從宏觀上介紹了bio請求如何轉化為request請求并添加到調度器的調度隊列中、如何合并進現有的request請求（包括plug 鏈表中的request和調度隊列中的request）。對于deadline來說，IO請求的合并和排序都是在請求添加到deadline 的調度隊列中的過程完成的。bio請求進入deadline 調度隊列有兩條路徑：

bio通過deadline_add_request接口添加到調度隊列

deadline_add_request接口的參數形式是request，bio在通用塊層會申請一個新的request或者合并到plug 鏈表中的現有的request中，最后調用deadline_add_request添加到調度隊列。

/*

* add rq to rbtree and fifo

*/

static void

deadline_add_request(struct request_queue *q, struct request *rq)

{

struct deadline_data *dd = q->elevator->elevator_data;

const int data_dir = rq_data_dir(rq);

deadline_add_rq_rb(dd, rq);

/*

* set expire time and add to fifo list

*/

rq->fifo_time = jiffies + dd->fifo_expire[data_dir];

list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);

}

接口很簡單，首先判斷request的IO方向，根據IO方向通過deadline_add_rq_rb將request添加到讀/寫紅黑樹中，request在紅黑樹中以請求的起始扇區作為節點的key value，可以直接認為紅黑樹中的request是按扇區增加的方向排好了序。然后給request添加一個超時時間厝，根據IO方向添加到先進先出鏈表尾部，fifo_list中同一IO方向上的request具有相同的fifo_expire，所以先添加進來的request先超時，每次都是從尾部添加，所以頭部的request先超時，這也是fifo_list名字的由來吧。

bio通過deadline_merge*接口合并到調度隊列中的request

在《Linux通用塊層介紹（part2: request層）》中我們介紹了通用塊層的blk_queue_bio接口，其中有如何一段代碼：

static blk_qc_t blk_queue_bio(struct request_queue *q, struct bio *bio)

{

...

switch (elv_merge(q, &req, bio)) {

case ELEVATOR_BACK_MERGE:

if (!bio_attempt_back_merge(q, req, bio))

break;

elv_bio_merged(q, req, bio);

free = attempt_back_merge(q, req);

if (free)

__blk_put_request(q, free);

else

elv_merged_request(q, req, ELEVATOR_BACK_MERGE);

goto out_unlock;

case ELEVATOR_FRONT_MERGE:

if (!bio_attempt_front_merge(q, req, bio))

break;

elv_bio_merged(q, req, bio);

free = attempt_front_merge(q, req);

if (free)

__blk_put_request(q, free);

else

elv_merged_request(q, req, ELEVATOR_FRONT_MERGE);

goto out_unlock;

default:

break;

}

...

}

這段代碼的意思就是嘗試將bio合并到電梯調度隊列中現有的request中去，首先調用elv_merge->deadline_merge判斷是哪種合并（見《Linux通用塊層介紹（part2: request層）》中介紹的合并類型），如果可以合并，則根據合并類型進行相應的合并，bio合并到request的功能由通用塊層的bio_attempt_front_merge/bio_attempt_back_merge接口完成。對于deadline IO調度器來說，request在紅黑樹中是以起始扇區作為key value的，如果是前向合并則會改變合并后的request的起始扇區號，因此bio合并之后還需調用elv_bio_merged->eadline_merged_request來重新更新request在紅黑樹中的key value和位置。不管是前向合并還是后向合并，都有可能觸發進階合并，最后都會調用一次attempt_front/back_merge->deadline_merged_requests來處理這種進階合并，過程就是調用deadline_remove_request接口將被合并的request從sort_list和fifo_list中刪除，同時更新合并后的request的超時時間。

deadline IO請求的派發

deadline 調度算法的核心思想就蘊含在請求的派發接口中，接口代碼比較簡潔，邏輯清晰，單次調用只派發一個request請求，調度數據結構記錄了派發的上下文，調度時充分權衡了請求的電梯性、饑餓性、超時性。

/*

* deadline_dispatch_requests selects the best request according to

* read/write expire, fifo_batch, etc

*/

static int deadline_dispatch_requests(struct request_queue *q, int force)

{

struct deadline_data *dd = q->elevator->elevator_data;

const int reads = !list_empty(&dd->fifo_list[READ]);

const int writes = !list_empty(&dd->fifo_list[WRITE]);

struct request *rq;

int data_dir;

/*

* batches are currently reads XOR writes

*/

if (dd->next_rq[WRITE])

rq = dd->next_rq[WRITE];

else

rq = dd->next_rq[READ];

if (rq && dd->batching < dd->fifo_batch)

/* we have a next request are still entitled to batch */

goto dispatch_request;

/*

* at this point we are not running a batch. select the appropriate

* data direction (read / write)

*/

if (reads) {

BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));

if (writes && (dd->starved++ >= dd->writes_starved))

goto dispatch_writes;

data_dir = READ;

goto dispatch_find_request;

}

/*

* there are either no reads or writes have been starved

*/

if (writes) {

dispatch_writes:

BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));

dd->starved = 0;

data_dir = WRITE;

goto dispatch_find_request;

}

return 0;

dispatch_find_request:

/*

* we are not running a batch, find best request for selected data_dir

*/

if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {

/*

* A deadline has expired, the last request was in the other

* direction, or we have run out of higher-sectored requests.

* Start again from the request with the earliest expiry time.

*/

rq = rq_entry_fifo(dd->fifo_list[data_dir].next);

} else {

/*

* The last req was the same dir and we have a next request in

* sort order. No expired requests so continue on from here.

*/

rq = dd->next_rq[data_dir];

}

dd->batching = 0;

dispatch_request:

/*

* rq is the selected appropriate request.

*/

dd->batching++;

deadline_move_request(dd, rq);

return 1;

}

deadline的電梯性

電梯調度器最重要的屬性就是保持IO請求按適應磁頭臂移動的方向去派發請求，從而盡可能的減少IO請求的在磁盤上的尋道時間，提升IO處理能力，類似于電梯移動算法，盡可能減少移動距離來提升運行效率，這就是IO調度器稱之為電梯調度器的原因。硬盤的讀寫原理這篇博文詳細介紹了磁盤構造原理以及為什么需要IO調度的原因。deadline的電梯性是通過批量(batching)機制來實現的，前面介紹了IO請求在紅黑樹中已排好序，deadline每次派發完一個request請求都會將紅黑樹中排好序的下一個request(如果有)暫存到next_rq成員中，下一次再次調用deadline_dispatch_requests時直接派發next_rq成員中的request，同時按紅黑樹的順序更新next_rq。如果一直按照這種思路派發，那么相反IO方向的請求有可能很長時間得不到響應，同一IO方向的請求也有可能出現超時。因此這種完全按紅黑樹的順序派發請求的機制必須有個限制，deadline 中的batching和fifo_batch就是起這個作用的，每順序派發一次，batching加一，如果batching超過了fifo_batch(默認16)就需要考量其他派發因子，如請求超時，fifo_batch設置過大會提升IO請求的吞吐率，增大IO請求的延遲，反之相反。這種同IO方向上的按順序批次派發我們稱只為批量機制，這種批量機制可能提前結束，如IO方向上沒有可繼續派發的IO請求了。

deadline的饑餓性

deadline的饑餓性說的是寫饑餓，寫饑餓產生的原因是deadline給予讀方向的IO請求更高的優先級，即優先處理讀請求，這是因為從實際應用角度來說讀請求一般都是同步的，給予讀更高的優先級有助于提升用戶體驗。總是一直優先處理讀請求勢必會造成寫請求的饑餓，為此deadline引入starved和writes_starved成員變量來防止寫饑餓，每優先處理一次讀請求則計數器starved加一，一旦starved達到閥值writes_starved（默認2）且還有寫請求，則下次派發時轉向派發寫請求。考慮到deadline的批量機制，默認情況下寫請求最多讓步于16 * 2 = 32個讀請求。

deadline的超時性

deadline的饑餓性只會影響IO請求派發的方向，deadline的電梯性和超時性決定派發哪個IO請求。前面已經介紹了每個進入調度器的request都會按照超時先后掛接到fifo_list中，頭部的request先超時，尾部的request后超時。在處理完一個批次的request之后，deadline會根據饑餓性確定的IO方向上有沒有request超時，如果有超時的request則轉向處理該request(fifo_list頭部request)。如果還沒有request超時,且同方向的next_rq有暫存的request，則繼續批量化處理next_rq中的request。如此以來，fifo_batch并不是批量機制的上限，只是給超時和饑餓的request提供處理的機會，如果即沒有超時又沒有饑餓則當然繼續按順序批量化處理request會提升效率。