1 linux的deadline io 调度算法分析
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以rhel5.6系统（kernel version 2.6.18）为基础分析linux内核的块设备层
的deadline io 调度算法。
2 把bio添加到请求中以及把请求添加到请求队列中
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2.1 最简单的情况，请求队列中一个请求都没有的时候，添加第一个bio
================================================================
bio通过generic_make_request函数传递进来。generic_make_request函数会
调用请求队列的make_request_fn函数指针完成实际的io操作。如果使用电梯
算法，请求队列的make_request_fn函数指针将指向__make_request函数。
我们只考虑与电梯算法相关的部分。
首先，调用elv_merge函数检查是否可以将当前的bio合并到以前的request
中。如果是第一次执行到这里，当然没有可以合并的request，于是调用
get_request_wait函数获取一个新的request，然后调用
init_request_from_bio函数将bio添加到request中。接下来调用
add_request函数将request添加到request_queue中。
add_request中的函数调用流程：
add_request->__elv_add_request->elv_insert
elv_insert函数会将新创建的request挂到request_queue的queue_head链表
上，并让request_queue的last_merge指针指向当前的request。最
后，elv_insert函数会调用到函数指针：
q->elevator->ops->elevator_add_req_fn
如果deadline是该块设备的io调度算法的话，这个指针就指向了
deadline_add_request函数。
deadline算法中有两个红黑树（读写请求各有一个），两个双向链表（读写
请求各有一个），一个哈希表（所有读写请求都在同一个哈希表上）。
deadline_add_request函数会将传递进来的request添加到与请求的读写方
向相对应的红黑树与双向链表中，以及哈希表上。同时，也记录下这个请求
的到期时间。
deadline中的红黑树以起始扇区号作为键值进行排序。双向链表按照request提
交进来的先后顺序进行排序，最先加进来的request放在链表的头部。因此，每
新添加一个请求的时候，都放在链表的尾部。哈希表使用request的结束扇
区号（即rq->sector + rq->nr_sectors）作为键值进行索引。读请求的期
满值默认为0.5秒，写请求的期满值默认为5秒。在合并与分发请求时，我们
会看到deadline算法如何使用这些数据。
调用完add_request函数后，__make_request的任务基本就结束了。每一个
请求队列，在真正处理请求的时候都会有一个延迟，一般默认设为3毫秒。
如果这3毫秒内又有request到来，则将该请求提交给io调度算法，并重新设
置延迟的期满时间为3毫秒。
2.2 将bio merge到request中
===========================
每当一个bio提交到__make_request函数中的时候，该函数总是调用
elv_merge函数检查是否能将当前的bio合并到以前的request中。elv_merge
函数分两步进行判断。
第一步，判断判断bio是否可以合并到request_queue的last_merge指针指向
的request。last_merge总是指向上一次提交进来的请求。如果进行连续读
写的话，这是可能性最大的情况。判断的方法很简单，首先看request的结
尾扇区号是否等于bio的起始扇区号，如果是的话就能够进行back merge，
然后判断request的起始扇区号是否等于bio的结尾扇区号，如果是的话就能
够进行front merge。
第二步，如果bio不能和last_merge指向的request进行合并的话，则调用io
调度算法的elevator_merge_fn成员函数，判断bio是否能和某个request进
行合并。
对于deadline调度算法，elevator_merge_fn指向deadline_merge函数。该
函数首先判断是否能进行back merge。以bio的起始扇区号为键值在哈希表
中寻找。由于deadline中的哈希表是以request的结束扇区号为键值的，所
以如果找到这样的request的话，说明这个request的结语扇区号与bio的起
始扇区号相等，因此bio可以back merge到这个request中。如果没有找到这
样的request，说明无法进行back merge，则继续尝试能否进行front merge。
方法是以bio的结束扇区号为键值在红黑树中进行搜索。红黑树是以request
的起始扇区号为键值进行排序的，因此，如果找到符合条件的request，说
明该request的起始扇区号等于bio的结束扇区号，可以进行front merge。
无论是back merge还是front merge，如果找到符合条件的request的话，都
要把request从哈希表上拿下来，再按照新的键值重新放上去，至于红黑树，会
在后续的操作中进行处理。
若是可以进行合并，elv_merge会返回用来合并的request指针，并且，通过
返回值表示是何种合并，ELEVATOR_BACK_MERGE表示back merge，
ELEVATOR_FRONT_MERGE表示front merge，ELEVATOR_NO_MERGE表示无法进行
合并。
2.2.1 back merge
-----------------
若是进行back merge，则调用函数指针q->back_merge_fn对request_queue
和request进行一些必要的处理，这个指针通常指向ll_back_merge_fn函数。
然后修改request的biotail，biotail->next，以及nr_sector等位，将bio
添加到request中。接下来调用attempt_back_merge函数，该函数的作用是
检查是否可以进一步的进行合并，例如，原先请求队列中有这样两个请
求，request1写块设备的secotr0到sector4，request2写块设备的
sector 8到sector 12。现在新加入的bio写sector5到sector7，bio被合并
到了request1中，request1变成写sector0到sector7，此时，request1和
request2可以进行合并了。若发生这种情况，attempt_back_merge函数会
进行处理，若没有，则调用elv_merged_request函数进行最后的收尾处理。
该函数会调用调度器的elevator_merged_fn方法，对于deadline调度器，
该方法指向deadline_merged_request函数。该函数的作用很简单，由于进
行了合并，request的起始扇区号和结束扇区号可能改变了，用新的扇区号
做键值更新request在哈希表和红黑树中的位置。
2.2.2 front merge
------------------
与back merge的处理基本对称，不再赘述。
3 从请求队列中取出一个请求
~~~~~~~~~~~~~~~~~~~~~~~~~~~
正常情况下，每当request_queue等待3毫秒还没有新的bio提交后，就会出发
unplug，最终会调到request_queue的request_fn方法。以scsi磁盘驱动为
例，该方法指向scsi_request_fn函数。scsi_request_fn会调用
elv_next_request函数来从请求队列中取出一个请求进行处理。而该函数会
调用__elv_next_request找出一个合适的请求。
__elv_next_request函数首先从request_queue的queue_head链表上寻找
request，如果找到的话就返回这个request，没找到的话就调用调度器的
elevator_dispatch_fn方法，通常，这个方法会将一些request放到
queue_head链表上。然后再检查request_queue的queue_head链表。一直循
环，直到从queue_head上找到一个request，将其返回，或者
elevator_dispatch_fn方法返回0，则__elv_next_request函数返回一个空指
针。
对于deadline调度器来说，elevator_dispatch_fn函数指针指向
deadline_dispatch_requests函数。
deadline_dispatch_requests函数负责从已经提交给调度器的request中选择
一个放到request_queue的queue_head链表中。
为了优化读写磁盘的效率，deadline调度器会对请求进行批处理，每当选定
一个请求方向时（读或写），总是连续处理该方向上的16个请求。然后才重
新选择另一个方向上的请求。当然，如果某个方向上已经没有请求了，则马
上选择另一个方向上的请求。
每当处理了一个方向上的请求，就将该方向上的下一个请求放到
next_drq[WRITE]中或next_drq[READ]中。因此，当进入
deadline_dispatch_requests函数的时候，首先判断next_drq[WRITE]或
next_drq[READ]是否为空，这两个指针至多有一个不为空。如果其中有一个
不为空，我们就获得了一个request。接下来判断这个request和上一次发送
的请求是否是连续的，若不是连续的，则打破批处理，然后判断当前的批处
理进行了多少次，如果超过了最大的允许次数，也要打破批处理，重新选择
request。这是为了防止在某一个方向上有大量连续的request，导致饿死了
另一个方向上的request。
如果确定要继续批处理，则直接跳到函数的末尾，即标签
“dispatch_find_request”处，递增批处理的统计次数，将同方向上的下一个
请求放到next_drq[WRITE]或next_drq[READ]中，记录当前request的结束扇区
号，以便再进入本函数时判断下一个request是否和当前这个是连续的。最后
把这个请求从deadline算法内部维护的哈希表，红黑数和链表上面移除，放到
request_queue的queue_head链表上。
如果前面判断不进行批处理，则先看是否有读请求需要处理。若读写请求都
有的话，就把starved变量加一，表示忽略了一次写请求。如果忽略的写请求
次数超过了变量writes_starved的值（默认为2），那么就不再忽略写请求，
跳转到标签“dispatch_writes”的位置，将变量data_dir设为WRITE，表示提
交一个写请求。否则将data_dir设为READ，表示提交一个读请求。
现在已经选择了request的方向（READ或WRITE），接下来判断在该方向上最
先进来的request是否已经超时了，或者该方向上还有没有request的起始扇
区号比上一个请求更靠后的request了（这样的request即使不连续也可以让
磁盘的磁头大体上朝一个方向移动）。如果两个条件中有一个条件为真，就
选择该方向上时间最早的request提交。如果这两个条件都为假的话，即没有
任何请求超时，而且有一个起始扇区号比上一个request大的请求，就提交这
个请求。
完。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以rhel5.6系统（kernel version 2.6.18）为基础分析linux内核的块设备层
的deadline io 调度算法。
2 把bio添加到请求中以及把请求添加到请求队列中
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2.1 最简单的情况，请求队列中一个请求都没有的时候，添加第一个bio
================================================================
bio通过generic_make_request函数传递进来。generic_make_request函数会
调用请求队列的make_request_fn函数指针完成实际的io操作。如果使用电梯
算法，请求队列的make_request_fn函数指针将指向__make_request函数。
我们只考虑与电梯算法相关的部分。
首先，调用elv_merge函数检查是否可以将当前的bio合并到以前的request
中。如果是第一次执行到这里，当然没有可以合并的request，于是调用
get_request_wait函数获取一个新的request，然后调用
init_request_from_bio函数将bio添加到request中。接下来调用
add_request函数将request添加到request_queue中。
add_request中的函数调用流程：
add_request->__elv_add_request->elv_insert
elv_insert函数会将新创建的request挂到request_queue的queue_head链表
上，并让request_queue的last_merge指针指向当前的request。最
后，elv_insert函数会调用到函数指针：
q->elevator->ops->elevator_add_req_fn
如果deadline是该块设备的io调度算法的话，这个指针就指向了
deadline_add_request函数。
deadline算法中有两个红黑树（读写请求各有一个），两个双向链表（读写
请求各有一个），一个哈希表（所有读写请求都在同一个哈希表上）。
deadline_add_request函数会将传递进来的request添加到与请求的读写方
向相对应的红黑树与双向链表中，以及哈希表上。同时，也记录下这个请求
的到期时间。
deadline中的红黑树以起始扇区号作为键值进行排序。双向链表按照request提
交进来的先后顺序进行排序，最先加进来的request放在链表的头部。因此，每
新添加一个请求的时候，都放在链表的尾部。哈希表使用request的结束扇
区号（即rq->sector + rq->nr_sectors）作为键值进行索引。读请求的期
满值默认为0.5秒，写请求的期满值默认为5秒。在合并与分发请求时，我们
会看到deadline算法如何使用这些数据。
调用完add_request函数后，__make_request的任务基本就结束了。每一个
请求队列，在真正处理请求的时候都会有一个延迟，一般默认设为3毫秒。
如果这3毫秒内又有request到来，则将该请求提交给io调度算法，并重新设
置延迟的期满时间为3毫秒。
2.2 将bio merge到request中
===========================
每当一个bio提交到__make_request函数中的时候，该函数总是调用
elv_merge函数检查是否能将当前的bio合并到以前的request中。elv_merge
函数分两步进行判断。
第一步，判断判断bio是否可以合并到request_queue的last_merge指针指向
的request。last_merge总是指向上一次提交进来的请求。如果进行连续读
写的话，这是可能性最大的情况。判断的方法很简单，首先看request的结
尾扇区号是否等于bio的起始扇区号，如果是的话就能够进行back merge，
然后判断request的起始扇区号是否等于bio的结尾扇区号，如果是的话就能
够进行front merge。
第二步，如果bio不能和last_merge指向的request进行合并的话，则调用io
调度算法的elevator_merge_fn成员函数，判断bio是否能和某个request进
行合并。
对于deadline调度算法，elevator_merge_fn指向deadline_merge函数。该
函数首先判断是否能进行back merge。以bio的起始扇区号为键值在哈希表
中寻找。由于deadline中的哈希表是以request的结束扇区号为键值的，所
以如果找到这样的request的话，说明这个request的结语扇区号与bio的起
始扇区号相等，因此bio可以back merge到这个request中。如果没有找到这
样的request，说明无法进行back merge，则继续尝试能否进行front merge。
方法是以bio的结束扇区号为键值在红黑树中进行搜索。红黑树是以request
的起始扇区号为键值进行排序的，因此，如果找到符合条件的request，说
明该request的起始扇区号等于bio的结束扇区号，可以进行front merge。
无论是back merge还是front merge，如果找到符合条件的request的话，都
要把request从哈希表上拿下来，再按照新的键值重新放上去，至于红黑树，会
在后续的操作中进行处理。
若是可以进行合并，elv_merge会返回用来合并的request指针，并且，通过
返回值表示是何种合并，ELEVATOR_BACK_MERGE表示back merge，
ELEVATOR_FRONT_MERGE表示front merge，ELEVATOR_NO_MERGE表示无法进行
合并。
2.2.1 back merge
-----------------
若是进行back merge，则调用函数指针q->back_merge_fn对request_queue
和request进行一些必要的处理，这个指针通常指向ll_back_merge_fn函数。
然后修改request的biotail，biotail->next，以及nr_sector等位，将bio
添加到request中。接下来调用attempt_back_merge函数，该函数的作用是
检查是否可以进一步的进行合并，例如，原先请求队列中有这样两个请
求，request1写块设备的secotr0到sector4，request2写块设备的
sector 8到sector 12。现在新加入的bio写sector5到sector7，bio被合并
到了request1中，request1变成写sector0到sector7，此时，request1和
request2可以进行合并了。若发生这种情况，attempt_back_merge函数会
进行处理，若没有，则调用elv_merged_request函数进行最后的收尾处理。
该函数会调用调度器的elevator_merged_fn方法，对于deadline调度器，
该方法指向deadline_merged_request函数。该函数的作用很简单，由于进
行了合并，request的起始扇区号和结束扇区号可能改变了，用新的扇区号
做键值更新request在哈希表和红黑树中的位置。
2.2.2 front merge
------------------
与back merge的处理基本对称，不再赘述。
3 从请求队列中取出一个请求
~~~~~~~~~~~~~~~~~~~~~~~~~~~
正常情况下，每当request_queue等待3毫秒还没有新的bio提交后，就会出发
unplug，最终会调到request_queue的request_fn方法。以scsi磁盘驱动为
例，该方法指向scsi_request_fn函数。scsi_request_fn会调用
elv_next_request函数来从请求队列中取出一个请求进行处理。而该函数会
调用__elv_next_request找出一个合适的请求。
__elv_next_request函数首先从request_queue的queue_head链表上寻找
request，如果找到的话就返回这个request，没找到的话就调用调度器的
elevator_dispatch_fn方法，通常，这个方法会将一些request放到
queue_head链表上。然后再检查request_queue的queue_head链表。一直循
环，直到从queue_head上找到一个request，将其返回，或者
elevator_dispatch_fn方法返回0，则__elv_next_request函数返回一个空指
针。
对于deadline调度器来说，elevator_dispatch_fn函数指针指向
deadline_dispatch_requests函数。
deadline_dispatch_requests函数负责从已经提交给调度器的request中选择
一个放到request_queue的queue_head链表中。
为了优化读写磁盘的效率，deadline调度器会对请求进行批处理，每当选定
一个请求方向时（读或写），总是连续处理该方向上的16个请求。然后才重
新选择另一个方向上的请求。当然，如果某个方向上已经没有请求了，则马
上选择另一个方向上的请求。
每当处理了一个方向上的请求，就将该方向上的下一个请求放到
next_drq[WRITE]中或next_drq[READ]中。因此，当进入
deadline_dispatch_requests函数的时候，首先判断next_drq[WRITE]或
next_drq[READ]是否为空，这两个指针至多有一个不为空。如果其中有一个
不为空，我们就获得了一个request。接下来判断这个request和上一次发送
的请求是否是连续的，若不是连续的，则打破批处理，然后判断当前的批处
理进行了多少次，如果超过了最大的允许次数，也要打破批处理，重新选择
request。这是为了防止在某一个方向上有大量连续的request，导致饿死了
另一个方向上的request。
如果确定要继续批处理，则直接跳到函数的末尾，即标签
“dispatch_find_request”处，递增批处理的统计次数，将同方向上的下一个
请求放到next_drq[WRITE]或next_drq[READ]中，记录当前request的结束扇区
号，以便再进入本函数时判断下一个request是否和当前这个是连续的。最后
把这个请求从deadline算法内部维护的哈希表，红黑数和链表上面移除，放到
request_queue的queue_head链表上。
如果前面判断不进行批处理，则先看是否有读请求需要处理。若读写请求都
有的话，就把starved变量加一，表示忽略了一次写请求。如果忽略的写请求
次数超过了变量writes_starved的值（默认为2），那么就不再忽略写请求，
跳转到标签“dispatch_writes”的位置，将变量data_dir设为WRITE，表示提
交一个写请求。否则将data_dir设为READ，表示提交一个读请求。
现在已经选择了request的方向（READ或WRITE），接下来判断在该方向上最
先进来的request是否已经超时了，或者该方向上还有没有request的起始扇
区号比上一个请求更靠后的request了（这样的request即使不连续也可以让
磁盘的磁头大体上朝一个方向移动）。如果两个条件中有一个条件为真，就
选择该方向上时间最早的request提交。如果这两个条件都为假的话，即没有
任何请求超时，而且有一个起始扇区号比上一个request大的请求，就提交这
个请求。
完。
