四、设备管理 —— I/O 管理

4.1 设备管理概述

4.1.1 I/O 设备

I/O 设备概述

背景: 现代计算机系统通常配备大量的 I/O 设备，用于计算机系统与外部世界（如用户、其它计算机或电子设备等）进行信息交换或存储

• I/O 设备又称为外围设备或外部设备，简称外设
• I/O 操作: 内存和 I/O 设备之间的信息传送操作

按信息传输方向划分 I/O 设备

• 输入设备: 将外界信息输入计算机（键盘、鼠标）
• 输出设备: 将计算结果输出（显示屏、打印机）
• 输入输出设备: 既可以输入信息，也可以输出信息（网卡、磁盘）

按交互功能划分 I/O 设备

• 人际交互设备: 用于用户与计算机之间的交互通信（鼠标、键盘、显示器）
• 存储设备: 持久性地存储大量信息并快速检索（磁盘、光盘）
• 机机通信设备: 用于计算机和计算机之间的通信（网卡、调制解调器）

按设备管理划分 I/O 设备

• 字符设备: 以字符为单位进行信息交换（大多数人机交互设备）
• 块设备: 以固定大小的数据块进行信息交换（磁盘）
• 网络设备: 用于与远程设备通信的设备（网卡）

4.1.2 设备管理

目标

1. 克服设备和 CPU 速度不匹配所引起的问题。令主机和设备并行工作，提高设备使用效率。
2. 对设备进行抽象，屏蔽设备的物理细节和操作过程，配置驱动程序，提供统一界面，供用户或高层软件使用。
   • 抽象为文件系统中的节点，统一管理
   • 裸设备: 不被操作系统直接管理，由应用程序读写，I/O 效率更高

管理内容

1. 设备中断处理
2. 缓冲区管理
3. 设备的分配与去配
4. 设备驱动调度
5. 实现虚拟设备

管理层次

• I/O 硬件: I/O 设备、接口线路、控制部件、通道
• I/O 软件: 系统 I/O 软件、用户空间 I/O 软件

4.2 I/O 控制方式

4.2.1 设备控制器

概述

将 I/O 设备中的机械部件和电子部件分开处理，其中电子部件称为设备控制器。

设备控制器又称为设备适配器、I/O 控制器、I/O 控制接口，简称 I/O 模块或 I/O 接口。

OS 与控制器交互，而非与设备交互。

功能

1. 接受、识别命令（来自 CPU 或通道）
2. 数据交换
3. 记录设备状态（供 CPU 处理）
4. 设备地址识别（连接多台设备时）

组成

• 与主机交互
  • （记录设备状态）状态/控制寄存器
  • （数据交换）数据缓冲寄存器
  • （接受命令）地址译码和 I/O 控制逻辑
• 与设备交互
  • 外设接口控制逻辑

4.2.2 轮询方式

具体流程

轮询方式是忙等待的过程。

1. 处理器向控制器发送一个 I/O 命令
2. 如果设备未就绪，则反复查看 I/O 状态，直至设备就绪
3. 执行数据交换

特点

1. 处理 I/O 请求会终止原程序的执行
2. CPU 需要参与数据传送
3. CPU 与设备串行工作，效率低下

4.2.3 中断方式

具体流程

1. 处理器向控制器发出 I/O 命令，然后继续执行后续指令。
   • 如果该进程支持异步 I/O，则继续执行该进程。
   • 否则，进程在这个中断点挂起，CPU 执行其他程序。
2. 控制器检查设备状态，就绪后发起中断。
3. CPU 响应中断，转向中断处理程序。
4. 中断处理程序执行数据读写操作。
5. 恢复执行原先程序。

特点

1. CPU 不需要等待 I/O 设备就绪
2. CPU 仍需要参与数据传送（响应中断后，原程序会停止执行）
3. CPU 和设备部分并行，效率提高

4.2.4 DMA 方式

DMA 模块

DMA: 直接存储器访问

DMA 模块: 模仿处理器来控制主存和设备控制器之间的数据交换

具体流程

1. 处理器向 DMA 模块发出 I/O 命令
2. 处理器继续执行其它工作，DMA 模块负责传送全部数据
3. 数据传送结束后，DMA 中断处理器

特点

