块IO层

系统中能够随机（不需要按顺序）访问固定大小数据片（chunks）的硬件设备称作块设备，这些固定大小的数据片就称作块。最常见的块设备是硬盘，除此之外，还有软盘驱动器、蓝光光驱和闪存等许多其他设备。注意，它们都是以安装文件系统的方式使用的—-这也是块设备一般的访问方式。
另一种基本的设备类型是字符设备。字符设备按照字符流的方式被有序访问，像串口和键盘就属于字符设备。如果一个硬件设备是以字符流的方式被访问的话，那就应该将它归于字符设备；反过来，如果一个设备是随机（无序）访问的，那么它就属于块设备。
对于这两种类型的设备，它们的区别在于是否可以随机访问数据—-换句话说，就是能否在访问设备时随意地从一个位置跳转到另一个位置。举个例子，键盘这种设备提供的就是一个数据流，当你输入“wolf”这个字符串时，键盘驱动程序会按照和输入完全相同的顺序返回这个由四个字符组成的数据流。如果让键盘驱动程序打乱顺序来读字符串，或读取其他字符，都是没有意义的。所以键盘就是一种典型的字符设备，它提供的就是用户从键盘输入的字符流。对键盘进行读操作会得到一个字符流，首先是“w”，然后是“o”，再是“l”，最后是“f”。当没人敲键盘时，字符流就是空的。硬盘设备的情况就不大一样了。硬盘设备的驱动可能要求读取磁盘上任意块的内容，然后又转去读取别的块的内容了，而被读取的块在磁盘上位置不一定要连续。所以说硬盘的数据可以被随机访问，而不是以流的方式被访问，因此它是一个块设备。
内核管理块设备要比管理字符设备细致得多，需要考虑的问题和完成的工作相对于字符设备来说要复杂的多。这是因为字符设备仅仅需要控制一个位置—-当前位置，而块设备访问的位置必须能够在介质的不同区间前后移动。所以事实上内核不必提供一个专门的子系统来管理字符设备，但是对于块设备的管理却必须有一个专门的提供服务的子系统。不仅仅是因为块设备的复杂性远远高于字符设备，更重要的原因是块设备对执行性能的要求很高；对硬盘每多一份利用都会对整个系统的性能带来提升，其效果要远远比键盘吞吐速度成倍的提高大得多。另外，我们将会看到，块设备的复杂性会为这种优化留下很大的施展空间。这一章的主题就是讨论内核如何对块设备和块设备的请求进行管理。该部分在内核中称作块I/O层。有趣的是，改写块I/O层正是2.5开发板内核的主要目标。本章涵盖了2.6内核中所有新的块I/O层。

剖析一个块设备

块设备中最小的可寻址单元是扇区。扇区大小一般是2的整数倍，而最常见的是512字节。扇区的大小是设备的物理属性，扇区是所有块设备的基本单元—-块设备无法对比它还小的单元进行寻址和操作，尽管很多块设备能够一次对多个扇区进行操作。虽然大多数块设备的扇区大小都是512字节，不过其他大小的扇区也很常见。比如，很多CD-ROM盘的扇区都是2KB的大小。
因为各种软件的用途不同，所以它们都会用到自己的最小逻辑可寻址单元—-块。块是文件系统的一种抽象—-只能基于块来访问文件系统。虽然物理磁盘寻址是按照扇区级进行的，但是内核执行的所有磁盘操作都是按照块进行的。由于扇区是设备的最小可寻址单元，所以块不能比扇区还小，只能数倍于扇区大小。另外，内核（对有扇区的硬件设备）还要求块大小是2的整数倍，而且不能超过一个页的长度。所以，对块大小的最终要求是，必须是扇区大小的2的整数倍，并且要小于页面大小。所以通常块大小是512字节、1KB或4KB。
扇区和块还有一些不同的叫法，为了不引起混淆，我们在这里简要介绍一下它们的其他名称。扇区----设备的最小寻址单元，有时会称作“硬扇区”或“设备块”；同样的，块----文件系统的最小寻址单元，有时会称作“文件块”或“I/O块”。在这一章里，会一直使用“扇区”和“块”这两个术语，但你还是应该记住它们的这些别名。下图是扇区和缓冲区之间的关系图。

