O Scheduler--CFQ（上）

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