60-IO管理与磁盘

I/O 设备

I/O 外设分类

1. 人可读：用于计算机与用户间交互，如打印机、终端（键盘、显示器）、鼠标等；
2. 机器可读：用于电子设备通信，如磁盘驱动器、USB 密钥、传感器、控制器、执行器等；
3. 通信：用于远程设备通信，如数字线路驱动器、调至解调器等；

I/O 外设间差异

1. 数据传输速率
2. 设备用途：设备用途对 OS 及支持设施中的软件和策略都有影响，如存储文件的磁盘需要文件管理系统，终端被不同特权级用户使用导致优先级不同
3. 控制复杂性：不同设备的行为控制显然不同，复杂度不同
4. 数据传送单位：按字节、或字符流、或块（簇）传送
5. 数据表示：不同设备的数据编码方式不同，包括字符编码、奇偶校验约定、汉明码等冗余位；
6. 错误条件：错误的性质、报告错误的方式、错误造成的后果、有效的相应范围

I/O 功能组织

I/O 技术分类

1. 程序控制 I/O：处理器代表进程给 I/O 模块发送 I/O 命令，该进程忙等待直到操作完成；
2. 中断驱动 I/O：处理器代表进程给 I/O 模块发送 I/O 命令，若 I/O 指令是非阻塞的，则处理器继续执行 I/O 命令的后续指令；若是阻塞的，则处理器执行的下一条指令来自 OS，将当前进程设置为阻塞态并调度其它就绪进程；
3. 直接内存访问 DMA：DMA 模块控制内存和 I/O 模块之间的数据交换，为传送一块数据，处理器给 DMA 模块发送请求，且只有整个数据块传送结束后才向 CPU 发送中断请求

I/O 功能的发展阶段

1. 直接控制：CPU 直接控制外围设备
2. 抽象控制程序，分离底层接口：CPU 使用非中断的程序控制 I/O，增加了控制器（I/O 模块），CPU 开始从外部设备接口的具体细节中分离出来
3. 引入中断：CPU 不必等待 I/O 操作的执行
4. 引入 DMA：I/O 模块通过 DMA 直接控制存储器，不必 CPU 参与，仅在传送开始和结束时需要 CPU
5. I/O 专用处理器：I/O 模块专设单独处理器，有专门的指令集，CPU 只指导 I/O 处理器执行内存中的特定 I/O 程序，I/O 处理器自行取指执行完成程序规定的任务，CPU 因此指定一系列 I/O 活动，只在整个序列执行完成后才中断 CPU（408 中的通道技术）
6. I/O 模块自己有局部存储器：（SPOOLing技术）

直接内存访问

DMA 单元能够模拟处理器获得系统总线的控制权，从而进行存储器和内存的双向数据传送。

DMA 工作流程

1. 处理器需要读或写一块数据，则向 DMA 模块发送包含以下信息的命令
   • 请求读 or 写操作的信号，通过 DMA 模块与 CPU 之间的读写控制线发送；
   • 相关 I/O 设备的地址，通过数据线发送；
   • 从存储器中读 or 向存储器中写的起始地址，通过数据线发送并保存在 DMA 模块的地址寄存器中；
   • 读 or 写的字数，也通过数据线传送，保存在 DMA 模块的数据计数寄存器中；
2. CPU 继续执行其他工作，I/O 任务完全由 DMA 模块执行，DMA 模块直接从存储器中（或向存储器）逐字传送整块数据
3. 传送结束后，DMA 模块向 CPU 发送中断请求，CPU 执行中断处理例程

DMA 配置方法

1. 单总线，DMA 与 I/O 模块分离
   • DMA 模块充当代理处理器，通过程序控制 I/O 进行数据交换；
   • 低效原因：与 CPU 控制的程序控制 I/O 一样，先传送请求后传送数据，即每传送一个字需要两个总线周期；
2. 单总线，但 DMA 与 I/O 模块集成
   • DMA 与 I/O 模块之间不必通过系统总线，DMA 成为 I/O 系统的一部分，大大降低所需总线周期；
   • 缺点：不易扩展，增加或减少 I/O 模块都要改动 DMA 模块的接口数量
