如果硬件设备是以数据流的方式访问的，它就是字符设备（character device），但如果是随机访问的就是块设备（block device），典型的如硬盘
sector（扇区）
The smallest addressable unit on a block device is a sector. Sectors come in various powers of two, but 512 bytes is the most common size
块设备上最小访问单元是扇区（sector），一般512字节大小
虽然最小物理访问单元是扇区，但是软件的最小逻辑访问单元是块（block），它是扇区大小的2的幂次方倍，一般为512 bytes, 1 kilobyte, and 4 kilobytes，但不会超过页大小（人为限制），那是管理内存的最小单位。
block（块）
文件系统都是以块为单位来操作磁盘的，CPU是不能直接操作磁盘上的数据，必须先把它们读到内存中，那么内存中存储一块大小的数据叫做buffer，buffer就是磁盘上一块大小的数据在内存中表示，那这个buffer对应哪个块设备上的哪块就需要内核来管理，内核使用buffer_head这个数据结构来描述block和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 */
};
在2.6之前，buffer_header在内核中得以重用，它是块设备IO的单位和容器,但这个结构有点大，用它来操作数据既不简洁也不简单，内核更擅长用页来处理，这样既简单又高效；另一方面buffer_header只能描述单个buffer，如果要操作大块数据势必要分成多个buffer_header，导致无谓的开销。于是在2.5版本就重点开发了bio结构作为block I/O操作的容器
bio结构
bio数据结构以段的形式将buffers组织在一起，这些buffers在内存中不必是连续的
struct bio {
...
unsigned short bi_vcnt;/* number of bio_vec */
struct bio_vec *bi_io_vec; /* bio_vec list */
...
}
bio结构体含有bio_vec数组，图上它们指向某个page，但并不表示指向整个page，而是其中一段，每个 bio_vec 就是这样一个三元组（page, offset, len）, 哪块物理页，偏移多少字节、长度多少就定位了一块buffer
struct bio_vec {
struct page *bv_page;/* pointer to the physical page on which this buffer resides */
unsigned int bv_len;/* the length in bytes of this buffer */
unsigned int bv_offset;/* the byte offset within the page where the buffer resides */
};
bio结构体的优点
- 可以轻松表示高内存，因为它只处理物理页而不是指针
- 既能表示普通page I/O也能表示direct I/O（不需要页缓存）
- 很容易实现scatter-gatter I/O 块操作
- 相比buffer_header,仅包含I/O 块操作的最小信息，不会包含与buffer无关的信息
但bio并不能替代buffer_header,它不能描述buffer的状态，所以需要两者共存互补。
IO调度器
一个运行的系统，每时每刻都会有不同的进程发起IO请求，这些请求都会放在一个请求队列中，用 <linux/blkdev.h>中的request_queue结构体表示，队列中的每个请求用request结构体表示，它是由多个bio结构体组成。
计算机中的硬盘是为数不多的机械装置，它读写数据的速度与内存相比都是上万倍的差距，由于是机械装置，磁头对扇区的寻址是计算机中最慢的操作之一，如果对IO请求逐个处理不做全局优化，计算机的性能将显著降低，比如下面一个请求队列
- 骑自行车到北京买包中南海
- 骑自行车到上海买包华子
- 骑自行车到北京买一条中南海
- 骑自行车到上海买一条华子
所以IO调度器的一个重点就是全局考虑队列的请求，优化寻址时间。
The Linus Elevator
Linux中的最简单的调度算法就是电梯调度算法，主要有四点
- If a request to an adjacent on-disk sector is in the queue, the existing request and the new request merge into a single request.如果IO请求的扇区和能在队列中找到毗邻的，合并成一个
- If a request in the queue is sufficiently old, the new request is inserted at the tail of the queue to prevent starvation of the other, older, requests.如果第一步找到的请求存在的时间有点久远会放弃合并插到队尾，否则对同一位置的频繁请求会导致后面的请求无法响应
- If a suitable location sector-wise is in the queue, the new request is inserted there. This keeps the queue sorted by physical location on disk.调度算法会按照请求的扇区对请求排序，根据新请求扇区的位置将其插入到队列中合适的位置，这样队列中请求的扇区物理位置是有序的，磁头像电梯一样一次只朝一个方向移动处理请求，避免来回无序的寻址。
- Finally, if no such suitable insertion point exists, the request is inserted at the tail of the queue.最后如果找不到合适位置就会插在队尾
The Deadline(截止日期) I/O Scheduler
电梯调度算法虽然顾全大局，能极有效的处理磁头移动，但仍然没解决请求饿死的问题，首先说说数据的读或写的特征，实际上它们截然不同
进程是不可以直接将数据写到磁盘的，进程只是把写请求和相关数据等信息提交到内核，然后就返回了，是异步的，内核为了性能也不会立马将数据写回磁盘，它有一个专门的进程周期性的将缓存的数据一起写回磁盘，所以通常是较大的数据流，这些写入请求倾向于写到磁盘相近的地方，很符合电梯调度算法的胃口，导致这个算法倾向于满头苦写无法自拔
进程也是不能直接读取磁盘上的数据，它要发起读请求，让内核去捞数据，但它可不会像写那样就返回了，它要等内核给它数据才会返回，所以读操作是同步的，对等待时长很敏感。与写相比，读的数据通常较小而且不连续，比如目录下的文件，有碎片化的特征，更要命的是还不能同时进行，这个没返回是不能读下一个的，有依赖关系。
由于读写的这种矛盾，流式写请求容易让后面的读请求在合理的时间内得不到处理，而产生写饿死读的问题，比如下面一个请求队列
- 骑自行车到北京大兴送货
- 骑自行车到北京丰台送货
- 骑自行车到北京石景山送货
- 骑自行车到北京海淀买送货
- 骑自行车到北京朝阳送货
- 骑自行车到北京东城送货
- 骑自行车到上海买包华子
Deadline调度器在电梯调度器的Sorted queue基础上添加了两个先入先出队列，并且每个新请求会设置一个有效期(expiration time), 读请求是500ms，写请求是5s，新请求不仅会正常插入到Sorted queue，还会添加到另一个队列的尾部（如：读请求到Read FIFO queue），调度器处理请求和以前一样，从Sorted queue获取请求，但如果Read队列或Write队列的队头请求要到期了就需要优先处理，也就是读队列的请求最久500ms左右能被处理，而写队列是5s，本质上就是让读请求的优先级高于写请求，从而避免写饿死读的情况发生。
Anticipatory(预料的) I/O Scheduler
Deadline调度器在性能和延时两端做了相当好的平衡，但读请求碎片化、独立性、需同步的特性使得磁头难免不断的来回移动，付出昂贵的代价。比如正在处理一堆写请求流，间歇的来了一波读请求(进程在一个读请求结束后才会发起下一个读请求)，如果两种请求涉及的扇区较远，那么就有大量时间花费在来回移动磁头上面。
Anticipatory就是为了解决这个问题，它在Deadline调度器的基础上添加了预判机制，在处理完读请求后并不着急离开，而是赌一把等上6ms，看这个时间内能不能等到下个读请求，如果等到了就立马处理然后继续等待，否则承认猜错了移动磁头返回原处。为了提高命中率而不是瞎猜，Anticipatory调度器会统计每个进程的IO信息来跟踪它们的行为，从而做出智能预判。
以上整理自：
Linux kernel Development - Robert Love
I/O Schedulers
