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

🚀 优质资源分享 🚀

学习路线指引（点击解锁）	知识定位	人群定位
🧡 Python实战微信订餐小程序 🧡	进阶级	本课程是python flask+微信小程序的完美结合，从项目搭建到腾讯云部署上线，打造一个全栈订餐系统。
💛Python量化交易实战💛	入门级	手把手带你打造一个易扩展、更安全、效率更高的量化交易系统

1 总体说明

Deadline调度器对一个请求的多方面特性进行权衡来进行调度，以期望既能满足块设备扇区的顺序访问又能兼顾到一个请求不会在队列中等待太久导致饿死。Deadline调度器为了兼顾这两个方面，通过红黑树来对请求按起始扇区序号进行排序，称为

sort_list

，通过

fifo

对请求按它们的生成时间进行排序，称为

fifo_list

。

batching

- 每当确定了一个传输方向（读/写），那么将会从相应的

sort_list

中将一批连续请求

dispatch

到

request_queue

的请求队列里，具体的数目由

fifo_batch（default-16）

来确定。

总体来讲，deadline算法对request进行了优先权控制调度，主要表现在如下几个方面：

读写请求分离，读请求具有高优先调度权，除非写请求即将被饿死的时候才会去调度写请求，这种处理可以保证读请求的延迟时间最小化；
对请求的顺序批量处理，对那些地址临近的顺序化请求，deadline给予了高优先级处理权。例如一个写请求得到调度后，其临近的request会在紧接着的调度过程中被处理，这种顺序批量处理的方法可以最大程度减少磁盘抖动；
保证每个请求的延迟时间。每个请求都赋予了一个最大延迟时间，如果达到延迟时间的上限，那么这个请求就会被提前处理，此时会破坏磁盘访问的顺序化而影响性能，但是保证了每个请求的最大延迟时间；

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 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); |
|  |  |
|  | /* |
|  |  * 设置超时时间，这个请求在超时时间 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 void |
|  | deadline\_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 int |
|  | deadline\_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

中先删除再重新加回

|  | 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); |
|  |  } |
|  | } |

3.4 合并后处理

合并后，调用

deadline_merged_requests()

做合并后的处理

|  | static void |
|  | deadline\_merged\_requests(struct request\_queue *q, struct request *req, |
|  | struct request *next) |
|  | { |
|  | if (!list\_empty(&req->queuelist) && !list\_empty(&next->queuelist)) { |
|  | /* 如果next的期限小于req */ |
|  | if (time\_before(next->fifo\_time, req->fifo\_time)) { |
|  | /* 这个queuelist实际上就是真正发给设备驱动程序的队列，处理完了的队列 */ |
|  |  list\_move(&req->queuelist, &next->queuelist); |
|  | /* 因为是next比req要先响应，合并完了肯定要以先响应的为准 */ |
|  |  req->fifo\_time = next->fifo\_time; |
|  |  } |
|  |  } |
|  |  |
|  | /* 从fifo\_list和sort\_list删除next */ |
|  |  deadline\_remove\_request(q, next); |
|  | } |

3.5 派发

最后，调用

deadline_dispatch_requests()

将请求派发到系统的

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; |
|  |  |
|  | /* 两个方向上的next\_rq同时只能有一个为真 */ |
|  | if (dd->next\_rq[WRITE]) |
|  |  rq = dd->next\_rq[WRITE]; |
|  | else |
|  |  rq = dd->next\_rq[READ]; |
|  |  |
|  | /* 如果有rq并且批量disaptch未到上限，则直接进行dispatch */ |
|  | if (rq && dd->batching < dd->fifo\_batch) |
|  | /* we have a next request are still entitled to batch */ |
|  | goto dispatch\_request; |
|  |  |
|  | 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; |
|  |  } |
|  |  |
|  | 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: |
|  | /* |
|  |  * 我们不是处理批量请求，而是选择数据方向上最优的请求 |
|  |  */ |
|  |  |
|  | /* |
|  |  * 如果fifo\_list有超时或者下一个请求的方向变了，就去 |
|  |  * fifo\_list去request，然后还得执行下面的dispatch\_request |
|  |  */ |
|  |  |
|  | /* |
|  |  * 该请求方向存在即将饿死的请求，或不存在批量处理的请求， |
|  |  * 则先从FIFO队列头取一个请求 |
|  |  */ |
|  | if (deadline\_check\_fifo(dd, data\_dir) || !dd->next\_rq[data\_dir]) { |
|  |  rq = rq\_entry\_fifo(dd->fifo\_list[data\_dir].next); |
|  |  } else { |
|  | /* |
|  |  * 为什么这里可以直接从fifo\_list取而不是sort\_list，因为 |
|  |  * 最终都需要通过rq的rb\_node到sort\_list找 |
|  |  */ |
|  | /* 按照扇区顺序处理请求 */ |
|  |  rq = dd->next\_rq[data\_dir]; |
|  |  } |
|  |  |
|  | /* 启动新一批请求dispatch */ |
|  |  dd->batching = 0; |
|  |  |
|  | dispatch\_request: |
|  | /* |
|  |  * rq is the selected appropriate request. |
|  |  */ |
|  |  dd->batching++; |
|  | /* |
|  |  * 从fifo\_list和sort\_list中删除，再加入req->queuelist中，这里就从 |
|  |  * IO调度层离开了，移动一个请求到请求队列的派发队列 |
|  |  */ |
|  |  deadline\_move\_request(dd, rq); |
|  |  |
|  | return 1; |
|  | } |

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

🚀 优质资源分享 🚀

1 总体说明

2 数据结构

3 一般流程说明

3.1 请求到达

3.2 入队完毕

3.3 前向合并

3.4 合并后处理

3.5 派发

继续阅读

禁止ubuntu系统弹出报错界面

数据结构与算法（27）——排序（二）

Ubuntu Linux下Apache的配置文件

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Cloud Studio初体验

使用 ctypes 进行 Python 和 C 的混合编程

【python】【数据处理】画多维数据分布图

samba服务器的功能

【Linux】UDP广播报文接收速率问题

【python】netconf协议对接管理设备

「Python 网络自动化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 网络设备

Linux设备模型（中）之上层容器

PowerPC平台 Linux移植三

在python中创建excel并写入

hdu7108哈希