1. CPU 不会终止原程序的执行（CPU 无须等待 I/O 设备就绪，也无需进行数据传送）
2. CPU 只在数据传送的开始和结束时参与
   • 开始时，CPU 需要对 DMA 模块进行初始化
   • 结束时，CPU 响应中断，但不必保存现场

DMA 方式中的周期窃取

当 DMA 和 CPU 同时经总线访问内存时，CPU 总是将总线的占有权让给 DMA 一个或几个主存周期。

由于 CPU 大部分情况下与 Cache 进行数据交换，因此周期窃取对 CPU 与主存的数据交换速率影响不大。

4.2.5 三类 I/O 控制方式总结

轮询方式

CPU 需要等待设备就绪，且参与数据传送。

中断方式

CPU 无需等待设备就绪，但响应中断后参与数据传送。

DMA 方式

CPU 在数据传送开始和结束时参与，与主存进行数据交换时不参与。

4.2.6 I/O 通道

概述

I/O 通道，又称为通道控制器、I/O 处理器。

设备控制器包含自身专用的处理器和通道程序。

• I/O 指令不再由处理器执行，而是存在主存中，由 I/O 通道所包含的处理器执行。
• 采用四级结构，处理器-通道-控制器-设备

带有局部存储器的 I/O 通道

• 相当于一台自治的计算机
  • I/O指令存储在控制器自带的局部存储器中，并由 I/O 通道所包含的处理器执行
• 可以控制大量的 I/O 设备，同时最小化 CPU 的干涉
• 常用于交互式终端通信，负责包括控制终端在内的大部分任务

流程

1. CPU 遇到 I/O 请求，启动指定通道
2. 一旦启动成功，通道开始控制 I/O 设备进行操作，CPU 执行其他任务
3. I/O 操作完成后，I/O 通道发出中断，CPU 停止当前工作，转向处理 I/O 操作结束事件

CPU 与通道并行工作。

4.3 总线与 I/O

4.3.1 总线概述

总线目标: 解决 I/O 速度不匹配问题。

总线连接方式不同，会导致计算机性能的巨大差异，从而导致计算机价格的巨大差异。只有合理地组织总线，才能使得处理器和设备充分并行，提高系统效率。

4.3.2 单总线

总线结构

将 CPU、主存和 I/O 模块连接到同一组总线上。

优点

结构简单、易于扩充。

缺点

1. 主存需要和 I/O 模块共用总线
2. 设备增多会造成总线变长，进而增加传输时延
3. 无法适用于大量高速设备

4.3.3 传统的三级总线

总线结构

• 主存和 Cache 通过主存总线传送数据，主存总线和扩展总线上的 I/O 设备之间传送数据通过扩展总线接口缓冲

优点

1. 主存与 I/O 之间的数据传送与处理器的活动分离
2. 可以支持更多的 I/O 设备

缺点

不适用于 I/O 设备数据速率相差太大的情形。

4.3.4 采用南北桥的多级总线

总线结构

通过存储总线、PCI 总线、E(ISA) 总线分别连接主存、高速 I/O 设备和低速 I/O 设备。

优点

可以支持不同数据速率的 I/O 设备。

4.3.5 采用 I/O 通道的多级总线

总线结构

1. 支持 CPU、主存和多个 I/O 通道之间的数据传送
2. 支持 I/O 通道和 I/O 控制器，以及 I/O 控制器和设备之间的数据传送

4.4 I/O 软件的实现层次

4.4.1 I/O 软件设计

设计目标

高效率: 改善设备效率，尤其是磁盘 I/O 操作的效率。

通用性: 用统一的标准来管理所有设备。

设计思路

把软件组织成层次结构，低层软件用来屏蔽硬件细节，高层软件向用户提供简洁、友善的界面。

设计原则

1. 设备无关性: 编写访问文件的程序与具体设备无关
2. 出错处理: 低层软件能处理的错误不让高层软件感知
3. 同步/异步传输: 支持阻塞和中断驱动两种工作方式
4. 缓冲技术: 建立数据缓冲区，提高吞吐率

4.4.2 I/O 软件层次结构

4.5 I/O 软件的实现

4.5.1 I/O 中断处理程序

概述

• 位于 OS 底层，与硬件设备密切相关，与系统其余部分尽可能少地发生联系
• 进程请求 I/O 操作时，通常被挂起，直到数据传输结束后并产生 I/O 中断时，操作系统接管 CPU 后转向中断处理程序
• 当设备向 CPU 提出中断请求时，CPU 响应请求并转入中断处理程序

