I/O分类
三种常见的设备接口类型
- 字符设备：键鼠、串口等
- 块设备：磁盘驱动器、磁带驱动器、光驱等
- 网络设备：以太网、无线、蓝牙等
设备访问特征：
- 字符设备：以字节为单位顺序访问；I/O命令使用get()、put()等，通常使用文件访问接口和语义
- 块设备：均匀的数据块访问；I/O命令使用 原始I/O 或 文件系统接口 或 内存映射文件访问
- 网络设备：格式化报文交换；I/O命令使用send/receive网络报文，通过网络接口支持多种网络协议
同步与异步I/O：
- 阻塞I/O Wait
- 读数据时 进程进入等待状态 直到完成数据读出
- 写数据时 进程进入等待状态 直到设备完成数据写入处理
- 非阻塞I/O Don’t Wait(可能会失败 或者少写)
- 立即从read或write系统调用返回 返回值为成功传输的字节数
- read或write的传输字节数可能为0
- 异步I/O Tell Me Later
- 读数据时 使用指针标记好用户缓冲区 立即返回 稍后内核将填充缓冲区并通知用户
- 写数据时 使用指针标记好用户缓冲区 立即返回 稍后内核将处理数据并通知用户
IO请求的流程：
- 用户发起 I/O请求
- 请求会发送到内核中的设备驱动
- 设备驱动将其转换为对硬件的控制
- 硬件控制完成之后 会产生中断 由内核的中断处理例程进行响应
- 回到设备驱动进行相应处理，最后回到用户态
I/O请求的流程图可看下方I/O结构章节中的I/O请求生命周期
I/O结构
设备控制器
- CPU和I/O设备间的接口
- 向CPU提供特殊指令和寄存器
I/O地址
CPU用来控制I/O硬件
内存地址或端口号：基于I/O指令或内存映射I/O
I/O指令
- 通过I/O端口号访问设备寄存器
- 特殊的CPU指令：out 0x21,AL
内存映射I/O
- 设备的寄存器/存储被映射到内存物理地址空间中
- 通过内存load/store指令完成I/O操作
- MMU设置映射，硬件跳线或程序在启动时设置地址
CPU与设备的通信方式
- 轮询(CPU直接访问I/O端口或者是映射到的内存地址，不用中断控制器)
- 设备中断
- DMA(将数据直接放到内存)
内核I/O结构
I/O请求生命周期
I/O数据传输
- 程序控制I/O(PIO Programmed I/O)
- 通过CPU的 in/out 或者 load/store 传输所有数据
- 硬件简单 编程容易
- 消耗的CPU时间和数据量成正比
- 适用于简单的、小型的设备I/O
- 直接内存访问(DMA)
- 设备控制器可直接访问系统总线
- 控制器直接与内存互相传输数据
- 设备传输数据不影响CPU
- 需要CPU参与设置
- 适用于高吞吐量I/O
DMA传输数据的操作：
- 首先，CPU通过设置其寄存器来对DMA控制器进行编程，以使其知道在何处传输（下图中的步骤1）。
它还向磁盘控制器发出命令，告诉它从磁盘读取数据到其内部缓冲区中并验证校验和。- 当有效数据位于磁盘控制器的缓冲区中时，DMA可以开始。 DMA控制器通过通过总线向磁盘控制器发出读取请求来启动传输（步骤2）。该读取请求看起来与任何其他读取请求一样，并且磁盘控制器不知道（或不在乎）它是来自CPU还是来自DMA控制器。通常，要写入的内存地址在总线的地址线上，因此，当磁盘控制器从其内部缓冲区中获取下一个Word时，它就知道将其写入哪里。写入存储到存储器是另一个标准的总线周期（步骤3）。
- 写入完成后，磁盘控制器也会通过总线将确认信号发送到DMA控制器（步骤4）。然后，DMA控制器增加要使用的内存地址，并减少字节数。如果字节计数仍大于0，则重复步骤2至4，直到计数达到0。
- 那时，DMA控制器中断CPU，以通知传输现在已完成。操作系统启动时，不必将磁盘块复制到内存；它已经在那里。
有时操作系统需要了解设备的状态（例如I/O操作完成的时间、I/O操作期间遇到的错误等），那么如何获悉这些状态呢？
有两种方式：轮询和设备中断
轮询：
I/O设备在特定的状态寄存器中放置状态和错误信息，操作系统定期检测这些状态寄存器。
特点：
- 简单
- I/O操作频繁或不可预测时，开销大(因为I/O频繁)和延时长(因为不可预测)
设备中断：
设备中断处理例程
- CPU在 I/O 之前设置任务参数
- CPU发出 I/O请求后 继续执行其他任务
- I/O设备处理 I/O请求
- I/O设备处理完成时 触发CPU中断请求
- CPU接受中断 分发到相应中断处理例程
特点：
- 处理不可预测时间效果好(CPU会在每两条指令执行间隔去检查是否有中断请求)
- 开销相对较高(CPU中断频率太高)
轮询和设备中断方式各有优缺点，因此一些设备可能结合了轮询和设备中断。例如高带宽网络设备，它在第一个传入数据包到达前采用中断，之后轮询后面的数据包直到硬件缓存为空。
磁盘调度
磁盘I/O传输时间主要由寻道时间、旋转延时和数据传送时间组成，其中寻道时间所消耗的时间最长。因此，我们主要针对磁盘调度（磁盘访问请求顺序）进行优化，从而减少寻道时间。
接下来介绍一些常见的磁盘调度算法。
先进先出算法(FIFO)
按顺序处理请求，根据进程请求访问磁盘的先后顺序进行调度。
- 公平对待所有进程
- 在有很多进程的情况下，接近随机调度的性能
最短服务时间优先(SSTF)
选择从磁臂当前位置需要移动最少距离的I/O请求。
- 可以保证每次寻道时间最短，但是不能保证总的寻道时间最短
扫描算法(SCAN)
磁臂在一个方向上移动，访问所有未完成的请求，只有移动到该方向的最外侧磁道或最内侧磁道才可以反向移动（即便在磁头移动的方向上已经没有请求，仍然必须移动到最内/外侧的磁道）。由于磁头移动的方式很像电梯，因此也被称为电梯算法(elevator algorithm)
- 各个位置磁道的响应频率不平均（C-SCAN算法改进了这个缺点）
循环扫描算法(C-SCAN)
与SCAN相比，规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至最靠边缘的的磁道上（即另一端）而途中不处理任何请求。
相比于SCAN算法，对于各个位置磁道响应频率比较平均，但平均寻道时间增加了
此外，就算磁盘边缘没有I/O请求的磁道也要走到头，浪费了时间。（ C-LOOK算法改进了这个缺点）
LOOK算法和C-LOOK算法
釆用SCAN算法和C-SCAN算法时磁头总是严格地遵循从盘面的一端到另一端，显然，在实际使用时还可以改进，即磁头移动只需要到达最边缘的被请求的磁道即可返回，不需要到达磁盘端点。这种形式的SCAN算法和C-SCAN算法称为LOOK和C-LOOK调度。
注意，若无特别说明，也可以默认SCAN算法和C-SCAN算法为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
- 中间区域的定义是为了有一个过渡期，避免新读入的缓存块在第一次出新区域时（此时其计数较少，但之后可能被频繁访问）马上被置换
缓存已满时：
- 在旧区域中引用计数最小的缓存块被置换
至此，操作系统课程结束，完结撒花🎉！(^-^)
