《操作系统》IO管理

IO管理功能

状态跟踪：要能实时掌握外部设备的状态
设备存取：要实现对设备的存取操作
设备分配：在多用户环境下，负责设备的分配与回收
设备控制：包括设备的驱动，完成故障的中断处理

I/O软件层次结构

四种结构

用户层IO软件
- 用户通过统一的接口发送命令
- 如发送read命令
设备独立性软件
- 对用户命令进行解析
- 如解析read命令
设备驱动程序
- 负责执行OS发出的IO命令，针对不同的硬件将命令解析为指令
- 若更换物理设备，只需要修改设备驱动程序，不需要修改应用程序
- 如解析好的read命令转换为指令
- 如计算磁盘的柱面号，磁头号，扇区号
中断处理程序
- 中断正在运行的进程，转而执行用户命令
- 如中断当前进程，执行相关指令

层次结构的特点

每层都是利用其下层提供的服务，完成输入/输出功能中的某些子功能
屏蔽子功能实现的细节，向高层提供服务
仅最底层才涉及硬件的具体特性

应用程序IO接口分类

字符设备接口
- 字符设备是指数据的存取和传输都是以字节为单位的设备
- 字符设备都属于独占设备
块设备接口
- 块设备是指数据的存取和传输都是以数据块为单位的设备，如磁盘
- 磁盘设备的IO常用DMA方式
网络设备接口
- 许多OS提供的网络IO接口为网络套接字接口
阻塞/非阻塞IO
- 大多数OS提供的IO接口都是采用阻塞IO

设备的分类

按信息交换单位分类
- 块设备
  - 传输速度较高 + 可寻址 + 可随机读写任一块
  - 属于有结构设备，如硬盘，磁盘，USB
- 字符设备
  - 传输速率低 + 不可寻址 + 时常采用中断IO方式
  - 属于无结构类型，如交互式终端机，打印机，鼠标
按传输速度分类
- 低速设备
  - 键盘，鼠标
- 中速设备
  - 激光打印机
- 高速设备
  - 磁盘机，光盘机
按设备特性分类
- 独占设备
  - 一个时段只能分配给一个进程
  - 所有字符设备都是独占设备
  - 速度慢，利用率低
  - 如输入机，打印机，磁带机等
- 共享设备
  - 一段时间内允许多个进程同时访问的设备
  - 共享设备必须是可寻址和可随机访问的设备
  - 软硬盘、磁盘、光盘等块设备都是共享设备
- 虚拟设备
  - 通过虚拟软件技术将独占设备改造成共享设备
  - 如通过SPOOLing技术将一台打印机虚拟成多台打印机
  - 本质上还是独占设备
按访问顺序
- 可以顺序访问的
  - 磁带
- 可以随机访问的（直接访问）
  - 光盘，磁盘，Upan
- 两者都可以的
  - 光盘，磁盘

设备控制器

主要功能

接收和识别CPU发来的命令
数据交换（设备和控制器的数据交换 + 控制器和主存数据交换）
标识和报告设备的状态，以供CPU处理
地址识别；数据缓冲；差错控制
设备管理器不属于操作系统范畴，属于硬件

设备控制器组成

设备控制器与CPU的接口
- 用于实现CPU与控制器之间的通信
- CPU通过控制线发出命令
- 通过地址线来指明要操作的设备
- 通过数据线来输入输出数据
设备控制器与设备的接口
- 用于实现控制器和设备之间的通信
IO逻辑
- IO逻辑用于负责接收和识别CPU的各种命名（如地址译码）
- 根据CPU的命令对相应设备发送命令
- 用于实现设备控制功能
组成图

设备控制器的三种寄存器（可被CPU直接访问的寄存器，也叫IO端口）

数据寄存器
- CPU向IO设备写入需要传输的数据
命令/控制寄存器
- 比如要打印内容为Hello，CPU需要先发送一个H字符给对应的IO设备
- CPU发送一个命令，告诉IO设备，要进行输入/输出操作，于是就会交给IO设备区工作
- 任务完成后，会将状态寄存器里面的状态标记为完成
状态寄存器
- 目的是告诉CPU现在已经在工作或工作已经完成
- 如果已经在工作状态，CPU再发送数据或者命令过来，都是无效的
- 直到前面的工作已经完成，状态寄存器标记成已完成，CPU才能发送下一个字符和命令
CPU与IO端口的通信方式
- 端口IO（独立编制）
  - 每个控制寄存器被分配一个IO端口
  - 可通过特殊的汇编指令操作这些寄存器，如in/out类似的指令
- 内存映射IO（统一编制）
  - 将所有控制寄存器映射到内存空间中，从而像读写内存一样读写数据缓冲区