3. 多总线，系统总线与 I/O 总线分离
   • 若干 I/O 模块都连接在 I/O 总线上，DMA 模块只需要一个接口与 I/O 总线连接，
   • DMA 与 I/O 模块之间的数据交换脱离系统总线
   • 系统总线仅用于 DMA 模块与内存交换数据及处理器交换控制信号

OS 设计问题

设计目标

1. 效率：I/O 操作是限制计算机系统性能的关键瓶颈
2. 通用性：设备千变万化，因此需要统一的方式处理所有设备：
   • 处理器看待 I/O 设备的方式统一（设备是特殊文件）
   • OS 管理 I/O 设备和 I/O 操作的方式（虚拟化）

I/O 功能的逻辑结构

1. 逻辑外部设备：
   • 逻辑 I/O：与用户进程直接相连，不关心实际控制设备的细节，将设备当作逻辑资源来处理，允许用户进程根据设备标识符进行打开、关闭、读、写之类的交互
   • 设备 I/O：请求的操作和数据被转换为 I/O 指令序列、通道命令和控制器命令，这一层使用缓冲技术提高利用率；
   • 调度和控制：I/O 操作的排队、调度实现层，处理中断、收集并报告 I/O 状态，与设备硬件直接交互；
2. 通信端口
   • 逻辑 I/O 模块被通信架构取代，如 TCP/IP 协议层；
   • 其它层次与逻辑外部设备一致；
3. 文件系统
   • 目录管理：符号文件名被转换为标识符，采用标识符时通过文件描述符表（FDT）或索引表直接或间接地访问文件，并提供用户处理文件的接口（增删改查）
   • 文件系统：处理文件的逻辑结构和用户指定的操作，如打开、关闭、读写，以及管理访问权限；
   • 物理组织：辅存设备的物理磁道、扇区结构，对于文件和记录的逻辑访问也必须转换为物理外存地址，并且处理存储空间和内存缓冲区的分配；

I/O 缓冲

为避免 I/O 操作时程序挂起等开销和低效操作，使用缓冲技术——在输入请求发出前就开始执行输入传送，并在输出请求发出一段时间后才开始执行输出传送。

设备分类

注意区分两类 I/O 设备：

• 面向块的 I/O 设备：将信息保存在块中，块的大小通常固定，传送中一次传送一块，并且通过快号访问数据；如磁盘、USB 智能卡等设备
• 面向流的 I/O 设备：以字节流的方式 I/O，如终端、打印机、通信端口、鼠标及其它非辅存设备

单缓冲

单缓冲方案描述

• 输入传送的数据被放到系统缓冲区中，传送完成时进程把该块移动到用户空间，并立即请求另一块（即预读，预输入）
• 数据通常是顺序访问的，由于局部性原理，在处理序列的最后才可能读入不必要的块
• 相对于无缓冲情况，单缓冲方案的用户进程可以在下一数据块读取的同时，处理已读入的数据块，因而处理与读取并行，提高了系统效率；
• 输入发生在系统内存提供的缓冲区中，而非用户进程的内存空间，因而 OS 可以安全地换出该进程；
• 准备将数据发送到一台设备时，首先将数据从用户空间复制到系统缓冲区，之后由系统缓冲区写出，提出请求的进程可以自由地继续执行或换出。

单缓冲方案的负面影响

• 增加了 OS 的逻辑复杂度：OS 必须记录给用户进程分配系统缓冲区的情况；
• 影响数据块交换逻辑：I/O 操作涉及的磁盘和用于交换的磁盘相同时，磁盘写操作排队等待将进程换出到同一设备是没有任何意义的，若试图换出进程并释放内存，则要在 I/O 操作完成后才能开始，而此时进程正要使用而不能换出到磁盘；

性能比较 (对块设备)

• 无缓冲时，每块执行时间为 $T+C$； $T$：输入一个数据块所需要的时间； $C$：两次输入请求之间所需的计算时间。

