deadline 簡(jiǎn)介

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請(qǐng)求，不提供排序和合并的功能，適合ssd和nvme等快速存儲(chǔ)設(shè)備。deadline 調(diào)度器由通用塊層的maintainer Jens Axboe在2002年首次寫(xiě)出并于同期合并進(jìn)內(nèi)核，此后幾乎沒(méi)經(jīng)過(guò)大的修改，歷久彌堅(jiān)，現(xiàn)在已是通用塊層單隊(duì)列的默認(rèn)IO調(diào)度器。deadline相對(duì)與其他電梯調(diào)度器綜合考慮IO請(qǐng)求的吞吐量和時(shí)延性，最要體現(xiàn)在以下三個(gè)方面：

ü電梯性

ü饑餓性

ü超時(shí)性

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

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

內(nèi)核通用塊層自帶四種IO調(diào)度器，每個(gè)塊設(shè)備在注冊(cè)的時(shí)候都會(huì)為其指定一種調(diào)度器，塊設(shè)備在運(yùn)行的時(shí)候可以通過(guò)/sys接口動(dòng)態(tài)調(diào)整當(dāng)前塊設(shè)備使用的調(diào)度器，當(dāng)然如果你喜歡，也可以自己實(shí)現(xiàn)一種滿(mǎn)足自己需求的IO調(diào)度器，并按照接口標(biāo)準(zhǔn)注冊(cè)到通用塊層。通用塊層為了滿(mǎn)足調(diào)度器的擴(kuò)充，方便管理各式各樣的調(diào)度器，提煉出了一個(gè)統(tǒng)一的框架，稱(chēng)之為電梯框架。每個(gè)調(diào)度器只需要需按照框架的標(biāo)準(zhǔn)實(shí)現(xiàn)自己調(diào)度策略的鉤子函數(shù)，然后向電梯框架注冊(cè)自己，后續(xù)的塊設(shè)備就可以使用該注冊(cè)的調(diào)度器。內(nèi)核中大量使用了設(shè)計(jì)與實(shí)現(xiàn)分離的編程手法，熟悉內(nèi)核md(multi device)子系統(tǒng)的開(kāi)發(fā)人員應(yīng)該很了解這種手法，md子系統(tǒng)規(guī)范出一個(gè)統(tǒng)一的接口，然后各個(gè)特性化的raid實(shí)現(xiàn)這些接口，并向md層注冊(cè)自己。電梯調(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)度器初始化接口，注冊(cè)時(shí)被調(diào)用，用于初始化調(diào)度器的私有數(shù)據(jù)結(jié)構(gòu);

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

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

lelevator_dispatch_fn：調(diào)度器出口函數(shù)，用于將調(diào)度器內(nèi)的IO請(qǐng)求派發(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)度器注冊(cè)的時(shí)候告訴調(diào)度器框架本調(diào)度器對(duì)外暴露的方法，除了對(duì)外暴露的接口以外，deadline內(nèi)部還有一些數(shù)據(jù)結(jié)構(gòu)，用于快速的保存和操作IO請(qǐng)求，如紅黑樹(shù)，鏈表等。這些數(shù)據(jù)結(jié)構(gòu)是deadline內(nèi)部使用的，可以統(tǒng)稱(chēng)為調(diào)度器的調(diào)度隊(duì)列，對(duì)外不可見(jiàn)，需要調(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ū)ο蟮慕嵌葋?lái)理解deadline調(diào)度器的話(huà)，可以將deadline看作一個(gè)封裝好的類(lèi)，上面介紹的接口就是這個(gè)類(lèi)的方法，上面介紹的數(shù)據(jù)結(jié)構(gòu)就是這個(gè)類(lèi)的數(shù)據(jù)成員。deadline_init_queue是這個(gè)類(lèi)的構(gòu)造函數(shù)，在給塊設(shè)備隊(duì)列分配調(diào)度器的時(shí)候被調(diào)用，用戶(hù)初始化類(lèi)的數(shù)據(jù)成員。deadline_exit_queue相當(dāng)于析構(gòu)函數(shù)，用于釋放調(diào)度器實(shí)例化時(shí)申請(qǐng)的資源。其他的接口包括將IO請(qǐng)求加入到調(diào)度器內(nèi)部數(shù)據(jù)結(jié)構(gòu)中，將IO請(qǐng)求從調(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是兩顆紅黑樹(shù)，用于對(duì)io請(qǐng)求按起始扇區(qū)編號(hào)進(jìn)行排序，deadline的電梯掃描就是基于這兩個(gè)紅黑樹(shù)進(jìn)行的，這里有兩顆樹(shù)，一顆讀請(qǐng)求樹(shù)，一顆寫(xiě)請(qǐng)求樹(shù)，分別作用于讀和寫(xiě)。 fifo_list是普通的先進(jìn)先出鏈表，也有兩個(gè)，分別對(duì)應(yīng)讀和寫(xiě)。每個(gè)IO請(qǐng)求在進(jìn)入調(diào)度器的時(shí)候都會(huì)根據(jù)當(dāng)前系統(tǒng)時(shí)間和超時(shí)時(shí)間給它賦上一個(gè)時(shí)間厝，然后根據(jù)IO方向添加到讀或者寫(xiě)fifo_list，fifo_list頭部保存即將超時(shí)的IO請(qǐng)求，調(diào)度器在派發(fā)IO請(qǐng)求的時(shí)候會(huì)檢測(cè)fifo_list中是否有已經(jīng)超時(shí)的IO請(qǐng)求，如果有則必須進(jìn)行派發(fā)處理，這就是deadline的字面意思，每個(gè)IO請(qǐng)求都有一個(gè)死亡線(xiàn)的截至?xí)r間，讀和寫(xiě)的超時(shí)時(shí)間由fifo_expire成員定義，默認(rèn)讀為500ms，寫(xiě)為5s，因此讀的優(yōu)先級(jí)比寫(xiě)要高，因?yàn)樽x請(qǐng)求大部分情況下是同步的，需要盡快得到滿(mǎn)足。

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

