第13章：I/O子系统
操作系统
13.1 I/O特点
三种常见设备接口类型
设备访问特征
- 字符设备
- 访问特征
- I/O命令
- get(), put()等
- 通常使用文件访问接口和语义
- 块设备
- 网络设备
- 访问特征
- I/O命令
- send/receive网络报文
- 通过网络接口支持多种网络协议
同步与异步 I/O
（1）阻塞 I/O：”Wait“
- 读数据时，进程将进入等待状态，直到完成数据读出
- 写数据时，进程将进入等待状态，直到设备完成数据写入处理
| 用户 |
I/O 请求处理过程 |
| 内核 |
设备驱动 |
| 内核 |
中断处理 |
| 内核 |
硬件控制数据传送 |
- 用户的请求首先通过系统调用到设备驱动，设备驱动会把用户请求转换成实际的硬件控制命令，绕过中断处理，直接控制硬件进行相应的操作。
- 操作结束之后，产生中断请求，转到设备驱动，最后通过系统调用的返回到用户态，用户得到相应的结果。
（2）非阻塞 I/O ：”Don't Wait“
- 立即从read或write系统调用返回，返回值为成功传输字节数
- read或write的传输字节数可能为0
（3）异步 I/O ：”Tell Me Later“
13.2 I/O 结构
CPU与设备的连接
- 设备控制器
- CPU和 I/O 设备间的接口
- 向CPU提供特殊指令和寄存器
| 总线接口 |
提供CPU和 I/O 设备间的接口 |
| 硬件控制器 |
|
| 寄存器（读数据、写数据、控制、状态） |
进行数据的交互和状态和控制的交互 |
| 可寻址存储或队列（内存映射） |
映射到内存当中，给一段内存区域，对这段内存区域的访问，对应过来就是I/O设备的访问 |
- I/O 地址
- I/O 地址通过总线连到CPU，总线和实际设备之间有总线适配器
- CPU用来控制 I/O 硬件
- 内存地址或端口号
设备到CPU的通道
中断控制器
- 设备产生中断之后，在中断控制器进行汇总然后送给CPU，CPU就能对外部设备的事件作出响应
CPU与外部设备的通信方式
- 轮询：无需中断控制器，CPU直接访问 I/O 端口，或者说访问设备所对应的内存地址空间
- 设备中断：外部设备有事件要通知CPU，就要通过中断到CPU
- DMA：外部设备需要把数据直接放到内存当中，可以通过CPU读，然后放到内存。在DMA控制器的控制下，把数据从 I/O 设备直接到内存单元
I/O 指令和内存映射 I/O
I/O 指令
- 通过 I/O 端口号访问设备寄存器
- 特殊的CPU指令
内存映射 I/O
- 设备的寄存器/存储被映射到内存物理地址空间中
- 通过内存load/store指令完成 I/O 操作
- MMU设置映射，硬件跳线或程序在启动时设置地址
内核 I/O 结构
| 软件 |
内核 |
|
|
I/O子系统 |
处理各种设备共同的一些内容，例如I/O请求转换成驱动的I/O请求；缓存设备给出的结果 |
|
设备驱动 |
|
| 硬件 |
设备控制器 |
|
|
设备 |
|
I/O请求生存周期
13.3 I/O数据传输
CPU与设备控制器的数据传输
- 程序控制I/O（PIO，Programmed I/O）
- 通过CPU的in/out或者load/store传输所有数据
- 特点
- 硬件简单，编程容易
- 消耗的CPU时间和数据量成正比
- 适用于简单的、小型的设备I/O
- 直接内存访问（DMA）
- 设备控制器可直接访问系统总线
- 控制器直接与内存互相传输数据
- 特点
通过直接I/O寻址读取磁盘数据的步骤
1. 设备驱动收到内存地址X2. 设备驱动控制磁盘控制器从磁盘读取数据3. 磁盘控制器初始化DMA传送4. 磁盘控制器传送数据到DMA控制器5. DMA控制器传送C字节数据到内存地址X6. DMA控制器完成数据传送后，产生中断请求，通知CPU传送完成
I/O设备通知操作系统的机制
- 操作系统需要了解设备状态
- I/O操作完成时间
- I/O操作遇到错误
- 两种方式
轮询
- I/O是设备在特定的状态寄存器中设置状态和错误信息
- 操作系统定期检测状态寄存器
- 特点
设备中断
- 设备中断处理流程
- CPU在I/O之前设置任务参数
- CPU发出I/O请求后，继续执行其他任务
- I/O设备处理I/O请求
- I/O设备处理完成时，触发CPU中断请求
- I/O接收中断，分发到响应中断处理例程
- 特点
- 一些设备可能结合了轮询和设备中断
- 如：高带宽网络设备
- 第一个传入数据包到达前采用中断
- 轮询后面的数据包直到硬件缓存为空
13.4 磁盘调度
磁盘工作机制和性能参数
- 读取或写入时，磁头必须被定位在期望的磁道，并从所期望的柱面和扇区的开始
- 寻道时间
- 旋转延迟
- 从零扇区开始处到达目的地所花费的时间
- 平均旋转延迟时间 = 磁盘旋转一周时间的一半
磁盘I/O传输时间
| 等待设备可用 |
|
| 等待通道可用 |
设备忙 |
| 寻道时间 |
设备忙 |
| 旋转延迟 |
设备忙 |
| 数据传送 |
设备忙 |
- Ta = Ts + 1/2r + b/rN
- Ta : 访问时间
- Ts ：寻道时间
- 1/2r ： 旋转延迟
- b/rN ： 传输时间
- b ：传输的比特数
- N ：磁道上的比特数
- r ：磁盘转数
磁盘调度算法
- 通过优化磁盘访问请求顺序来提高磁盘访问性能
- 寻道时间是磁盘访问最耗时的部分
- 同时会有多个在同一磁盘上的I/O请求
- 随机处理磁盘访问请求的性能表现很差
（一）先进先出（FIFO）算法
- 按顺序处理请求
- 公平对待所有进程
- 在有很多进程的情况下，接近随机调度的性能
（二）最短服务时间优先（SSTF）算法
- 选择从磁臂当前位置需要移动最少的I/O请求
- 总是选择最短寻道时间
（三）扫描算法（SSAN）
- 磁臂在一个方向上移动，访问所有未完成的请求，直到磁臂到达该方向上最后的磁道
- 调换方向
- 也称为电梯算法（elevator algorithm）
（四）循环扫描算法（C-SSAN）
- 限制了仅在一个方向上扫描
- 当最后一个磁道也被访问过了后，磁臂返回到磁盘的另外一端再次进行
（五）C-Look算法
- 磁臂先到达该方向上最后一个请求处，然后立即反转，而不是先到最后点路径上的所有请求
（六）N步扫描算法（N-Step-SCAN）
- 磁头粘着（Arm Stickness）现象
- SSTF、SSAN及CSSAN等算法中，可能出现磁头停留在某处不动的情况
- 如：进程反复请求某一磁道的I/O操作
- N步扫描算法
- 将磁盘请求队列分成长度为N的队列
- 按FIFO算法依次处理所有队列
- 扫描算法处理每个队列
（七）双队列扫描（FSCAN）算法
- FSCAN算法是N步扫描算法的简化
- FSCAN算法
- 把磁盘I/O请求分成两个队列
- 交替使用扫描算法处理一个队列
- 新生成的磁盘I/O请求放入另一队列中
- 所有新请求都被推迟到下一次扫描时处理
13.5 磁盘缓存
单缓存与双缓存
单缓存（Single Buffer Cache）
- 设立一个缓存区，设备往缓存区写数据时，CPU不能从操作；当CPU从缓存区读数据时，设备不能写数据
- 由于任何时刻只有一方能够操作，速度就会很受限制
双缓存（Double Buffer Cache）
- 设立两个缓存区，当设备往缓存区1写数据时，CPU可以从缓存区2读数据，可以提升交换速度
访问频率置换算法（Frequency-based Replacement）
问题
- 在一段密集磁盘访问后，LFU算法的引用计数变化无法反映当前的引用情况
算法思路
- 考虑磁盘访问的密集特征，对密集引用不计数
- 在短周期中使用LRU算法，在长周期中使用LFU算法
| 栈顶 |
新区域 |
中间区域 |
旧区域 |
栈底 |
|
引用计数不变 |
引用计数加1 |
引用计数加1 |
|
- 栈中缓存块被访问时移到栈顶；如果该块在新区域，引用计数不变；否则，引用计数加1
- 在新区域中引用计数不变的目的是避免密集访问时引用计数不利影响
- 在中间区域和旧区域中引用计数加1是为了使用LFU算法
- 未缓存数据块读入后放在栈顶，引用计数加1
- 在旧区域中引用计数最小的缓存块被置换
- 中间区域的定义是为了避免新读入的缓存块在第一次出新区域时马上被置换，有一个过渡期
