linux吧 关注：505,108贴子：2,568,301
2. noop
(1) noop的原理
noop很简单，如果你刚从kernel.org中下载了linux-3.12.5，你可以在 block/noop-iosched.c找到源码
只有区区124行。
而这个调度算法的数据结构：
|-----------------------------------------<
struct noop_data {
struct list_head queue;
};
|----------------------------------------->
只有一个成员queue，其实就noop中维护的一个fifo（先进先出）链表的链表头，当io请求过来了，就会被加入到这个链表的后面。
在链表前面的就会被移到系统的请求队列(request_queue)中。我们来看看关键的两个函数。
|-----------------------------------------------------------------------------<
static void noop_add_request(struct request_queue *q, struct request *rq)
{
struct noop_data *nd = q->elevator->elevator_data;
list_add_tail(&rq->queuelist, &nd->queue);
}
|----------------------------------------------------------------------------->
看到了list_add_tail了吧，这里就将请求加入到链表的后面。
再来看看请求是如何从noop的fifo链表移动到系统的请求队列(request_queue)中的
|-----------------------------------------------------------------------------<
static int noop_dispatch(struct request_queue *q, int force)
{
struct noop_data *nd = q->elevator->elevator_data;
if (!list_empty(&nd->queue)) {
struct request *rq;
rq = list_entry(nd->queue.next, struct request, queuelist);
list_del_init(&rq->queuelist);
elv_dispatch_sort(q, rq);
return 1;
}
return 0;
}
|----------------------------------------------------------------------------->
同样很简单
rq = list_entry(nd->queue.next, struct request, queuelist);
这个list_entry宏是根据当前的链表节点找到对应的对象。其实质是container_of()宏，内核中大量使用这个宏，可以说它是内核的基础。
如果你之前接触过驱动，那么对这个宏肯定不陌生。
这个对象的类型是由第二参数决定的，这个节点在对象结构体中的名字是由第三个参数决定的，那么第一个参数就是要处理的节点了。
为什么是queue.next呢？因为queue是头(head)，它的下一个(next)才是链表的第一个节点(node)。
list_del_init(&rq->queuelist);
将刚才找到的节点(node)从链表中删掉，为什么呢？因为这个即将进入request_queue，得让第二节点变成第一个，
否则后面的请求就永无翻身之日了。
elv_dispatch_sort(q, rq);
相信大家已经知道这个函数是将刚才取出的第一个rq放入到系统的请求队列(request_queue)中。
好了，noop就是这么简单。
(2) 一些个人见解
从上面的分析来看，noop很简单，因此性能很好，可以理解成noop是一个极端性能分子。
为什么说noop是个极端分子呢？原因有二：
<1> 没有对io进行排序
试想一下，如果队列中，先要求访问0扇区，后又要求访问最后一个扇区，马上又迂回到2扇区，机械硬盘的磁头只能疯跑了。
但是，没有机械结构的存储器（SSD，u盘，sd卡，内存等等）这回就牛了：随你怎么跳。所以说noop适合这些没机械结构的器件。
不过noop也不是什么都不做，还是会做一些后端合并操作的。这是因为调度器的框架会自己去做后端合并(ELEVATOR_BACK_MERGE)，
你选任何一种调度器后端合并都是逃不掉的。参考代码:
block/elevator.c
<2> 没有参与调度
试想一下，在长长的fifo队列中，最后一个是写操作，而前面全部是读操作，那写操作说"XXX"。
相信你中午去学校食堂吃饭时，看见排了长长的一队，你却只能在最后面，也会在心里面默念"XXX"。
吃饭时排这么长的队什么的最讨厌了（长时间得不到响应，饿死了），所以我是特别不喜欢noop。
如果能有一种调度能稍微打断排队顺序，而不去做io排序，那么在SSD上用这种调度就比较理想了。
不会陷入极端，并且也不会损失多少性能，还能带来一定额实时性。事实上还真有这种io调度算法，它就是sio，但这份内核中却没有。
<3> 结论
noop是个极端性能分子，适合那些没有机械结构的存储器使用，例如：ssd sd卡 u盘。当读写操作频繁时，成效率就低了。
(1) noop的原理
noop很简单，如果你刚从kernel.org中下载了linux-3.12.5，你可以在 block/noop-iosched.c找到源码
只有区区124行。
而这个调度算法的数据结构：
|-----------------------------------------<
struct noop_data {
struct list_head queue;
};
|----------------------------------------->
只有一个成员queue，其实就noop中维护的一个fifo（先进先出）链表的链表头，当io请求过来了，就会被加入到这个链表的后面。
在链表前面的就会被移到系统的请求队列(request_queue)中。我们来看看关键的两个函数。
|-----------------------------------------------------------------------------<
static void noop_add_request(struct request_queue *q, struct request *rq)
{
struct noop_data *nd = q->elevator->elevator_data;
list_add_tail(&rq->queuelist, &nd->queue);
}
|----------------------------------------------------------------------------->
看到了list_add_tail了吧，这里就将请求加入到链表的后面。
再来看看请求是如何从noop的fifo链表移动到系统的请求队列(request_queue)中的
|-----------------------------------------------------------------------------<
static int noop_dispatch(struct request_queue *q, int force)
{
struct noop_data *nd = q->elevator->elevator_data;
if (!list_empty(&nd->queue)) {
struct request *rq;
rq = list_entry(nd->queue.next, struct request, queuelist);
list_del_init(&rq->queuelist);
elv_dispatch_sort(q, rq);
return 1;
}
return 0;
}
|----------------------------------------------------------------------------->
同样很简单
rq = list_entry(nd->queue.next, struct request, queuelist);
这个list_entry宏是根据当前的链表节点找到对应的对象。其实质是container_of()宏，内核中大量使用这个宏，可以说它是内核的基础。
如果你之前接触过驱动，那么对这个宏肯定不陌生。
这个对象的类型是由第二参数决定的，这个节点在对象结构体中的名字是由第三个参数决定的，那么第一个参数就是要处理的节点了。
为什么是queue.next呢？因为queue是头(head)，它的下一个(next)才是链表的第一个节点(node)。
list_del_init(&rq->queuelist);
将刚才找到的节点(node)从链表中删掉，为什么呢？因为这个即将进入request_queue，得让第二节点变成第一个，
否则后面的请求就永无翻身之日了。
elv_dispatch_sort(q, rq);
相信大家已经知道这个函数是将刚才取出的第一个rq放入到系统的请求队列(request_queue)中。
好了，noop就是这么简单。
(2) 一些个人见解
从上面的分析来看，noop很简单，因此性能很好，可以理解成noop是一个极端性能分子。
为什么说noop是个极端分子呢？原因有二：
<1> 没有对io进行排序
试想一下，如果队列中，先要求访问0扇区，后又要求访问最后一个扇区，马上又迂回到2扇区，机械硬盘的磁头只能疯跑了。
但是，没有机械结构的存储器（SSD，u盘，sd卡，内存等等）这回就牛了：随你怎么跳。所以说noop适合这些没机械结构的器件。
不过noop也不是什么都不做，还是会做一些后端合并操作的。这是因为调度器的框架会自己去做后端合并(ELEVATOR_BACK_MERGE)，
你选任何一种调度器后端合并都是逃不掉的。参考代码:
block/elevator.c
<2> 没有参与调度
试想一下，在长长的fifo队列中，最后一个是写操作，而前面全部是读操作，那写操作说"XXX"。
相信你中午去学校食堂吃饭时，看见排了长长的一队，你却只能在最后面，也会在心里面默念"XXX"。
吃饭时排这么长的队什么的最讨厌了（长时间得不到响应，饿死了），所以我是特别不喜欢noop。
如果能有一种调度能稍微打断排队顺序，而不去做io排序，那么在SSD上用这种调度就比较理想了。
不会陷入极端，并且也不会损失多少性能，还能带来一定额实时性。事实上还真有这种io调度算法，它就是sio，但这份内核中却没有。
<3> 结论
noop是个极端性能分子，适合那些没有机械结构的存储器使用，例如：ssd sd卡 u盘。当读写操作频繁时，成效率就低了。
<3> 最后需要将请求放到系统的request_queue队列中去
|-----------------------------------------------------------------------------<
static int deadline_dispatch_requests(struct request_queue *q, int force)
{
struct deadline_data *dd = q->elevator->elevator_data;
const int reads = !list_empty(&dd->fifo_list[READ]);
const int writes = !list_empty(&dd->fifo_list[WRITE]);
struct request *rq;
int data_dir;
/*
* batches are currently reads XOR writes
*/
if (dd->next_rq[WRITE])
rq = dd->next_rq[WRITE];
else
rq = dd->next_rq[READ];
if (rq && dd->batching < dd->fifo_batch)
/* we have a next request are still entitled to batch */
goto dispatch_request;
/*
* at this point we are not running a batch. select the appropriate
* data direction (read / write)
*/
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;
}
return 0;
dispatch_find_request:
/*
* we are not running a batch, find best request for selected data_dir
*/
if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
/*
* A deadline has expired, the last request was in the other
* direction, or we have run out of higher-sectored requests.
* Start again from the request with the earliest expiry time.
*/
rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
} else {
/*
* 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];
}
dd->batching = 0;
dispatch_request:
/*
* rq is the selected appropriate request.
*/
dd->batching++;
deadline_move_request(dd, rq);
return 1;
}
|----------------------------------------------------------------------------->
这个函数稍微有点复杂。
首先是next_rq，在deadline的数据结构体中是这么定义的
struct request *next_rq[2];
这两个指针一个用于指向读方向上的下一个请求，另一个指向写方向上的下一个请求。
if (dd->next_rq[WRITE])
rq = dd->next_rq[WRITE];
else
rq = dd->next_rq[READ];
if (rq && dd->batching < dd->fifo_batch)
/* we have a next request are still entitled to batch */
goto dispatch_request;
取得下一个请求，如果rq不为空指针，并且进一步的batching < fifo_batch
那么就继续将下一个请求发送到系统的request_queue上去。
rq怎样才能不为空呢，后面分析到有关next_rq[?]的赋值才能说到，所以第一次进来时，这个rq是NULL。
因此第一次进来时会走到后面的代码。
|-----------------------------------------------------------------------------<
static int deadline_dispatch_requests(struct request_queue *q, int force)
{
struct deadline_data *dd = q->elevator->elevator_data;
const int reads = !list_empty(&dd->fifo_list[READ]);
const int writes = !list_empty(&dd->fifo_list[WRITE]);
struct request *rq;
int data_dir;
/*
* batches are currently reads XOR writes
*/
if (dd->next_rq[WRITE])
rq = dd->next_rq[WRITE];
else
rq = dd->next_rq[READ];
if (rq && dd->batching < dd->fifo_batch)
/* we have a next request are still entitled to batch */
goto dispatch_request;
/*
* at this point we are not running a batch. select the appropriate
* data direction (read / write)
*/
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;
}
return 0;
dispatch_find_request:
/*
* we are not running a batch, find best request for selected data_dir
*/
if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
/*
* A deadline has expired, the last request was in the other
* direction, or we have run out of higher-sectored requests.
* Start again from the request with the earliest expiry time.
*/
rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
} else {
/*
* 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];
}
dd->batching = 0;
dispatch_request:
/*
* rq is the selected appropriate request.
*/
dd->batching++;
deadline_move_request(dd, rq);
return 1;
}
|----------------------------------------------------------------------------->
这个函数稍微有点复杂。
首先是next_rq，在deadline的数据结构体中是这么定义的
struct request *next_rq[2];
这两个指针一个用于指向读方向上的下一个请求，另一个指向写方向上的下一个请求。
if (dd->next_rq[WRITE])
rq = dd->next_rq[WRITE];
else
rq = dd->next_rq[READ];
if (rq && dd->batching < dd->fifo_batch)
/* we have a next request are still entitled to batch */
goto dispatch_request;
取得下一个请求，如果rq不为空指针，并且进一步的batching < fifo_batch
那么就继续将下一个请求发送到系统的request_queue上去。
rq怎样才能不为空呢，后面分析到有关next_rq[?]的赋值才能说到，所以第一次进来时，这个rq是NULL。
因此第一次进来时会走到后面的代码。
const int reads = !list_empty(&dd->fifo_list[READ]);
const int writes = !list_empty(&dd->fifo_list[WRITE]);
...
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;
}
先看读方向的fifo队列是不是空的，如果不是就先满足读请求，但是如果写队列不为空，并且starved++ >= writes_starved，
就把方向改为写，这里writes_starved是写的饥饿线，而starved表示写的饥饿程度，只有当starved > writeds_starved，
写才会被满足。可以看到只有这个地方会发生starved增加1的操作，所以并不是读请求每发送一次就+1，应该是一批读请求过后再+1。如何
确定一批读请求呢，这又回到了上一段与next_rq有关的代码，后面会讲到。
if (writes) {
dispatch_writes:
BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
dd->starved = 0;
data_dir = WRITE;
goto dispatch_find_request;
}
如果读方向上的fifo队列是空的，或则上一段中已经判断出写已经足够饥饿了，代码就会走到这里。
先把starved置0，不难理解，写已经被满足了，不饿了。
这一个代码和上一段代码都只会设置
data_dir = XXX;
这样一个状态，表示方向。然后跳转到dispatch_find_request
return 0;
中间还穿插着这么一小句代码，表示读写都不是，挂了。
|-------------------------------------------------------------------------------|
dispatch_find_request:
/*
* we are not running a batch, find best request for selected data_dir
*/
if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
/*
* A deadline has expired, the last request was in the other
* direction, or we have run out of higher-sectored requests.
* Start again from the request with the earliest expiry time.
*/
rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
} else {
/*
* 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];
}
dd->batching = 0;
|-------------------------------------------------------------------------------|
deadline_check_fifo(dd, data_dir)
用于检测对应方向上的fifo队列中第一个node的截止时间（还记得前面在将请求放入fifo队列之前为每个请求都
赋予了一个截至时间吗？），如果时间超了，就必须从这个fifo队列上取请求了。
对于读来说，这个时间由deadline的结构体中的fifo_expire[READ]决定，通常是500ms。那么fifo_expire[WRITE]
决定写的截止时间，通常是5s。
!dd->next_rq[data_dir]
如果下一个请求的方向不同了，那么本方向上的next_rq就是空，还是从fifo队列上取第一个节点。
为什么是fifo_list[data_dir].next
因为fifo_list[data_dir]是链表头(head)，不是一个有效的节点(node)，头的next是第一个节点。
那么为什么总是取第一个节点，前面noop已经说过了，fifo队列，取走了第一个，第二就又变成第一个了。
dd->batching = 0;
将batching置0了，表示开始新的一批io请求。
这里做一个小小的总结：
<1> 要获得写方向，必须让写的饥饿程度(starved)超过写的饥饿线(write_starved)；
<2> 如果对应方向上的fifo队列上的请求（总是第一个）截至时间到了，那么就从fifo队列上取请求，因为必须要满足这个请求了；
<3> 如果前后两次请求的方向不同（一读一写），还是从fifo上取请求（开始新的一批请求）。
<4> 如果前后两次请求方向是一致的，那么就从next_rq[方向]取得请求（此时next_rq[方向]不会为空）；
const int writes = !list_empty(&dd->fifo_list[WRITE]);
...
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;
}
先看读方向的fifo队列是不是空的，如果不是就先满足读请求，但是如果写队列不为空，并且starved++ >= writes_starved，
就把方向改为写，这里writes_starved是写的饥饿线，而starved表示写的饥饿程度，只有当starved > writeds_starved，
写才会被满足。可以看到只有这个地方会发生starved增加1的操作，所以并不是读请求每发送一次就+1，应该是一批读请求过后再+1。如何
确定一批读请求呢，这又回到了上一段与next_rq有关的代码，后面会讲到。
if (writes) {
dispatch_writes:
BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
dd->starved = 0;
data_dir = WRITE;
goto dispatch_find_request;
}
如果读方向上的fifo队列是空的，或则上一段中已经判断出写已经足够饥饿了，代码就会走到这里。
先把starved置0，不难理解，写已经被满足了，不饿了。
这一个代码和上一段代码都只会设置
data_dir = XXX;
这样一个状态，表示方向。然后跳转到dispatch_find_request
return 0;
中间还穿插着这么一小句代码，表示读写都不是，挂了。
|-------------------------------------------------------------------------------|
dispatch_find_request:
/*
* we are not running a batch, find best request for selected data_dir
*/
if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
/*
* A deadline has expired, the last request was in the other
* direction, or we have run out of higher-sectored requests.
* Start again from the request with the earliest expiry time.
*/
rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
} else {
/*
* 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];
}
dd->batching = 0;
|-------------------------------------------------------------------------------|
deadline_check_fifo(dd, data_dir)
用于检测对应方向上的fifo队列中第一个node的截止时间（还记得前面在将请求放入fifo队列之前为每个请求都
赋予了一个截至时间吗？），如果时间超了，就必须从这个fifo队列上取请求了。
对于读来说，这个时间由deadline的结构体中的fifo_expire[READ]决定，通常是500ms。那么fifo_expire[WRITE]
决定写的截止时间，通常是5s。
!dd->next_rq[data_dir]
如果下一个请求的方向不同了，那么本方向上的next_rq就是空，还是从fifo队列上取第一个节点。
为什么是fifo_list[data_dir].next
因为fifo_list[data_dir]是链表头(head)，不是一个有效的节点(node)，头的next是第一个节点。
那么为什么总是取第一个节点，前面noop已经说过了，fifo队列，取走了第一个，第二就又变成第一个了。
dd->batching = 0;
将batching置0了，表示开始新的一批io请求。
这里做一个小小的总结：
<1> 要获得写方向，必须让写的饥饿程度(starved)超过写的饥饿线(write_starved)；
<2> 如果对应方向上的fifo队列上的请求（总是第一个）截至时间到了，那么就从fifo队列上取请求，因为必须要满足这个请求了；
<3> 如果前后两次请求的方向不同（一读一写），还是从fifo上取请求（开始新的一批请求）。
<4> 如果前后两次请求方向是一致的，那么就从next_rq[方向]取得请求（此时next_rq[方向]不会为空）；
最后一步，真正将请求放到request_queue上。
dispatch_request:
/*
* rq is the selected appropriate request.
*/
dd->batching++;
deadline_move_request(dd, rq);
return 1;
首先batching++，表示这批请求已经有1个了，记个数。
然后调用deadline_move_request，这个函数会开始对next_rq赋值，所以第一次进这个函数时，next_rq[方向]是空的，从第二次开始就不一定了。
|----------------------------------------------------------------------------<
static void
deadline_move_request(struct deadline_data *dd, struct request *rq)
{
const int data_dir = rq_data_dir(rq);
dd->next_rq[READ] = NULL;
dd->next_rq[WRITE] = NULL;
dd->next_rq[data_dir] = deadline_latter_request(rq);
dd->last_sector = rq_end_sector(rq);
/*
* take it off the sort and fifo list, move
* to dispatch queue
*/
deadline_move_to_dispatch(dd, rq);
}
|---------------------------------------------------------------------------->
首先确定本次请求方向(data_dir)
然后在为本次请求同方向上的next_rq进行赋值
dd->next_rq[data_dir] = deadline_latter_request(rq);
先看看这里面的一个函数
|----------------------------------------------------------<
static inline struct request *
deadline_latter_request(struct request *rq)
{
struct rb_node *node = rb_next(&rq->rb_node);
if (node)
return rb_entry_rq(node);
return NULL;
}
|----------------------------------------------------------<
会在红黑树上去查找下一个节点，rb_next是内核中有关红黑树的操作，定义在lib/rbtree.c。rb_next做了什么，上面一段话已经表述过了，这里
再贴一下：
“树上每个节点可以有左右两个孩子。如果有左孩子，那么左孩子请求的起始扇区是小于它的父节点请求的起始扇区的；
如果有右边孩子，那么右孩子的起始扇区是大于或等于父节点的起始扇区的。
首先，应该明白扇区号是不断递增的，所以为了找到与当前请求的起始扇区最接近的节点，只需从右子树上去找最小值，也就是不断的去找左孩子，直到
找到没有左孩子的节点（想一想，左边代表小于，一直都在小于，直到无法再小于了，那自然就是最小值了）。
如果当前节点没有右孩子怎么办，就回到父节点，并且如果它在父节点左边，那就表示它比父节点小，父节点就满足递增关系且最接近当前节点的节点，此时
返回父节点就可以了。如果它在父节点的右边，那就退回到父节点，迭代这一操作直到找到一个为其左孩子的父节点。如果回到了根，就返回NULL。”
所谓的io排序就体现在这里。
最后真正的dispatch在函数deadline_move_to_dispatch中
|--------------------------------------------------------------------------<
static inline void
deadline_move_to_dispatch(struct deadline_data *dd, struct request *rq)
{
struct request_queue *q = rq->q;
deadline_remove_request(q, rq);
elv_dispatch_add_tail(q, rq);
}
|-------------------------------------------------------------------------->
这里代码还是比较容易理解的
deadline_remove_request(q, rq);
将rq从红黑树以及fifo队列中删掉，并且移除其截止时间。
elv_dispatch_add_tail(q, rq);
移动到request_queue中去。
这时再回头看看
/*
* batches are currently reads XOR writes
*/
if (dd->next_rq[WRITE])
rq = dd->next_rq[WRITE];
else
rq = dd->next_rq[READ];
if (rq && dd->batching < dd->fifo_batch)
/* we have a next request are still entitled to batch */
goto dispatch_request;
如果第二次进来，rq有可能不为空，而rq是从红黑树中查找到的，其起始扇区最靠近上一次请求。
如果batching还是小于fifo_batch，就会直接去dispatch，所以从这里可以知道fifo_batch限定了一批请求的最大数量。
所以如果fifo_batch的值很小，将不利于批操作，所以吞吐量会下降。但是获得了更多的重新选择读或写方向的机会，实时性变好了。
反之则是吞吐量上升，实时性下降。
至此，deadline的基本原理分析完毕。
dispatch_request:
/*
* rq is the selected appropriate request.
*/
dd->batching++;
deadline_move_request(dd, rq);
return 1;
首先batching++，表示这批请求已经有1个了，记个数。
然后调用deadline_move_request，这个函数会开始对next_rq赋值，所以第一次进这个函数时，next_rq[方向]是空的，从第二次开始就不一定了。
|----------------------------------------------------------------------------<
static void
deadline_move_request(struct deadline_data *dd, struct request *rq)
{
const int data_dir = rq_data_dir(rq);
dd->next_rq[READ] = NULL;
dd->next_rq[WRITE] = NULL;
dd->next_rq[data_dir] = deadline_latter_request(rq);
dd->last_sector = rq_end_sector(rq);
/*
* take it off the sort and fifo list, move
* to dispatch queue
*/
deadline_move_to_dispatch(dd, rq);
}
|---------------------------------------------------------------------------->
首先确定本次请求方向(data_dir)
然后在为本次请求同方向上的next_rq进行赋值
dd->next_rq[data_dir] = deadline_latter_request(rq);
先看看这里面的一个函数
|----------------------------------------------------------<
static inline struct request *
deadline_latter_request(struct request *rq)
{
struct rb_node *node = rb_next(&rq->rb_node);
if (node)
return rb_entry_rq(node);
return NULL;
}
|----------------------------------------------------------<
会在红黑树上去查找下一个节点，rb_next是内核中有关红黑树的操作，定义在lib/rbtree.c。rb_next做了什么，上面一段话已经表述过了，这里
再贴一下：
“树上每个节点可以有左右两个孩子。如果有左孩子，那么左孩子请求的起始扇区是小于它的父节点请求的起始扇区的；
如果有右边孩子，那么右孩子的起始扇区是大于或等于父节点的起始扇区的。
首先，应该明白扇区号是不断递增的，所以为了找到与当前请求的起始扇区最接近的节点，只需从右子树上去找最小值，也就是不断的去找左孩子，直到
找到没有左孩子的节点（想一想，左边代表小于，一直都在小于，直到无法再小于了，那自然就是最小值了）。
如果当前节点没有右孩子怎么办，就回到父节点，并且如果它在父节点左边，那就表示它比父节点小，父节点就满足递增关系且最接近当前节点的节点，此时
返回父节点就可以了。如果它在父节点的右边，那就退回到父节点，迭代这一操作直到找到一个为其左孩子的父节点。如果回到了根，就返回NULL。”
所谓的io排序就体现在这里。
最后真正的dispatch在函数deadline_move_to_dispatch中
|--------------------------------------------------------------------------<
static inline void
deadline_move_to_dispatch(struct deadline_data *dd, struct request *rq)
{
struct request_queue *q = rq->q;
deadline_remove_request(q, rq);
elv_dispatch_add_tail(q, rq);
}
|-------------------------------------------------------------------------->
这里代码还是比较容易理解的
deadline_remove_request(q, rq);
将rq从红黑树以及fifo队列中删掉，并且移除其截止时间。
elv_dispatch_add_tail(q, rq);
移动到request_queue中去。
这时再回头看看
/*
* batches are currently reads XOR writes
*/
if (dd->next_rq[WRITE])
rq = dd->next_rq[WRITE];
else
rq = dd->next_rq[READ];
if (rq && dd->batching < dd->fifo_batch)
/* we have a next request are still entitled to batch */
goto dispatch_request;
如果第二次进来，rq有可能不为空，而rq是从红黑树中查找到的，其起始扇区最靠近上一次请求。
如果batching还是小于fifo_batch，就会直接去dispatch，所以从这里可以知道fifo_batch限定了一批请求的最大数量。
所以如果fifo_batch的值很小，将不利于批操作，所以吞吐量会下降。但是获得了更多的重新选择读或写方向的机会，实时性变好了。
反之则是吞吐量上升，实时性下降。
至此，deadline的基本原理分析完毕。
<4> 其他的一些代码
|-------------------------------------------------------------------------------------<
...
SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1);
SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1);
SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0);
SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0);
SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0);
...
STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1);
STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1);
STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0);
STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0);
STORE_FUNCTION(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0);
|------------------------------------------------------------------------------------->
这里的代码将一些变量放到sysfs中去，让用户可以修改。
你可以去/sys/block/sda/queue/iosched/看看都有什么
ls /sys/block/sda/queue/iosched/
fifo_batch front_merges read_expire write_expire writes_starved
fifo_batch
上面代码中提到fifo_batch，默认值是16，所以如果需要更好的实时性，可以echo一个更小的值给它。
front_merges
上面代码中提到的front_merges，如果你不喜欢做前端合并，可以echo 0 > front_merges将它的值改为0（上面的if语句就会为假）
默认为1，也即是开启状态。开启后能减少请求，但会增加对红黑树的操作。
read_expire
读请求的响应截止时间，默认值500ms，这个时间到了，必须要对读请求进行响应。对应于fifo_expire[READ]
write_expire
写请求的响应截止时间，默认值5000ms，对应于fifo_expire[WRITE]。即便这个时间到了，也还需要写的饥饿程度超过了饥饿线。
writes_starved
写的饥饿线，默认值是2。也就是说进行了两批读操作后才考虑写。
|-------------------------------------------------------------------------------------<
...
SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1);
SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1);
SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0);
SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0);
SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0);
...
STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1);
STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1);
STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0);
STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0);
STORE_FUNCTION(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0);
|------------------------------------------------------------------------------------->
这里的代码将一些变量放到sysfs中去，让用户可以修改。
你可以去/sys/block/sda/queue/iosched/看看都有什么
ls /sys/block/sda/queue/iosched/
fifo_batch front_merges read_expire write_expire writes_starved
fifo_batch
上面代码中提到fifo_batch，默认值是16，所以如果需要更好的实时性，可以echo一个更小的值给它。
front_merges
上面代码中提到的front_merges，如果你不喜欢做前端合并，可以echo 0 > front_merges将它的值改为0（上面的if语句就会为假）
默认为1，也即是开启状态。开启后能减少请求，但会增加对红黑树的操作。
read_expire
读请求的响应截止时间，默认值500ms，这个时间到了，必须要对读请求进行响应。对应于fifo_expire[READ]
write_expire
写请求的响应截止时间，默认值5000ms，对应于fifo_expire[WRITE]。即便这个时间到了，也还需要写的饥饿程度超过了饥饿线。
writes_starved
写的饥饿线，默认值是2。也就是说进行了两批读操作后才考虑写。
(2) 一些个人见解
从上面分析看deadline也是一种简单的算法，由于它的操作不复杂，所以用在SSD，u盘，sd卡也是OK的。并且你使用deadline还能获得一定的实时保证，
不像noop那么极端。所以在没有别的选择时，我更偏向于在闪存器件中选择使用deadline，并且你还可以根据需求调整各参数，以满足一些应用需求。
deadline是一种重读轻写的调度。实际中，读操作多半是同步的，因为应用程序需要等待数据才能继续运行，而写则经常可以放在空闲的时候去进行。
并且读与写的平衡还可以通过read_expire write_expire writes_starved来调整。
4. 其他
实际中，还存在很多种io调度的算法，例如cfq，也是比较常见的，但由于我没看过cfq的代码，也无法给大家作出分析。我对cfq的理解也只局限于
理论上的，一般来说，cfq比较适合进程比较多的桌面环境，所以在机械硬盘运行的桌面系统中使用cfq很常见。
除了cfq，还有as, bfq, sio, vr等等。
sio是我觉得最适合闪存器件的io调度，可惜kernel-3.12.5中没有，因为它像noop一样不进行扇区排序，又同时像deadline一样要考虑
读写的最长响应时间。这样显得更合理。
目前我在ssd中使用的io调度是sio，这个sio是我自己基于deadline修改的（其实就是去掉了红黑树排序的那些代码）。在没有sio时还是推荐
deadline，毕竟deadline又不复杂，那点排序代码损失不大，但却获得了一定的实时保证。
从上面分析看deadline也是一种简单的算法，由于它的操作不复杂，所以用在SSD，u盘，sd卡也是OK的。并且你使用deadline还能获得一定的实时保证，
不像noop那么极端。所以在没有别的选择时，我更偏向于在闪存器件中选择使用deadline，并且你还可以根据需求调整各参数，以满足一些应用需求。
deadline是一种重读轻写的调度。实际中，读操作多半是同步的，因为应用程序需要等待数据才能继续运行，而写则经常可以放在空闲的时候去进行。
并且读与写的平衡还可以通过read_expire write_expire writes_starved来调整。
4. 其他
实际中，还存在很多种io调度的算法，例如cfq，也是比较常见的，但由于我没看过cfq的代码，也无法给大家作出分析。我对cfq的理解也只局限于
理论上的，一般来说，cfq比较适合进程比较多的桌面环境，所以在机械硬盘运行的桌面系统中使用cfq很常见。
除了cfq，还有as, bfq, sio, vr等等。
sio是我觉得最适合闪存器件的io调度，可惜kernel-3.12.5中没有，因为它像noop一样不进行扇区排序，又同时像deadline一样要考虑
读写的最长响应时间。这样显得更合理。
目前我在ssd中使用的io调度是sio，这个sio是我自己基于deadline修改的（其实就是去掉了红黑树排序的那些代码）。在没有sio时还是推荐
deadline，毕竟deadline又不复杂，那点排序代码损失不大，但却获得了一定的实时保证。
