操作系统 -- 设备管理

设备管理概述

I/O 设备

I/O 设备，又称输入输出设备、外围设备、外部设备、外设：用于计算机系统与外部世界（如用户、其他计算机或设备）的信息交换或存储。
I/O 擦欧总：内存和外设间的信息传送操作
- 影响计算机系统的通用性和可扩充性
- 影响计算机系统综合处理能力及性价比的重要因素

I/O 设备分类

信息传输视角
- 输入设备：将外界信息输入计算机，如键盘、鼠标、扫描仪等。
- 输出设备：将计算结果输出，如显示器、打印机等。
- 输入输出设备：输入信息并输出信息，如磁盘驱动器、网卡等。
交互功能视角
- 人机交互设备：用于用户与计算机间的交互通信，如鼠标、键盘、显示器等。
- 存储设备：存储大量信息并快速检索，如磁盘驱动器、光盘驱动器等。
- 机机通信设备：用于计算机间通信：如网卡、调制解调器等。
设备管理视角
- 字符设备：以字符为单位进行信息交换，如鼠标、显示器。
- 块设备：以固定大小的数据块为单位进行信息交换，如磁盘。
  - 块石存储介质上连续信息组成的一个区域。
- 网络设备：机机通信设备，例如网卡。
  - 可以抽象为传送字符流的字符设备，也可以抽象为传送连续小块数据的块设备。

设备管理的目标

解决设备和 CPU 速度的不匹配，使主机和设备充分并行工作，提高设备使用效率
屏蔽设备的物理细节和操作过程，配置驱动程序，提供统一界面
- 抽象为裸设备。
- 抽象为设备文件。

设备管理的功能

设备中断处理
缓冲区管理
设备的分配和去配
设备驱动调度
虚拟设备的实现

设备管理的实现层次

I/O 硬件：包括 I/O 设备及其接口线路、控制部件、通道等。
I/O 软件：包括系统 I/O 软件和用户空间 I/O 软件。

I/O 控制方式

设备控制器

为了达到模块化和通用性的设计目标，通常分开设置设备的机械部件和电子部件。
电子部件成为设备控制器，又称为设备适配器、I/O 控制器、I/O 控制接口、I/O 模块、I/O 接口等。
系统于控制器交互，而非与设备交互
设备控制器具体控制设备进行 I/O

设备控制器的功能

设备控制器是 CPU 与设备之间的接口

接收和识别 CPU 或通道发来的命令
实现数据交换
发现和记录设备及自身的状态信息，供 CPU 处理时使用
当连接多台设备时，识别设备的地址

设备控制器组成示意

I/O 控制的轮询方式

处理器向控制器发送 I/O 命令，轮询 I/O 结果。
若设备未就绪，则重复测试过程，直至设备就绪。
执行内存数据交换。
等待 I/O 操作完成后，处理器才可以继续其他操作。

I/O 控制的轮询方式

I/O 控制的中断方式

处理器向控制器发出具体 I/O 命令，然后继续执行后续指令
- 若进程支持异步 I/O，后续指令仍可是该进程中的指令。
- 否则，该进程在这个中断上挂起，处理器执行其他工作。
控制器检查设备状态，就绪后发出中断。
CPU 响应中断，进行中断处理。
中断处理执行内存数据交换。

I/O 控制的中断方式

I/O 控制的 DMA 方式

DMA，Direct Memory Access 直接存储器访问，能够替代处理器来控制主存和设备控制器间的数据交换

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

I/O 控制的 DMA 方式

DMA 方式中的周期窃取

DMA 和 CPU 同时通过总线访问内存，CPU 会把总线的占有权让给 DMA 一个/几个主存周期

周期窃取对 CPU 与主存的数据交换影响不大

数据传送过程是不连续的和不规则的

CPU 大部分情况下与 Cache 进行数据交换，直接访问内存较少

I/O 控制方式的总结

CPU 作用	是否需要等待设备	是否参与内存数据交换
轮询方式	需要	参与
中断方式	不需要	参与
DMA 方式	不需要	不参与

轮询方式：CPU 等待设备就绪，且参与内存数据交换
中断方式：CPU 无需等待设备就绪，响应中断后参与内存数据交换
DMA 方式：CPU 只在 I/O 开始和结束时参与，不参与主存数据交换

I/O 通道

又称为通道控制器、I/O 处理器，用于完成逻辑上独立的 I/O 任务
采用四级连接：处理器、通道、控制器、设备。
- 通道克控制多台同类或不同类的设备
处理器不再执行 I/O 指令，而是在主存中组织通道程序，由 I/O 通道来执行。