• 单缓冲时，执行时间为 $max(T,C)+M$， $M$：数据从系统缓冲区复制到用户内存所需要的时间。

单缓冲用于流式 I/O

对于面向流的 I/O，单缓冲方案能以每次传送一行的方式或每次传送一字节的方式使用：

1. 每次传送一行：适用于滚动模式的终端
   • 每次输入一行，用回车表示到达行尾，并且输出到终端时也是类似地每次输出一行，如行式打印机；
   • 用缓冲区保存单独一行数据，输入期间用户进程挂起等待整行到达，对于输出用户进程将一行输出放在缓冲区中，然后继续执行自己的后续任务;
   • 进程不需要挂起，除非第一次输出操作的缓冲区内容清空之前，又需要发出第二行输出；
2. 每次传送一字节：适用于表格式终端
   • 每次击键都很重要，如传感器、键鼠等外设；
   • OS 与用户进程之间的交互是 生产者/消费者 模型

双缓冲

又称缓冲交换 buffer swapping

双缓冲方案描述：

• 一个进程向一个缓冲区传送数据的同时，OS 正在清空另一个缓冲区，当然输出数据到缓冲区也可以；

性能分析 (对块设备)

• 对于面向块的传送，可以粗略估计执行时间 $max(C,T)$：
  • 对于 $C\le T$，面向块的设备全速运行；
  • 对于 $C>T$，双缓冲可以确保进程不需要等待 I/O

双缓冲用于流式 I/O

1. 对于每次传送一行的 I/O，用户进程不需要为输入或输出挂起；
2. 对于每次传送一字节的 I/O，双缓冲并不比单缓冲有明显优势；

这两种情况都是 生产者/消费者 模型

循环缓冲

• 双缓冲方案仍不足以跟得上大量 I/O 操作时，可以采用循环缓冲方案。
• 此时每个缓冲区都是循环缓冲区组的一个单元，对应了 有界缓冲区生产者/消费者 模型。

缓冲的作用 (削峰填谷)

• 缓冲是用来平滑 I/O 需求的峰值的技术，
• 对于单进程而言当计算需求大于 I/O 设备服务能力时，缓冲再多也无法满足 I/O 设备与 CPU 并驾齐驱。
• 但多道程序设计环境中，不同进程的计算需求和 I/O 需求各不相同，缓冲是提高 OS 和计算机系统整体效率的好办法。（削峰填谷思想）

磁盘调度

磁盘性能参数

磁盘驱动器工作时，磁盘以恒定速度旋转，为了读写数据，磁头需要位于指定磁道的指定扇区开始处。因此

• 寻道时间 (seek time)：磁头定位到指定磁道所需要的时间；
• 旋转延迟 (rotational time)：磁盘控制器等待指定扇区开始处旋转到磁头所需要的时间；
• 传输时间 (transfer time)：磁头定位完成后开始读写操作，进行数据传输的时间；
• 排队延迟 (wait time)：进程发出 I/O 请求后，需要在等待队列中等待设备可用；同样若设备共享 I/O 通道，则还需要等待通道可用；

旋转定位感知技术

Rotational Positional Sensing, RPS:

1. 发出寻道命令时，通道被释放以处理其它 I/O 操作；
2. 寻道完成后，设备确定何时数据扇区旋转到磁头下面；
3. 当扇区接近磁头时，设备试图重建到主机的通信路径；
4. 若控制单元或通道正忙于处理另一个 I/O，则重建连接的尝试失败，设备必须旋转一周后再重新尝试连接，这称为 RPS 失败，也是一种额外延迟。

寻道时间

• 很难减少的延迟；
• 主要两个部分：
  • 最初启动时间；
  • 访问臂达到一定速度后，横跨必要的磁道所需的时间：由于横跨时需要验证磁道标识，这个稳定时间导致横跨磁道的时间不是磁道数量的线性函数；

旋转延迟

• 平均旋转延迟 = 旋转一周的时间的一半
• 假设旋转速率 15000 rpm，相当于 250 rps，则旋转一周时间为 1000/250=4 ms，则平均旋转延迟=(0+4)/2=2 ms

