三种常见设备接口类型
- 字符设备
- 键盘/鼠标 串口
- 块设备
- 磁盘 磁带 光驱
- 网络设备
- 以太网 无线 蓝牙
三种设备访问特征
- 字符设备
- 以字节为单位顺序访问
- get() put() 通常使用文件访问接口和语义来访问
- 块设备
- 均匀的数据块访问
- 原始 I/O 或 文件系统接口
- 内存映射文件访问
- 网络设备
- 格式化报文交换
- send/receive 网络报文
- 通过网络接口支持多种网络协议
同步与异步I/O
- 用户发起 I/O请求
- 请求会发送到内核中的设备驱动
- 设备驱动将其转换为对硬件的控制
- 硬件控制完成之后 会产生中断 由内核的中断处理例程进行响应
- 送回设备驱动 回到用户态
- 阻塞I/O Wait
- 读数据时 进程进入等待状态 直到完成数据读出
- 写数据时 进程进入等待状态 直到设备完成数据写入处理
- 非阻塞I/O Don’t Wait(可能会失败 或者少写)
- 立即从read或write系统调用返回 返回值为成功传输的字节数
- read或write的传输字节数可能为0
- 异步I/O Tell Me Later
- 读数据时 使用指针标记好用户缓冲区 立即返回 稍后内核将填充缓冲区并通知用户
- 写数据时 使用指针标记好用户缓冲区 立即返回 稍后内核将处理数据并通知用户
I/O结构
- 北桥(高速设备)
- 内存
- AGP/PCI-Express
- Built-in Display
- 南桥(I/O设备)
- ATA/IDE
- PCI总线
- USB/Firewire总线
- Interrupt控制器
CPU与设备的连接
- 设备控制器
- CPU和I/O设备间的接口
- 向CPU提供特殊指令和寄存器
- I/O地址
- CPU用来控制I/O硬件
- 通过映射到内存地址或I/O指令对端口的操作进行访问
- CPU与设备的通信方式
- 轮询(CPU直接访问I/O端口或者是映射到的内存地址 不用中断控制器)
- 设备中断
- DMA(将数据直接放到内存)
I/O指令和内存映射I/O
- I/O指令
- 通过I/O端口号访问设备寄存器
- 特殊的CPU指令 out in
- 内存映射I/O
- 设备的寄存器/存储被映射到内存物理地址空间中
- 通过内存 load/store指令完成 I/O操作
- MMU设置映射 硬件跳线或程序在启动时设置地址
内核I/O结构
I/O请求生命周期
CPU与设备控制器的数据传输
- 程序控制I/O(PIO Programmed I/O)
- 通过CPU的 in/out 或者 load/store 传输所有数据
- 硬件简单 编程容易
- 消耗的CPU时间和数据量成正比
- 适用于简单的 小型的设备I/O
- 直接内存访问(DMA)
- 设备控制器可直接访问系统总线
- 控制器直接与内存互相传输数据
- 设备传输数据不影响CPU
- 需要CPU参与设置
- 适用于高吞吐量I/O
通过直接I/O寻址读取磁盘数据的步骤
- 设备驱动收到读取磁盘数据到内存地址X
- 设备驱动控制磁盘控制器从磁盘读取数据
- 磁盘控制器初始化DMA传送
- 磁盘控制器传送数据到DMA控制器
- DMA控制器传送C字节数据到内存地址X
- DMA控制器完成数据传输后 产生中断请求 通知CPU传送完成
I/O设备通知操作系统的机制
操作系统需要了解设备状态
- I/O操作完成时间
- I/O操作遇到错误
两种方式通知操作系统
- 轮询(我感觉都不像是通知了 明明是CPU自己去查)
- 设备中断
一些设备可能结合了轮询和设备中断
- 高带宽网络设备
- 第一个传入数据包到达前采用中断
- 轮询 后面的数据包直到硬件缓存为空
轮询
I/O设备在特定的 状态寄存器中放置状态和错误信息 操作系统 定期检测 状态寄存器
- 简单
- I/O操作频繁或不可预测时 开销大(总去查)和延时长(很长时间没去查)
设备中断
设备中断处理例程
- CPU在 I/O 之前设置任务参数
- CPU发出 I/O请求后 继续执行其他任务
- I/O设备处理 I/O请求
- I/O设备处理完成时 触发CPU中断请求
- CPU接受中断 分发到相应中断处理例程
- 处理不可预测时间效果好(CPU会在每两条指令执行期间去检查是否有中断请求)
- 开销相对较高(CPU中断频率太高)
磁盘工作机制和性能参数
读取或写入时 磁头必须被定位在期望的磁道 并从所期望的柱面和扇区的开始
- 寻道时间
- 定位到期望的磁道所花费时间
- 旋转延时
- 从0扇区开始到达目的地花费的时间
平均旋转延迟时间 = 磁盘旋转一周的时间的一半
磁盘I/O传输时间
Ta = Ts + 1/2r + b/rN
- Ts 寻道时间(时间最长 最需要优化)
- 1/2r 旋转延时的时间为磁盘旋转一周的时间的一半
- b/rN
- b 传输的比特数
- N 磁道上的比特数
- r 磁盘转数
磁盘调度算法
通过优化磁盘访问请求顺序来提高磁盘访问性能
- 寻道时间是磁道访问最耗时的部分
- 同时会有多个在同一磁盘上的I/O请求
- 随机处理磁盘访问请求的性能很差
先进先出算法(FIFO)
- 按顺序处理请求
- 公平对待所有进程
- 在有很多进程的情况下 接近随机调度的性能
磁盘访问序列 = 98,183,37,122,14,124,65,67
初始磁头位置 53
最短服务时间优先(SSTF)
- 选择从磁臂当前位置需要移动最少的I/O请求
- 总是选择最短寻道时间
磁盘访问序列 = 98,183,37,122,14,124,65,67
初始磁头位置 53
扫描算法(SCAN)
磁臂在一个方向上移动 访问所有未完成的请求 直到磁臂到达该方向上最后的磁道 也称为电梯算法(elevator algorithm)
- 中间磁道的访问性能较好 两头的比较差 C-SCAN算法改进了这个缺点
磁盘访问序列 = 98,183,37,122,14,124,65,67
初始磁头位置 53
循环扫描算法(C-SCAN)
限制了仅在一个方向上扫描 当最后一个磁道也被访问过了以后 磁币返回到磁盘的另外一段再次进行
- 就算对头没有I/O请求也要走到头 浪费了 C-LOOK算法改进了这个缺点
C-LOOK算法
磁臂先到达该方向上最后一个请求处 然后立即反转 而不是先到最后点路径上的所有请求
N步扫描(N-Step-SCAN)算法
用于解决磁头粘着问题
磁头粘着(Arm Stickiness)现象
- SSTF SCAN CSCAN等算法中 可能出现磁头停留在某处不动的情况
- 进程反复请求对某一磁道的I/O操作
将磁盘请求队列分成长度为N的子队列
按FIFO算法依次处理所有子队列
扫描算法处理每个队列
双队列扫描算法(FSCAN)
FSCAN算法是N步扫描算法的简化 只将磁盘请求队列分成两个子队列 可以减少平均等待时间
- 把磁盘I/O请求分成两个队列
- 交替使用扫描算法处理一个队列
- 新生成的磁盘I/O请求放入另一队列中 所有的新请求都将被推迟到下一次扫描时处理
磁盘缓存
磁盘缓存是磁盘扇区在内存中的缓存区
- 磁盘缓存的调度算法很类似虚拟存储调度算法
- 磁盘的访问频率远低于虚拟存储中的内存访问频率
- 通常磁盘缓存调度算法会比虚拟存储复杂
单缓存与双缓存
- 单缓存(Single Buffer Cache)
- 读和写不能同时进行 速度受限
- 双缓存(Double Buffer Cache)
- 读和写可同时进行
访问频率置换算法(Frequency-based Replacement)
- 解决的问题
- 在一段密集磁盘访问后 LFU算法的引用计数变化无法反映当前的引用情况
- 算法思路
- 考虑磁盘访问的密集特征 对密集引用不计数
- 在短周期中使用LRU算法 而在长周期中使用LFU算法
把LRU算法中的特殊栈分成三部分 并在每个缓存块增加一个引用计数
- 栈中缓存块被访问时移到栈顶 如果该块在新区域 引用计数不变 否则 引用计数加1
- 在新区域中引用计数不变的目的是避免密集访问对引用计数不利影响
- 在中间区域和旧区域中引用计数加1是为了使用LFU算法
- 未缓存数据块读入后放在栈顶，引用计数为1
- 中间区域的定义是为了避免新读入的缓存块在第一次出新区域时马上被置换 有一个过渡期