1. 首頁 > 生活百科 > >

Linux Block模塊之deadline調度算法代碼解析

生活百科

1 總體說明Deadline調度器對一個請求的多方面特性進行權衡來進行調度，以期望既能滿足塊設備扇區的順序訪問又能兼顧到一個請求不會在隊列中等待太久導致餓死 。Deadline調度器為了兼顧這兩個方面，通過紅黑樹來對請求按起始扇區序號進行排序，稱為 sort_list，通過 fifo 對請求按它們的生成時間進行排序，稱為 fifo_list。
batching - 每當確定了一個傳輸方向（讀/寫），那么將會從相應的 sort_list 中將一批連續請求 dispatch 到 request_queue 的請求隊列里，具體的數目由 fifo_batch（default-16） 來確定 。
總體來講，deadline算法對request進行了優先權控制調度，主要表現在如下幾個方面：

  1. 讀寫請求分離，讀請求具有高優先調度權，除非寫請求即將被餓死的時候才會去調度寫請求 ， 這種處理可以保證讀請求的延遲時間最小化；
  2. 對請求的順序批量處理，對那些地址臨近的順序化請求，deadline給予了高優先級處理權 。例如一個寫請求得到調度后，其臨近的request會在緊接著的調度過程中被處理，這種順序批量處理的方法可以最大程度減少磁盤抖動；
  3. 保證每個請求的延遲時間 。每個請求都賦予了一個最大延遲時間，如果達到延遲時間的上限，那么這個請求就會被提前處理，此時會破壞磁盤訪問的順序化而影響性能，但是保證了每個請求的最大延遲時間；
2 數據結構struct deadline_data { /** sort_list紅黑樹的根，用于對IO請求根據起始扇區進行排序* 這里有兩棵樹，一棵讀請求樹，一棵寫請求樹*/ struct rb_root sort_list[2]; /* 按照到期時間排列的先入先出隊列FIFO */ struct list_head fifo_list[2]; /** 記錄批量處理請求的下一個讀/寫請求*/ struct request *next_rq[2]; /** 當前的發送數，當batching小于fifo_batch時，* 請求會連續的發送，大于或等于16時就會啟動下一輪dispatch*/ unsigned int batching; sector_t last_sector; /* 寫饑餓的次數 */ unsigned int starved; /** 這個數組分別存儲了讀/寫請求的期限* 讀請求為500ms，寫請求為5s* 即使寫請求超時也不一定立即得到相應，而是等到讀請求當前的批次* 大于寫請求饑餓線的時候才去處理寫請求*/ int fifo_expire[2]; /* 批量發送的最大值 */ int fifo_batch; /* 寫請求饑餓線，默認為2 */ int writes_starved; /* 表示能否進行前向合并的檢查 */ int front_merges;};3 一般流程說明3.1 請求到達調用 deadline_add_request() 添加請求，代碼執行流程如下：
static voiddeadline_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); /** 設置超時時間 ， 這個請求在超時時間 jiffies + dd->fifo_expire[data_dir]* 必須得到響應*/ rq->fifo_time = jiffies + dd->fifo_expire[data_dir]; /* 將rq加入fifo_list */ list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);}static voiddeadline_add_rq_rb(struct deadline_data *dd, struct request *rq){ /* 獲取sort_list中指向根節點的指針root */ struct rb_root *root = deadline_rb_root(dd, rq); /* 將請求插入到紅黑樹中 */ elv_rb_add(root, rq);}3.2 入隊完畢調用 deadline_merge() 對請求進行合并，elevator會自己做后向合并，并且后向合并優先于前向合并
static intdeadline_merge(struct request_queue *q, struct request **req, struct bio *bio){ struct deadline_data *dd = q->elevator->elevator_data; struct request *__rq; int ret; /* 如果可以向前合并 */ if (dd->front_merges) {sector_t sector = bio_end_sector(bio);/* 如果能找到一個請求，它的起始扇區號和bio的結束扇區號相同即連續的 */__rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);if (__rq) {BUG_ON(sector != blk_rq_pos(__rq));/* 如果找到則進行合并 */if (elv_bio_merge_ok(__rq, bio)) {ret = ELEVATOR_FRONT_MERGE;goto out;}} } return ELEVATOR_NO_MERGE;out: *req = __rq; return ret;}3.3 前向合并如果做了前向合并，調用 deadline_merged_request() 進行處理，因為前向合并使得請求的起始扇區發生變化，所以相應的處理就是從 sort_list 中先刪除再重新加回
【Linux Block模塊之deadline調度算法代碼解析】static void deadline_merged_request(struct request_queue *q,struct request *req, int type){ struct deadline_data *dd = q->elevator->elevator_data; /* 把合并了的請求從sort_list刪除再加入 */ if (type == ELEVATOR_FRONT_MERGE) {elv_rb_del(deadline_rb_root(dd, req), req);deadline_add_rq_rb(dd, req); }}

推薦閱讀