Linux内核设计与实现(15)--块I/O层

系统中能够随机访问（不按顺序）固定大小数据片（chunks）的硬件设备称作块设备。

与字符设备最大区别在于，是否可以随机访问。字符设备按照字节流的方式有序的访问。

由于管理字符设备仅仅需要控制当前位置，而块设备访问的位置必须能够在介质的不同区间前后移动，管理块设备要远比字符设备复杂，并且块设备对执行性能的要求很高，内核专门提供了一个专门的I/O层来管理块设备。

1.块设备

块设备中最小的可寻址单元是扇区，扇区大小一般是2的整数倍，最常见的是512字节，CD-ROM是2KB。扇区的大小是设备的物理属性，扇区是所有块设备的基本单元。

内核的最小逻辑可寻址单元是块，块是文件系统的一种抽象（内核基于块来访问文件系统）。

虽然物理磁盘寻址按扇区进行，但内核执行的所有磁盘操作都是按块进行的。所以块不能小于扇区，只能数倍于扇区大小，但一般不超过一个页大小。

2.缓冲区和缓冲区头

当一个块被调入内存时（读入后或等待写出时），它要存储在一个缓冲区中。每个缓冲区与一个块对应，相当于是磁盘块在内存中的表示。

一个页可以容纳一个或多个内存中的块。

每一个缓冲区，都有一个buffer_head结构体来表示块的相关信息，在 定义，它包含了内核操作缓冲区所需要的全部信息。

此处)折叠或打开

1. struct buffer_head {
2. //缓冲区状态标志
3.     unsigned long b_state;        /* buffer state bitmap (see above) */
4. //页面中的缓冲区
5.     struct buffer_head *b_this_page;/* circular list of page's buffers */
6. //存储缓冲区的页面
7.     struct page *b_page;        /* the page this bh is mapped to */
9. //起始块号
10.     sector_t b_blocknr;        /* start block number */
11. //映像的大小
12.     size_t b_size;            /* size of mapping */
13. //页面内的数据指针
14.     char *b_data;            /* pointer to data within the page */
16. //相关联的块指针
17.     struct block_device *b_bdev;
18. //I/O完成方法
19.     bh_end_io_t *b_end_io;        /* I/O completion */
20. //io完成方法预留
21.      void *b_private;        /* reserved for b_end_io */
22. //相关映射链表
23.     struct list_head b_assoc_buffers; /* associated with another mapping */
24. //相关的地址空间
25.     struct address_space *b_assoc_map;    /* mapping this buffer is
26.                          associated with */
27.     atomic_t b_count;        /* users using this buffer_head */
28. };

b_state 域表示缓冲区的状态，可以是下表中的一种或多种状态的组合：

缓冲区头的目的在于描述磁盘块和物理内存缓冲区之间的映射关系，在操作缓冲区头之前，应该先使用

get_bh() 函数增加缓冲区头的引用计数，确保该缓冲区头不会再被分配出去；当完成对缓冲区头的操作之后，还必须使用 put_bh() 函数减少引用计数。

在2.6内核以前，缓冲区头的作用比现在更重要，而在2.6版本中，许多I/O操作都是通过内核直接对页面或地址空间进行操作来完成，不再使用缓冲区头了。引入了一种新型、灵活并且轻量级的容器，就是bio

3.bio结构体

该结构体代表了正在活动的以片段链表形式组织的块I/O操作。通过用片段来描述缓冲区，即使一个缓冲区分散在内存的多个位置上，bio结构体也能对内核保证I/O操作的执行。这样的向量I/O就是聚散I/O.

此处)折叠或打开

