一 块I/O基本概念
字符设备：按照字符流的方式被有序访问的设备。如串口、键盘等。
块设备：系统中不能随机（不需要按顺序）访问固定大小的数据片（chunk 块）的设备。
如：硬盘、软盘、CD-ROM驱动器、闪存等。都是通过以安装文件系统的方式使用。
块设备的组成：
扇区：是块设备中最小的可寻址单元（常见大小512字节）；是块设备的基本寻址和操作单元。
块：是文件系统最小逻辑可寻址单元，文件系统的抽象，只能通过块访问文件系统。通常包含多个扇区。
当一个块被调入内存时（读入后或等待写出时），它要存储在一个缓冲区中；每个缓冲区与一个块对应，
缓冲区相当于是磁盘块在内存中的表示；块大小不超过一个页面，一个页可以容纳一个或多个内存中的块。
缓冲区：是内核操作块设备的逻辑单元，每个缓冲区需要一个描述符来表示块的控相关制信息。
数据结构：缓冲区头 buffer_head，内核操作I/O块基本容器是：bio。操作内核中所有的缓冲区对应的I/O块。
请求队列：块设备将他们挂起的块I/O请求保存在请求队列中。
二 I/O调度机制
简单的以内核产生I/O请求的次序直接将请求发向块设备，造成性能将难以接受。因为磁盘寻址是整个计算机中
最慢的操作之一，每一次寻址定位硬盘磁头到特定块上某个位置需要花费不少时间；要提高I/O操作性能，尽量缩短磁盘寻址时间。
在提交请求到块设备前，内核需要对请求进行处理：先执行合并与排序的预操作——I/O调度机制子系统，负责I/O请求的提交。
I/O调度程序管理块设备的请求队列，决定队列中的请求排列顺序，何时派发请求到设备。以减少磁盘寻址时间，提高全局吞吐量。
其实现的方法是合并与排序：
合并：将两个或多个请求结合成一个新的请求，比如访问磁盘扇区相邻时，合并为一个对单个和多个相邻磁盘扇区操作的新请求。
合并后仅需要一次请求一条寻址命令。
排序：没有相邻操作扇区请求时，但可能是比较接近的；将整个请求队列按扇区增长方向有序排列，操作时保持磁头以直线一个
方向移动，缩短请求磁盘寻址时间。
三 调度程序实现
1 Linus Elevator
当一个请求加入到队列时：
如果队列已存在一个对相邻磁盘扇区操作的请求，将新请求和这个已存在的请求合并成一个请求。
如果队列中存在一个驻留时间过长的请求，将新请求插入到队列尾部，防止请求发生饥饿。
如果队列中以扇区方向为序存在合适插入位置，将新请求插入到该位置，与被访问磁盘物理位置为序排列。
如果队列不存在合适位置插入，将请求插入到队列尾部。
2 最终期限I/O调度程序
Linus Elevator调度程序存在使请求发生饥饿的情况：
l 对某个磁盘区域繁重操作，使得磁盘其他位置上的操作请求得不到运行；
l 同一位置顺序上的请求流可以造成较远位置请求得不到运行；
l 写操作和提交应用程序是异步执行，读操作和提交应用程序是同步执行会阻塞，读操作响应时间影响性能。
要在提高全局吞吐量和使请求得到公平处理之间进行平衡。
最终期限I/O调度程序中：每个请求都有一个超时时间，读请求默认500毫秒，写请求5秒。
提交请求时：
一个请求递交给排序队列，按照合并和排序插入队列；
将读请求按次序插入到读FIFO队列中；
将写请求按次序插入到写FIFO队列中；
派发请求时：
通常从排序队列中取队首请求加入到派发队列中；
如果写FIFO队列首或读FIFO队列首请求超时，调度程序从FIFO队列中提取队首请求加入到派发队列中。
如下图所示：
此方式能尽量保证：
请求超时前得到执行，防止请求发生饥饿；
读请求超时时间比写请求短很多，保证写请求不会因为堵塞读请求而使读请求发生饥饿。
3 预测I/O调度程序
最终期限调度程序降低请求发生饥饿的概率，同时降低了系统吞吐量。预测I/O调度程序的目标就是在保持
良好读响应同时提供良好的全局吞吐量。
预测I/O调度程序与最终期限调度程序不同之处：请求提交后并不直接放回处理其他请求，而是会空闲片刻（6毫秒），
使应用程序有提交其他请求的机会——任何对相邻磁盘位置的操作请求都会立刻得到处理，等待结束后，预测I/O调度程序
重新返回原来的位置，继续执行以前的剩下请求。
预测I/O调度程序所能带来的优势取决于能否正确预测应用程序和文件系统的行为，需要启发和统计工作，预测准确能够
减少寻址开销，提高系统响应，提高吞吐量。
还有其他调度程序：完全公正的排队I/O调度程序（每个进程独立I/O请求队列）和空操作I/O调度程序（相邻合并）
要在提高全局吞吐量和使请求得到公平处理之间进行平衡。
系统调度程序再启动时可以进行配置。