功能

检查设备状态寄存器内容，判断产生中断的原因，根据 I/O 操作的完成情况进行相应的处理。

• （错误）如果数据传输有错，向上层软件报告设备的出错信息，实施重新执行
• （正常结束）如果正常结束，唤醒等待传输的进程，使其转换为就绪态
• （未结束）如果有等待传输的 I/O 命令，通知相关软件启动下一个 I/O 请求

4.5.2 设备驱动程序

概述

• 设备驱动程序包括与设备密切相关的所有代码
• 从独立于设备的软件中接收并执行 I/O 请求
  • 逻辑 I/O（用户提交）转化为物理 I/O
  • 监督设备是否正确执行，管理数据缓冲区，进行必要的纠错处理

设备驱动程序与中断处理程序的区别

中断处理程序: 响应并原子处理 I/O 中断

设备驱动程序: 负责设备中具体的处理细节

功能

• 设备初始化
  • 在系统初次启动或设备传输数据时，预置设备和控制器以及通道状态
• 执行设备驱动例程
  • 负责启动设备，进行数据传输
  • 对于具有通道方式的设备，还负责生成通道指令和通道程序，启动通道工作
• 调用和执行中断处理程序
  • 负责处理设备和控制器及通道所发出的各种中断

层次

每个设备驱动程序只处理一种设备，或者一类紧密相关的设备。

整体驱动程序

• 直接向 OS 提供接口和控制硬件，适用于功能简单的驱动程序，效率较高，但较难迁移

分层驱动程序

• 将驱动程序分成多层，放在栈中，系统接到 I/O 请求时先调用栈顶的驱动程序，栈顶的驱动程序可以直接处理请求或向下调用更低层的驱动程序，直至请求被处理。
• 适用于功能复杂、重用性要求较高的驱动程序，结构清晰且便于移植，但会增加一部分系统开销。

4.5.3 独立于设备的 I/O 软件

执行适用于所有设备的常用 I/O 功能，并向用户层软件提供一致性接口。

功能

1. 设备命名: 通过路径名寻址设备
2. 设备保护: 检查用户是否有权访问所申请设备
3. 提供与设备无关的数据单位: 字符数量，块尺寸
4. 缓冲技术: 传输速率，时间约束，不能直接送达目的地
5. 设备分配和状态跟踪: 分配不同类型的设备
6. 错误处理和报告: 驱动程序无法处理的错误

4.5.4 用户空间的 I/O 软件

库函数

• 一小部分 I/O 软件不在 OS 中，是与应用程序链接在一起的库函数，甚至完全由运行于用户态的程序组成。
• 系统调用通常由库函数封装后供用户使用，封装函数只是将系统调用所用的参数放在合适位置，然后执行访管指令来陷入内核，再由内核函数实现真正的 I/O 操作。

SPOOLing 软件

在内核外运行的系统 I/O 软件，采用预输入、缓输出和井管理技术，通过创建守护进程和特殊目录解决独占型设备的空占问题。

4.6 I/O 缓冲区

4.6.1 I/O 缓冲区概述

提出原因

为了解决 CPU 与设备之间速度不匹配的矛盾，协调逻辑记录大小和物理记录大小不一致的问题（每次读入大小），提高 CPU 和设备并行性，减少 I/O 操作对 CPU 的中断次数，放宽对 CPU 中断响应时间的要求。

缓冲区位置

在内存中开辟的存储区，专门用于临时存放 I/O 操作的数据。

缓冲区的两个操作

• 写操作: 将数据送至缓冲区，直到装满，进程继续计算，同时系统将缓冲区的内容写到设备上。
• 读操作: 系统将设备上的物理记录读至缓冲区，根据要求将当前所需要的数据从缓冲区中读出并传送给进程。

4.6.2 单缓冲区

只有一个缓冲区，I/O设备 $\rightarrow$ OS，OS $\rightarrow$ 用户进程，两个过程不能同时进行，效果一般。

4.6.3 双缓冲区

使用两个缓冲区，I/O 先将数据传给 Buffer1，Buffer1 将数据传给用户的同时，I/O 将数据传给 Buffer2，使得 “I/O设备 $\rightarrow$ OS”，“OS $\rightarrow$ 用户” 两个过程可以并行，效率提高。