至少相对于硬盘而言，另外一些术语更通用—-如簇、柱面以及磁头。这些表示是针对某些特定的块设备的，大多数情况下，对用户空间的软件是不可见的。扇区这一术语之所以对内核重要，是因为所有设备的I/O必须以扇区为单位进行操作。以此类推，内核所使用的“块”这一高级概念就是建立在扇区之上的。

缓冲区和缓冲区头

当一个块被调入内存时（也就是说，在读入后或等待写出时），它要存储在一个缓存区中。每个缓冲区与一个块对应，它相当于是磁盘块在内存中的表示。前面提到过，块包含一个或多个扇区，但大小不能超过一个页面，所以一个页可以容纳一个或多个内存中的块。由于内核在处理数据时需要一些相关的控制信息（比如块属于哪一个块设备，块对应于哪个缓冲区等），所以每一个缓冲区都有一个对应的描述符。该描述符用buffer_head结构体表示，称作缓冲区头，在文件<linux/buffer_head.h>中定义，它包含了内核操作缓冲区所需要的全部信息。
下面给出缓冲区头结构体和其中各个域的说明：

struct buffer_head {
    unsigned long           b_state;            //缓冲区状态标志
    struct buffer_head      *b_this_page;       //页面中的缓冲区
    struct page             *b_page;            //存储缓冲区中的页面
    sector_t                b_blocknr;          //起始块号
    size_t                  b_size;             //映像的大小
    char                    *b_data;            //页面内的数据指针
    struct block_device     *b_bdev;            //相关联的块设备
    bh_end_io_t             *b_end_io;          //I/O完成方法
    void *                  b_private;          //io完成方法
    struct list_head        b_assoc_buffers;    //相关的映射链表
    struct address_space    *b_assoc_map;       //相关的地址空间
    atomic_t                b_count;            //缓冲区使用计数
};

b_state域表示缓冲区的状态，可以是下表中一种标志或多种标志的组合。合法的标志存放在bh_state_bits枚举中，该枚举在<linux/buffer_head.h>中定义。
bh_state标志

状态标志	意义
BH_Uptodate	该缓冲区包含可用数据
BH_Dirty	该缓冲区是脏的（缓存中的内容比磁盘中的块内容新，所以缓冲区内容必须被写回磁盘）
BH_Lock	该缓冲区正在被I/O操作使用，被锁定以防被并发访问
BH_Req	该缓冲区有I/O请求操作
BH_Mapped	该缓冲区是映射磁盘块的可用缓冲区
BH_New	该缓冲区是通过get_block()刚刚映射的，尚且不能访问
BH_Async_Read	该缓冲区正通过end_buffer_async_read()被异步I/O读操作使用
BH_Async_Write	该缓冲区正通过end_buffer_async_write()被异步I/O写操作使用
BH_Delay	该缓冲区尚未和磁盘块关联
BH_Boundary	该缓冲区处于连续块区的边界—-下一个块不再连续
BH_Write_EIO	该缓冲区在写的时候遇到I/O错误
BH_Ordered	顺序写
BH_Eopnotsupp	该缓冲区发生“不被支持”错误
BH_Unwritten	该缓冲区在硬盘上的空间已被申请但是没有实际的数据写出
BH_Quiet	此缓冲区禁止错误

bh_state_bits列表还包含了一个特殊标志—-BH_PrivateStart，该标志不是可用状态标志，使用它是为了指明可被其他代码使用的起始位。块I/O层不会使用BH_PrivateStart或更高的位。那么某个驱动程序希望通过b_state域存储信息时就可以安全地使用这些位。驱动程序可以在这些位中定义自己地状态标志，只要保证自定义的状态标志不与块I/O层的专用位发生冲突就可以了。
b_count域表示缓冲区的使用计数，可通过两个定义在文件<linux/buffer_head.h>中的内联函数对此域进行增减。

static inline void get_bh(struct buffer_head *bh)
{
    atomic_inc(&bh->b_count);
}

static inline void put_bh(struct buffer_head *bh)
{
    atomic_dec(&bh->b_count);
}

