北京英本科技有限公司www.ingben.com 1 / 5 读者须知：此文档为英本网(http://www.ingben.com/)原创，版权归英本网所有。谨以此奉献给linux爱好者，研究者，英本学员等。技术讨论QQ群：67962133

CFQ调度是基于优先级调度的，系统中的每一个进程都有一个优先级类（这个优先级类分成了3种：real-time (RT), best-eort (BE)，idle），RT 和 BE分成了8种不同的优先级来说明服务的不同优先级别。BE作为进程默认的优先级类，通过nice命令来设置。

每一个进程都有有个cfq_queue队列来服务同步的请求req，对于异步请求req分别对应了8种不同优先级的BE队列，8种不同优先级的RT队列，和一个空闲队列。这些队列信息进程间是共享的，大家都知道。

下图是CFQ算法中结构体之间的关系图（vdisktime最小的cfq_group先服务）：

理解CFQ算法重点是要分析这个算法用到的结构体变量。 217 220 struct cfq_data { 221 struct request_queue *queue; 223 struct cfq_rb_root grp_service_tree;//此红黑树服务于cfg_group 224 struct cfq_group root_group; 229 enum wl_prio_t serving_prio; 230 enum wl_type_t serving_type; 231 unsigned long workload_expires; 232 struct cfq_group *serving_group; 233 234 //有8种不同优先级的树，每一个树中的优先级是相同的，不同的树优先级不同。 239 struct rb_root prio_trees[CFQ_PRIO_LISTS]; 240//cfq里面有多少个正在使用的队列 241 unsigned int busy_queues; 242 unsigned int busy_sync_queues;//多少个同步的队列 244 int rq_in_driver;

www.ingben.comwww.ingben.com 北京英本科技有限公司www.ingben.com

2 / 5 245 int rq_in_flight[2]; 250 int rq_queued; 251 int hw_tag; 258 int hw_tag_est_depth; 259 unsigned int hw_tag_samples; 264 struct timer_list idle_slice_timer; 265 struct work_struct unplug_work; 267 struct cfq_queue *active_queue; 268 struct cfq_io_context *active_cic; 269 270//io priority有3种类型的优先级，分别是：idle,best effort,real time。这里的横坐标2指的是best effort和real time2种类型的优先级。每一种类型里面有8个优先级。 273 struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];

//空闲队列 274 struct cfq_queue *async_idle_cfqq; 276 sector_t last_position; 281 unsigned int cfq_quantum; 282 unsigned int cfq_fifo_expire[2]; 283 unsigned int cfq_back_penalty; 284 unsigned int cfq_back_max;

//cfq_slice[0]同步时间片，cfq_slice[1]异步时间片 285 unsigned int cfq_slice[2]; 286 unsigned int cfq_slice_async_rq; 287 unsigned int cfq_slice_idle; 288 unsigned int cfq_group_idle; 289 unsigned int cfq_latency; 290 291 unsigned int cic_index; 292 struct list_head cic_list; 297 struct cfq_queue oom_cfqq; 299 unsigned long last_delayed_sync; 302 struct hlist_head cfqg_list;

305 unsigned int nr_blkcg_linked_grps; 306 };

174 struct cfq_group { 175 176 struct rb_node rb_node;//代表了grp_service_tree树中的一个节点 177

www.ingben.comwww.ingben.com 北京英本科技有限公司www.ingben.com

3 / 5 178 179 u64 vdisktime;//grp_service_tree树中一个节点的key,为节点的虚拟磁盘时间 180 unsigned int weight; 181 unsigned int new_weight; 182 bool needs_update; 183 184 组里面有多少个cfq 队列 185 int nr_cfqq; 186 187 //每一个不同优先级树中的队列（实际是上cfq_queue）正在处理中。 193 unsigned int busy_queues_avg[CFQ_PRIO_NR];

//2指的是RT和BE 2种类型，3指的是SYNC,SYNC_NOIDLE,ASYNC 202 struct cfq_rb_root service_trees[2][3];

203 struct cfq_rb_root service_tree_idle; 205 unsigned long saved_workload_slice; 206 enum wl_type_t saved_workload; 207 enum wl_prio_t saved_serving_prio; 208 struct blkio_group blkg; 209 #ifdef CONFIG_CFQ_GROUP_IOSCHED 210 struct hlist_node cfqd_node; 211 int ref; 212 #endif 213 214 int dispatched; 215 };

97 struct cfq_queue { 98 99 int ref; 101 unsigned int flags; 103 struct cfq_data *cfqd; 105 struct rb_node rb_node; 107 unsigned long rb_key; 109 struct rb_node p_node;//此变量对应了8种不同优先级树中的一个节点。 111 struct rb_root *p_root;

//sort_list是按照红黑树的结构存放待处理的请求

www.ingben.comwww.ingben.com 北京英本科技有限公司www.ingben.com

4 / 5 113 struct rb_root sort_list; 115 struct request *next_rq;//红黑树中下一个将要处理的请求 117 int queued[2]; 119 int allocated[2]; 121 struct list_head fifo;//fifo是个先进先出的队列，fifo里面的队员是sort_list红黑树的节点，即sort_list里面的节点按照先进先出的原理存放到了fifo队列中去，这种fifo是deadline算法。 124 unsigned long dispatch_start; 125 unsigned int allocated_slice; 126 unsigned int slice_dispatch; 127 128 unsigned long slice_start; 129 unsigned long slice_end; 130 long slice_resid;

133 int meta_pending; 134 135 int dispatched;//记录了多少个请求将要被驱动程序处理 136 137 /由于每个进程的io class（idile,be,rt），io proiority，io type（sync,asyc）,因此ioprio,ioprio_class都会相应发生变化，这里就行了记录。 138 unsigned short ioprio, org_ioprio; 139 unsigned short ioprio_class, org_ioprio_class; 141 pid_t pid; 143 u32 seek_history; 144 sector_t last_request_pos; 145 146 struct cfq_rb_root *service_tree; 147 struct cfq_queue *new_cfqq; 148 struct cfq_group *cfqg;//这个队列记录了进程信息 150 unsigned long nr_sectors; 151 };

8 struct cfq_io_context { 9 void *key; 10 //cfqq[0]表示进程异步IO的对应的cfq_queuq,cfqq[1]表示进程同步IO的对应的cfq_queuq 11 struct cfq_queue *cfqq[2]; 13 struct io_context *ioc; 15 unsigned long last_end_request; 17 unsigned long ttime_total; 18 unsigned long ttime_samples;