设备控制方式

外围设备和内存之间的控制方式
用于控制设备和内存或CPU之间的数据传送

程序直接控制方法

一种轮询等待方法，让CPU一直查询寄存器的状态，直到状态标记为完成

中断驱动程序

有一个硬件的中断控制器，当设备完成任务后触发中断到中断控制器，中断控制器就通知CPU，例如键盘
一个中断产生了，CPU需要停下当前手里的事情来处理中断
- 软中断，例如代码调用INT指令触发
- 硬件中断，硬件通过中断控制器触发
中断的方式对频繁读写数据的磁盘不友好，因为CPU经常被打断，会占用CPU大量时间，可使用DMA解决

DMA方式（Direct Memory Access）

概念
- 可以使设备在CPU不参与的情况下，自行完成把设备IO数据放入内存的操作
- 实现该功能需要有DMA控制器硬件的支持
工作方式
- CPU对DMA控制器下发指令，告知读取数据量和数据在内存中放置的目标位置
- DMA控制器向磁盘控制器发出指令，通知它从磁盘读取数据到内部的缓冲区中，接着磁盘控制器将缓冲区的数据传输到内存
- 磁盘控制器完成把数据传输到内存的操作后，磁盘控制器在总线上发出一个确认成功的信号到DMA控制器
- DMA控制器收到信号后，DMA控制器发出中断通知CPU指令完成，CPU就可以直接使用内存里的数据了
工作流程
- 初始化DAM控制器并启动磁盘
- 从磁盘传输一块数据到内存缓冲区
- DMA控制器发送中断请求
- 执行DMA结束中断服务程序
特性
- 整个过程仅仅在开始和结束时需要CPU干预
- 每个DMA控制器对应一台设备与内存传递数据
- DMA方式主要用于块设备，磁盘尤其是典型的块设备
示例图

通道控制方式

过程
- 设置通道后，CPU只需要向通道发送一条IO指令，通道在收到该指令后，便从内存中取出本次要执行的目标通道程序，然后执行该通道程序
- 仅当通道完成规定的IO任务后，才向CPU发出中断信号
特性
- CPU、通道、IO设备可并行工作，资源利用率很高
- 实现复杂，需要专门硬件支持
- 一个通道可控制多台设备与内存的数据交换
分类
- 字节多路通道
  - 通常包含许多非分配型字通道，数量可以达到几十到几百个，每个通道连接一台IO设备，并控制该设备的IO操作
  - 常用于连接大量低速或中速IO设备
示例图

四种方式比较

IO控制方式	过程	CPU干预频率	每次传输数据的单位	数据流向
程序直接控制方式	CPU发出指令后需要不断轮询	极高	字	设备-CPU-内存内存-CPU-设备
中断驱动方式	CPU发出IO指令后可以做其他事，本次IO完成后设备控制器发出中断信号	高	字	设备-CPU-内存内存-CPU-设备
DAM方式	CPU发出IO命令后可以做其他事，本次IO完成后DMA控制器发出中断信号	中	块	设备-内存内存-设备
通道控制方式	CPU发出IO指令后可以做其他事，通道会执行通道程序以完成IO，完成后通道向CPU发出中断信号	低	一组块	设备-内存内存-设备

优缺点
- 每个阶段的优点都是解决上一个阶段的最大缺点，总体来说就是尽量减少CPU对IO过程的干预，把CPU从繁杂的IO控制事务中解放出来，以便更多地去完成其他任务

设备分配

设备分配指根据用户的IO请求分配所需的设备
计算机系统为每台设备确定一个设备的绝对号以便区分和识别设备

设备分配策略

分配原则
- 设备固有属性决定了设备的使用方式（充分发挥设备的使用效率，尽可能让设备忙碌）
- 设备独立性可以提高设备分配的灵活性和设备的利用率（设备独立性是指用户使用设备的透明性，即用户程序与实际使用的物理设备无关）
- 设备安全性可以保证分配设备时不会导致永久阻塞（避免造成进程死锁）
分配方式
- 静态分配
  - 对独占设备的分配
  - 在作业执行前分配
  - 不会出现死锁
  - 设备使用率低
- 动态分配
  - 在进程执行中分配，通过系统调用发送请求，根据具体策略分配设备
  - 分配算法不好时会发生死锁
  - 设备利用率高
分配算法
- 先请求先分配，优先级高者分配（类调度算法）

设备分配安全性

