Linux I/O Scheduler--Deadline

Linux I/O Scheduler--Deadline

一、原理

Deadline调度器对一个请求的多方面特性进行权衡来进行调度，以期即能满足块设备扇区的顺寻访问又兼顾到一个请求不会在队列中等待太久导致饿死。试想当应用程序频繁访问文件的一部分而此时如果有另一个远端的请求，那么这个请求将会在很长一段时间内得不到响应，这显然是不合理的。Deadline调度器为了兼顾这两个方面，引入了四个队列，这四个队列可分为两类，每一类都由读和写两种队列组成。一类队列用来对请求按起始扇区序号进行排序，通过红黑树来组织，称为sort_list；另一类对请求按它们的生成时间进行排序，由链表来组织，称为fifo_list。

二、batching

每当确定了一个传输方向(读或写)，那么将会从相应的sort_list中将一批连续请求dispatch到requst_queue的请求队列里，具体的数目由fifo_batch来确定。只有下面三种情况才会导致一次批量传输的结束：

1.对应的sort_list中已经没有请求了

2.下一个请求的扇区不满足递增的要求

3.上一个请求已经是批量传输的最后一个请求了。

三、deadline和dispatch

所有的请求在生成时都会被赋上一个期限值(根据jiffies)，并按期限值排序在fifo_list中，读请求的期限时长默认为为500ms，写请求的期限时长默认为5s，可以看出内核对读请求是十分偏心的，其实不仅如此，在deadline调度器中，还定义了一个starved和writes_starved，writes_starved默认为2，可以理解为写请求的饥饿线，内核总是优先处理读请求，starved表明当前处理的读请求批数，只有starved超过了writes_starved后，才会去考虑写请求。因此，假如一个写请求的期限已经超过，该请求也不一定会被立刻响应，因为读请求的batch还没处理完，即使处理完，也必须等到starved超过writes_starved才有机会被响应。为什么内核会偏袒读请求？这是从整体性能上进行考虑的。读请求和应用程序的关系是同步的，因为应用程序要等待读取的内容完毕，才能进行下一步工作，因此读请求会阻塞进程，而写请求则不一样，应用程序发出写请求后，内存的内容何时写入块设备对程序的影响并不大，所以调度器会优先处理读请求。