CFQ,即Completely Fair Queueing絕對公平調度器,力圖為競爭塊設備使用權的所有進程分配一個等同的時間片,在調度器分配給進程的時間片內,進程可以將其讀寫請求發送給底層塊設備,當進程的時間片消耗完,進程的請求隊列將被掛起,等待調度。相對於Noop和Deadline調度器,CFQ要復雜得多,因此可能要分幾次才能將其分析完。
相關閱讀:
Linux I/O Scheduler--CFQ(下) http://www.linuxidc.com/Linux/2012-12/76349.htm
優先級
每個進程都會有一個IO優先級,CFQ調度器將會將其作為考慮的因素之一,來確定該進程的請求隊列何時可以獲取塊設備的使用權。IO優先級從高到低可以分為三大類:RT(real time),BE(best try),IDLE(idle),其中RT和BE又可以再劃分為8個子優先級。實際上,我們已經知道CFQ調度器的公平是針對於進程而言的,而只有同步請求(read或syn write)才是針對進程而存在的,他們會放入進程自身的請求隊列,而所有同優先級的異步請求,無論來自於哪個進程,都會被放入公共的隊列,異步請求的隊列總共有8(RT)+8(BE)+1(IDLE)=17個。
調度器的結構
CFQ調度器在整個工作過程中所涉及到的結構比較多,我們可以把這些結構分為兩類,一類是用來描述調度器本身相關的結構,由於CFQ將進程作為考慮對象,因此另一類結構就是特定於進程的結構,對於這些結構,我們只選擇其內部的重要元素進行分析。和調度器相關的數據結構主要有兩個,一個是描述調度器的struct cfq_data,一個是描述隊列的struct cfq_queue。
struct cfq_data {
struct request_queue *queue;
/*
* rr list of queues with requests and the count of them
*/
struct cfq_rb_root service_tree;
/*
* Each priority tree is sorted by next_request position. These
* trees are used when determining if two or more queues are
* interleaving requests (see cfq_close_cooperator).
*/
struct rb_root prio_trees[CFQ_PRIO_LISTS];
unsigned int busy_queues;
int rq_in_driver[2];
int sync_flight;
/*
* queue-depth detection
*/
int rq_queued;
int hw_tag;
int hw_tag_samples;
int rq_in_driver_peak;
/*
* idle window management
*/
struct timer_list idle_slice_timer;
struct work_struct unplug_work;
struct cfq_queue *active_queue;
struct cfq_io_context *active_cic;
/*
* async queue for each priority case
*/
struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
struct cfq_queue *async_idle_cfqq;
sector_t last_position;
/*
* tunables, see top of file
*/
unsigned int cfq_quantum;
unsigned int cfq_fifo_expire[2];
unsigned int cfq_back_penalty;
unsigned int cfq_back_max;
unsigned int cfq_slice[2];
unsigned int cfq_slice_async_rq;
unsigned int cfq_slice_idle;
unsigned int cfq_latency;
struct list_head cic_list;
/*
* Fallback dummy cfqq for extreme OOM conditions
*/
struct cfq_queue oom_cfqq;
unsigned long last_end_sync_rq;
};