deadline 簡介

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

ü電梯性

ü饑餓性

ü超時(shí)性

各個(gè)性質(zhì)的解析后面會(huì)具體介紹。測試數(shù)據(jù)表明，deadline在大多數(shù)多線程應(yīng)用場景和數(shù)據(jù)庫應(yīng)用場景下表現(xiàn)的性能要優(yōu)于cfq和as。

通用塊層調(diào)度器框架

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

lelevator_init_fn：調(diào)度器初始化接口，注冊時(shí)被調(diào)用，用于初始化調(diào)度器的私有數(shù)據(jù)結(jié)構(gòu);

lelevator_exit_fn：調(diào)度器退出接口，解注冊時(shí)被調(diào)用，用于釋放申請的數(shù)據(jù)結(jié)構(gòu);

lelevator_add_req_fn：調(diào)度器入口函數(shù)，用于向調(diào)度器中添加IO請求;

lelevator_dispatch_fn：調(diào)度器出口函數(shù)，用于將調(diào)度器內(nèi)的IO請求派發(fā)給設(shè)備驅(qū)動(dòng);

deadline 實(shí)現(xiàn)原理

deadline調(diào)度器實(shí)現(xiàn)的接口有：

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,

};

這些接口在調(diào)度器注冊的時(shí)候告訴調(diào)度器框架本調(diào)度器對外暴露的方法，除了對外暴露的接口以外，deadline內(nèi)部還有一些數(shù)據(jù)結(jié)構(gòu)，用于快速的保存和操作IO請求，如紅黑樹，鏈表等。這些數(shù)據(jù)結(jié)構(gòu)是deadline內(nèi)部使用的，可以統(tǒng)稱為調(diào)度器的調(diào)度隊(duì)列，對外不可見，需要調(diào)度器的接口才能操作。

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;

};

從面向?qū)ο蟮慕嵌葋砝斫鈊eadline調(diào)度器的話，可以將deadline看作一個(gè)封裝好的類，上面介紹的接口就是這個(gè)類的方法，上面介紹的數(shù)據(jù)結(jié)構(gòu)就是這個(gè)類的數(shù)據(jù)成員。deadline_init_queue是這個(gè)類的構(gòu)造函數(shù)，在給塊設(shè)備隊(duì)列分配調(diào)度器的時(shí)候被調(diào)用，用戶初始化類的數(shù)據(jù)成員。deadline_exit_queue相當(dāng)于析構(gòu)函數(shù)，用于釋放調(diào)度器實(shí)例化時(shí)申請的資源。其他的接口包括將IO請求加入到調(diào)度器內(nèi)部數(shù)據(jù)結(jié)構(gòu)中，將IO請求從調(diào)度器內(nèi)部派發(fā)出去，將一個(gè)bio合并到調(diào)度器內(nèi)部的一個(gè)request中等。deadline內(nèi)調(diào)度隊(duì)列中最重要的兩個(gè)成員為：

lstruct rb_root sort_list[2];

lstruct list_head fifo_list[2];

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

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

deadline IO請求的添加

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

bio通過deadline_add_request接口添加到調(diào)度隊(duì)列

deadline_add_request接口的參數(shù)形式是request，bio在通用塊層會(huì)申請一個(gè)新的request或者合并到plug 鏈表中的現(xiàn)有的request中，最后調(diào)用deadline_add_request添加到調(diào)度隊(duì)列。

/*

* 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方向，根據(jù)IO方向通過deadline_add_rq_rb將request添加到讀/寫紅黑樹中，request在紅黑樹中以請求的起始扇區(qū)作為節(jié)點(diǎn)的key value，可以直接認(rèn)為紅黑樹中的request是按扇區(qū)增加的方向排好了序。然后給request添加一個(gè)超時(shí)時(shí)間厝，根據(jù)IO方向添加到先進(jìn)先出鏈表尾部，fifo_list中同一IO方向上的request具有相同的fifo_expire，所以先添加進(jìn)來的request先超時(shí)，每次都是從尾部添加，所以頭部的request先超時(shí)，這也是fifo_list名字的由來吧。

bio通過deadline_merge*接口合并到調(diào)度隊(duì)列中的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合并到電梯調(diào)度隊(duì)列中現(xiàn)有的request中去，首先調(diào)用elv_merge->deadline_merge判斷是哪種合并（見《Linux通用塊層介紹（part2: request層）》中介紹的合并類型），如果可以合并，則根據(jù)合并類型進(jìn)行相應(yīng)的合并，bio合并到request的功能由通用塊層的bio_attempt_front_merge/bio_attempt_back_merge接口完成。對于deadline IO調(diào)度器來說，request在紅黑樹中是以起始扇區(qū)作為key value的，如果是前向合并則會(huì)改變合并后的request的起始扇區(qū)號，因此bio合并之后還需調(diào)用elv_bio_merged->eadline_merged_request來重新更新request在紅黑樹中的key value和位置。不管是前向合并還是后向合并，都有可能觸發(fā)進(jìn)階合并，最后都會(huì)調(diào)用一次attempt_front/back_merge->deadline_merged_requests來處理這種進(jìn)階合并，過程就是調(diào)用deadline_remove_request接口將被合并的request從sort_list和fifo_list中刪除，同時(shí)更新合并后的request的超時(shí)時(shí)間。

deadline IO請求的派發(fā)

deadline 調(diào)度算法的核心思想就蘊(yùn)含在請求的派發(fā)接口中，接口代碼比較簡潔，邏輯清晰，單次調(diào)用只派發(fā)一個(gè)request請求，調(diào)度數(shù)據(jù)結(jié)構(gòu)記錄了派發(fā)的上下文，調(diào)度時(shí)充分權(quán)衡了請求的電梯性、饑餓性、超時(shí)性。

/*

* 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的電梯性

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

deadline的饑餓性

deadline的饑餓性說的是寫?zhàn)囸I，寫?zhàn)囸I產(chǎn)生的原因是deadline給予讀方向的IO請求更高的優(yōu)先級，即優(yōu)先處理讀請求，這是因?yàn)閺膶?shí)際應(yīng)用角度來說讀請求一般都是同步的，給予讀更高的優(yōu)先級有助于提升用戶體驗(yàn)?？偸且恢眱?yōu)先處理讀請求勢必會(huì)造成寫請求的饑餓，為此deadline引入starved和writes_starved成員變量來防止寫?zhàn)囸I，每優(yōu)先處理一次讀請求則計(jì)數(shù)器starved加一，一旦starved達(dá)到閥值writes_starved（默認(rèn)2）且還有寫請求，則下次派發(fā)時(shí)轉(zhuǎn)向派發(fā)寫請求。考慮到deadline的批量機(jī)制，默認(rèn)情況下寫請求最多讓步于16 * 2 = 32個(gè)讀請求。

deadline的超時(shí)性

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