本文以rhel5.6所使用的2.6.18内核进行分析。
1 cfq用到的几个数据结构
~~~~~~~~~~~~~~~~~~~~~~~~
在cfq中，进程被按照优先级分组。cfq尽量优先处理高优先级组中的请求，同
时也避免低优先级组中的请求被饿死。一个进程可能同时向多个不同的块设备
提交io请求，而一个使用cfq调度算法的块设备又要处理多个进程中传下来的
请求，并将它们分组。所以，cfq使用下面这些数据结构分别描述进程，优先
级组，以及一个cfq块设备。
1.1 struct io_context
======================
每个进程都有一个io_context结构体，从其定义中包含
struct as_io_context *aic;
和
struct rb_root cic_root;
这两位来看，它是专为as和cfq两个io调度算法准备的，在cfq中，它是
struct cfq_io_context的基类。
1.2 struct cfq_io_context
==========================
cfq_io_context是cfq中为每个进程分配的结构体，继承自io_context。每个
进程都只有一个io_context，但它同时向多少个使用cfq调度算法的块设备提
交io请求，就会有多少个cfq_io_context，这些个cfq_io_context被组织在
一个红黑树中，树根是io_context中的cic_root，cfq_io_context中的"void
*key"位用作红黑树的键值。由于每个cfq_io_context对应一个使用cfq调度
算法的块设备，所以实际上cfq使用struct cfq_data结构体的地址作为键值，
每个使用cfq算法的块设备都有唯一的一个struct cfq_data结构体。
1.3 struct cfq_queue
=====================
当多个进程向同一个块设备提交io请求的时候，cfq会对进程按照优先级进行
分组，进程的优先级信息存储在进程结构体的"unsigned short ioprio"位中，
如果该位没有进行设置，cfq按照进程的nice值计算出一个优先级。默认共有
8个优先级，对于每个优先级组，使用一个cfq_queue结构体进行表示。
1.4 struct cfq_data
====================
每个使用cfq调度算法的块设备都有一个cfq_data结构，保存在struct
elevator_queue的void *elevator_data位中。
1.5 struct cfq_rq
==================
每个request都有一个cfq_rq，保存在request的void *elevator_private位
中。
2 cfq_set_request函数
~~~~~~~~~~~~~~~~~~~~~~
每当有一个新的io请求提交之后，电梯算法都会调用cfq_set_request函数让
cfq为该请求分配必要的资源。
首先调用cfq_get_io_context函数获取一个struct cfq_io_context结构，如
果没有的话cfq_get_io_context函数会分配一个新的。
接下来看cfq_io_context的"struct cfq_queue *cfqq"位有没有包含一个
struct cfq_queue，如果没有的话就调用cfq_get_queue函数。
cfq_get_queue函数计算当前进程的io优先级，并检察当前块设备的struct
cfq_data结构中有没有对应该优先级的cfq_queue，有的话就返回，没有的话
就分配一个新的。然后调用cic_set_cfqq函数让当前进程的cfq_io_context指
向该cfq_queue。
接下来分配一个新的对应于当前请求的struct cfq_rq结构。
3 cfq_insert_request函数
~~~~~~~~~~~~~~~~~~~~~~~~~
调用完cfq_set_request函数后，电梯算法会调用cfq_insert_request将新提
交的请求插入到cfq的数据结构中。
首先检查cfq_queue的优先级是否改变，如果改变将相应的信息更新。然后将
该请求对应的cfq_rq插入到以cfq_queue的"struct rb_root sort_list"为根
的红黑树中。将请求按照提交时间的先后顺序放到cfq_queue的fifo链表上，
如果该请求是可合并的，则将请求放到cfq_data的哈希表中，在合并请求时，
会用到该哈希表。最后，调用cfq_crq_enqueued函数更新一些时间戳以及统计
信息。
4 cfq_dispatch_requests函数
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
每当电梯算法要补充一些请求到请求队列上的时候，会调用
cfq_dispatch_request函数。
首先调用cfq_select_queue选择一个优先级队列，然后调
用__cfq_dispatch_requests函数将该优先级队列上的一部分请求放到请求队
列上。
选择优先级队列时，总是从最高等级的优先级队列开始选择，但每个等级都有
一个时间片，如果该等级的时间片到期，则选择下一个等级的队列。
5 merge
~~~~~~~~
5.1 cfq_merge函数
==================
电梯算法调用cfq_merge函数判断一个新的请求是否能和以前的请求合并。
首先判断是否能进行后向合并。cfq_data中有一个哈希表，储存了所有可以
合并的请求，并且以请求的结束扇区号作为键值。所以，以当前请求的起始
扇区号作为键值进行搜索，如果能够搜到一个请求，则说明搜到的请求的结
束扇区号和当前请求的起始扇区号相等，可以进行后向合并。
如果没有找到能够进行后向合并的请求，则尝试寻找是否有能进行前向合并
的请求。以当前请求的结束扇区号为键值，在与当前请求的io优先级相等的
cfq_queue的红黑树中寻找。由于该红黑树中的成员是以请求的起始扇区号为
键值的，如果找到，说明可以进行前向合并。
cfq_merge的返回值会告诉调用它的函数是可以进行前向合并，还是后向合并，
还算不可以合并。如果可以合并，会将可用来合并的请求放到struct
request **req中返回。
5.2 cfq_merged_request函数
===========================
所谓合并，就是将一个新传递进来的bio放到一个以前的request中。实际的
合并操作是在ll_rw_blc.c和elevator.c中完成的。在合并完成之后，电梯算
法会调用cfq_merged_request函数让cfq进行一些必要的更新。由于进行了合
并，request的起始扇区号和结束扇区号可能会发生变化，而cfq内部所用的
哈希表以及红黑树是以这两个值作为键值的。所以,cfq_merged_request的作
用就是检验这两个值是否变化，若变化了则以新的键值放置相应的数据结构
成员
1 cfq用到的几个数据结构
~~~~~~~~~~~~~~~~~~~~~~~~
在cfq中，进程被按照优先级分组。cfq尽量优先处理高优先级组中的请求，同
时也避免低优先级组中的请求被饿死。一个进程可能同时向多个不同的块设备
提交io请求，而一个使用cfq调度算法的块设备又要处理多个进程中传下来的
请求，并将它们分组。所以，cfq使用下面这些数据结构分别描述进程，优先
级组，以及一个cfq块设备。
1.1 struct io_context
======================
每个进程都有一个io_context结构体，从其定义中包含
struct as_io_context *aic;
和
struct rb_root cic_root;
这两位来看，它是专为as和cfq两个io调度算法准备的，在cfq中，它是
struct cfq_io_context的基类。
1.2 struct cfq_io_context
==========================
cfq_io_context是cfq中为每个进程分配的结构体，继承自io_context。每个
进程都只有一个io_context，但它同时向多少个使用cfq调度算法的块设备提
交io请求，就会有多少个cfq_io_context，这些个cfq_io_context被组织在
一个红黑树中，树根是io_context中的cic_root，cfq_io_context中的"void
*key"位用作红黑树的键值。由于每个cfq_io_context对应一个使用cfq调度
算法的块设备，所以实际上cfq使用struct cfq_data结构体的地址作为键值，
每个使用cfq算法的块设备都有唯一的一个struct cfq_data结构体。
1.3 struct cfq_queue
=====================
当多个进程向同一个块设备提交io请求的时候，cfq会对进程按照优先级进行
分组，进程的优先级信息存储在进程结构体的"unsigned short ioprio"位中，
如果该位没有进行设置，cfq按照进程的nice值计算出一个优先级。默认共有
8个优先级，对于每个优先级组，使用一个cfq_queue结构体进行表示。
1.4 struct cfq_data
====================
每个使用cfq调度算法的块设备都有一个cfq_data结构，保存在struct
elevator_queue的void *elevator_data位中。
1.5 struct cfq_rq
==================
每个request都有一个cfq_rq，保存在request的void *elevator_private位
中。
2 cfq_set_request函数
~~~~~~~~~~~~~~~~~~~~~~
每当有一个新的io请求提交之后，电梯算法都会调用cfq_set_request函数让
cfq为该请求分配必要的资源。
首先调用cfq_get_io_context函数获取一个struct cfq_io_context结构，如
果没有的话cfq_get_io_context函数会分配一个新的。
接下来看cfq_io_context的"struct cfq_queue *cfqq"位有没有包含一个
struct cfq_queue，如果没有的话就调用cfq_get_queue函数。
cfq_get_queue函数计算当前进程的io优先级，并检察当前块设备的struct
cfq_data结构中有没有对应该优先级的cfq_queue，有的话就返回，没有的话
就分配一个新的。然后调用cic_set_cfqq函数让当前进程的cfq_io_context指
向该cfq_queue。
接下来分配一个新的对应于当前请求的struct cfq_rq结构。
3 cfq_insert_request函数
~~~~~~~~~~~~~~~~~~~~~~~~~
调用完cfq_set_request函数后，电梯算法会调用cfq_insert_request将新提
交的请求插入到cfq的数据结构中。
首先检查cfq_queue的优先级是否改变，如果改变将相应的信息更新。然后将
该请求对应的cfq_rq插入到以cfq_queue的"struct rb_root sort_list"为根
的红黑树中。将请求按照提交时间的先后顺序放到cfq_queue的fifo链表上，
如果该请求是可合并的，则将请求放到cfq_data的哈希表中，在合并请求时，
会用到该哈希表。最后，调用cfq_crq_enqueued函数更新一些时间戳以及统计
信息。
4 cfq_dispatch_requests函数
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
每当电梯算法要补充一些请求到请求队列上的时候，会调用
cfq_dispatch_request函数。
首先调用cfq_select_queue选择一个优先级队列，然后调
用__cfq_dispatch_requests函数将该优先级队列上的一部分请求放到请求队
列上。
选择优先级队列时，总是从最高等级的优先级队列开始选择，但每个等级都有
一个时间片，如果该等级的时间片到期，则选择下一个等级的队列。
5 merge
~~~~~~~~
5.1 cfq_merge函数
==================
电梯算法调用cfq_merge函数判断一个新的请求是否能和以前的请求合并。
首先判断是否能进行后向合并。cfq_data中有一个哈希表，储存了所有可以
合并的请求，并且以请求的结束扇区号作为键值。所以，以当前请求的起始
扇区号作为键值进行搜索，如果能够搜到一个请求，则说明搜到的请求的结
束扇区号和当前请求的起始扇区号相等，可以进行后向合并。
如果没有找到能够进行后向合并的请求，则尝试寻找是否有能进行前向合并
的请求。以当前请求的结束扇区号为键值，在与当前请求的io优先级相等的
cfq_queue的红黑树中寻找。由于该红黑树中的成员是以请求的起始扇区号为
键值的，如果找到，说明可以进行前向合并。
cfq_merge的返回值会告诉调用它的函数是可以进行前向合并，还是后向合并，
还算不可以合并。如果可以合并，会将可用来合并的请求放到struct
request **req中返回。
5.2 cfq_merged_request函数
===========================
所谓合并，就是将一个新传递进来的bio放到一个以前的request中。实际的
合并操作是在ll_rw_blc.c和elevator.c中完成的。在合并完成之后，电梯算
法会调用cfq_merged_request函数让cfq进行一些必要的更新。由于进行了合
并，request的起始扇区号和结束扇区号可能会发生变化，而cfq内部所用的
哈希表以及红黑树是以这两个值作为键值的。所以,cfq_merged_request的作
用就是检验这两个值是否变化，若变化了则以新的键值放置相应的数据结构
成员