定义
- 设备分配安全性是指设备分配中应防止发生进程死锁
安全分配方式
- 为进程分配一个设备后就将该进程阻塞，本次IO完成后才将进程唤醒
- 安全分配方式在一个时间段内每个进程只能使用一个设备
- 优点：破坏了请求等待条件，不会发生死锁
- 缺点：对于一个进程来说，CPU和IO设备只能串行工作，系统资源利用率低
不安全分配方式
- 进程发出IO请求后，系统为其分配IO设备，进程可继续执行，之后还可以发出新的IO请求，只有某个IO请求得不到满足时才将进程阻塞
- 不安全分配方式一个进程可以同时使用多个设备
- 优点：进程的计算任务和IO任务可以并行处理，使进程推进
- 缺点：有可能发生死锁

设备分配依据的数据结构

设备、控制器、通道间的关系
设备控制表（DCT）
- 系统为每个设备配置一张DCT
- 用于记录设备情况
控制器控制表（COCT）
- 每个设备控制器都会对应一张COCT
- 操作系统会根据COCT的信息对控制器进行操作管理
通道控制表（CHCT）
- 每个通道都会对应一张CHCT
- 操作系统会根据CHCT的信息对通道进行操作管理
系统设备表（SDT）
- 记录了系统中全部设备的情况，每个设备对应一个表目

逻辑设备名到物理设备名的映射

目的
- 为了提高设备分配的灵活性和利用率
- 分别实现IO重定向
- 引入设备独立性
定义
- 设备独立性：只应用程序独立于具体使用的物理设备/用户在编程时使用的设备与实际设备无关
- 逻辑设备表LUT：将逻辑设备名映射为物理设备名
- LUT表项包括：逻辑设备名，物理设备名，设备驱动程序入口地址
分类
- 每个系统只设置一个张LUT
  - 适用于单用户系统
- 每个用户设置一张LUT
  - 用户登录时，系统为用户建立一个进程，同时建立一张LUT
好处
- 方便用户编程
- 使程序运行不受具体机器环境的限制
- 便于程序移植

缓冲区管理

引入目的
- 缓和CPU和IO设备之间速度不匹配的矛盾【主要矛盾】
- 提高CPU与IO设备之间的并行性
- 减少对CPU的中断频率，放宽了CPU对中断响应时间的限制
实现方法
- 采用硬件缓冲器
- 采用缓冲区（位于内存）
主要考虑的问题
- 缓冲区是一种临界资源，使用时要考虑同步与互斥的问题
需要使用缓冲技术的IO操作
- 使用鼠标
- 多任务操作系统下的磁带驱动器（假设没有设备预分配）
- 包含用户文件的磁盘驱动器
- 使用存储器映射IO，直接和总线相连的图形卡

缓冲技术分类及计算

T时间：数据从磁盘到缓冲区
M时间：数据从缓冲区到用户
C时间：CPU对一块数据处理的时间
单缓冲
- 流程
  - Max(C,T) + M
- T > C 时，处理一块数据需要（T + M）
- T < C 时，处理一块数据需要（C + M）
双缓冲
- 流程
  - Max(T,C + M)
- T > C + M 时，平均处理一个数据块需要时间T
- T < C + M 时，平均处理一个数据块需要时间(C + M)
循环缓冲
- 将多个大小相等的缓冲区连接成一个循环队列
- 下图中橙色表示已充满数据的缓冲区，绿色表示空缓冲区
- 当需要向缓冲区中充入数据时，只要找到in指针指向的空缓冲区，向其中充入数据，然后再把in指针指向下一个空缓冲区
- 当需要取出满缓冲区的内容时，找到out指针执行的满缓冲区，读取完数据后，将指针指向下一个满缓冲区
缓冲池
- 缓冲池由系统中共用的存放在主存中的缓冲区组成，被认为是最好的方法
- 缓冲区根据使用情况分为
  - 空缓冲队列
  - 输入队列：存储的是从设备发送给内存的数据
  - 输出队列：存储的是从内存发给设备的数据
- 根据一个缓冲区在实际运算中扮演的功能不同分为四种工作缓冲区
  - 用于收容输入数据的工作缓冲区（hin）
  - 用于提取输入数据的工作缓冲区（sin）
  - 用于收容输出数据的工作缓冲区（hout）
  - 用于提取输出数据的工作缓冲区（sout）

SPOOLing技术（假脱机技术）

脱机技术和假脱机技术对比

脱机技术
- 引入目的：缓解设备与CPU的速度矛盾，实现预输入，缓输出
- 组成：外围机 + 更高速的设备（磁带）
- 输入：在外围控制机的控制下，慢速输入设备先将数据输入到更快速的磁带上，之后主机就可以快速地从磁带上读入数据，缓解速度矛盾
- 输出：先将数据输出到快速的磁带上，之后通过外围控制机控制磁带将数据一次输出到慢速的设备上
- 假脱机技术
  - 又SPOOLing技术，软件的方式模拟脱机技术，不需要外围机，一项将独占设备改造成共享设备的软件技术