在操作缓冲区头之前，应该先使用get_bh()函数增加缓冲区头的引用计数，确保该缓冲区头不会再被分配出去；当完成对缓冲区头的操作之后，还必须使用put_bh()函数减少引用计数。
与缓冲区对应的磁盘物理块由b_blocknr-th域索引，该值是b_bdev域指明的块设备中的逻辑块号。
与缓冲区对应的内存物理页由b_page域表示，另外，b_data域直接指向相应的块（它位于b_page域所指明的页面中的某个位置上），块的大小由b_size域表示，所以块在内存中的起始位置在b_data处，结束位置在（b_data + b_size）处。
缓冲区头的目的在于描述磁盘块和物理内存缓冲区（在特定页面上的字节序列）之间的映射关系。这个结构体在内核中只扮演一个描述符的角色，说明从缓冲区到块的映射关系。
在2.6内核以前，缓冲区头的作用比现在还要重要。因为缓冲区作为内核中的I/O操作单元，不仅仅描述了从磁盘块的物理内存的映射，而且还是所有块I/O操作的容器。可是，将缓冲区头作为I/O操作单元带来了两个弊端。首先，缓冲区头是一个很大且不易控制的数据结构体（现在是缩减过的了），而且缓冲区头对数据的操作既不方便也不清晰。对内核来说，它更倾向于操作页面结构，因为页面操作起来更为简单，同时效率也高。使用一个巨大的缓冲区头表示每一个独立的缓冲区（可能比页面小）效率低下，所以在2.6版本中，许多I/O操作都是通过内核直接对页面或地址空间进行操作来完成，不再使用缓冲区头了。
缓冲区头带来的第二个弊端就是：它仅能描述单个缓冲区，当作为所有的I/O的容器使用时，缓冲区头会促使内核把大块数据的I/O操作，分解为对多个buffer_head结构体进行操作。这样做必然会造成不必要的负担和空间浪费。

bio结构体

目前内核中块I/O操作的基本容器有bio结构体表示，它定义在文件<linux/bio.h>中。该结构体代表了正在现场的（活动的）以片段（segment）链表形式组织的块I/O操作。一个片段是一小块连续的内存缓冲区，这样的话，就不需要保证单个缓冲区一定要连续。所以通过用片段来描述缓冲区，即使一个缓冲区分散在内存的多个位置上，bio结构体也能对内核保证I/O操作的执行。像这样的向量I/O就是所谓的聚散I/O。
bio结构体定义于<linux/bio.h>中，下面给出的bio结构体和各个域的描述。

struct bio {
    sector_t            bi_sector;          //磁盘上相关的扇区
    struct bio          *bi_next;           //请求链表
    struct block_device *bi_bdev;           //相关的块设备
    unsigned long       bi_flags;           //状态和命令标志
    unsigned long       bi_rw;              //读还是写
    unsigned short      bi_vcnt;            //bio_vecs偏移的个数
    unsigned short      bi_idx;             //bio_io_vect的当前索引
    unsigned short      bi_phys_segments;   //结合后的片段数目
    unsigned int        bi_size;            //I/O计数
    unsigned int        bi_seg_front_size;  //第一个可合并的段大小
    unsigned int        bi_seg_back_size;   //最后一个可合并的段大小
    unsigned int        bi_max_vecs;        //bio_vecs数目上限
    unsigned int        bi_comp_cpu;        //结束CPU
    atomic_t            bi_cnt;             //使用计数
    struct bio_vec      *bi_io_vec;         //bio_vecs链表
    bio_end_io_t        *bi_end_io;         //I/O完成方法
    void                *bi_provate;        //拥有者的私有方法
    bio_destructor_t    *bi_destructor;     //撤销方法
    struct bio_vec      bi_inline_vecs[0];  //内嵌bio向量
};

使用bio结构体的目的主要是代表正在现场执行的I/O操作，所以该结构体的主要域都是用来管理相关信息的，其中最主要的几个域是bi_io_vecs、bi_vcnt和bi_idx。下图显示了bio结构体及其他结构体之间的关系。

I/O向量

bi_io_vec域指向一个bio_vec结构体数组，该结构体链表包含了一个特定的I/O操作所需要使用到的所有片段。每个bio_vec结构都是一个形式为<page,offset,len>的向量，它描述的是一个特定的片段：片段所在的物理页、块在物理页中的偏移位置、从给定偏移量开始的块长度。整个bio_io_vec结构体数组表示了一个完整的缓冲区。bio_vec结构定义在<linux/bio.h>中：

struct bio_vec {
    //指向这个缓冲区所驻留的物理页
    struct page         *bv_page;

    //这个缓冲区以字节为单位的大小
    unsigned int        bv_len;

    //缓冲区所驻留的页中以字节为单位的偏移量
    unsigned int        bv_offset;
};