传输时间

• 取决于磁盘的旋转速度；
• $T=\frac{b}{rN}$，T 表示传输时间，b 表示传送字节数，N 表示一个磁道中的字节数，r 表示旋转速度 (单位 rps)
• $\frac{b}{N}$ 实际上是磁盘需要旋转的圈数；
• 因此总平均存取时间为：

$$T_a=T_{seek}+\frac{1}{2r}+\frac{b}{rN}$$

时序比较

磁盘举例：平均寻道时间 4ms，转速 7500rpm，每个磁道 500 扇区，每个扇区 512Bytes。要读取 2500 个扇区、1.28MB 的文件，分别以顺序读取和随机读取作讨论。

1. 顺序读取：文件紧凑地保存在磁盘的相邻磁道（不考虑磁道切换的寻道时间）

   • 旋转延迟=(0+1000/125)/2=4 ms，(7500 rpm=125 rps)
   • 读第一个磁道时间：4+4+8=16 ms
   • 接下来读取其余 4 磁道各自只需要旋转延迟 4 ms + 数据传输 8 ms；
   • 故总时间=16+4x12=64ms=0.064s

2. 随机读取：文件随机分布在磁盘上

   • 每个扇区需要：寻道时间 4 ms，旋转延迟 4 ms，读取时间 8/500=0.016 ms；
   • 总时间=2500 x 8.016=20040 ms=20.04s

因此如何提升文件在磁盘上存储的局部性，是提高 I/O 速度的关键方法。

磁盘调度策略

寻道时间固定，但对请求队列的寻道策略不固定。OS 为每个 I/O 设备维护一个磁道请求队列。

Random

随机访问磁道，完全不考虑文件的局部性，因此性能是最差的。作为与其它调度策略对比的基准。

FIFO

• 按顺序处理队列中的请求项，实现最简单，完全公平；
• 没有磁臂黏着现象，不会饥饿；
• 没有局部性，完全取决于请求的到达时间，当大量进程竞争一个磁盘时请求是近似随机的，此时在性能上也接近于随机调度；

Priority

• 基于优先级的请求处理；
• 不会优化磁盘的利用率，主要是为了满足 OS 的响应性需求；
• 长作业的优先级较低，有些取巧办法会把作业分成小块瞒天过海；

LIFO

• 优先处理最新的请求，只要一项任务能积极地使用 I/O 系统，将会被尽快处理；
• 尤其在处理高突发时性能较好，很好地利用了局部性；
• 局部性强，当然会产生饥饿现象、磁臂黏着；
• 一旦任务在队列中发出 I/O 请求，但是执行中又从队头退出，就不能再回到队头，除非前面的队列清空；

SSTF

• 选择磁头臂从当前位置开始移动最少的磁盘 I/O 请求；
• 局部选择最小寻道时间并不能保证全局平均寻道时间最少；
• 具有局部性，会发生饥饿现象、磁臂黏着；

SCAN

• 又称电梯算法，运动在一程中是单向的，到达尽头后运动方向相反；
• 不会饥饿，但是会磁臂黏着，新请求频繁到达在扫描方向之前时，就会长期停留在此，但是总还是会度过此处突发请求到达尽头；
• 对最近横跨过的区域不公平，越接近尽头被扫描到的可能越大，不能很好地利用局部性；
• 若从最里面磁道扫描到最外面磁道的期望时间为 t，则该外设上扇区的期望服务时间间隔为 2t；

C-SCAN

• 循环 SCAN，扫描方向限定不变，到达尽头后从另一端开始方向不变地扫描，减少了新请求的最大延迟；
• 期望服务时间间隔为 $t+see{k}_{max}$；

N-SCAN

• 磁臂黏着：若干进程对一个磁道具有较高的访问速度和访问频度，则设备被垄断在这个磁道，磁头很久不动；
• 将磁盘请求队列分成长度为 N 的若干段，每次用 SCAN 只处理一个子队列；
• 子队列间的策略是 FIFO；
• 正在处理某子队列时，新的磁盘请求必须添加到其它子队列；
• N 较大时性能接近于 SCAN，N=1 时退化成 FIFO；

