I/O子系统
为了满足各种要求，计算机的输入/输出设备种类繁多，功能繁杂，速度不一。操作系统通过I/O子系统对I/O设备进行有效的管理。
计算机的输入设备为信息进入计算机的设备，如键盘，鼠标等，输出设备将计算结果展示给用户，如显示器、打印机、喇叭等。输入/输出设备为计算机与外部交换信息的通道。I/O设备种类繁多，其中各设备速度差距悬殊。操作系统通过I/O子系统来管理I/O设备。
常见设备I/O特征
常见的接口分为三类，字符设备、块设备和网络设备，访问特征均不一样。
| 设备接口类型 | 例子 | 访问特征 | I/O命令 |
|---|---|---|---|
| 字符设备 | 键盘、鼠标、串口 | 以字节为单位顺序访问 | 文件访问接口 |
| 块设备 | 磁盘驱动器、磁带驱动器、光驱 | 均匀的数据块访问 | 文件系统接口、内存映射 |
| 网络设备 | 以太网、无线、蓝牙 | 格式化报文交换 | 网络报文、网络协议 |
进程I/O操作方式
从进程的角度来看，I/O方式分为三种
| I/O类型 | 特点 | 读写方法 |
|---|---|---|
| 阻塞I/O | Wait | 读写时，进程将进入等待状态，直到设备完成数据处理 |
| 非阻塞I/O | Don’t Wait | 读写时立即从read或write系统调用返回，返回值为成功传输字节数；可能不成功 |
| 异步I/O | Tell Me Later | 读写数据时，使用指针标记好用户缓冲区，立即返回；稍后内核将填充缓冲区/处理数据并通知用户 |
其中阻塞I/O和非阻塞I/O均为同步I/O，这三种I/O操作方式区别主要在于继承发出操作命令后，进程是否等待；操作结果反馈方式。
阻塞I/O
非阻塞I/O
- 可能读写不成功，或不一致
异步I/O
CPU和设备之间的I/O方式
连接方式
CPU与设备的通信方式：轮询设备、中断和DMA(DMA同时也为传输方式)
设备控制器为CPU和I/O设备间的接口，向CPU提供特殊指令和寄存器，也就是CPU用来控制I/O设备的I/O地址，分为两种：
I/O指令：通过I/O端口号访问设备寄存器
- 特殊的CPU指令
out 0x21,AL
内存映射I/O：设备的寄存器/存储空间被映射到内存物理地址空间中，通过内存load/store指令完成I/O操作
- MMU设置映射，硬件跳线或程序在启动时设置地址
内核I/O结构
I/O请求生命周期(异步I/O)
中断控制中，CPU和外部设备并行工作。
传输方式
CPU与设备控制器之间的数据传输分为两种方式：
程序控制I/O（PIO，Programmed I/O）
通过CPU的in/out或者load/store传输所有数据（内存映射）或者memory读写方式，即把device的寄存器，内存等映射到物理内存中；
特点：
- 硬件简单，编程容易
- 消耗的CPU时间和数据量成正比
适用于简单的、小型的设备I/O
直接内存访问（DMA）
- 设备控制器可直接访问系统总线
- 控制器直接与内存互相传输数据
- 特点：
- 设备传输数据不影响CPU
- 需要CPU参与设置
- 适用于高吞吐量I/O
通过DMA读取磁盘数据例子
具体步骤：
- 设备驱动收到读取磁盘数据到内存地址X的请求
- 设备驱动控制磁盘控制器从磁盘读取数据
- 磁盘控制器初始化DMA传送
- 磁盘控制器传送数据到DMA控制器
- DMA控制器传送C字节数据到内存地址X
- DMA控制器完成数据传送后，产生中断请求，通知CPU传送完成
通知方式
操作系统需要了解设备的状态，比如I/O完成时间，I/O操作遇到的错误。
设备通知CPU(I/O操作完成时间、I/O操作是否发生错误、设备状态等)有两种方式：
- CPU主动轮询
- 设备中断
轮询
处理流程：
- I/O设备在特定的状态寄存器中放置状态和错误信息
- 操作系统定期检测状态寄存器
特点：
- 简单
- I/O操作频繁或不可预测时，开销大和延时长
设备中断
处理流程：
- CPU在I/O之前设置任务参数
- CPU在发出I/O请求后，继续执行其他任务
- I/O设备处理I/O请求
- I/O设备处理完成时，触发CPU中断请求
- CPU接收中断，分发到相应中断处理例程
特点：
- 处理不可预测事件效果好
- 开销相对较高
计算机组成原理中按照控制方式将I/O方式分为
程序直接控制 CPU直接使用输入/输出指令来控制外部设备
程序中断 外部设备请求，CPU响应，CPU和外设并行工作
直接存储访问 专用输入/输出存储器
通道
字节多路通道 简单的共享通道，分时处理，面向低、中速字符设备
选择通道 选择一台外设独占整个通道，以成组方式传送数据块，效率高，适合快速设备
数组多路通道 以上两种方式的结合，效率高，控制复杂
外围处理机
磁盘
磁盘的工作机制和传输时间
磁盘I/O传输一般分为以下5个步骤：
- 等待设备可用
- 等待通道（PIO或DMA通道）可用
- 寻道
- 旋转延迟
- 数据传输
后四个步骤称为设备忙状态，所占用的时间为传输时间。
在磁盘I/O传输时间中，着重优化寻道时间。
磁盘调度算法
目的：通过优化磁盘访问请求顺序来提高磁盘访问性能
进行磁盘调度的原因：
- 寻道时间是磁盘访问最耗时的部分
- 同时会有多个在同一磁盘上的I/O请求（所以可以调整顺序）
- 随机处理磁盘访问请求的性能表现很差
下列算法中使用的例子：
- 磁盘访问序列：
98, 183, 37, 122, 14, 124, 65, 67 - 初始磁头位置：
53
| 算法 | 处理方式 | 特征 | 例子 | 移动距离 |
|---|---|---|---|---|
| 先进先出（FIFO）算法 | 按顺序处理请求 | 能够保证公平；性能较差 | 53->98->183->37->122->14->124->65->67 |
640 |
| 最短服务时间优先（SSTF）算法 | 选择从磁臂当前位置需要移动最少的I/O请求 | 很不公平 | 53->65->67->14->98->122->124->183 |
236 |
| 扫描（SCAN）算法 | 磁臂在一个方向上移动，访问所有未完成的请求，直到磁臂到达该方向上最后的磁道；然后调换方向 | 判断简单；不公平，偏好中间位置磁道 | 53->37->14->0->65->67->98->122->124->183->199 |
236 |
| 循环扫描（C-SCAN）算法 | 对SCAN算法的改进：限制仅在一个方向上扫描；当最后一个磁道也被访问过了后，磁臂返回到磁盘的另外一端再次进行 | 比SCAN算法更公平 | 53->37->14->0->199->183->124->122->98->67->65 |
386 |
| C-LOOK算法 | 对C-SCAN算法的改进：不走到磁盘的头，而是只走到最远的请求 | 同样能保证公平性 | 53->37->14->183->124->122->98->67->65 |
326 |
| N步扫描（N-step-SCAN）算法 | 将磁盘请求队列分成长度为N的子队列，按FIFO算法依次处理所有子队列；再用扫描算法处理每个队列 | 防止磁头粘着现象 | 53->37->183->98->14->124->122->67->65 |
500 |
| 双队列扫描（FSCAN）算法 | 将磁盘请求队列分成两个子队列，交替使用扫描算法处理每一个队列；处理一个队列时，所有新生成的磁盘I/O请求都被放入另一队列中 | 比N步扫描更简单 | 53->37->183->122->98->67->65->14->124 |
441 |
磁盘缓存
缓存是数据传输双方访问速度差异较大时，引入的速度匹配中间层。
磁盘缓存是磁盘扇区在内存中的缓冲区。
- 磁盘缓存的调度算法很类似虚拟存储调度算法
- 磁盘的访问频率远远低于虚拟存储中的内存访问频率
- 通常磁盘缓存调度算法会比虚拟存储复杂
单缓存与双缓存
根据缓冲区个数分类：
- 单缓存（Single Buffer Cache）：只有一个缓冲区，用户进程和I/O设备只能交替访问缓存区
- 双缓存（Double Buffer Cache）：设置两个缓存区，任何时刻用户进程和I/O设备可同时访问不同的缓存区
访问频率置换（Frequency-based Replacement）算法
在一段密集磁盘访问后，LFU算法的引用计数变化无法反映当前的引用情况
算法思路
- 考虑磁盘访问的密集特征，对密集引用不计数
- 在短周期中使用LRU算法，而在长周期中使用LFU算法
具体实现
把LRU算法中的特殊栈分成3部分，并为每个缓存块增加一个引用计数
- 新区域（New Section）：栈顶
- 中间区域（Middle Section）
- 旧区域（Old Section）：栈底