在每个给定的块I/O操作中，bi_vcnt域用来描述bi_io_vec所指向的vio_vec数组中的向量数目。当块I/O操作执行完毕后，bi_idx域指向数组的当前索引。
总而言之，每一块I/O请求都通过一个bio结构体表示。每个请求包含一个或多个块，这些块存储在bio_vec结构体数组中。这些结构体描述了每个片段在物理页中的实际位置，并且像向量一样被组织在一起。I/O操作的第一个片段由b_io_vec结构体所指向，其他的片段在其后依次放置，共有bi_vcnt个片段。当块I/O层开始执行请求、需要使用各个片段时，bi_idx域会不断更新，从而总指向当前片段。
bi_idx域指向数组中的当前bio_vec片段，块I/O层通过它可以跟踪块I/O操作的完成进度。但该域更重要的作用在于分割bio结构体。像冗余廉价磁盘阵列（RAID，出于提高性能和可靠性的目的，将单个磁盘的卷扩展到多个磁盘上）这样的驱动器可以把单独的bio结构体（原本是为单个设备使用准备的），分割到RAID阵列中的各个硬盘上去。RAID设备驱动只需要拷贝这个bio结构体，再把bi_idx域设置为每个独立硬盘操作时需要的位置就可以了。
bi_cnt域记录bio结构体的使用计数，如果该域值减为0，就应该撤销该bio结构体，并释放它占用的内存。通过下面两个函数管理使用计数。

void bio_get(struct bio *bio);
void bio_put(struct bio *bio);

前者增加使用计数，后者减少使用计数（如果计数减到0，则撤销bio结构体）。在操作正在活动的bio结构体时，一定要首先增加它的使用计数，以免在操作过程中该bio结构体被释放；相反，在操作完毕后，要减少使用计数。
最后要说明的是bi_private域，这是一个属于拥有者（也就是创建者）的私有域，只有创建了bio结构的拥有者可以读写该域。

新老方法对比

缓冲区头和新的bio结构体之间存在显著差别。bio结构体代表的是I/O操作，它可以包括内存中的一个或多个页；而另一方面，buffer_head结构体代表的是一个缓冲区，它描述的仅仅是磁盘中的一个块。因为缓冲区头关联的是单独页中的单独磁盘块，所以它可能会引起不必要的分割，将请求按块为单位划分，只能靠以后才能重新组合。由于bio结构体是轻量级的，它描述的块可以不需要连续存储区，并且不需要分割I/O操作。
利用bio结构体代替buffer_head结构体还有以下好处：

1. bio结构体很容易处理高端内存，因为它处理的是物理页而不是直接指针。
2. bio结构体既可以代表普通页I/O，同时也可以代表直接I/O（指那些不通过页高速缓存的I/O操作）。
3. bio结构体便于执行分散-集中（矢量化的）块I/O操作，操作中的数据可取自多个物理页面。
4. bio结构体相比缓冲区头属于轻量级的结构体。因为它只需要包含块I/O操作所需的信息就行了，不用包含与缓冲区本身相关的不必要信息。

但是还是需要缓冲区头这个概念，毕竟它还负责描述磁盘块到页面的映射。bio结构体不包含任何和缓冲区相关的状态信息—-它仅仅是一个矢量数组，描述一个或多个单独块I/O操作的数据片段和相关信息。在当前设置中，当bio结构体描述当前正在使用的I/O操作时，buffer_head结构体仍然需要包含缓冲区的信息。内核通过这两种结构分别保存各自的信息，可以保证每种结构所含的信息量尽可能地少。

请求队列

块设备将它们挂起的块I/O请求保存在请求队列中，该队列由reques_queue结构体表示，定义在文件<linux/blkdev.h>中，包含一个双向请求链表以及相关控制信息。通过内核中像文件系统这样高层的代码将请求加入到队列中。请求队列只要不为空，队列对应的块设备驱动程序就会从队列头获取请求，然后将其送入到对应的块设备上去。请求队列表中的每一项都是一个单独的请求，由reques结构体表示。
队列中中的请求由结构体request表示，它定义在文件<linux/blkdev.h>中。因为一个请求可能要操作多个连续的磁盘块，所以每个请求可以由多个bio结构体组成。注意，虽然磁盘上的块必须要连续，但是在内存中这些块并不一定要连续—-每个bio结构体都可以描述多个片段，而每个请求也可以包含多个bio结构体。

