wuzhongjie 的BLOG
用户名：wuzhongjie
文章数：141
评论数：160
访问量：311601
注册日期：
阅读量：5863
阅读量：12276
阅读量：421592
阅读量：1109931
51CTO推荐博文
IO调度器&当IO旅行到调度器的时候，发现自己受到的待遇竟然很不一样，有些IO倚仗着特权很快就放行了；有些IO迟迟得不到处理，甚至在有些系统中居然饿死！面对这样的现状，IO显然是很不高兴的，凭什么别人就能被很快送到下一个旅程，自己需要在调度器上耗费青春年华？这里是拼爹的时代，人家出身好，人家是读请求，人家就可以很快得到资源。咱们是写请求，出生贫寒，只能等着，但也不会让你饿死。这就是我们常见的deadline策略。在更加糟糕的地方，deadline都没有，拼的是家族血脉关系，相邻的IO可以很快处理掉，其他的等着吧，那就会出现饿死的情况。这就是我们常说的noop策略，其实就是Linus电梯。在文明一点的社会，大家会比较公平，从应用的整体来看，大家会享有相同的IO带宽，但是，从IO的个体来看，公平性还是没有的。这个社会没有绝对的公平，只要保证所有家庭的公平性，那么社会就会比较和谐。当然，我们发现有些家庭（应用）不是特别合群，我们也可以对其进行惩罚，IO带宽的分配就会对其进行缩减。这就是我们常见的CFQ策略。在IO调度器层，可以有很多的策略，不同的系统可以定义不同的策略，目的都是在与更好的聚合IO，并且对不同的应用进行QOS控制。在Linux系统中，可以注册自己的调度算法，如果不注册自己的调度器，那么可以采用上述提到的三种调度器之一。其中，deadline是在Linus电梯的基础上发展起来的，其对读写请求进行了有区别的调度，还会考虑到IO饥饿的情况。最为传统的调度器不能规避IO饥饿问题。CFQ调度器考虑了应用的公平性，在很多情况下可以得到最佳性能，有关于这三种调度器的设计比较会在下面篇章中详细阐述。当IO请求通过generic_make_request进行转发时，如果被访问的设备是一个有queue的块设备，那么系统会调用blk_queue_bio函数进行bio的调度合并。blk_queue_bio函数说明如下：void blk_queue_bio(struct request_queue *q, struct bio *bio)
const bool sync = !!(bio-&bi_rw & REQ_SYNC);
struct blk_plug *
int el_ret, rw_flags, where = ELEVATOR_INSERT_SORT;
struct request *
unsigned int request_count = 0;
* low level driver can indicate that it wants pages above a
* certain limit bounced to low memory (ie for highmem, or even
* ISA dma in theory)
blk_queue_bounce(q, &bio);
if (bio-&bi_rw & (REQ_FLUSH | REQ_FUA)) {
spin_lock_irq(q-&queue_lock);
where = ELEVATOR_INSERT_FLUSH;
* Check if we can merge with the plugged list before grabbing
* any locks.
/* 尝试将bio合并到当前plugged的请求队列中 */
if (attempt_plug_merge(q, bio, &request_count))
spin_lock_irq(q-&queue_lock);
/* elv_merge是核心函数，找到bio前向或者后向合并的请求 */
el_ret = elv_merge(q, &req, bio);
if (el_ret == ELEVATOR_BACK_MERGE) {
/* 进行后向合并操作 */
if (bio_attempt_back_merge(q, req, bio)) {
if (!attempt_back_merge(q, req))
elv_merged_request(q, req, el_ret);
} else if (el_ret == ELEVATOR_FRONT_MERGE) {
/* 进行前向合并操作 */
if (bio_attempt_front_merge(q, req, bio)) {
if (!attempt_front_merge(q, req))
elv_merged_request(q, req, el_ret);
/* 无法找到对应的请求实现合并 */
* This sync check and mask will be re-done in init_request_from_bio(),
* but we need to set it earlier to expose the sync flag to the
* rq allocator and io schedulers.
rw_flags = bio_data_dir(bio);
rw_flags |= REQ_SYNC;
* Grab a free request. This is might sleep but can not fail.
* Returns with the queue unlocked.
/* 获取一个empty request请求 */
req = get_request_wait(q, rw_flags, bio);
if (unlikely(!req)) {
bio_endio(bio, -ENODEV);
/* @q is dead */
* After dropping the lock and possibly sleeping here, our request
* may now be mergeable after it had proven unmergeable (above).
* We don't worry about that case for efficiency. It won't happen
* often, and the elevators are able to handle it.
/* 采用bio对request请求进行初始化 */
init_request_from_bio(req, bio);
if (test_bit(QUEUE_FLAG_SAME_COMP, &q-&queue_flags))
req-&cpu = raw_smp_processor_id();
plug = current-&
if (plug) {
* If this is the first request added after a plug, fire
* of a plug trace. If others have been added before, check
* if we have multiple devices in this plug. If so, make a
* note to sort the list before dispatch.
if (list_empty(&plug-&list))
trace_block_plug(q);
if (!plug-&should_sort) {
struct request *__
__rq = list_entry_rq(plug-&list.prev);
if (__rq-&q != q)
plug-&should_sort = 1;
if (request_count &= BLK_MAX_REQUEST_COUNT) {
/* 请求数量达到队列上限值，进行unplug操作 */
blk_flush_plug_list(plug, false);
trace_block_plug(q);
/* 将请求加入到队列 */
list_add_tail(&req-&queuelist, &plug-&list);
drive_stat_acct(req, 1);
/* 在新的内核中，如果用户没有调用start_unplug，那么，在IO scheduler中是没有合并的，一旦加入到request queue中，马上执行unplug操作，这个地方个人觉得有点不妥，不如以前的定时调度机制。对于ext3文件系统，在刷写page cache的时候，都需要首先执行start_unplug操作，因此都会进行request/bio的合并操作。 */
spin_lock_irq(q-&queue_lock);
/* 将request加入到调度器中 */
add_acct_request(q, req, where);
/* 调用底层函数执行unplug操作 */
__blk_run_queue(q);
out_unlock:
spin_unlock_irq(q-&queue_lock);
}对于blk_queue_bio函数主要做了三件事情：1）进行请求的后向合并操作2）进行请求的前向合并操作3）如果无法合并请求，那么为bio创建一个request，然后进行调度在bio合并过程中，最为关键的函数是elv_merge。该函数主要工作是判断bio是否可以进行后向合并或者前向合并。对于所有的调度器，后向合并的逻辑都是相同的。在系统中维护了一个request&hash表，然后通过bio请求的起始地址进行hash寻址。Hash表的生成原理比较简单，就是将所有request的尾部地址进行分类，分成几大区间，然后通过hash函数可以寻址这几大区间。Hash函数是：hash_long(ELV_HASH_BLOCK((sec)),&elv_hash_shift)一旦通过hash函数找到所有位于这个区间的request之后，通过遍历的方式匹配到所需要的request。具体该过程的实现函数如下：static struct request *elv_rqhash_find(struct request_queue *q, sector_t offset)
struct elevator_queue *e = q-&
/* 通过hash函数找到区间内的所有request */
struct hlist_head *hash_list = &e-&hash[ELV_HASH_FN(offset)];
struct hlist_node *entry, *
struct request *
/* 遍历地址区间内的所有request */
hlist_for_each_entry_safe(rq, entry, next, hash_list, hash) {
BUG_ON(!ELV_ON_HASH(rq));
if (unlikely(!rq_mergeable(rq))) {
__elv_rqhash_del(rq);
/* 如果地址匹配，那么找到所需的request */
if (rq_hash_key(rq) == offset)
return NULL;
}采用hash方式维护request，有一点需要注意：当一个request进行合并处理之后，需要对该request在hash表中进行重新定位。这主要是因为request的尾地址发生了变化，有可能会超过一个hash区间的范围。如果后向合并失败，那么调度器会尝试前向合并。不是所有的调度器支持前向合并，如果调度器支持这种方式，那么需要注册elevator_merge_fn函数实现前向调度功能。例如deadline算法采用了红黑树的方式实现前向调度。如果前向调度无法完成合并。那么调度器认为该合并失败，需要产生一个新的request，并且采用现有bio对其进行初始化，然后加入到request&queue中进行调度处理。当IO利用generic_make_request来到块设备层之后，对其进行处理的重要函数blk_queue_bio主要任务是合并IO。由于不同的调度器有不同的合并方法、IO分类方法，所以，具体调度器的算法会采用函数注册的方式实现。blk_queue_bio仅仅是一个上层函数，最主要完成后向合并、调用调度器方法进行前向合并以及初始化request准备调度。&待续&本文出自 “” 博客，转载请与作者联系！
了这篇文章
类别：┆阅读(0)┆评论(0)
本文收录至博客专题：《》
02:08:45 23:29:52Posts - 141,
Articles - 36,
Comments - 241
11:29 by zhenjing, ... 阅读,
Linux内核块设备I/O子系统
Linux IO调度程序是块设备I/O子系统的主要组件，它介于通用块层和块设备驱动程序之间，如下图所示。当Linux内核组件要读写数据时，并非一有请求便立即执行，而是将请求放入请求(输入)队列，并推迟执行。为什么如此设计？原因在于Linux需要应对的最核心的块设备是磁盘。磁盘的寻道时间严重制约磁盘性能，若想提高磁盘IO性能必须想尽办法减少磁盘寻道次数。
块设备I/O子系统最核心的任务也就是提高块设备的整体性能，为此Linux实现了四种IO调度算法，算法基本思想就是通过合并和排序IO请求队列中的请求大大降低所需的磁盘寻道时间，从而提供整体IO性能。
2.6内核实现了四种IO调度算法，分别为预期(Anticipatory)算法、最后期限(Deadline)算法、完全公平对列(CFQ)算法以及NOOP算法(No Operation)。用户可在内核引导时指定一种I/O调度算法，也可在运行时通过&sysfs&文件系统/sys/block/sda/queue/scheduler改变块设备的I/O调度算法(cat可查看当前使用IO调度算法)。默认的IO调度程序是"预测"IO调度程序。
&Noop&算法
最简单的&I/O调度算法。该算法仅适当合并用户请求，并不排序请求：新的请求通常被插在调度队列的开头或末尾，下一个要处理的请求总是队列中的第一个请求。这种算法是为不需要寻道的块设备设计的，如SSD。
"CFQ（完全公平队列）&算法的主要目标是在触发I/O请求的所有进程中确保磁盘I/O带宽的公平分配。为了达到这个目标，算法使用许多个排序队列&&缺省为64&&它们存放了不同进程发出的请求。当算法处理一个请求时，内核调用一个散列函数将当前进程的线程组标识符(PID)；然后，算法将一个新的请求插人该队列的末尾。因此，同一个进程发出的请求通常被插入相同的队列中。
算法本质上采用轮询方式扫描I/O输入队列，选择第一个非空队列，依次调度不同队列中特定个数(公平)的请求，然后将这些请求移动到调度队列的末尾。
&最后期限&算法
除了调度队列外，&最后期限&算法还使用了四个队列。其中的两个排序队列分别包含读请求和写请求，其中的请求是根据起始扇区号排序的。另外两个最后期限队列包含相同的读和写请求，但这是根据它们的&最后期限&排序的。引人这些队列是为了避免请求饿死，由于电梯策略(曾经的调度算法)优先处理与上一个所处理的请求最近的请求，因而就会对某个请求忽略很长一段时间，这时就会发生这种情况。请求的最后期限本质上就是一个超时定时器，当请求被传给电梯算法时开始计时。缺省情况下，读请求的超时时间是500ms，写请求的超时时间是5s&&读请求优先于写请求，因为读请求通常阻塞发出请求的进程。最后期限保证了调度程序照顾等待很长一段时间的那个请求，即使它位于排序队列的末尾。
当算法要补充调度队列时，首先确定下一个请求的数据方向。如果同时要调度读和写两个请求，算法会选择&读&方向，除非该&写&方向已经被放弃很多次了（为了避免写请求饿死）。
接下来，算法检查与被选择方向相关的最后期限队列：如果队列中的第一个请求的最后期限已用完，那么算法将该请求移到调度队列的末尾。同时，它也会移动该过期的请求后面的一组来自排序队列的相同扇区号的请求。如果将要移动的请求在磁盘上物理相邻，那么这一批队列的长度会很长，否则就很短。
最后，如果没有请求超时，算法对来自于排序队列的最后一个请求连带之后的一组相同扇区的请求进行调度。当指针到达排序队列的末尾时，搜索又从头开始（&单方向算法&）。
&预期&算法
&预期&算法是Linux提供的最复杂的一种1/O调度算法。基本上，它是&最后期限&算法的一个演变，借用了&最后期限&算法的基本机制：两个最后期限队列和两个排序队列；I/O调度程序在读和写请求之间交互扫描排序队列，不过更倾向于读请求。扫描基本上是连续的，除非有某个请求超时。读请求的缺省超时时间是125ms，写请求的缺省超时时间是250ms。但是，该算法还遵循一些附加的启发式准则：
有些情况下，算法可能在排序队列当前位置之后选择一个请求，从而强制磁头从后搜索。这种情况通常发生在这个请求之后的搜索距离小于在排序队列当前位置之后对该请求搜索距离的一半时。
算法统计系统中每个进程触发的I/O操作的种类。当刚刚调度了由某个进程p发出的一个读请求之后，算法马上检查排序队列中的下一个请求是否来自同一个进程p。如果是，立即调度下一个请求。否则，查看关于该进程p的统计信息：如果确定进程p可能很快发出另一个读请求，那么就延迟一小段时间（缺省大约为7ms）。因此，算法预测进程p发出的读请求与刚被调度的请求在磁盘上可能是&近邻&。
linux的回写机制
不管如何优化块设备调度算法，也不可能解决磁盘IO和CPU速度严重不匹配的问题，为此Linux引入了页高速缓存。页高速缓存最开始是为内存管理而设计的，在2.6内核中，各种基于页的数据管理都纳入页高速缓存。因此块设备的IO缓冲区也属于页高速缓存。这些和使用者无关，是内核开发者需要关心的。对于开发者，需要知道的是：所有文件的IO操作都是&读写缓存&。对于读操作，只有当数据不在缓存时才需要IO操作。对于写操作，一定需要IO操作，但内核把数据写到高速缓存后write系统调用立马返回，内核采用特定的写进程统一回写dirty的缓存页。即内核对读写是分别对待的：&同步读，异步写&！
Linux的写回由特定进程按照特定算法来进行回写。在2.6.32之前的内核，pdflush后台回写例程负责完成这个工作。啥时回写呢？&下面两种情况下，脏页会被写会到磁盘：
1.在空闲内存低于一个特定的阈值时，内核必须将脏页写回磁盘，以便释放内存。2.当脏页在内存中驻留超过一定的阈值时，内核必须将超时的脏页写会磁盘，以确保脏页不会无限期地驻留在内存中。
回写开始后，pdflush会持续写数据，直到满足以下两个条件：
1.已经有指定的最小数目的页被写回到磁盘。2.空闲内存页已经回升，超过了阈值dirty_background_ration。
系统管理员可以在/proc/sys/vm中设置回写相关的参数，也可以通过sysctl系统调用来设置它们。下表给出了可以设置的量：
回写机制看上去很完美，在实际工作中却未必。一个问题是：pdflush线程数据是可变的(2-8)，但面对的是所有块设备的数据，当某个块设备很慢，必然阻塞其他块设备的回写。为此2.6.32引入新的pdflush线程模型，每个块设备拥有独立的pdflush线程，设备之间的回写不再互相干扰。
看上去如此完美的回写机制，实际中有2个缺陷：1) 回写不及时引发丢数据(sync|fsync)；2) 回写期间读IO性能极差，尤其是大数据量时。
Linux：2.6.16&
测试过程：限速情况下持续追加写入磁盘，速度20-10MB/s,&
实测曲线：
结论：pdflush回写期间极其消耗磁盘IO，严重影响读性能。
linux kernel development 3rd(Linux内核设计与实现)推荐这篇日记的豆列
······}