I/O 通道的工作流程

CPU 遇到 I/O 任务，组织通道程序，置通道程序地址字 CAW，启动指定通道
通道从 CAW 获得通道程序，控制 I/O 设备进行操作，CPU 执行其他任务
I/O 操作完成后，I/O 通道发出中断，CPU 处理中断，并从通道程序状态字 CSW 获得通道执行情况，处理 I/O 操作

CPU与通道高度并行工作

总线与 I/O

总线的作用：解决 I/O 速度不匹配的问题，I/O 和 CPU 速度不匹配、各个设备之间的 I/O 设备不匹配问题。使主机和设备充分并行，提高系统效率。

单总线结构模型

将 CPU、主存和 I/O 模块连接到同一总线
优点：结构简单，易于扩充
缺点：共用总线；设备多的时候总线压力大，传输的时延长，且慢速外设占用的带宽多。

单总线结构模型

三级总线模型

主线和 Cache 通过主存总线连接，主存总线和扩展总线上的 I/O 设备间通过扩展总线接口缓冲。
优点：主存与 I/O 之间的数据传送、处理器的内存活动分离；可以支持更多的 I/O 设备
缺点：不适用于 I/O 设备数据速率相差太大的情形

三级总线模型

南桥与北桥

通过存储总线、PCI 总线、E(ISA) 总线分别连接主存、高速 I/O 设备和低速 I/O 设备
优点：可以支持不同数据速率的 I/O 设备

南桥与北桥

基于通道的服务器总线模型

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

基于通道的服务器总线模型

I/O 软件的实现层次

I/O 软件的设计目标

设计目标：

高效率：改善设备效率，尤其是磁盘 I/O 操作的效率
通用性：用统一标准来管理所有设备

设计思路：把软件组织成层次结构，底层软件用来屏蔽硬件细节，高层软件向用户提供简洁、友善、统一的界面

I/O 软件设计要考虑的问题

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

I/O 软件的层次结构

I/O 软件的实现

I/O 中断处理程序

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

I/O 中断处理程序的功能

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

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

设备驱动程序

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

设备驱动程序的功能

设备初始化：在设备传输数据时，预置设备、控制器以及通道状态
执行设备驱动例程：负责启动设备，进行数据传输；对于通道，还负责组织通道程序，启动通道工作
执行与设备相关的具体中断处理：负责处理设备、控制器及通道所发出的各种具体中断

设备驱动程序的层次

每个设备驱动程序原则只处理一种设备，或者一类紧密相关的设备
设备驱动程序可以分层实现
- 高层/处理类设备，低层/处理具体设备
- 系统建立栈，接到I/O请求时先调用栈顶的驱动程序，然后继续向下调用低层驱动程序，直至所有物理操作被处理
- 这一方式使设备驱动的实现结构清晰、便于移植，但会增加一部分系统开销

独立于设备的 I/O 软件

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

设备命名：通过路径名寻址设备
设备保护：用户是否有权访问设备
提供与设备无关的数据单位：字符/块
缓冲技术：调整 CPU 与 I/O 速度不匹配
分配和状态跟踪：分配设备
错误处理/报告：驱动无法处理的错误

用户空间的 I/O 软件

库函数：一部分 I/O 软件可以使用库函数实现，放在操作系统内核之外，运行时与应用程序链接
虚拟设备软件：用一类设备模拟另一类设备的仿真I/O软件

I/O 缓冲

设置 I/O 缓冲的目的

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

I/O 缓冲区

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

写操作：将数据送至缓冲区，直到装满或需要写出，待适当时候系统将缓冲区内容写到设备上
读操作：系统将设备上的物理记录读至缓冲区，根据要求将当前所需要的数据从缓冲区中读出并传送给进程

单缓冲技术

操作系统在主存系统区中开设一个缓冲区

输入：先把数据读至缓冲区，再把缓冲区数据送至用户区，应用程序处理数据；如此往复，系统继续读入后继数据
输出：把数据从用户区传送到缓冲区，再将数据输出到设备，应用程序继续请求输出

单缓冲技术

双缓冲技术

操作系统在主存系统区开设两个缓冲区

输入：先把数据输入缓冲区 1，再从缓冲区 1 把数据传到用户去，供应用程序处理；（同时设备可将数据传送到缓冲区 2）
输出：现将数据从用户区传送到缓冲区 1，再将数据传送到设备；（同时应用程序可将数据传送到缓冲区 2）