1. /*
2.  * main unit of I/O for the block layer and lower layers (ie drivers and
3.  * stacking drivers)
4.  */
5. struct bio {
6.     sector_t        bi_sector;//磁盘上相关的扇区    /* device address in 512 byte
7.                          sectors */
8.     struct bio        *bi_next;    /* request queue link */
9.     struct block_device    *bi_bdev;//相关的块设备
10.     unsigned long        bi_flags;    /* status, command, etc */
11.     unsigned long        bi_rw;        /* bottom bits READ/WRITE,
12.                          * top bits priority
13.                          */
15.     unsigned short        bi_vcnt;    /* how many bio_vec's */
16.     unsigned short        bi_idx;        /* current index into bvl_vec */
18.     /* Number of segments in this BIO after
19.      * physical address coalescing is performed.
20.      */
21.     unsigned int        bi_phys_segments;
23.     unsigned int        bi_size;    /* residual I/O count */
25.     /*
26.      * To keep track of the max segment size, we account for the
27.      * sizes of the first and last mergeable segments in this bio.
28.      */
29.     unsigned int        bi_seg_front_size;//第一个可合并的段大小
30.     unsigned int        bi_seg_back_size;//最后一个可合并的段大小
32.     unsigned int        bi_max_vecs;    /* max bvl_vecs we can hold */
34.     unsigned int        bi_comp_cpu;    /* completion CPU */
36.     atomic_t        bi_cnt;    //使用计数    /* pin count */
38.     struct bio_vec        *bi_io_vec;    /* the actual vec list */
40.     bio_end_io_t        *bi_end_io;//I/O完成方法
42.     void            *bi_private; //owner的私有方法
43. #if defined(CONFIG_BLK_DEV_INTEGRITY)
44.     struct bio_integrity_payload *bi_integrity; /* data integrity */
45. #endif
47.     bio_destructor_t    *bi_destructor;    /* destructor *///撤销方法
49.     /*
50.      * We can inline a number of vecs at the end of the bio, to avoid
51.      * double allocations for a small number of bio_vecs. This member
52.      * MUST obviously be kept at the very end of the bio.
53.      */
54.     struct bio_vec        bi_inline_vecs[0];//内嵌bio向量
55. };

使用bio结构体的目的主要是代表正在现场执行的I/O操作，所以该结构体中的主要域都是用来管理相关信息的，其中最重要的几个域是bi_io_vecs, bi_vcnt和bi_idx。它们关系如下

3.1 I/O向量

bi_io_vec域指向一个bio_vec结构体数组，该结构体链表包含了一个特定I/O操作所需要使用到的所有片段。每个bio_vec结构都是一个形式为 的向量，它描述了一个特定的片段：片段所在的物理页，块在物理页中的偏移量，从给定偏移量开始的块长度。

Bio_io_vec结构体数组表示了一个完整的缓冲区,bio_vec结构定义在

此处)折叠或打开

1. struct bio_vec {
2.     struct page    *bv_page; //指向这个缓冲区所驻留的物理页
3.     unsigned int    bv_len; //这个缓冲区以字节为单位的大小
4.     unsigned int    bv_offset;//缓冲区所驻留的页中以字节为单位的偏移量
5. };

在每个给定的块I/O操作中，bi_vcnt域用来描述bi_io_vec所指向的vio_vec数组中的向量数目。当块I/O操作执行完毕后，bi_idx域指向数组的当前索引。

总之，每一个块I/O请求都通过一个bio结构体表示，每个请求包含一个或多个块，这些块存储在bio_vec结构体数组中。

3.2新老方法比较

bio结构体代表的是I/O操作，它可以包括内存中的一个或多个页。而buffer_head结构体代表的是一个缓冲区，它描述的仅仅是磁盘中的一个块。

因为缓冲区关联的是单独页中的单独磁盘块，可能会引起不必要的分割，而bio结构体是轻量级的，描述得块可以不需要连续存储区，并且不需要分割I/O操作。

利用bio 结构体代替buffer_head结构体还有以下好处：

bio结构体很容易处理高端内存，因为它处理的是物理页而不是直接指针。

bio 结构体既可以代表普通页I/O，也可以代表直接I/O（指那些不通过页高速缓存的I/O操作）

bio结构体便于执行分散-集中（矢量化）块I/O操作，操作中的数据可取自多个物理页面。

