浙江龙网

  1. 首页 > 生活百科 > >

Linux Block模块之deadline调度算法代码解析

生活百科

1 总体说明Deadline调度器对一个请求的多方面特性进行权衡来进行调度，以期望既能满足块设备扇区的顺序访问又能兼顾到一个请求不会在队列中等待太久导致饿死 。Deadline调度器为了兼顾这两个方面，通过红黑树来对请求按起始扇区序号进行排序，称为 sort_list，通过 fifo 对请求按它们的生成时间进行排序，称为 fifo_list。
batching - 每当确定了一个传输方向（读/写），那么将会从相应的 sort_list 中将一批连续请求 dispatch 到 request_queue 的请求队列里，具体的数目由 fifo_batch（default-16） 来确定 。
总体来讲，deadline算法对request进行了优先权控制调度，主要表现在如下几个方面：

  1. 读写请求分离，读请求具有高优先调度权，除非写请求即将被饿死的时候才会去调度写请求 ， 这种处理可以保证读请求的延迟时间最小化；
  2. 对请求的顺序批量处理，对那些地址临近的顺序化请求，deadline给予了高优先级处理权 。例如一个写请求得到调度后，其临近的request会在紧接着的调度过程中被处理，这种顺序批量处理的方法可以最大程度减少磁盘抖动；
  3. 保证每个请求的延迟时间 。每个请求都赋予了一个最大延迟时间，如果达到延迟时间的上限，那么这个请求就会被提前处理，此时会破坏磁盘访问的顺序化而影响性能，但是保证了每个请求的最大延迟时间；
2 数据结构struct deadline_data { /** sort_list红黑树的根，用于对IO请求根据起始扇区进行排序* 这里有两棵树，一棵读请求树，一棵写请求树*/ struct rb_root sort_list[2]; /* 按照到期时间排列的先入先出队列FIFO */ struct list_head fifo_list[2]; /** 记录批量处理请求的下一个读/写请求*/ struct request *next_rq[2]; /** 当前的发送数，当batching小于fifo_batch时，* 请求会连续的发送，大于或等于16时就会启动下一轮dispatch*/ unsigned int batching; sector_t last_sector; /* 写饥饿的次数 */ unsigned int starved; /** 这个数组分别存储了读/写请求的期限* 读请求为500ms，写请求为5s* 即使写请求超时也不一定立即得到相应，而是等到读请求当前的批次* 大于写请求饥饿线的时候才去处理写请求*/ int fifo_expire[2]; /* 批量发送的最大值 */ int fifo_batch; /* 写请求饥饿线，默认为2 */ int writes_starved; /* 表示能否进行前向合并的检查 */ int front_merges;};3 一般流程说明3.1 请求到达调用 deadline_add_request() 添加请求，代码执行流程如下：
static voiddeadline_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); /** 设置超时时间 ， 这个请求在超时时间 jiffies + dd->fifo_expire[data_dir]* 必须得到响应*/ rq->fifo_time = jiffies + dd->fifo_expire[data_dir]; /* 将rq加入fifo_list */ list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);}static voiddeadline_add_rq_rb(struct deadline_data *dd, struct request *rq){ /* 获取sort_list中指向根节点的指针root */ struct rb_root *root = deadline_rb_root(dd, rq); /* 将请求插入到红黑树中 */ elv_rb_add(root, rq);}3.2 入队完毕调用 deadline_merge() 对请求进行合并，elevator会自己做后向合并，并且后向合并优先于前向合并
static intdeadline_merge(struct request_queue *q, struct request **req, struct bio *bio){ struct deadline_data *dd = q->elevator->elevator_data; struct request *__rq; int ret; /* 如果可以向前合并 */ if (dd->front_merges) {sector_t sector = bio_end_sector(bio);/* 如果能找到一个请求，它的起始扇区号和bio的结束扇区号相同即连续的 */__rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);if (__rq) {BUG_ON(sector != blk_rq_pos(__rq));/* 如果找到则进行合并 */if (elv_bio_merge_ok(__rq, bio)) {ret = ELEVATOR_FRONT_MERGE;goto out;}} } return ELEVATOR_NO_MERGE;out: *req = __rq; return ret;}3.3 前向合并如果做了前向合并，调用 deadline_merged_request() 进行处理，因为前向合并使得请求的起始扇区发生变化，所以相应的处理就是从 sort_list 中先删除再重新加回
【Linux Block模块之deadline调度算法代码解析】static void deadline_merged_request(struct request_queue *q,struct request *req, int type){ struct deadline_data *dd = q->elevator->elevator_data; /* 把合并了的请求从sort_list删除再加入 */ if (type == ELEVATOR_FRONT_MERGE) {elv_rb_del(deadline_rb_root(dd, req), req);deadline_add_rq_rb(dd, req); }}

推荐阅读


上一篇：Linux Block模块之IO合并代码解析

下一篇：RAID5 IO处理之replace代码详解