I/O调度程序

如果简单地以内核产生的请求的次序直接将请求发向块设备的话，性能肯定让人难以接受。磁盘寻址是整个计算机中最慢的操作之一，每一次寻址（定位硬盘磁头到特定块上的某个位置）需要花费不少时间。所以尽量缩短寻址时间无疑是提高系统性能的关键。
为了优化寻址操作，内核既不会简单地按请求接收次序，也不会立即将其提交给磁盘。相反，它会在提交前，先执行名为合并与排序的预操作，这种预操作可以极大地提高系统的整体性能。在内核中负责提交I/O请求的子系统称为I/O调度程序。
I/O调度程序将磁盘I/O资源分配给系统中所有挂起的块I/O请求。具体地说，这种资源分配是通过将请求队列中挂起的请求合并和排序来完成的。注意不要将I/O调度程序和进程调度程序混淆。进程调度程序的作用是将处理器资源分配给系统中的运行进程。这两种子系统看起来非常相似，但并不相同。进程调度程序和I/O调度程序都是将一个资源虚拟给多个对象，对进程调度来说，处理器被虚拟并被系统中的运行进程共享。这种虚拟提供给用户的就是多任务和分时操作系统，像Unix系统。相反，I/O调度程序虚拟块设备给多个磁盘请求，以便降低磁盘寻址时间，确保磁盘性能的最优化。

I/O调度程序的工作

I/O调度程序的工作是管理块设备的请求队列。它决定队列中的请求排列顺序以及在什么时刻派发请求到设备。这样做有利于减少磁盘寻址时间，从而提高全局吞吐量。注意，全局这个定语很重要，坦率地讲，一个I/O调度器可能为了提高系统整体性能，而对某些请求不公。
I/O调度程序通过这两种方法减少磁盘寻址时间：合并与排序。合并指将两个或多个请求结合成一个新请求。考虑以下这种情况，文件系统请求提交到请求队列—-从文件中读取一个数据区（当然，最终所有的操作都是针对扇区和块进行的，而不是文件，还假定请求的块都是来自文件块），如果这时队列中已经存在一个请求，它访问的磁盘扇区和当前请求访问的磁盘扇区相邻（比如，同一个文件早些时候被读取的数据区），那么这两个请求就可以合并为一个对单个和多个相邻磁盘扇区操作的新请求。通过合并请求，I/O调度程序将多次请求的开销压缩成一次请求的开销。更重要的是，请求合并后只需要传递给传递给磁盘一条寻址命令，就可以访问到请求合并前必须多次寻址才能访问完的磁盘区域了，因此合并请求显然能减少系统开销和磁盘寻址次数。
现在，假设在读请求被提交给请求队列的时候，队列中并不需要操作相邻扇区的其他请求，此时就无法将读取请求与其他请求合并，当然，可以将其插入请求队列的尾部。但是如果由其他请求需要操作磁盘上类似的位置呢？如果存在一个请求，它要操作的磁盘扇区位置与当前请求比较接近，那么是不是该让这两个请求在请求队列中也相邻呢？事实上，I/O调度程序的确是这样处理上述情况的，整个请求队列将按扇区增长方向有序排列。使所有请求按硬盘上扇区的排列顺序有序排列（尽可能的）的目的不仅是为了缩短单独一次请求的寻址时间，更重要的优化在于，通过保持磁盘头以直线方向移动，缩短了所有请求的磁盘寻址时间。该排序算法类似于电梯调度—-电梯不能随意地从一层跳到另一层，它应该向一个方向移动，当抵达了同一方向上的最后一层后，再掉头向另一个方向移动。出于这种相似性，所以I/O调度程序（或这种排序算法）称作电梯调度。

Linus电梯

