Linux内核学习笔记（三）Block I/O层
块设备（Block Device）简介
块设备是一种以块（block）为单位可以进行随机存取的硬件设备。常见的块设备有硬盘，软盘，闪存等。
块设备的最小寻址单元是扇区（sector），一个扇区是2\^n个字节，512Bytes是最常见的扇区大小。内核的文件系统使用块（block）作为最小寻址单元。block的大小是sector的2\^n次方倍（n可以为0），但是不大于page size. 常见的block大小为512Bytes，1KB，4KB。
buffer 与 buffer_head结构体
当一个block被读入内存或者等待写入块设备时，保存在buffer中，一个buffer对应一个block。每个buffer都有一个对应的描述符，这个描述符被称为buffer head，使用buffer_head结构体来表示（定义在<linux/buffer_head.h>中），buffer_head结构体的唯一角色是作为buffer-to-block映射关系的描述符，该结构体保存了内核对buffer进行操作需要的所有信息。
下面是buffer的定义：
struct buffer_head
{
unsigned long b_state; /* buffer state flags */
struct buffer_head *b_this_page; /* list of page’s buffers */
struct page *b_page; /* associated page */
sector_t b_blocknr; /* starting block number */
size_t b_size; /* size of mapping */
char *b_data; /* pointer to data within the page */
struct block_device *b_bdev; /* associated block device */
bh_end_io_t *b_end_io; /* I/O completion */
void *b_private; /* reserved for b_end_io */
struct list_head b_assoc_buffers; /* associated mappings */
struct address_space *b_assoc_map; /* associated address space */
atomic_t b_count; /* use count */
};
b_state用于表示buffer的状态，如是否dirty，是否正在进行一个IO操作等。
b_count是buffer的使用计数，调用get_bh() 和put_bh()分别会增加和减少计数。
b_bdev指向buffer对应的block所在的块设备对象。
b_page指向buffer所在的page（物理page）。
b_data直接指向block所在位置（在b_page中的某个位置），b_size表示block的大小。该block起始于b_data,终止于b_data + b_size。
bio结构体
bio结构体的主要作用是表示一个正在进行的块I/O操作，bio结构体定义在<linux/bio.h>中
struct bio {
sector_t bi_sector; /* associated sector on disk */
struct bio *bi_next; /* list of requests */
struct block_device *bi_bdev; /* associated block device */
unsigned long bi_flags; /* status and command flags */
unsigned long bi_rw; /* read or write? */
unsigned short bi_vcnt; /* number of bio_vecs off */
unsigned short bi_idx; /* current index in bi_io_vec */
unsigned short bi_phys_segments; /* number of segments */
unsigned int bi_size; /* I/O count */
unsigned int bi_seg_front_size; /* size of first segment */
unsigned int bi_seg_back_size; /* size of last segment */
unsigned int bi_max_vecs; /* maximum bio_vecs possible */
unsigned int bi_comp_cpu; /* completion CPU */
atomic_t bi_cnt; /* usage counter */
struct bio_vec *bi_io_vec; /* bio_vec list */
bio_end_io_t *bi_end_io; /* I/O completion method */
void *bi_private; /* owner-private method */
bio_destructor_t *bi_destructor; /* destructor method */
struct bio_vec bi_inline_vecs[0]; /* inline bio vectors */
};
其中最重要的域是bi_io_vec，bi_vcnt，bi_idx;
- bi_io_vec是一个指针，指向一个bio_vec数组，每个bio_vec结构体对应一个segment，一个segment由一个或者多个物理上连续的buffer组成。
- bi_vcnt是bi_io_vec数组的长度
- bi_idx是当前正在进行I/O操作bio_vec对象的索引。
bi_io_vec数组使得bio结构体可以支持在一次I/O操作中，使用多个在内存中不连续的segment，这个又叫做 scatter-gather I/O。
bio_vec定义在<linux/bio.h>中：
struct bio_vec {
struct page *bv_page; //向segment所在的物理page
unsigned int bv_len; //segment的大小（字节）
unsigned int bv_offset;//segment起始点在page中的偏移量。
};
请求队列（Request Queue）
上层（如文件系统）发起I/O请求，这个请求在内核中使用struct request来表示。内核使用struct request_queue将多个请求存储到一起，该结构体包含相关的控制信息和一个存储request对象的双向链表。一个request可以包含一个或者多个bio对象。虽然segment之间可以在内存中不连续（即使是一个bio中的segment之间也可以不连续），但是一个request需要访问的磁盘block在磁盘上必须是连续的。
struct request中存储的双向链表又被称为为dispatch queue，该队列的顺序就是设备驱动处理请求的顺序（下一个被驱动发送给设备控制器的I/O请求总是dispatch queue的队首，即第一个请求），
I/O调度器
如果直接按照内核发起I/O请求的顺序将这些请求发送给块设备，性能是很糟糕的。主要原因是磁盘每次处理一个请求时需要先seek到对应的位置，然后再进行传输。seek是非常耗时的，所以需要对I/O请求进行调度，从而减少seek次数，提高性能。内核中负责该功能的子系统叫做I/O调度器。
I/O调度器通过对I/O请求进行合并与排序来调度，不同的I/O调度算法使用的具体策略是不同的。
- 合并：新加入请求时，如果发现队列中已有请求的目标blocks与新加入的请求的目标blocks是相邻的，就将他们合并为一个I/O请求。
- 排序：队列按照请求对应的sector进行排序，目标是使得当磁盘按顺序处理队列中的请求时，可以沿着一个方向进行seek操作，不用不断地来回seek，这样可以大幅度减少每次seek的时间开销。这个很像电梯的工作方式，所以调度器又被称为电梯（elevator）。
调度器需要自己维护额外的请求队列，从而对请求进行合并和排序。并根据自己的策略选择下一个要服务的请求加入dispatch queue中。
Linus Elevator
Linux Elevator的工作方式是当一个新的请求到来时，如果能和已有的请求合并，那么进行合并。
如果不能合并，就将新的请求插入队列中使得队列有序（按照sector决定顺序）。如果在队列中没有合适的位置，就插入到队列的尾部。此外，如果队列中的一个请求太老了（超过了threshold），那么新的请求直接放到队列尾部，即使这个请求可以插入到队列中。从而避免一个请求长时间得不到响应，但是这个方法并不能有效的解决这种情况。这个调度器是2.4版本内核的默认调度器，现在已经基本不用了。
Deadline I/O调度器
Deadline I/O调度器在Linux Elevator的基础上，加入了两个FIFO队列，一个是read FIFO队列，一个是write FIFO队列。一个新的请求加入时，不仅按按照Linux Elevator的方式加入有序队列，同时根据请求的类型，将其加入其中一个FIFO队列。每次选择请求交给dispatch queue时，先检查read FIFO队列和write FIFO队列的队首，判断队首的请求等待时间是否超时，如果超时就选择在队首的超时请求，如果队首没有超时，那么选择有序队列的第一个请求。read请求的超时时间默认为500ms，write请求的超时时间默认为5s，这样规定是因为read一般是同步的（进程会阻塞），所以对时间很敏感。而write一般是异步的（进程只需要将数据写入buffer，不需要等待buffer真正写入磁盘中），对时间不敏感。所以设定的read的超时时间远远小于write的超时时间。Deadline I/O调度器通过牺牲少量全局吞吐量来保证不会出现请求饥饿（request starvation）的情况。
Anticipatory I/O调度器
Anticipatory I/O调度器在Deadline调度器的基础上加入了一个新的特性：anticipation heuristic。这个新的特性是为了避免出现磁盘不断地来回seek的情况。 在选择一个请求加入dispatch queue后，调度器不会马上去从队列中选择下一个请求，而是等待一段时间（默认为6ms），这段时间很可能会收到和刚刚的read请求的block相邻的read请求（这个一般是因为同一个进程在连续地读），这个请求就会被立刻加入dispatch queue。如果等待期间没有收到这样read请求，Anticipatory I/O调度器会按照Deadline的策略从队列中取出下一个请求进行。
Complete Fair Queueing I/O调度器（完全公平调度器）
CFQ调度器和前面的三个调度器差别很大，它为每个进程都维护一个I/O请求队列，每个进程的队列都各自进行合并和排序。调度器会使用时间片轮转的方式的方式每次从不为空的队列中取出一定数量的请求（默认是4个）。通过这种方式保证了进程级别的公平，确保每个进程都能获得公平的磁盘带宽分配。
Noop I/O调度器
Noop调度器只对请求队列进行合并操作，不会进行排序。每次选择队首的请求加入dispatch queue中。这种调度方式非常适合不需要进行seek操作的存储介质，比如闪存等。
IO调度器的选择
目前主流Linux发行版本使用三种I/O调度器：DeadLine、CFQ、Noop，通常来说Deadline适用于大多数环境,特别是写入较多的文件服务器，从原理上看，DeadLine是一种以提高机械硬盘吞吐量为思考出发点的调度算法，尽量保证在有I/O请求达到最终期限的时候进行调度，非常适合业务比较单一并且I/O压力比较重的业务，比如Web服务器，数据库应用等。CFQ 为所有进程分配等量的带宽,适用于有大量进程的多用户系统，CFQ是一种比较通用的调度算法，它是一种以进程为出发点考虑的调度算法，保证大家尽量公平,为所有进程分配等量的带宽,适合于桌面多任务及多媒体应用。Noop适合采用SSD（闪存的一种）等存储介质（不需要进行seek操作）的系统。
参考资料
《Linux Kernel Development 3rd Edition》
《Understanding The Linux Kernel 3rd Edition》