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 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);

	/*
	 * 設定超時時間，這個請求在超時時間 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 void
deadline_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 int
deadline_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 中先刪除再重新加回

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);
	}
}

3.4 合併後處理

合併後，呼叫 deadline_merged_requests() 做合併後的處理

static void
deadline_merged_requests(struct request_queue *q, struct request *req,
			 struct request *next)
{
	if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
		/* 如果next的期限小於req */
		if (time_before(next->fifo_time, req->fifo_time)) {
			/* 這個queuelist實際上就是真正發給裝置驅動程式的佇列，處理完了的佇列 */
			list_move(&req->queuelist, &next->queuelist);
			/* 因為是next比req要先響應，合併完了肯定要以先響應的為準 */
			req->fifo_time = next->fifo_time;
		}
	}

	/* 從fifo_list和sort_list刪除next */
	deadline_remove_request(q, next);
}

3.5 派發

最後，呼叫 deadline_dispatch_requests() 將請求派發到系統的 request_queue 佇列中

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;

	/* 兩個方向上的next_rq同時只能有一個為真 */
	if (dd->next_rq[WRITE])
		rq = dd->next_rq[WRITE];
	else
		rq = dd->next_rq[READ];

	/* 如果有rq並且批次disaptch未到上限，則直接進行dispatch */
	if (rq && dd->batching < dd->fifo_batch)
		/* we have a next request are still entitled to batch */
		goto dispatch_request;

	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;
	}

	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:
	/*
	 * 我們不是處理批次請求，而是選擇資料方向上最優的請求
	 */

	/*
	 * 如果fifo_list有超時或者下一個請求的方向變了，就去
	 * fifo_list去request，然後還得執行下面的dispatch_request
	 */

	/*
	 * 該請求方向存在即將餓死的請求，或不存在批次處理的請求，
	 * 則先從FIFO佇列頭取一個請求
	 */
	if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
		rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
	} else {
		/*
		 * 為什麼這裡可以直接從fifo_list取而不是sort_list，因為
		 * 最終都需要通過rq的rb_node到sort_list找
		 */
		/* 按照磁區順序處理請求 */
		rq = dd->next_rq[data_dir];
	}

	/* 啟動新一批請求dispatch */
	dd->batching = 0;

dispatch_request:
	/*
	 * rq is the selected appropriate request.
	 */
	dd->batching++;
	/*
	 * 從fifo_list和sort_list中刪除，再加入req->queuelist中，這裡就從
	 * IO排程層離開了，移動一個請求到請求佇列的派發佇列
	 */
	deadline_move_request(dd, rq);

	return 1;
}