双缓冲技术

循环缓冲技术

OS分配一组缓冲区，每个缓冲区有指向下个缓冲区的链接指针，构成循环缓冲
继续调节设备和进程速度不匹配问题

循环缓冲技术

设备独立性

作业执行前对设备提出申请的时候，指定某台具体物理设备会让设备分配变得更加简单。（微型计算机 OS 多采用这种方式）
缺点：如果所指定设备出现故障，即便计算机系统中有同类设备也不能运行

设备独立性及其实现

设备独立性：用户通常不指定物理设备，而是指定逻辑设备，使得用户进程和物理设备分离开来，再通过其它途径建立逻辑设备和物理设备之间的映射。
设备管理中需要将逻辑设备名转换为物理设备名，为此系统需要提供逻辑设备名和物理设备名的对应表以供转换使用。

设备独立性的优点

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

独占型外围设备的分配

独占型外围设备：一个设备一次只能由一个进程独占使用

设备分配方式

静态分配：进程运行前申请。实现简单，能够防止系统发生死锁，但会降低设备利用率
动态分配：进程随用随申请。提高设备的利用率

设备分配的数据结构

设备类表
- 每类设备对应于设备类表中的一栏
- 包括：设备类、总台数、空闲台数、设备表起始地址等
- 支持设备独立性时使用
设备表
- 每类设备都有各自的设备表，用来登记这类设备中的每台物理设备
- 包括：物理设备名，逻辑设备名，占有设备的进程，分配标识，好/坏标志等

磁盘的物理结构

磁盘一般由多个盘片组成
每个盘片一般有两个盘面
盘面包括多个同心圆结构的磁道，不同盘面上位于相同位置的磁道构成助眠
每个磁道分为固定多个扇区，相邻扇区组合成簇
物理块地址：
- 柱面号、磁头号、扇区号
- 0面0道1扇区：面指磁头而不是指柱面

磁盘结构

磁盘读写数据的方式

读写数据的时候，磁头必须要定位到指定磁道上的指定扇区的开始处，过程如下：

寻道：控制移动臂到达指定的柱面
旋转：等待要读写的扇区转动到磁头下方
选择磁头号，机械能数据的传送

磁盘存取的时间

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

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

磁盘的驱动调度

磁盘可能同时收到若干的 I/O 请求，若是随机响应 I/O 请求，可能会得到很坏的性能
驱动调度：OS 的磁盘调度策略，即按照最佳次序执行处理访问磁盘的多个 I/O 请求，以减少磁盘访问的总处理时间
驱动调度策略包括：
- 移臂调度
- 旋转调度

移臂调度及算法

目的：使移动臂的移动时间最短，从而减少寻道总时间
移臂调度算法：
- 先来先服务（First Come First Service, FCFS）：移臂距离大，性能不好（即如果两个相邻的任务的距离比较远，由于先来先服务的特性，会移动较远的距离）
- 最短查找时间优先（最小短距法）
  - 先执行查找时间最短的请求，具有较好的寻道性能
  - 存在“饥饿”现象（由于找的都是最短的，因此会偏于寻找一边的任务，另一边较远的将会等待较长的时间）
- 扫描算法（SCAN）
  - 单向扫描：移动臂向一个方向扫描，归途不提供服务，适用于不断有均匀分布的大量柱面请求的情形
  - 双向扫描：移动臂每次向一个方向移动，遇到最近的 I/O 请求便进行处理，到达最后一个柱面后再向相反方向移动
  - 电梯调度：双向扫描的改进，当前移动方向没有访问请求的时候，就改变移动方向

旋转调度

目的：使得旋转延迟的总时间最少
循环排序：
- 通过优化 I/O 请求排序，在最少旋转圈数内完成位于同一柱面的访问请求
- 旋转位置测定硬件和多磁头同时读写技术有利于提高旋转调度的效率
优化分布
- 通过信息在存储空间的排列方式来减少旋转延迟
- 交替排序：由于磁盘匀速运转，可能处理当前扇区数据的时候，下个扇区已经跳过。因此，可以对扇区间隔编号，如交叉因子为 $n:1$ 表示相邻编号间会间隔 $n-1$ 个扇区
- 把相邻扇区集中成簇读写
- 按柱面集中存储数据（另一种集簇方式），可以减少数据读写时的移臂操作。

Reference

南京大学软件学院本科三年级课程《计算机与操作系统》