FSCAN

• 只使用两个子队列，开始时所有请求在一个子队列，另一个子队列为空且只接受新请求；
• 对新请求的处理在所有老请求之后；

RAID

基于通过并行提高性能的基本原理：

• 如果使用一个组件对性能的影响有限，则并行使用多个组件可获得额外的性能提高。
• 因此，通过将访问的数据块分布在多个磁盘上，可以并行提高 I/O 请求的速度。

RAID 的特点

Redundant Array of Independent Disks：

1. 物理上是一组磁盘驱动器，但 OS 视作单个逻辑驱动器；
2. 数据分布在物理驱动器阵列中，称为条带化 (striping)；
3. 使用冗余磁盘容量保存奇偶校验信息，保证在一个磁盘失效时数据仍然具有可恢复性。

RAID 指标参数总览

• 磁盘请求：表明该 RAID 需要多少个磁盘，其中 RAID 2 通过汉明码冗余，因此需要 m=logN 个冗余磁盘；
• 数据可用性：指数据的可恢复性，安全性；
• 大 I/O 数据传送能力：读写速度；
• 小 I/O 请求率：完成 I/O 请求的能力；

RAID 性能总结

• 磁盘请求：单磁盘 < RAID0 < 2 < 3 = 4 = 5 < 6 < 1
• 数据可用性排序：RAID0 < 单磁盘 << 2 ~ 3 ~ 4 ~ 5 < 1 < 6;
• 大 I/O 数据量传送能力：
  • 读：单磁盘 < RAID0 ~ 4 ~ 5 ~ 6 < 1 < 2 ~ 3
  • 写：RAID6 < 4 ~ 5 < 单磁盘 ~ 1 < 0 < 2 ~ 3
• 小 I/O 请求率：
  • 读：单磁盘 < RAID0 ~ 4 ~ 5 ~ 6 < 2 ~ 3 ~ 1
  • 写：RAID6 < 4 ~ 5 < 单磁盘 < 1 < 0 < 2 < 3

RAID 0

用户数据和系统数据分布在所有阵列的所有磁盘中。当被请求的块不在同一磁盘，则多个请求可以并行发出，减少 I/O 排队等待的时间；

存储数据的策略

• 在整体的逻辑磁盘上，存储空间被划分成多个条带，每个条带可以是物理块、扇区等单元；
• 这些条带被循环映射到连续的 RAID 成员的物理磁盘上，逻辑条带映射到相同大小的物理磁盘区域中，阵列的每个磁盘的第一个区域连接成物理上的一个条带 (A1 A2 是条带 1，A3 A4 是条带 2)
• 优点是：若一个 I/O 请求由多个逻辑上连续的条带组成，则可以并行处理（每个磁盘都发挥作用）

如何实现高数据传送能力？

1. 不考虑冗余性；
2. 应用程序需要请求逻辑上连续的数据，这样能够物理地并行使用多个磁盘，从而提高传送速率；

如何实现高速 I/O 请求率？

1. 事务处理环境中响应性比数据传送能力更重要，而 RAID0 可以通过在多个磁盘中平衡 I/O 负载来提供较高的执行速率；
2. 当存在多个未完成的 I/O 请求时，能够实现有效的负载平衡；
3. 若条带相对较大，则一个 I/O 请求可能只包括对一个磁盘的访问，从而多个等待的 I/O 请求可以并行处理；

RAID 1

• 通过临时复制所有数据实现冗余，每个逻辑条带映射到两个单独的物理磁盘。

优点

1. 读请求可由包含请求数据的任一磁盘提供服务，因此读最快是 RAID 0 的两倍；
2. 写请求需要对两个条带都进行更新，但这是并行完成的，因此写操作由较慢者决定，较 RAID 0 写速度稍慢一点，但并没有冗余校验的性能损失；
3. 失效恢复只需要从镜像磁盘中直接复制即可；