下面看看Linux中实际使用的I/O调度程序。我们看到的第一个I/O调度程序称为Linus电梯。在2.4版内核中，Linus电梯是默认的I/O调度程序。虽然后来在2.6版内核中它被另外两种调度程序取代了，但是由于这个电梯比后来的调度程序简单，而且它们执行的许多功能都相似，所以它可以作为一个优秀的入门介绍程序。
Linus电梯能执行合并与排序预处理。当有新的请求加入队列时，它首先会检查其他每一个挂起的请求是否可以和新请求合并。Linus电梯I/O调度程序可以执行向前向后合并，合并类型描述的是请求向前面还是向后面，这一点和已有请求相连。如果新请求正好连在一个现存的请求前，就是向前合并；相反如果新请求直接连在一个现存的请求后，就是向后合并。鉴于文件的分布（通常是以扇区号的增长表现）特点和I/O操作执行方式具有典型性（一般都是从头读向尾，很少从反方向读），所以向前合并相比向后合并要少的多，但是Linus电梯还是会对两种合并类型都进行检查。
如果合并尝试失败，那么就需要寻找可能的插入点（新请求在队列中的位置必须符合请求以扇区方向有序排序的原则）。如果找到，新请求将被插入到该点；如果没有合适的位置，那么新请求就被加入到队列尾部。另外，如果发现队列中有驻留时间过长的请求，那么新请求也将被加入到队列尾部，即使插入后还要排序。这样做是为了避免由于访问相近磁盘位置的请求太多，从而造成访问磁盘其他位置的请求难以得到执行机会这一问题。不幸的是，这种“年龄”检测方法并不很有效，因为它并非是给等待了一段时间的请求提供实质性服务，它仅仅是在经过了一定时间后停止插入-排序请求，这改善了等待时间但最终还是会导致请求饥饿现象的发生，所以这是一个2.4内核I/O调度程序中必须要修改的缺陷。
总而言之，当一个请求加入到队列中时，有可能发生四种操作，它们依次是：

1. 如果队列中已存在一个对相邻磁盘扇区操作的请求，那么新请求将和这个已经存在的请求合并成一个请求。
2. 如果队列中存在一个驻留时间过长的请求，那么新请求将被插入到队列尾部，以防止其他旧的请求饥饿发生。
3. 如果队列中以扇区方向为序存在合适的插入位置，那么新的请求将被插入到该位置，保证队列中的请求是以被访问磁盘物理位置为序进行排列的。
4. 如果队列中不存在合适的请求插入位置，请求将被插入到队列尾部。

最终期限I/O调度程序

最终期限（deadline）I/O调度程序是为了解决Linus电梯所带来的饥饿问题而提出的。出于减少磁盘寻址时间的考虑，对某个磁盘区域上的繁重操作，无疑会使得磁盘上其他位置上的操作请求得不到运行机会。实际上，一个对磁盘同一位置操作的请求流可以造成较远位置的其他请求永远得不到运行机会，这是一种很不公平的饥饿现象。
更糟糕的是，普通的请求饥饿还会带来名为写-饥饿-读（writes-starving-reads）这种特殊问题。写操作通常是在内核有空时才将请求提交给磁盘的，写操作完全和提交它的应用程序异步执行；读操作则恰恰相反，通常当应用程序提交一个读请求时，应用程序会发生堵塞直到读请求被满足，也就是说，读操作是和提交它的应用程序同步执行的。所以虽然写反应时间（提交写请求花费的时间）不会给系统响应速度造成很大影响，但是读响应时间（提交读请求花费的时间）对系统响应时间来说却非同小可。虽然写请求时间对应用程序性能带来的影响不大，但是应用程序却必须等待读请求完成后才能运行其他程序，所以读操作响应时间对系统的性能非常重要。
问题还可能更严重，这是因为读请求往往会相互依靠。比如，要读大量的文件，每次都是针对一块很小的缓冲区数据区进行读操作，而应用程序只有将上一个数据区从磁盘中读取并返回之后，才能继续读取下一个数据区（或下一个文件）。糟糕的是，不管是读还是写，二者都需要读取像索引节点这样的元数据。从磁盘进一步读取这些块会使I/O操作串行化。所以如果每一次请求都会发生饥饿现象，那么对读取文件的应用程序来说，全部延迟加起来会造成过长的等待时间，让用户无法忍受。综上所述，读操作具有同步性，并且彼此之间往往相互依靠，所以读请求响应时间直接影响系统性能，因此2.6版本内核新引入了最后期限I/O调度程序来较少请求饥饿现象，特别是读请求饥饿现象。
注意，减少请求饥饿必须以降低全局吞吐量为代价。Linus电梯调度程序虽然也做了这样的折中，但显然不够—-Linus电梯可以提供更好的系统吞吐量（通过最小化寻址），可是它总按照扇区顺序将请求插入到队列，从不检查驻留时间过长的请求，更不会将请求插入到队列尾部，所以它虽然能让寻址时间最短，但是却会带来同样不可取的请求饥饿问题。为了避免饥饿同时提供良好的全局吞吐量，最后期限I/O调度程序做了更多的努力。既要尽量提高全局吞吐量，又要使请求得到公平处理，这是很困难的。
在最后期限I/O调度程序中，每个请求都有一个超时时间。默认情况下，读请求的超时时间是500ms，写请求的超时时间是5s。最后期限I/O调度请求类似于Linus电梯，也以硬盘物理位置为次序维护请求队列，这个队列称为排序队列。当一个新请求递交给排序队列时，最后期限I/O调度程序在执行合并和插入请求时类似于Linus电梯，但是最后期限I/O调度程序同时也会以请求类型为依据将它们插入到额外队列中。读请求按次序被插入到特定的读FIFO队列中，写请求被插入到特定的写FIFO队列中。虽然普通队列以磁盘扇区为序进行排序，但是这些队列是以FIFO（很有效，以时间为基准排序）形式组织的，结果新队列总是被加入到队列尾部。对于普通操作来说，最后期限I/O调度程序将请求从排序队列的头部取下，再推入到派发队列中，派发队列然后将请求提交给磁盘驱动，从而保证了最小化的请求寻址。
如果在写FIFO队列头，或是在读FIFO队列头的请求超时（也就是，当前时间超过了请求指定的超时时间），那么最后期限I/O调度程序便从FIFO队列中提取请求进行服务。依靠这种方法，最后期限I/O调度程序试图保证不会发生有请求在明显超期的情况下仍不能得到服务的现象，参见下图。

