deadline算法的核心就是在傳統的電梯算法中加入了請求逾時的機制,該機制主要展現在兩點:(1)請求 逾時時,對逾時請求的選擇。(2)沒有請求逾時時,當掃描完電梯最後一個request後,準備傳回時,對第一個request的選擇。基于以上兩點,平 衡了系統i/o吞吐量和響應時間。此外,該算法開考慮到了讀操作對寫操作造成的饑餓。 算法核心資料結構: struct deadline_data { struct rb_root sort_list[2]; struct list_head fifo_list[2]; struct request *next_rq[2]; unsigned int batching; sector_t last_sector; unsigned int starved; int fifo_expire[2]; int fifo_batch; int writes_starved; int front_merges; }; sort_list:按照request中的sector号大小,把每個request組織在以sort_list為根的紅黑樹中。這樣友善快速查找。總共有讀寫兩棵樹。 fifo_list:按照逾時先後順尋,把request鍊入filo_list,同樣也是分為讀寫兩個隊列。 是以,任何一個request,在未送出給裝置的請求隊列之前,都會同時存在于以上兩個結構中。 next_rq:指向sort_list中的下一個請求。 batching:排程算法可能連續送出多個請求,batching用于記錄目前連續送出的request數目V灰猙atching < fifo_batch,都可以繼續進行連續送出。 starved:送出讀request而造成寫饑餓的次數。如果starved超過writes_starved,則需要送出寫request,進而避免寫饑餓。 deadline I/O排程器中最重要的兩個方法是:deadline_add_request和deadline_dispatch_requests。它們分别向排程器隊列(非請求隊列)添加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); rq_set_fifo_time(rq, jiffies + dd->fifo_expire[data_dir]); list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]); } deadline_add_request把請求分别加入紅黑樹和fifo。并記錄請求的逾時時間。這兒借用了request的donelist的next字段。因為在deadline排程隊列的請求,絕不可能被調入請求完成隊列: #define rq_set_fifo_time(rq,exp) ((rq)->donelist.next = (void *) (exp)) 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; if (dd->next_rq[WRITE]) rq = dd->next_rq[WRITE]; else rq = dd->next_rq[READ]; if (rq) { if (dd->last_sector != rq->sector) dd->batching += dd->fifo_batch; if (dd->batching < dd->fifo_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: if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) { rq = rq_entry_fifo(dd->fifo_list[data_dir].next); } else { rq = dd->next_rq[data_dir]; } dd->batching = 0; dispatch_request: dd->batching++; deadline_move_request(dd, rq); return 1; } deadline_dispatch_requests是deadline算法的核心。主要分為三個部分:(1)确定是要分發讀還是寫 request。影響處理分發類型因素主要包括是否處于batching階段以及是否發生寫饑餓。(2)确定方向以後,根據讀寫方向找到該方向上下一個請 求進行分發。影響定位下一個請求因素主要包括請求是否逾時。(3)找到合适的request後,調用deadline_move_request分發給塊 裝置的請求隊列。 1.确定讀寫方向. a.首先,根據是否處于batching來确定目前處理讀寫的方向。因為如果處在batching過 程中,就意味着排程程式需要連續處理同一方向的請求。這樣可以有效增加系統吞吐量。是以,根據batching的方向,可以确定目前處理請求的方向。而讀 寫batching是互斥的: if (dd->next_rq[WRITE]) rq = dd->next_rq[WRITE]; else rq = dd->next_rq[READ]; 通過這個判斷,保證了batching隻會在某一方向進行,而不會交錯。因為在deadline_move_request中有: dd->next_rq[READ] = NULL; dd->next_rq[WRITE] = NULL; dd->next_rq[data_dir] = deadline_latter_request(rq); 也就是在batching方向的next_rq才可能指向下一個request。 if (rq) { if (dd->last_sector != rq->sector) dd->batching += dd->fifo_batch; if (dd->batching < dd->fifo_batch) goto dispatch_request; } 如 果存在下一個request,也就是沒有掃描到電梯的末尾。則判斷該request是否和上一個request相連。如果相連,并且batching的 request數沒有超過fifo_batch,則目前這個request就是我們要分發的request。是以直接跳到最後,把request分發到設 備請求隊列。此時将忽略寫饑餓和逾時的處理。如果不連續,則要結束batching。 b.如果此時并不處于batching過程中,則根據是否造成寫饑餓“超标”來确定讀寫方向。 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; } 排程器先處理read,也就是read請求優先。但在處理過 程中考慮到了寫饑餓。如果此時還有寫請求,則寫饑餓計數+1,如果寫饑餓次數大于了writes_starved,則寫饑餓已經“超标”了,是以直接跳到 dispath_writes去處理寫請求。如果寫饑餓沒有“超标”,則繼續處理讀請求。 2.根據讀寫方向,找到目前要處理的請求: dispatch_find_request: if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) { rq = rq_entry_fifo(dd->fifo_list[data_dir].next); } else { rq = dd->next_rq[data_dir]; } dd->batching = 0; 在尋找指定方向上的請求時,考慮了請求的逾時時間。這就是deadline的算法核心所 在。排程器首先調用deadline_check_fifo來檢查隊列中隊首,也就是最老的一個請求是否逾時。如果逾時則指定目前處理的請求為該逾時的請 求。但如果沒有逾時,但已經掃描了電梯的末尾:!dd->next_rq[data_dir]。此時需要傳回到電梯首部。但與傳統的電梯算法不 同,deadline排程器不是傳回到sector最小的request開始繼續掃描。而是傳回到等待時間最久的那個requst,從那個request 開始,沿sector遞增方向繼續掃描。也就是說,如果逾時,或者掃描到電梯尾,都會傳回來處理等待最久的request,并從這個request開始繼 續進行電梯掃描。當然,如果既沒有發生逾時,也沒有掃描到電梯末尾,則沿sector遞增方向上的下一個request就是目前要處理的request。 3.找到要處理的request後,把它分發到塊裝置的請求隊列。 整個deadline排程器比較簡潔,總共隻有400多行。它充分考慮了batching,寫饑餓,請求逾時這三大因素。在保證吞吐量的基礎上,有考慮到了響應延時。 linux deadline I/O排程算法分析筆記 |