缺点：

• 成本过高，所需磁盘要两倍于支持的逻辑空间；

RAID 2

策略描述

• RAID 2 和 RAID 3 采用了并行访问技术，通过同步所有磁盘的轴心，每个时刻磁头都处于各自磁盘的同一位置，使得所有磁盘都参与每个 I/O 请求的执行。
• RAID 2 和 RAID 3 中使用小条带，通常只有 1 个字或字节。
• RAID 2 对每个数据磁盘的相应位都计算一个错误校正码，这个码位保存在多个奇偶校验磁盘的相应位中；
• 错误校正使用汉明码，能够纠正 1 位错误、检出 2 位错误；
• 冗余磁盘数量与数据磁盘数量的对数成正比，读操作需要访问所有磁盘，被请求的数据及相关错误校正码被送达并计算，写操作则要访问所有数据磁盘和奇偶校验磁盘；

优点：

• RAID 2 和 RAID 3 的数据传送能力最强，请求率是单个磁盘的两倍；

缺点：

• 贵

RAID 3

• 为所有数据磁盘的同一位置的位的集合计算一个奇偶校验，存放在单独的奇偶校验冗余磁盘中；

数据恢复

1. 磁盘故障时访问奇偶校验驱动器，根据其余设备重建数据；
2. 考虑 5 个磁盘，前四个是数据磁盘，第五个是校验磁盘，则第 i 位奇偶检验计算如下：$X4(i)=X3(i)\oplus X2(i)\oplus X1(i)\oplus X0(i)$,
3. 则恢复指定驱动器 $X1(i)$，可以两边都加 $X1(i)\oplus X4(i)$：$X1(i)=X4(i)\oplus X3(i)\oplus X2(i)\oplus X0(i)$
4. 即每个磁盘上的内容都可由其它所有磁盘对应内容通过异或运算获得；

性能

• 数据分成了很小的条带，RAID 3 能实现非常高的数据传送率，任何一个 I/O 请求都是从所有数据磁盘中并行传送数据，对大数据量的传送性能提高明显；
• 但是一次只能执行一个 I/O 请求，在面向事务处理的环境中性能不乐观。

RAID 4

策略描述

• RAID 4 到 RAID 6 采用独立访问技术，每个磁盘成员都单独运转，不同的 I/O 请求并行地满足；
• 数据条带相对较大；
• 适合较高 I/O 请求率的应用程序，但不适合需要较高数据传送率的应用程序；
• RAID 4 对每个数据磁盘的相应条带计算一个逐位奇偶校验，保存在奇偶校验磁盘的相应条带中。

数据恢复

1. 考虑 5 个磁盘，前四个是数据磁盘，第五个是校验磁盘，则第 i 位奇偶检验计算如下：$X4(i)=X3(i)\oplus X2(i)\oplus X1(i)\oplus X0(i)$；
2. 更新 $X1(i)$，标记为 $X^{\prime }1(i)$ ，则:

$$\begin{array}{rl}X{4}^{\prime }(i)& =X3(i)\oplus X2(i)\oplus X{1}^{\prime }(i)\oplus X0(i)\\ & =X3(i)\oplus X2(i)\oplus X{1}^{\prime }(i)\oplus X0(i)\oplus X1(i)\oplus X1(i)\\ & =X3(i)\oplus X2(i)\oplus X1(i)\oplus X0(i)\oplus X1(i)\oplus X{1}^{\prime }(i)\\ & =X4(i)\oplus X1(i)\oplus X{1}^{\prime }(i)\end{array}$$

性能

• I/O 写请求时会引发性能损失，RAID 4 必须更新数据和奇偶校验位；
• 要计算新的奇偶校验，RAID 4 必须读取旧用户条带和旧奇偶校验条带，然后用新数据和新奇偶校验更新这两个条带，因此每个条带的写都包含两次读和两次写；
• 因此读性能接近 RAID 0，写性能慢于单个磁盘；
• 奇偶校验盘可能成为瓶颈；