注意，最后期限I/O调度程序并不能严格保证请求的响应时间，但是通常情况下，可以在请求超时或超时前提交和执行，以防止请求饥饿现象的发生。由于读请求给定的超时时间要比写请求短许多，所以最后期限I/O调度程序也确保了写请求不会因为堵塞读请求而使读请求发生饥饿。这种对读操作的照顾确保了读响应时间尽可能短。
最后期限I/O调度程序的实现在文件block/deadline-iosched.c中。

预测I/O调度程序

虽然最后期限I/O调度程序为降低读操作响应时间做了许多工作，但是它同时也降低了系统吞吐量。假设一个系统处于很繁重的写操作期间，每次提交读请求，I/O调度程序都会迅速处理读请求，所以磁盘首先为读操作进行寻址，执行读操作，然后返回再寻址进行写操作，并且对每个读请求都重复这个过程。这种做法对读请求来说是件好事，但是两次寻址操作（一次对读操作定位，一次返回来进行写操作定位）却损害了系统全局吞吐量。预测I/O调度程序的目标就是在保持良好的读响应的同时也能提供良好的全局吞吐量。
预测I/O调度的基础仍然是最后期限I/O调度程序，所以它们有很多相同之处。预测I/O调度程序也实现了三个队列（加上一个派发队列），并为每个请求设置了超时时间，这点与最后期限I/O调度程序一样。预测I/O调度程序最主要的改进是它增加了预测启发能力。
预测I/O调度试图减少在进行I/O操作期间，处理新到的读请求所带来的寻址数量。和最后期限I/O调度程序一样，读请求通常会在超时前得到处理，但是预测I/O调度程序的不同之处在于，请求提交后并不直接返回处理其他请求，而是会有意空闲片刻（实际空闲时间可以设置，默认为6ms）。这几ms，对应用程序来说是个提交其他读请求的好机会—-任何对相邻磁盘位置操作的请求都会立刻得到处理。在等待时间结束后，预测I/O调度程序重新返回原来的位置，继续执行以前剩下的请求。
要注意，如果等待可以减少读请求所带来的向后再向前（back-and-forth）寻址操作，那么完全值得画一些时间来等待更多的请求；如果一个相邻的I/O请求在等待期到来，那么I/O调度程序可以节省两次寻址操作。如果存在愈来愈多的访问同样区域的读请求到来，那么片刻等待无疑会避免大量的寻址操作。
当然，如果没有I/O请求在等待期到来，那么预测I/O调度程序会给系统性能会给系统性能带来轻微的损失，浪费掉几ms。预测I/O调度程序所能带来的优势取决于能否正确预测应用程序和文件系统的行为。这种预测依靠一系列的启发和统计工作。预测I/O调度程序跟踪并且统计每个应用程序块I/O操作的习惯行为，以便正确预测应用程序的未来行为。如果预测准确率足够高，那么预测调度程序便可以大大减少服务读请求所需的寻址开销，而且同时仍能满足请求所需要的系统响应时间要求。这样的话，预测I/O调度程序既减少了读响应时间，又能减少寻址次数和时间，所以说它既缩短了系统响应时间，又提高了系统吞吐量。
预测I/O调度程序的实现在文件内核源代码树的block/as-iosched.c中，它是Linux内核中缺省的I/O调度程序，对大多数工作负荷来说都执行良好，对服务器也是理想的。不过，在某些非常见而又有严格工作负荷的服务器（包括数据库挖掘服务器）上，这个调度程序执行的效果不好。

