Chinaunix首页 | 论坛 | 博客
  • 博客访问: 690775
  • 博文数量: 183
  • 博客积分: 2650
  • 博客等级: 少校
  • 技术积分: 1428
  • 用 户 组: 普通用户
  • 注册时间: 2008-11-22 17:02
文章分类
文章存档

2017年(1)

2015年(46)

2014年(4)

2013年(8)

2012年(2)

2011年(27)

2010年(35)

2009年(60)

分类: LINUX

2010-02-06 21:23:48

linux deadline I/O调度算法分析笔记


deadline算法的核心就是在传统的电梯算法中加入了请求超时的机制,该机制主要体现在两点:(1)请求 超时时,对超时请求的选择。(2)没有请求超时时,当扫描完电梯最后一个request后,准备返回时,对第一个request的选择。基于以上两点,平 衡了系统i/o吞吐量和响应时间。此外,该算法开考虑到了读操作对写操作造成的饥饿。
算法核心数据结构:
struct deadline_data {
 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数目V灰猙atching < fifo_batch,都可以继续进行连续提交。
starved:提交读request而造成写饥饿的次数。如果starved超过writes_starved,则需要提交写request,从而避免写饥饿。

deadline I/O调度器中最重要的两个方法是:deadline_add_request和deadline_dispatch_requests。它们分别向调度器队列(非请求队列)添加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_add_request把请求分别加入红黑树和fifo。并记录请求的超时时间。这儿借用了request的donelist的next字段。因为在deadline调度队列的请求,绝不可能被调入请求完成队列:
#define rq_set_fifo_time(rq,exp) ((rq)->donelist.next = (void *) (exp))
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) {
  /* 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;
 }
 /*
  * 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;
}

deadline_dispatch_requests是deadline算法的核心。主要分为三个部分:(1)确定是要分发读还是写 request。影响处理分发类型因素主要包括是否处于batching阶段以及是否发生写饥饿。(2)确定方向以后,根据读写方向找到该方向上下一个请 求进行分发。影响定位下一个请求因素主要包括请求是否超时。(3)找到合适的request后,调用deadline_move_request分发给块 设备的请求队列。
1.确定读写方向.
a.首先,根据是否处于batching来确定当前处理读写的方向。因为如果处在batching过 程中,就意味着调度程序需要连续处理同一方向的请求。这样可以有效增加系统吞吐量。因此,根据batching的方向,可以确定当前处理请求的方向。而读 写batching是互斥的:
 /*
  * batches are currently reads XOR writes
  */
 if (dd->next_rq[WRITE])
  rq = dd->next_rq[WRITE];
 else
  rq = dd->next_rq[READ];
通过这个判断,保证了batching只会在某一方向进行,而不会交错。因为在deadline_move_request中有:
 dd->next_rq[READ] = NULL;
 dd->next_rq[WRITE] = NULL;
 dd->next_rq[data_dir] = deadline_latter_request(rq);
也就是在batching方向的next_rq才可能指向下一个request。
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;
 }
如 果存在下一个request,也就是没有扫描到电梯的末尾。则判断该request是否和上一个request相连。如果相连,并且batching的 request数没有超过fifo_batch,则当前这个request就是我们要分发的request。因此直接跳到最后,把request分发到设 备请求队列。此时将忽略写饥饿和超时的处理。如果不连续,则要结束batching。
b.如果此时并不处于batching过程中,则根据是否造成写饥饿“超标”来确定读写方向。
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;
 }
调度器先处理read,也就是read请求优先。但在处理过 程中考虑到了写饥饿。如果此时还有写请求,则写饥饿计数+1,如果写饥饿次数大于了writes_starved,则写饥饿已经“超标”了,因此直接跳到 dispath_writes去处理写请求。如果写饥饿没有“超标”,则继续处理读请求。
2.根据读写方向,找到当前要处理的请求:
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的算法核心所 在。调度器首先调用deadline_check_fifo来检查队列中队首,也就是最老的一个请求是否超时。如果超时则指定当前处理的请求为该超时的请 求。但如果没有超时,但已经扫描了电梯的末尾:!dd->next_rq[data_dir]。此时需要返回到电梯首部。但与传统的电梯算法不 同,deadline调度器不是返回到sector最小的request开始继续扫描。而是返回到等待时间最久的那个requst,从那个request 开始,沿sector递增方向继续扫描。也就是说,如果超时,或者扫描到电梯尾,都会返回来处理等待最久的request,并从这个request开始继 续进行电梯扫描。当然,如果既没有发生超时,也没有扫描到电梯末尾,则沿sector递增方向上的下一个request就是当前要处理的request。
3.找到要处理的request后,把它分发到块设备的请求队列。
 
整个deadline调度器比较简洁,总共只有400多行。它充分考虑了batching,写饥饿,请求超时这三大因素。在保证吞吐量的基础上,有考虑到了响应延时。
 
 
 
阅读(1204) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~