deadline IO請(qǐng)求的添加

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

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

deadline_add_request接口的參數(shù)形式是request，bio在通用塊層會(huì)申請(qǐng)一個(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]);

}

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

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

deadline IO請(qǐng)求的派發(fā)

deadline 調(diào)度算法的核心思想就蘊(yùn)含在請(qǐng)求的派發(fā)接口中，接口代碼比較簡(jiǎn)潔，邏輯清晰，單次調(diào)用只派發(fā)一個(gè)request請(qǐng)求，調(diào)度數(shù)據(jù)結(jié)構(gòu)記錄了派發(fā)的上下文，調(diào)度時(shí)充分權(quán)衡了請(qǐng)求的電梯性、饑餓性、超時(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請(qǐng)求按適應(yīng)磁頭臂移動(dòng)的方向去派發(fā)請(qǐng)求，從而盡可能的減少I(mǎi)O請(qǐng)求的在磁盤(pán)上的尋道時(shí)間，提升IO處理能力，類(lèi)似于電梯移動(dòng)算法，盡可能減少移動(dòng)距離來(lái)提升運(yùn)行效率，這就是IO調(diào)度器稱(chēng)之為電梯調(diào)度器的原因。硬盤(pán)的讀寫(xiě)原理這篇博文詳細(xì)介紹了磁盤(pán)構(gòu)造原理以及為什么需要IO調(diào)度的原因。deadline的電梯性是通過(guò)批量(batching)機(jī)制來(lái)實(shí)現(xiàn)的，前面介紹了IO請(qǐng)求在紅黑樹(shù)中已排好序，deadline每次派發(fā)完一個(gè)request請(qǐng)求都會(huì)將紅黑樹(shù)中排好序的下一個(gè)request(如果有)暫存到next_rq成員中，下一次再次調(diào)用deadline_dispatch_requests時(shí)直接派發(fā)next_rq成員中的request，同時(shí)按紅黑樹(shù)的順序更新next_rq。如果一直按照這種思路派發(fā)，那么相反IO方向的請(qǐng)求有可能很長(zhǎng)時(shí)間得不到響應(yīng)，同一IO方向的請(qǐng)求也有可能出現(xiàn)超時(shí)。因此這種完全按紅黑樹(shù)的順序派發(fā)請(qǐng)求的機(jī)制必須有個(gè)限制，deadline 中的batching和fifo_batch就是起這個(gè)作用的，每順序派發(fā)一次，batching加一，如果batching超過(guò)了fifo_batch(默認(rèn)16)就需要考量其他派發(fā)因子，如請(qǐng)求超時(shí)，fifo_batch設(shè)置過(guò)大會(huì)提升IO請(qǐng)求的吞吐率，增大IO請(qǐng)求的延遲，反之相反。這種同IO方向上的按順序批次派發(fā)我們稱(chēng)只為批量機(jī)制，這種批量機(jī)制可能提前結(jié)束，如IO方向上沒(méi)有可繼續(xù)派發(fā)的IO請(qǐng)求了。

deadline的饑餓性

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

deadline的超時(shí)性

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