Bio结构体相比缓冲区头属于轻量级的结构体，因为它只需要包含块I/O操作所需的信息就行了，不用包含于缓冲区头本身相关的不必要信息。

Bio结构体仅仅是一个矢量数组，它不包含任何和缓冲区相关的状态信息，它描述一个或多个单独块I/O操作的数据片段和相关信息。内核通过这两种结构分别保存各自信息，可以保证每种结构所含的信息量尽可能地少。

4.请求队列

块设备将它们挂起的块I/O请求保存在请求队列中，该队列由reques_queue结构体表示，包含一个双向请求链表以及相关控制信息。通过文件系统将请求加入到队列中，请求队列只要不为空，队列对应的块设备驱动程序就会从队列头获取请求，然后将其送入对应的块设备上去，请求队列表中的每一项都是一个单独的请求，由reques结构体表示。

队列中的请求由结构体request表示，因为一个请求可能要操作多个连续的磁盘块，所以每个请求可以由多个bio结构体组成。

5.I/O调度程序

磁盘寻址是整个计算机中最慢的操作（定位磁头道特定块上的某个位置，机械操作）之一，所以尽量缩短寻址时间无疑是提高系统性能的关键。

为了优化寻址操作，内核不会简单地暗请求接受次序，也不会立即将其提交给磁盘，相反，它会在提交前，限制性名为合并与排序的预操作，这种预操作极大地提高系统整体性能，在内核中负责提交I/O请求的子系统叫做I/O调度程序。

I/O调度程序与进程调度都是讲一个资源虚拟给多个对象，但他们是不同的：

进程调度程序，是把处理器虚拟给多个运行进程共享；

I/O调度程序，是把块设备虚拟给多个磁盘请求，一遍降低磁盘寻址时间，确保磁盘性能最优化。

5.1 I/O调度程序的工作

I/O调度程序决定队列中的请求排列顺序以及在什么时刻派发请求到块设备。这样有利于减少磁盘寻址时间，从而提高全局吞吐量，I/O调度器提高的是系统整体性能，对个别请求可能不公平。

I/O调度程序通过两种方法减少磁盘寻址时间：合并与排序。

合并，是指当有多个请求，访问的磁盘扇区是相邻的，那么把它们合并为一次请求，请求合并后只需要传递给磁盘一条寻址命令，就可以访问合并前必须多次寻址才能访问完的磁盘区域。因此合并请求能减少系统开销和磁盘寻址次数。

排序：把所有的请求队列按扇区增长方向有序排列，这样可以缩短单独一次请求的寻址时间，更重要的优化是，通过保持磁头以直线方向移动，缩短了所有请求的磁盘寻址时间。该排序算法类似于电梯调度（向一个方向运动，当抵达了同一方向最后一层后，再掉头向另一方向）。

5.2 Linus电梯

Linux电梯是2.4版本内核默认的I/O调度程序，在2.6中被另外两种调度程序取代，但由于它比后来的调度程序简单，且它们执行的许多功能都相似，所以当作一个优秀的入门介绍程序。

Linus电梯能执行合并与排序预处理。当有新的请求加入队列时，首先会检查它是否可以和其他挂起的请求合并，Linus电梯可以执行向前和向后合并，鉴于文件的分布(以扇区号的增长表现)和I/O操作执行方法具有典型性（从头读到尾），所以向前合并相比向后合并要少得多，但Linus电梯对两种合并类型都进行检查。

如何合并尝试失败，那么就需要寻找可能的插入点，如果找到，新请求插入到该点；如果没有合适位置，那么新请求被加入队列尾（保持整个队列有序性）。

另外，如果发现队列中有驻留时间过长的请求，那么新请求也将被加入到队列尾部，即使插入后还要排序。但是，这种“年龄”检测方法不是很有效，因为它并非是给等待了一段时间的请求提供实质**，仅仅是在经过了一定时间后停止插入-排序请求，这改善了等待时间但最终还是会导致请求饥饿现象出现，所以这是2.4内核I/O调度必须要修改的缺陷。