RAID 5

• 将奇偶校验条带循环分布在所有磁盘中；
• 可避免 RAID 4 中一个奇偶校验磁盘的潜在 I/O 瓶颈问题；
• 损失任何一个磁盘而不会损失数据的特性；

RAID 6

• 策略：

  • 采用两种不同的奇偶校验计算，保存在不同磁盘的不同块中；
  • P 校验使用异或计算，Q 校验使用独立数据校验，使得即使有两个数据磁盘错误，也可以重新生成数据；

• 性能：

  • MTTR (mean time to repair)时间内，只有同时丢失三个以上条带时数据才会丢失，数据可用性很高；
  • 写性能很差，比 RAID5 还慢，读性能接近 RAID0。

磁盘缓存

• 内存中为磁盘扇区设置一个缓冲区，包含磁盘中某些扇区的副本。
• 类似 cache，对特定扇区进行 I/O 请求时，会先检测是否处于磁盘缓冲区中。
• SPOOLing 技术会设置输入井和输出井，就是通过磁盘缓冲区实现。

磁盘缓冲区中的数据如何发送到请求进程？

1. 在内存中将这块数据从磁盘高速缓存传送到用户进程的存储空间中。（显然效率低）
2. 使用共享内存，传送指向磁盘高速缓存中对应项的指针。（节省了内存中转移数据的时间，且允许多读者单写者模型的多进程访问）

磁盘缓存的置换策略

LRU

1. 逻辑上缓冲区由关于块的栈组成，最近访问过的块位于栈顶；
2. 缓冲区中的一个块被访问时会移至栈顶，栈满时从辅存中读取块会移走栈底块、压入栈顶；
3. 实际上不需要移动这些块，只是逻辑上的栈顶指针与之关联即可；
4. 利用了 LIFO 的良好局部性；

LFU：

1. 给每个块关联一个计数器，每一次块被访问都导致计数器加 1；
2. 由于局部性，部分块短时间内多次访问会极快增加计数器的值，过了访问密集阶段，过高的计数值使置换策略误解而不能及时置换无用块；
3. 改进可以是递减计数器的 LFU，更好的是 FBR。

FBR(基于频率的置换算法)

1. 简化版本 a，
   • 块在逻辑上组织成一个栈，栈顶一部分区域留作新区；
   • 缓冲区命中时，被访问的块移到栈顶，若该块已在新区中，则访问计数器不会增加，否则计数器增 1；
   • 新区够大时，短时间重复访问的块的计数器不变化；发生未命中时换出不在新区中的计数最少的块；
   • 缺点：新块换入并放入新区时，计数器为 1，当年龄超过新区时计数器仍然为 1，此时最容易被置换。因此对使用周期超出新区的块，虽然访问也比较频繁，但会不停地换入换出；
2. 改进版本 b，
   • 增加一个中区，新区中计数器数量不会变化，老区中块才会被置换；
   • 性能较 a 版本显著提升；

UNIX I/O

• UNIX 将 I/O 设备视作特殊文件，由文件系统管理，按照与用户数据相同的方式读写。

• 文件子系统管理辅存设备中的文件，充当设备的进程接口；
• 有两种类型 I/O：有缓冲 (内存中 buffer)和无缓冲 (DMA)

缓冲区高速缓冲

缓冲区实际上就是硬盘缓存，通过 DMA 传输数据。

• 为了管理缓冲区，需要维护三个列表：

  1. 空闲列表：缓冲区中所有可用于分配的存储槽；
  2. 设备列表：列出当前与每个磁盘相关联的所有缓冲区；
  3. 驱动程序 I/O 队列；

• 特点：

  • 所有缓冲区要么都在空闲列表中，要么都在驱动程序 I/O 队列中，
  • 缓冲区一旦与一个设备关联，就会一直保持关联，即使处于空闲列表中；
  • 这些列表通过与每个缓冲区关联的指针来维护，不是物理上的真正列表。
  • 设备列表被组织成散列表，使用链地址法处理冲突溢出；
  • 置换算法是 LRU；