4.6.4 循环缓冲区

循环缓冲区，I/O 给 Buffer2 数据，Buffer1 把数据给用户；I/O 给 Buffer3 数据时，Buffer2 把数据给用户。

4.7 设备独立性

设备独立性的本质是对于 “用户申请物理设备” 这一过程再加了一层封装。

4.7.1 设备独立性概念

用户执行作业前不指定物理设备，而是指定逻辑设备，使得用户作业和物理设备分离开，再通过其它途径建立逻辑设备和物理设备之间的映射。

条件

设备管理中需要将逻辑设备名转换为物理设备名，因此系统需要提供逻辑设备名和物理设备名的对应表以供转换使用。

4.7.2 设备独立性优点

• 应用程序通用性更强。
  • 应用程序与具体物理设备无关，系统增减或变更设备时不需要修改源程序。
• 易于应对 I/O 设备故障，提高系统可靠性。
• 增加设备分配的灵活性，更有效地利用设备资源，实现多道程序设计。

4.8 独占型外设的分配

4.8.1 独占型外设概念

独占型外设: 只能由一个进程独占式使用

共享设备: 可以让多个进程同时使用。此类设备的管理主要是驱动调度和实施驱动，一般不必分配。

计算机中绝大多数设备属于独占型设备，如键盘、鼠标，而只有磁盘、光盘、磁带库不属于独占设备。

4.8.2 设备分配方式

静态分配

静态分配: 进程运行前申请

• 实现简单，能够防止系统发生死锁，但会降低设备利用率。

动态分配

动态分配: 进程随用随申请

• 提高设备利用率，但可能发生死锁问题。

例如: 一个系统只有一台磁带机和一台打印机，现在有两个进程 A 和 B 执行时都需要这两台机器，而 A 动态分配到了磁带机，B 动态分配到了打印机，此时就发生了死锁。

4.8.3 设备分配的数据结构

设备表

每条设备都有各自的设备表，用来登记这类设备中的每台物理设备。

内容: 物理设备名、逻辑设备名、占有设备的进程号、是否分配、好/坏标志

设备类表

每类设备对应于设备类表中的一栏。

内容: 设备类、总台数、空闲台数、设备表起始地址

支持设备独立性时才会使用设备类表。

4.9 磁盘的物理结构

4.9.1 磁盘结构

盘片

• 磁盘由多个盘片组成
• 每个盘片被划分为多个同心圆结构的磁道
  • 不同盘片上位于相同位置的磁盘构成的圆柱体称为柱面

扇区、簇（多个相邻扇区）

每个磁道分为固定多个或不等个数的扇区，为了对大量扇区寻址，OS 将相邻扇区组合成簇存储文件。

磁盘物理块地址

• (柱面号, 磁头号, 扇区号): 表示移动臂在哪一个柱面上，磁头定位了哪个盘面，扇区定位了哪一个具体的物理记录。
• (0面0道1扇区): 0盘面，0柱面，1扇区（盘面、柱面从 0 开始编号，扇区从 1 开始编号）

4.9.2 磁盘读取数据流程

磁盘读取数据时，磁头必须定位到指定的磁道上的指定扇区的开始处。

具体过程

1. 寻道: 控制移动臂到达指定柱面，选择磁头号
2. 旋转: 等待要读写的扇区旋转到磁头下
3. 数据传送

4.9.3 磁盘存取时间

磁盘完成数据读写所需时间 = 寻道时间 + 旋转延迟 + 传送时间

$T_a=T_s+\displaystyle\frac{1}{2r}+\displaystyle\frac{b}{rN}$

$T_a:$ 存取时间
$T_s:$ 寻道时间
$r:$ 磁盘旋转速度（转/秒）
$B:$ 要传送的字节数
$N:$ 一个磁道中的字节数

4.10 磁盘的驱动调度

4.10.1 磁盘调度

调度原因

磁盘可能同时接收到若干 I/O 请求，如果随机选择并响应 I/O 请求，可能得到最坏的性能。

调度策略

磁盘存取时间主要是寻道与旋转，因此调度策略主要是移臂调度和旋转调度。

4.10.2 移动臂调度

目的

使移动臂的移动时间最短，从而减少寻道总时间。

（1）先进先出

• 移动臂式随机移动，寻道性能较差
• 按顺序处理请求，对所有进程公平

（2）最短查找时间优先