总之，当一个请求加入队列是，可能发生四种操作之一：

（1）如果队列中已存在一个相邻磁盘扇区操作的请求，那么新请求将和这个已存的请求合并；

（2）如果队列中存在一个驻留时间过长的请求，那么新请求将被插入到队列尾部，以防止其他旧的请求饥饿发生；

（3）如果队列中以扇区方向为有序存在合适的插入位置，那新请求就会被插入该位置；

（4）如果队列中不存在合适的请求插入位置，请求将被插入队尾；

5.3 最终期限I/O调度程序

第一个问题，Linus电梯会导致饥饿现象；

第二个问题，写-饥饿-读问题；

写操作通常是在内核有空时才提交给磁盘，所以写操作与应用程序是异步的；而读操作，当应用程序提交一个读请求时，应用程序会发生堵塞知道读请求被满足，也就是说读操作是和提交它的应用程序同步执行的。所以读操作响应时间对系统的性能非常重要。并且读请求往往相互依赖，如果每一次请求都发生饥饿现象，那么对读取文件的应用程序来说，过长的延迟是无法忍受的。

减少饥饿必须以降低全局吞吐量为代价，既要尽量提高全局吞吐量，又要使请求得到公平处理，这是很困难的。

在最后期限I/O调度程序中，每个请求都有一个超时时间，默认情况下，读请求超时时间500ms, 写请求超时时间5s.

最后期限I/O调度程序，维护四个队列：类似Linus电梯调度，也以磁盘物理位置为次序维护请求队列，即排序队列。但同时也会以请求类型为依据将它们插入到额外队列中，读请求按次序被插入特定读FIFO队列中，写请求插入到特定的写FIFO队列中。排序队列是以扇区号为序排列，而读/写FIFO是以时间为序。

对于普通操作，deadline将请求从排序队列的头部取出，再推入到派发队列中，派发队列将请求提交给磁盘驱动，从而保证最小化的请求寻址。

如果读/写FIFO头的请求超时，那么deadline就从该FIFO队列中提取请求进行服务。

四个队列关系如下图

Deadline并不能严格保证请求的响应时间，但是可以防止饥饿现象的发生。

Deadline在block/deadline-ioshced.c中实现。

5.4 预测I/O调度程序(anticipatory,as)

deadline降低了读操作响应时间，但是同时也降低了系统吞吐量。假设一个系统处于很繁重的写操作期间，每次提交读请求，I/O调度程序都会迅速处理读请求，所以磁盘首先为读请求寻址，执行完读操作，再返回寻址进行写操作，这降低了读请求的响应时间，但是损害了系统全局吞吐量。As的目标是保持良好读响应的同时也能提高良好全局吞吐量。

as 与deadline一样维持4个队列，as最主要的改进是增加了预测启发能力。

as 试图减少在进行I/O操作期间，处理新到的读请求所带来的寻址数量。与deadline不同的是，在新的读请求提交后不直接返回处理其他请求，而是会有意空闲片刻（默认6ms），在这个时间内，任何对相邻磁盘位置的操作请求都会立刻得到处理。在等待时间结束后，as返回原来位置，继续执行以前剩下的请求。如果没有I/O请求在等待期到来，as会浪费掉几ms, 但是在有多个访问同样区域的读请求到来时，片刻等待会避免大量的寻址操作。

as 所能带来的优势取决于正确预测应用程序和文件系统的行为，as跟踪并且统计每个应用程序块I/O操作的习惯行为，以便正确预测应用程序的未来行为。预测准确率高，那么可以大大减少服务请求所需的寻址开销，而且同时仍能满足请求所需要的系统响应时间要求。

as在block/as-iosched.c实现，是Linux内核缺省的I/O调度程序。对大多数工作负荷来说都执行良好，对服务器也是理想的，不过在某些非常见而又有严格工作负荷的服务器（比如数据库挖掘服务器）上，效果不好。

5.5 完全公正的排队I/O调度程序（Complete Fair Queuing，CFQ）