SPOOLing技术运行过程

输入进程和输出进程
- 预输入程序管理
  - 用于模拟脱机技术中的外围控制机
  - 需要和用户进程并发执行才可以模拟脱机技术，所以要实现该技术需要多道程序技术的支持
输入井和输出井
- 井输入程序管理
  - 用于模拟脱机技术中的磁带
输入缓冲区和输出缓冲区
- 缓输出程序管理
  - 输入缓冲区用于暂存从输入设备输入的数据，之后再转存到输入井中
  - 输出缓冲区用于暂存从输出井传送的数据，之后再传送到输出设备上
流程图

SPOOLing系统的优特点

加快作业执行的速度，提高IO速度，将对低速IO设备执行的IO操作转变为对磁盘缓冲区中数据的存取
使独占设备变为共享设备，且没有为任何进程分配设备
提高了独占设备的利用率，缓和了CPU和低速IO设备之间速度不匹配的矛盾
实现了虚拟设备功能，对每个进程而言，都认为自己独占了一个设备
以空间换时间，需要磁盘空间（输入输出井）和内存空间（输入输出缓冲区）

SPOOLing技术实例：共享打印机

打印机为独占设备，只允许各个进程串行使用设备，一段时间内只能满足一个进程的要求
- 流程
  - 多个用户输出打印请求时，系统会接受请求，但不会真正把打印机分配给它们，而是由假脱机管理进程为每个进程做两件事
    - 在磁盘输出井中为进程申请一个空间磁盘块，之后假脱机管理进程会把进程要打印的数据块送入刚申请的空闲磁盘块中【打印结果优先送入磁盘固定位置】
    - 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（用于说明用户的打印数据存放位置等信息），再将该表挂到假脱机文件队列上
  - 打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，根据表中的要求将打印数据从输出井传送到输出缓冲区，再输出到打印机打印
  - 虽然系统中只有一台打印机，但每个进程提出打印请求时，系统都会为其在输出井中分配一个存储区（类似于逻辑设备）
  - 每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享

磁盘

基本概念和结构

基本结构
- 磁盘
  - 磁盘表面由一些磁性物质组成，可以用这些磁性物理记录二进制数据
- 磁道
  - 磁盘表面被划分成的一个个磁道
- 扇区
  - 一个磁道又被划分为一个个扇区，每个扇区就是一个磁盘块
  - 每个扇区的数据量相同（如1KB）
- 簇
  - 一组扇区
- 盘面
  - 磁盘由多个盘片叠成的，每个盘片有两个盘面，每个盘面对应一个磁头，所有的磁头都连在同一个磁臂上
  - 磁臂可以沿着盘面做径向运动，从而带动磁头到达不同的磁道实现对不同扇区的读写操作
- 柱面
  - 所有盘面中的相对位置相同的磁道组成了柱面
磁盘中读写数据
- 需要借助磁头
  - 将磁头移动到想要读写的扇区所在的磁道
  - 磁盘转动，让目标扇区从磁头底下划过，才能完成对扇区的读写操作
磁盘的物理地址
- 使用（柱面号，盘面号，扇区号）来定位任意一个磁盘块
- 文件数据存放在外存中的几号块，此处块号就可以转换为（柱面号、盘面号、扇区号）的地址形式
- 根据物理地址读取一个块
  - 柱面号移动磁臂，让磁头指向指定柱面
  - 激活指定盘面对应的磁头
  - 磁盘旋转的过程，指定的扇区会从磁头底下划过，这样就完成了对指定扇区的读写
磁盘分类
- 根据磁头是否可以活动划分
  - 活动头磁盘
  - 固定头磁盘
- 根据盘面是否可以更换划分
  - 可换磁盘
  - 固定盘磁盘

磁盘管理

格式化流程
- 低级/物理格式化
  - 在磁盘可以存储数据之前，将它划分为扇区，便于磁盘控制器进行读写操作
- 分区
  - 将磁盘划分为由一个或多个柱面组成的分区（如C区，D区）
  - 每个分区的起始扇区和大小都记录在磁盘主引导记录的分区表中
- 高级/逻辑格式化
  - 创建文件系统的根目录
  - 对保存空闲磁盘块信息的数据结构进行初始化
引导块
- 计算机启动时需要运行一个初始化程序（自举程序），该程序放在ROM中
- 启动系统磁盘（具有启动分区的磁盘）
坏快
- 对坏块的处理本质上是用某种机制使系统不去使用坏块