• 先执行查找时间最短的请求，具有较好的寻道性能
• 存在 “饥饿” 现象

（3）扫描算法 ———— 单向扫描

• 扫描臂总向一个方面扫描，归途中不提供服务
• 适用于不断有大量柱面均匀分布的请求的情形

（4）扫描算法 ———— 双向扫描

该算法是对单向扫描的一个改进。

• 移动臂每次向一个方向移动，遇到最近的 I/O 请求便进行处理，到达最后一个柱面后再向相反方向移动
• 对最近扫描所跨越区域的请求响应较慢

（5）电梯调度

对扫描算法进行一个终版优化。电梯调度算法是解决移臂调度的经典算法。

• 无请求时移动臂停止不动，有请求时按电梯规律移动
• 每次选择沿移动臂的移动方向最近的柱面
• 如果当前移动方向上没有但相反方向有请求时，改变移动方向

4.10.3 旋转调度

目的

使得旋转延迟总时间最少。

（1）循环排序

• 通过优化 I/O 请求排序，在最少旋转圈数内完成位于同一柱面的访问请求。
• 旋转位置测定硬件和多磁头同时读写技术有利于提高旋转调度的效率。

（2）优化分布

通过优化信息在存储空间的排列方式来减少旋转延迟。

• 交替排序
  • 如果沿着磁道按序对扇区编号，可能由于磁盘转速太快，造成处理当前扇区的数据时，下一个扇区已经跳过，需要再转一圈才能继续读数据。
  • 因此，对扇区编号时会间隔编号，例如 2:1 表示相邻编号之间会间隔 1 个扇区，3:1 表示会间隔 2 个扇区。
• 相邻扇区成簇
  • 把相邻多个扇区集中成簇一起读写
• 柱面集中存储
  • 连续记录数据时，先记录在同一柱面的不同磁道上，然后再更换柱面
  • 减少数据读写时的移臂操作

4.11 SPOOLing 系统

SPOOLing 系统的实质就是用缓冲区实现 “输入预先完成，输出成批输出” 的效果，提高效率。

本质上还是将一个 “输入-执行-输出” 的连续过程切分为三个离散过程，来保证 CPU 与外设的并发性。

4.11.1 虚拟设备

虚拟设备: 使用一类物理设备模拟另一类物理设备的技术。

• 内存卡模拟磁盘
• 块设备模拟字符设备
• 输入输出重定向（文件）

4.11.2 SPOOLing 系统结构

五大组成部件

为存放输入、输出数据，系统在磁盘上开辟输入井和输出井，用作缓冲区。

1. 输入井
2. 输出井
3. 预输入程序: 将数据从输入设备传送到磁盘输入井
4. 预输出程序: 将数据从磁盘输出井传送到输出设备
5. 井管理程序: 控制作业和井之间的数据交换（I/O 重定向）

SPOOLing 结构功能

• 预输入
  • OS 将作业需要的输入数据成批从输入设备上预先输入到磁盘的输入缓冲区中暂存
  • 调度作业执行时，作业使用数据不必再启动输入设备，从磁盘的输入缓冲区读入即可
• 缓输出
  • 作业不启动输出设备，只是将输出数据暂存到磁盘输出缓冲区中
  • 作业执行完毕后，数据由 OS 成批输出
• 优点
  • 设备利用率提高
  • 作业运行时间缩短
  • 每个作业都感觉各自拥有所需的独占设备

4.11.3 打印 SPOOLing 系统

打印机空占问题

如果用户进程通过打开打印机的设备文件来申请和使用打印机，往往会造成该进程打开设备文件后长达数小时不用，但其他进程又无法使用打印机。

解决方案

• 打印机守护进程是唯一有特权使用打印机设备的进程
• 打印文件前，用户进程先产生完整的待输出文件，并存放在打印目录下
• 打印机空闲时，启动守护进程，打印待输出文件

4.12 批处理系统作业管理

多道批处理 OS 的作业管理

• 作业说明语言: 用于作业控制的语言
• 作业说明书: 刻画具体作业的控制方式
• 作业状态
  • 输入状态（预输入）
  • 后备状态（空闲）
  • 运行状态（运行）
  • 完成状态（缓输出）
• 作业调度: 从后备状态作业中选择部分进入运行状态（前提是资源充足）
• 作业调度算法: 优先数、短作业、响应比、设备搭配等