CFQ是为专有工作负荷设计的。

CFQ把I/O请求放入特定的队列中，这种队列是根据引起I/O请求的进程组织的，每个队列，把刚进入的请求进行插入合并，这与其他I/O调度程序类似，不同在于每个提交I/O的进程都有自己的队列。

CFQ以时间片轮转调度队列，从每个队列中选取请求数(默认是4，可配置)进行处理，然后进行下一轮调度，这样就在进程级，确保了每个进程接受公平的磁盘带宽片段。

尽管CFQ主要推荐给桌面工作负荷使用，但如果没其他异常情况，它几乎所有的工作负荷都能很好地执行。在block/cfq-iosched.c定义。

5.6 空操作的I/O调度程序

当一个新请求提交到队列时，Noop把它与任一相邻的请求合并，除了这个，noop啥都不干，这就维持队列以近乎FIFO的顺序排列，块设备驱动程序可以从这种队列中摘取请求。

Noop适用于真正的随机访问设备（比如闪存卡），这种块设备没有“寻道”负担，那就没必要进行插入排序，因此noop是理想的候选者。

Noop在block/noop-iosched.c定义，专为随机访问设备而设计的。

5.7 I/O调度程序的选择

2.6内核中有四种不同I/O调度程序，每一种都可以在内核配置启用，缺省使用as.在启动时也可以通过elevator=xxx来覆盖缺省，xxx是一个有效而激活的I/O调度程序

PS:关于Linus电梯算法产生饥饿的原因

LKD3中说当新请求产生时，会检查驻留时间过长请求，一旦发现就会把新请求插入队尾；若当真如此，饥饿又会如何产生呢？

在最终期限I/O调度程序一部分，又提到由于Linus电梯会产生饥饿现象，所以在其基础上改进，添加了请求等待超时处理，才在提高请求响应的同时避免饥饿现象。

这两个说法似乎有点矛盾了，翻了下原版书，中文版几乎是直译的;

google了一把，也没看到合理详细的解释 ，最后没办法，下linux2.4.10版源码，其中新请求处理部分代码如下（片段）
ll_rw_blk.c-->__make_rquest()函数里

此处)折叠或打开

1. el_ret = elevator->elevator_merge_fn(q, &req, head, bh, rw,max_sectors);
2. switch (el_ret) {
4. case ELEVATOR_BACK_MERGE:
5. if (!q->back_merge_fn(q, req, bh, max_segments))
6. break;
7. ->elevator_merge_cleanup_fn(q, req, count);
8. ->bhtail->b_reqnext = bh;
9. ->bhtail = bh;
10. ->nr_sectors = req->hard_nr_sectors += count;
11. (count);
12. (req->rq_dev, req->cmd, count, 0);
13. (q, req, max_sectors, max_segments);
14. goto out;
16. case ELEVATOR_FRONT_MERGE:
17. if (!q->front_merge_fn(q, req, bh, max_segments))
18. break;
19. ->elevator_merge_cleanup_fn(q, req, count);
20. ->b_reqnext = req->bh;
21. ->bh = bh;
22. ->buffer = bh->b_data;
23. ->current_nr_sectors = count;
24. ->sector = req->hard_sector = sector;
25. ->nr_sectors = req->hard_nr_sectors += count;
26. (count);
27. (req->rq_dev, req->cmd, count, 0);
28. (q, head, req, max_sectors, max_segments);
29. goto out;
31. /*
32.          * elevator says don't/can't merge. get new request
33.          */
34. case ELEVATOR_NO_MERGE:
35. /*
36.              * use elevator hints as to where to insert the
37.              * request. if no hints, just add it to the back
38.              * of the queue
39.              */
40. if (req)
41. = &req->queue;
42. break;
44. default:
45. ("elevator returned crap (%d)\n", el_ret);
46. ();
47. }

从以上代码可知，Linus电梯压根就没做时间检测，新请求找到插入点，就插入；没找到，直接放到队尾。所以，产生饥饿是必然现象了。