固态硬盘SSD

特性
- 一个SSD由一个或多个内存芯片和闪存翻译层组成
- SSD由半导体存储器构成，没有移动的部件
- SSD是基于闪存的存储技术
- SSD随机读写性能明显高于磁盘，优势主要体现在随机存取上
- SSD随机写较慢，但不比常规硬盘差
磨损均衡
- 引入目的：弥补SSD的寿命缺陷
- 动态磨损均衡：写入时自动选择较新的闪存块
- 静态磨损均衡：即使无写入操作，SSD也会自动检测并进行自动数据分配，让新的闪存块进行大部分的读写任务

磁盘调度算法

目的
- 提高磁盘的访问性能，通常做法是优化磁盘的访问请求顺序来做到
- 寻道时间是磁盘访问最耗时的部分，如果请求顺序优化得当，可节省一些不必要的寻道时间，从而提高磁盘访问性能
- 绝大多数OS为了改善磁盘访问时间，以簇为单位进行空间划分

一次磁盘读/写操作需要的时间

寻找时间（寻道时间）$T_S$
- 在读/写数据前，需要将磁头移动到指定磁道所花费的时间
  - 寻道时间分为两步
    - 启动磁头臂消耗的时间S
    - 移动磁头消耗的时间，假设磁头匀速移动，每跨越一个磁道消耗时间为m，共跨越n条磁道
  - $T_S = S + m \times n$
延迟时间$T_R$
- 通过旋转磁盘，使磁头定位到目标扇区所需要的时间
- $T_R = \left(\frac{1}{2}\right) \times \left(\frac{1}{r}\right) = \frac{1}{2r}$
- 由于$\frac{1}{r}$就是转一圈所需的时间，找到目标扇区平均需要转半圈，因而要再乘以$\frac{1}{2}$
传输时间$T_R$
- 从磁盘读出或向磁盘中写入数据所经历的时间
- 假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N
- $T_R = \left(\frac{b}{N}\right) \times \left(\frac{1}{r}\right) = \frac{b}{rN}$
总平均时间
- $T_a = T_S + \frac{1}{2r} + \frac{b}{rN}$
- 无法通过操作系统优化延迟时间和传输时间，所以只能优化寻找时间

磁盘调度算法

假设存在一个请求序列，每个数字代表磁道的位置
- 98,183,37,122,14,124,65,67,初始磁头当前位于第53磁道
先来先服务算法（FCFS）
- 思想
  - 先到来的请求，先被服务
- 优点
  - 公平
  - 请求访问的磁道若比较集中则算法拥有不错的性能
- 缺点
  - 简单粗暴
  - 大量进程竞争使用磁盘时，请求访问的磁道可能十分分散，此时由于寻道时间过长，显得算法性能表现很差
- 处理顺序
  - 98,183,37,122,14,124,65,67
- 寻道示例图
最短寻找时间优先（SSTF）
- 思想
  - 优先选择从当前磁头位置所需寻道时间最短的请求
- 优点
  - 贪心算法的思想，只选择局部最优，并非总体最优
  - 比FCFS效果好
- 缺点
  - 存在饥饿现象
  - 饥饿原因：磁头在一小块区域内来回移动
- 处理顺序
  - 65,67,37,14,98,122,124,183
- 寻道示例图
扫描/电梯算法（SCAN）
- 思想
  - 磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向
- 优点
  - 性能较好，寻道时间较短
  - 不会产生饥饿现象
- 缺点
  - 中间部分的磁道相比其他部分响应频率要高，即每个磁道的响应频率存在差异
- 处理顺序
  - 假设扫描调度算法先朝磁道号减少的方向移动
  - 磁头先响应左边的请求，到达最左端后才开始反向移动，响应右边的请求
  - 37,14,0,65,67,98,122,124,183
- 寻道示例图
C-SCAN算法
- 思想
  - 只有磁头朝某个特定方向移动时，才处理磁道访问请求
  - 返回时直接不处理任何请求快速移动到最靠边缘的磁道（磁头复位）
  - 磁头只响应一个方向上的请求
- 优点
  - 对于各个位置磁道响应频率很平均
- 缺点
  - 相比于扫描算法，平均寻道时间更长
- 处理顺序
  - 假设循环扫描调度算法先朝磁道增加的方向移动
  - 磁头先响应了右边的请求
  - 直到碰到了最右端的磁道199，立即不响应任何请求地回到磁盘的开始处
  - 直到到达最开始的磁道后，才继续顺序响应右边的请求
  - 65,67,98,122,124,183,199,0,14,37
- 寻道示例图