老娘舅有什么好吃的:Linux IO调度层分析

2011-08-12 11:35:48|  分类：Linux |字号 订阅
Linux IO调度程序是块设备I/O子系统的主要组件，它介于通用块层和块设备驱动程序之间，所图2-1所示。当Linux内核组件要读写一些数据时，并不是请求一发出，内核便立即执行该请求，而是将其推迟执行。延迟的设定是块设备性能的关键机制！当传输一个新数据块时，内核检查能否通过扩展前一个一直处于等待状态的请求而满足新请求。

图 IO调度层所在系统中的位置
在2.6内核中，内核中实现了四种IO调度算法，分别为预期(Anticipatory)算法、最后期限(Deadline)算法、完全公平队列(CFQ)算法以及NOOP算法(No Operation)。可以在内核引导式指定一种I/O调度算法，也可以在运行时通过sysfs文件系统/sys/block/sda/queue/scheduler来为块设备定制一个特定的I/O调度算法或查看块设备目前所使用的何种IO调度算法。
由于Linux IO调度程序是介于通用块层和块设备驱动程序之间，所以它接收来自通用块层的请求，试图合并请求，并找到最合适的请求下发到块设备驱动程序中。之后块设备驱动程序会调用一个策略函数来相应这个请求。这个策略函数是由设备类型来决定的，例如，如果设备是SCSI硬盘，那么scsi总线层便将scsi_request_fn注册到该策略函数中。
在linux2.6.21的内核源代码中，用于实现IO调度程序的文件有：
文件路径
描述
/include/linux/elevator.h
定义了调度算法一些公用的数据结构以及操作函数接口
/block/elevator.c
实现elevator.h中声明的一些函数
/block/noop-iosched.c
用于实现Noop算法
/block/as-iosched.c
用于实现预期算法
/block/deadline-iosched.c
用于实现最后期限算法
/block/cfq-iosched.c
用于实现完全公平队列算法
在elevator.h中定义了一些重要的数据结构，包括elevator_ops，elevator_type以及elevator_queue。
elevator_ops定义了一些操作函数接口，这些接口函数由不同的IO调度算法重载，下面是该数据结构中一些主要字段的意义：
字段
类型
描述
elevator_merge_fn
elevator_merge_fn *
将bio合并到合适的request中（准确地说，插入到request链表的首部）
elevator_merged_fn
elevator_merged_fn *
执行插入bio之后的一些附加操作
elevator_merge_req_fn
elevator_merge_req_fn*
合并两个request操作
elevator_allow_merge_fn
elevator_allow_merge_fn*
判断bio是否允许合并到request中
elevator_dispatch_fn
elevator_dispatch_fn*
在队列中取出最合适的request
elevator_add_req_fn
elevator_add_req_fn*
向队列中插入一个新的request
elevator_queue_empty_fn
elevator_queue_empty_fn*
判断队列是否为空
elevator_completed_req_fn
elevator_completed_req_fn*
请求完成时进行的一些操作
elevator_former_req_fn
elevator_request_list_fn*
取前一个request操作
elevator_latter_req_fn
elevator_request_list_fn*
取后一个request操作
elevator_init_fn
elevator_init_fn*
初始化操作
elevator_exit_fn
elevator_exit_fn*
退出操作
elevator_type结构用于描述调度的种类，其中主要字段描述如下：
字段
类型
描述
ops
struct elevator_ops
实现该调度算法函数操作
elevator_attrs
struct elv_fs_entry *
Sys接口
elevator_name
Char *
该调度算法的名称
elevator_queue结构描述了该块设备驱动使用何种IO调度算法。通常每个物理块设备都自己维护一个请求队列，每个请求队列上单独执行I/O调度。在请求对列中有一个字段elevator,它的类型指向sturct elevator_queue的指针。elevator_queue结构如下：
struct elevator_queue
{
struct elevator_ops *ops;
void *elevator_data;
struct kobject kobj;
struct elevator_type *elevator_type;
struct mutex sysfs_lock;
struct hlist_head *hash;
};
字段ops定义了调度算法的所有可能的操作：链接和断开elevator，增加和合并队列中的请求，从队列中删除请求，获得队列中下一个待处理的请求等等。
字段是elevator_type，它是指向struct elevator_type类型的指针，它描述了块设备所使用io调度算法。
字段hash包含了处理请求队列所需的所有信息，通过这个哈希表可以快速索引我们需要的某个request。
字段elevator_data用于描述IO调度程序用来处理请求的附加数据结构，如果使用Deadline算法，elevator_data指向struct deadline_data结构。
按照我的理解，elevator.h定义了一个框架，它类似面向对象程序中的基类，每个具体的 IO调度程序可以看作是它的派生类。父类elevator中定义了一些公用的方法，而这些方法的实现依据不同的调度算法其实现的方式也不同。子类会实现父类elevator中定义的函数集elevator_ops。下一节以deadline算法为例来描述IO调度程序是如何处理来自通用块层的请求，并最终下发到物理设备上。
Deadline算法维护5个队列，除了请求队列以外，算法还使用了四个队列。其中两个排序队列分别包含读请求和写请求，这个队列是按照起始扇区数来排序的。另外两个最后期限队列包含相同的读和写请求，只不过它们是根据其“最后期限”排序的。这两个队列的目的是为了避免请求饿死。因为电梯策略优先处理与上一个处理请求最近的请求，因而就会对摸个请求忽略很长一段时间，这时就会发生这个情况。请求的最后期限本质上就是超时定时器，当请求被传给电梯算法是开始计时。缺省情况下，Deadline算法读请求的超时时间为500ms，而写请求的超时时间为5s。也就是说，Deadline算法读请求优先于写请求，因为读请求通常阻塞发出请求的进程。而最后期限保证了调度程序照顾等待很长一段时间的那个请求，即使它位于排序队列的末尾。
Deadline算法核心数据结构如下：
struct deadline_data {
/*
* run time data
*/
/*
* requests (deadline_rq s) are present on both sort_list and fifo_list
*/
struct rb_root sort_list[2];
struct list_head fifo_list[2];
/*
* next in sort order. read, write or both are NULL
*/
struct request *next_rq[2];
unsigned int batching;           /* number of sequential requests made */
sector_t last_sector;             /* head position */
unsigned int starved;             /* times reads have starved writes */
/*
* settings that change how the i/o scheduler behaves
*/
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数目。当batching < fifo_batch，都可以继续进行连续提交。
starved:提交读request而造成写饥饿的次数。如果starved超过writes_starved，则需要提交写request，从而避免写饥饿。
我们知道，每个块设备程序都有一个请求队列与之关联。在块设备初始化时，会分配并初始化请求队列。在这个时候，我们便可以为块设备驱动程序指定特定的IO调度算法，默认情况下是强制使用系统默认的调度算法。
熟悉块设备驱动的人知道，内核是通过generic_make_request函数来不断转发bio，直到该bio被挂载到物理设备的请求队列中。generic_make_request函数会获取bio所指向bdev的请求队列，并通过请求队列的q->make_request_fn方法来下发bio。如果该bdev指向的是物理设备时，make_request_fn是由内核的__make_request函数来实现，通常IO调度也就是在该函数中发生。该函数过程分析如下(只列出与IO调度有关系的部分)：
int __make_request(request_queue_t *q, struct bio *bio)
{
……
el_ret = elv_merge(q, &req, bio);
switch (el_ret) {
//前两种可以合并
case ELEVATOR_BACK_MERGE:
if (!ll_back_merge_fn(q, req, bio))
break;
……
//插入到链表尾部
req->biotail->bi_next = bio;
req->biotail = bio;
……
if (!attempt_back_merge(q, req))
elv_merged_request(q, req, el_ret);
goto out;
case ELEVATOR_FRONT_MERGE:
……
//插入到链表头
bio->bi_next = req->bio;
req->bio = bio;
……
if (!attempt_front_merge(q, req))
elv_merged_request(q, req, el_ret);
goto out;
//不能合并，需要新创一个request。
/* ELV_NO_MERGE: elevator says don't/can't merge. */
default:
;
}
……
}
elv_merge函数相当重要，它试图在请求队列中找到一个能够合并该bio的request，函数返回三个可能值：
ELEVATOR_NO_MERGE：队列已经存在的请求中不能包含bio结构，需要创建一个新请求。
ELEVATOR_BACK_MERGE：bio结构可作为末尾的bio而插入到某个请求中；
ELEVATOR_FRONT_MERGE：bio结构可作为某个请求的第一个bio被插入；
可将bio合并到request中
在elv_merge函数中，首先试图将bio合并到上一次被合并的req中。如果可以合并的话，返回结果。q->last_merge保存上一次合并的请求的指针。
if (q->last_merge) {
ret = elv_try_merge(q->last_merge, bio);
if (ret != ELEVATOR_NO_MERGE) {
*req = q->last_merge;
return ret;
}
}
否则，通过elv_rqhash_find函数在调度算法的hash表（即elevator_queue中的hash字段）中查找可以将bio插入到某个req末尾的请求是否存在，如果存在，则返回ELEVATOR_BACK_MERGE，表明bio可作为末尾的bio而插入到某个请求中。
__rq = elv_rqhash_find(q, bio->bi_sector);
if (__rq && elv_rq_merge_ok(__rq, bio)) {
*req = __rq;
return ELEVATOR_BACK_MERGE;
}
如果hash表中不存在这样的req的话，则调用调度算法的elevator_merge_fn函数将bio合并到req表头中。
if (e->ops->elevator_merge_fn)
return e->ops->elevator_merge_fn(q, req, bio);
仍以deadline算法为例，deadline算法中的elevator_merge_fn函数是由deadline_merge函数实现。该函数试图将bio插入到请求的链表头。在deadline_merge函数中通过elv_rb_find函数在读写的排序队列sort_list中（通过红黑二叉树来实现）查找可以把bio插入到请求的链表头的req（这里只是找到可以插入的req，究竟bio是否可以插入到此req中是在执行插入的时候才做判断）如果找到，则返回ELEVATOR_FRONT_MERGE，否则返回ELEVATOR_NO_MERGE。
static int deadline_merge(request_queue_t *q, struct request **req, struct bio *bio)
{
struct deadline_data *dd = q->elevator->elevator_data;
struct request *__rq;
int ret;
/*
* check for front merge
*/
if (dd->front_merges) {
sector_t sector = bio->bi_sector + bio_sectors(bio);
__rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
if (__rq) {
BUG_ON(sector != __rq->sector);
if (elv_rq_merge_ok(__rq, bio)) {
ret = ELEVATOR_FRONT_MERGE;
goto out;
}
}
}
return ELEVATOR_NO_MERGE;
out:
*req = __rq;
return ret;
}
之后会__make_request函数会根据elv_merge函数的返回值进行相应的处理。这里以插入到req链表末尾为例，插入到req链表头的与此相似。首先ll_back_merge_fn函数判断bio是否可以插入到req请求链表的末尾。
req->biotail->bi_next = bio;
req->biotail = bio;
req->nr_sectors = req->hard_nr_sectors += nr_sectors;
然后调用attempt_back_merge试图将req和req下一个请求合并。
static inline int attempt_back_merge(request_queue_t *q, struct request *rq)
{
struct request *next = elv_latter_request(q, rq);
if (next)
return attempt_merge(q, rq, next);
return 0;
}
该函数首先通过elv_latter_request函数从队列中取出当前rq的后一个请求next。elv_latter_request函数会调用调度算法的elevator_latter_req_fn方法。在Deadline算法中，该函数由elv_rb_latter_request实现。由于Deadline算法的排序队列使用红黑树来实现，所以这个函数很简单，就是调用rb_next在红黑树中查找当前rq的下个请求，并返回之。
如果当前请求rq的后一个请求next存在的话，则通过attempt_merge将next合并到当前请求req中。attempt_merge函数首先判断这两个请求是否可以合并。如果可以合并的话，首先将后一个请求的bio链接到前一个请求的bio尾部，更新前一个请求的biolist指针，之后调用elv_merge_requests函数将两个请求合并。elv_merge_requests函数会调用IO调度算法的elevator_merge_req_fn方法，在Deadline算法中该方法由deadline_merged_requests函数来实现。
在deadline_merged_requests中，首先在rq和next中选择最小的“Deadline值”作为rq的“Deadline”值。然后从排序队列rbtree和fifo中移除next请求。
之后回到attempt_merge中，合并请求之后还需更新该请求在hash表中的索引（elv_rqhash_reposition(q, rq)），从hash表中删除被合并的请求（elv_rqhash_del(q, next)），保存最后一个被合并请求的指针q->last_merge。
如果无法将当前req与其后面一个next合并的话，但是确实有bio加入当前req链表尾，那么会调用elv_merged_request函数。elv_merged_request会调用具体的IO调度算法中的elevator_merged_fn函数，执行插入bio之后的一些附加操作。
创建一个新request
如果bio无法插入到当前请求队列中任何一个request，那么内核会创建一个新的request：
req = get_request_wait(q, rw_flags, bio);
然后使用bio初始化该req：
init_request_from_bio(req, bio);
之后将该req加入到请求队列中：
add_request(q, req);
在add_request函数中，会调用__elv_add_request将req以一种特定的方式加入到请求队列中。一共有4种插入方式：
#define ELEVATOR_INSERT_FRONT 1
#define ELEVATOR_INSERT_BACK    2
#define ELEVATOR_INSERT_SORT    3
#define ELEVATOR_INSERT_REQUEUE     4
在add_request中使用的是ELEVATOR_INSERT_SORT，表示使用elevator方式加入到队列中，而不是fifo。
static inline void add_request(request_queue_t * q, struct request * req)
{
drive_stat_acct(req, req->nr_sectors, 1);
/*
* elevator indicated where it wants this request to be
* inserted at elevator_merge time
*/
__elv_add_request(q, req, ELEVATOR_INSERT_SORT, 0);
}
__elv_add_request函数会根据req中cmd_flag字段修改插入到队列的方式。之后会调用elv_insert将请求插入到队列中。按照我们现在的流程， req会以ELEVATOR_INSERT_SORT的方式加入到队列中，在elv_insert中，即会执行下面分支：
case ELEVATOR_INSERT_SORT:
BUG_ON(!blk_fs_request(rq));
rq->cmd_flags |= REQ_SORTED;
q->nr_sorted++;
if (rq_mergeable(rq)) {
elv_rqhash_add(q, rq);
if (!q->last_merge)
q->last_merge = rq;
}
/*
* Some ioscheds (cfq) run q->request_fn directly, so
* rq cannot be accessed after calling
* elevator_add_req_fn.
*/
q->elevator->ops->elevator_add_req_fn(q, rq);
可以看到，如果req可以合并的话，它会被加入到hash表中，其中hash键值为req的起始扇区号加上req的请求扇区数。之后会调用IO调度算法的elevator_add_req_fn方法。在Deadline算法中，该函数由deadline_add_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);
/*
* set expire time (only used for reads) and add to fifo list
*/
rq_set_fifo_time(rq, jiffies + dd->fifo_expire[data_dir]);
list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
}
可以看到，Deadline算法将req加入到相应读写的排序队列中，然后设置req的最后期限值，并加入到相应读写的fifo中。
获取合适的req进行处理
在任何情况下，请求队列中的请求都由块设备驱动程序的策略例程来完成。策略例程是块设备驱动程序中的一个函数或一组函数，他与硬件块设备之间相互作用以满足请求队列中所汇集的请求。通过请求队列描述符中的request_fn方法就可以调用策略例程。
现在很多块设备驱动都采用如下策略：
策略例程处理队列中第一个请求并设置块设备控制器，以便在数据传送完成时可以产生一个中断。然后策略例程就中止。
当磁盘控制器产生中断时，中断控制器重新调用策略例程。策略例程要么为当前请求在启动一次数据传送，要么当请求的所有数据块已经传送完成时，把该请求从调度对立中删除然后开始处理下一个请求。
对于SCSI块设备，队列的策略函数request_fn方法是由scsi_request_fn来实现。scsi_request_fn方法通过调用elv_next_request()函数从请求队列中获取一个合适的请求。elv_next_request函数是一个循环，它实质上通过__elv_next_request函数从请求队列中找到下一个要处理的req。
static inline struct request *__elv_next_request(request_queue_t *q)
{
struct request *rq;
while (1) {
while (!list_empty(&q->queue_head)) {
rq = list_entry_rq(q->queue_head.next);
if (blk_do_ordered(q, &rq))
return rq;
}
if (!q->elevator->ops->elevator_dispatch_fn(q, 0))
return NULL;
}
}
在__elv_next_request函数中，首先如果请求队列不为空，则从请求队列中取出req并返回。如果请求队列中不存在请求了，这时会调用IO调度算法的elevator_dispatch_fn方法获取要处理的req并将其加入到请求队列中。在Deadline算法中，该函数由deadline_dispatch_requests方法来实现。
l         函数首先确定读写的方向。如果处于batching中，就意味着调度程序需要连续处理同一方向的请求。因此，根据batching的方向，可以确定当前处理请求的方向
if (dd->next_rq[WRITE])
rq = dd->next_rq[WRITE];
else
rq = dd->next_rq[READ];
if (rq) {
/* we have a "next request" */
if (dd->last_sector != rq->sector)
/* end the batch on a non sequential request */
dd->batching += dd->fifo_batch;
if (dd->batching < dd->fifo_batch)
/* we are still entitled to batch */
goto dispatch_request;
}
如果next req存在的话，则判断该req是否和上一个req相连。如果相连，并且batching的request数没有超过fifo_batch，则当前这个req就是我们要分发的req，所以直接将request分发到设备请求队列中。此时将忽略写饥饿和超时的处理。如果不连续，则要结束batching。
如果没有处于batching中，优先处理读请求。但在处理过程中考虑到了写饥饿。如果此时还有写请求，则写饥饿计数+1。如果此时写饥饿次数大于了writes_starved，则该写请求已经不能再被放弃了，因此直接跳到dispath_writes去处理写请求。否则，则继续处理读请求。
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;
}
/*
* there are either no reads or writes have been starved
*/
if (writes) {
dispatch_writes:
BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
dd->starved = 0;
data_dir = WRITE;
goto dispatch_find_request;
}
l         根据读写的方向，选择最合适的请求。
if (deadline_check_fifo(dd, data_dir)) {
/* An expired request exists - satisfy it */
dd->batching = 0;
rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
} else if (dd->next_rq[data_dir]) {
/*
* The last req was the same dir and we have a next request in
* sort order. No expired requests so continue on from here.
*/
rq = dd->next_rq[data_dir];
} else {
struct rb_node *node;
/*
* The last req was the other direction or we have run out of
* higher-sectored requests. Go back to the lowest sectored
* request (1 way elevator) and start a new batch.
*/
dd->batching = 0;
node = rb_first(&dd->sort_list[data_dir]);
if (node)
rq = rb_entry_rq(node);
}
首先调用deadline_check_fifo在最后期限队列中检查第一个请求是否超时，如果超时，则处理这个请求。如果没有超时，则判断相同请求方向的下一个请求是否存在（根据secotr号来排序的）。如果存在，则处理该请求。否则说明了扫描到了电梯的末尾，则返回排序队列的第一个req（即sector最小的req）进行处理。
l         将找到的请求分发到请求队列中。
static void deadline_move_request(struct deadline_data *dd, struct request *rq)
{
const int data_dir = rq_data_dir(rq);
struct rb_node *rbnext = rb_next(&rq->rb_node);
dd->next_rq[READ] = NULL;
dd->next_rq[WRITE] = NULL;
if (rbnext)
dd->next_rq[data_dir] = rb_entry_rq(rbnext);
dd->last_sector = rq->sector + rq->nr_sectors;
/*
* take it off the sort and fifo list, move
* to dispatch queue
*/
deadline_move_to_dispatch(dd, rq);
}
首先保存当前req的下一个req指针，然后更新last_sector值，调用deadline_move_to_dispatch（）将req从红黑树和FIFO队列中删除，然后将req加入到请求队列中。