完全公正的排队I/O调度程序

完全公正的排队I/O调度程序（Complete Fair Queuing，CFQ），是为专有工作负荷设计的，不过，在实际中，也为多种工作负荷提供了良好的性能。但是，它与前面介绍的I/O调度程序有根本的不同。
CFQ I/O调度程序把进入的I/O请求放入特定的队列中，这种队列是根据I/O请求的进程组织的。例如，来自foo进程的I/O请求进入foo队列，而来自bar进程的I/O请求进入bar队列。在每个队列中，刚进入的请求与相邻请求合并在一起，并进行插入分类。队列由此按扇区方式分类，这与其他I/O调度程序队列类似。CFQ I/O调度程序的差异在于每一个提交I/O的进程都有自己的队列。
CFQ I/O调度程序以时间片轮转调度队列，从每个队列中选取请求数（默认值为4，可以进行配置），然后进行下一轮调度。这就在进程级提供了公平，确保每个进程接收公平的磁盘带宽片段。预定的工作负荷是多媒体，在这种多媒体中，这种公平的算法可以得到保证，比如，音频播放器总能够及时从磁盘再填满它的音频缓冲区。不过，实际上，CFQ I/O调度程序在很多场合都能够很好地执行。
完全公正的排队I/O调度程序位于block/cfq-iosched.c。尽管这主要推荐给桌面工作负荷使用，但是，如果没有其他异常情况，它在几乎所有的工作负荷中都能很好地执行。

空操作的I/O调度程序

第四种也是最后一种I/O调度程序是空操作（Noop）I/O调度程序，之所以这样命名是因为它基本上是一个空操作，不管做多少事情。空操作I/O调度程序不进行排序，或者也不进行什么其他形式的预寻址操作。依此类推，它也没必要实现那些老套的算法，也就是在以前的I/O调度程序中看到的为了最小化请求周期而采用的算法。
不过，空操作I/O调度程序忘不了执行合并，这就像它的家务事。当一个新的请求提交到队列时，就把它与任一相邻的请求合并。除了这一操作，空操作I/O调度程序的确不再做什么，只是维护请求队列以近乎FIFO的顺序排列，块设备驱动程序便可以从这种队列中摘取请求。
空操作I/O调度程序不勤奋工作是有道理的。因为它打算用在块设备，那是真正的随机访问设备，比如闪存卡。如果块设备只有一点或没有“寻道”的负担，那么，就没有必要对进入的请求进行插入排序，因此，空操作I/O调度程序是理想的候选者。
空操作I/O调度程序位于block/noop-iosched.c，它是专为随机访问设备而设计的。

I/O调度程序的选择

你现在已经看到2.6内核中四种不同的I/O调度程序。其中的每一种I/O调度程序都可以被启用，并内置在内核中。作为缺省，块设备使用完全公平的I/O调度程序。在启动时，可以通过命令行选项elevator=foo来覆盖缺省，这里foo是一个有效而激活的I/O调度程序，参看下表。
给定elevator选项的参数

参数	I/O调度程序
as	预测
cfq	完全公正的排队
deadline	最终期限
noop	空操作

例如，内核命令行选项elevator=as会启用预测I/O调度程序给所有的块设备，从而覆盖默认的完全公正调度程序。

小结

在本章中，我们讨论了块设备的基本知识，并考察了块I/O所用的数据结构：bio，表示活动的I/O操作；buffer_head，表示块到页的映射；还有请求结构，表示具体的I/O请求。我们追寻了I/O请求简单但重要的生命历程，其生命的重要点就是I/O调度程序。我们讨论了I/O调度程序所涉及的困惑问题，同时仔细推敲了当前内核的4种I/O调度程序，以及2.4版本种原有的Linus电梯调度。