计算机操作系统(4) 设备管理
第四章 设备管理
4.1 设备管理基础
4.1.1 设备管理概述
I/O设备
- I/O设备，又称输入输出设备、外围设备、外部设备、外设
- 用于计算机系统与外部世界(如用户、其它计算机或设备)的信息交换或存储
- I/O操作：内存和I/O设备之间的信息传送操作
- 影响计算机的通用性和可扩充性
- 影响计算机系统综合处理能力及性价比的重要因素
I/O设备的分类
- 信息传输视角
- 输入设备：将外界信息输入计算机
- 例如：键盘，鼠标，扫描仪等
- 输出设备：将计算结果输出
- 例如：显示器，打印机等
- 输入输出设备：输入信息并输出信息
- 例如：磁盘驱动器，网卡等
- 输入设备：将外界信息输入计算机
交互功能视角
- 人机交互设备：用于用户与计算机间的交互通信
- 例如：鼠标，键盘，显示器等
- 存储设备：存储大量信息并快速检索
- 例如：磁盘驱动器，光盘驱动器等
- 机机通信设备：用于计算机间通信
- 例如：网卡，调制解调器等
- 人机交互设备：用于用户与计算机间的交互通信
设备管理视角
- 字符设备：以字符为单位进行信息交换，例如鼠标、显示器
- 块设备：以固定大小的数据块为单位进行信息交换，例如磁盘
- 块是存储介质上连续信息组成的一个区域
- 网络设备：机机通信设备，例如网卡等
- 可抽象为传送字符流的字符设备，也可以抽象为传送连续小块数据的块设备
设备管理的目标
解决设备和CPU速度的不匹配，使主机和设备充分并行工作，提高设备使用效率
屏蔽设备的物理细节和操作过程，配置驱动程序，提供统一界面
- 抽象为裸设备
- 抽象为设备文件
- 操作系统将所有设备(如磁带机、打印机、显示器和终端等)都定义为文件，统一在文件系统之下，赋予文件属性，对设备的操作就类似于对文件的操作，其优点:
- 尽可能统一文件和设备的I/O处理
- 尽可能把设备文件和普通文件纳入同一保护机制下
- 为了方便用户或高层进程使用，设备管理还对各种设备进行抽象，配置驱动程序，提供统一界面，屏蔽设备的物理细节和操作过程
设备管理的功能
- 设备中断管理
- 缓冲区管理
- 设备的分配和去配
- 设备驱动调度
- 虚拟设备的实现
设备管理的层次
- I/O硬件
- I/O设备及其接口线路
- 控制部件
- 通道
- I/O软件
- 系统I/O软件
- 用户空间I/O软件
4.1.2 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，后续指令可以仍是该进程中的指令
- 否则，该进程在这个中断上挂起，处理器执行其他工作
- 控制器检查设备状态，就绪后发出中断
- CPU响应中断，进行中断处理
- 中断处理执行内存数据交换
I/O控制的DMA方式
- 直接存储器访问(Direct Memory Access)
- DMA模块
- 能够替代处理器来控制主存和设备控制器之间的数据交换
DMA的工作流程
- 处理器向DMA模块发出I/O命令
- 处理器继续执行其它工作，DMA模块负责传送全部数据
- 数据传送结束后，DMA中断处理器
DMA方式中的周期窃取
- 当DMA和CPU同时经总线访问内存时，CPU会把总线的占有权让给DMA一个或几个主存周期
- 周期窃取对CPU与主存的数据交换影响不大
- 数据传送过程是不连续的和不规则的
- CPU大部分情况下与Cache进行数据交换，直接访问内存较少
I/O控制方式的总结
- 轮询方式：CPU等待设备就绪，且参与内存数据交换
- 中断方式：CPU无需等待设备就绪，响应中断后参与内存数据交换
- DMA方式：CPU只在I/O开始和结束时参与，不参与主存数据交换
I/O通道
- 又称为通道控制器、I/O处理器，用于完成逻辑上独立的I/O任务
- 采用四级连接：处理器，通道，控制器，设备
- 通道可控制多台同类或不同类的设备
- 处理器不再执行I/O指令，而是在主存中组织通道程序，由I/O通道执行
- 为获得CPU和外围设备间更高的并行工作能力，为让种类繁多，物理特性各异的外围设备能以标准的接口连接到系统中，计算机系统引入了自成独立体系的通道结构
I/O通道的工作流程
CPU遇到I/O任务，组织通道程序，置通道程序地址字CAW，启动指定通道
通道从CAW获取通道程序，控制I/O设备进行操作。CPU执行其他任务
I/O操作完成后，I/O通道发出中断，CPU处理中断，并从通道程序状态字CSW获得通道执行情况，处理I/O操作
- CPU与通道高度并行工作
4.1.3 总线与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控制器和设备之间的数据传送
4.2 设备管理软件
4.2.1 I/O软件的实现层次
I/O软件的设计目标
- 设计目标
- 高效率：改善设备效率，尤其是磁盘I/O操作的效率
- 通用性：用统一的标准来管理所有设备
- 设计思路
- 把软件组织成层次结构，低层软件用来屏蔽硬件细节，高层软件向用户提供简洁、友善、统一的界面
I/O软件设计要考虑的问题
- 设备无关性：访问设备的程序与具体设备无关
- 出错处理：低层软件能处理的错误不让高层软件感知
- 同步/异步传输：支持同步(阻塞)和异步(中断驱动)两种工作方式
- 缓冲技术：建立内存数据缓冲区，提高吞吐率
I/O软件的层次结构
4.2.2 I/O软件的实现
I/O中断处理程序
- 位于OS底层，与硬件设备密切相关，与系统其余部分尽可能少地发生联系
- 进程请求I/O操作时，通常被阻塞
- 数据传输结束后产生I/O中断
- CPU响应请求并转入中断处理程序
I/O中断处理程序的功能
- 检查设备状态寄存器内容，判断中断原因，根据I/O操作的完成情况进行相应的处理
- 如果数据传输有错，向上层软件报告设备的出错信息，实施重新执行
- 如果正常结束，唤醒等待传输的进程，使其转换为就绪态
- 如果有等待传输的I/O命令，通知相关软件启动下一个I/O请求
设备驱动程序
- 包括与设备密切相关的所有代码
从独立于设备的软件中接收抽象的I/O请求
一条典型的请求是读第 n 块
如果请求到来时驱动程序空闲，则立即执行。
如果它正在处理另一条请求，它将该请求挂在等待队列中。
把用户提交的逻辑I/O请求转化为物理I/O操作的启动和执行
- 如设备名->端口地址、逻辑记录->物理记录、逻辑操作->物理操作等
监督设备是否正确执行，访问数据缓冲区，进行必要的纠错处理
例如，磁盘驱动程序包含：计算出所请求块的物理地址、检查马达驱动器是否在运转、检测磁头臂是否定位在正确的柱面位置等
- 简而言之，它必须确定需要哪些控制器命令及命令的执行次序，然后就向控制器的设备寄存器写入这些命令和相应参数。
- 某些控制器一次只能接收一条命令(如DMA)，另一些可接收一串命令并自动进行处理(如通道方式)
设备驱动程序的功能
- 设备初始化：在设备传输数据时，预置设备、控制器以及通道状态
- 执行设备驱动例程：负责启动设备，进行数据传输；对于通道，还负责组织通道程序，启动通道工作
- 执行与设备相关的具体中断处理：负责处理设备、控制器及通道所发出的各种具体中断
设备驱动程序的层次
每个设备驱动程序原则上只处理一种设备，或者一类紧密相关的设备
设备驱动程序可以分层实现
- 高层/处理类设备，底层/处理具体设备
- 系统建立栈，接到I/O请求时先调用栈顶的驱动程序，然后继续向下调用低层驱动程序，直到所有物理操作被处理
- 这一方式使设备驱动的实现结构清晰、便于移植，但会增加一部分系统开销
独立于设备的I/O软件
- 执行适用于所有设备的常用I/O功能，并向用户层软件提供一致性接口，包括：
- 设备命名：通过路径名寻址设备
- 设备保护：用户是否有权访问设备
- 提供与设备无关的数据单位：字符/块
- 缓冲技术：调整CPU与I/O速度不匹配
- 分配和状态跟踪：分配设备
- 错误处理/报告：驱动无法处理的错误
用户空间的I/O软件
- 库函数：一部分I/O软件可以使用库函数实现，放在操作系统内核之外，运行时与应用程序链接
- 虚拟设备软件：用一类设备模拟另一类设备的仿真I/O软件
4.2.3 I/O缓冲
设置I/O缓冲的目的
- 解决CPU与设备之间速度不匹配的矛盾
- 协调逻辑记录大小和物理记录大小不一致的问题
- 提高CPU和设备的并行性
- 减少I/O操作对CPU的中断次数
- 放宽对CPU中断响应时间的要求
I/O缓冲区
- I/O缓冲区：在内存中开辟的存储区，专门用于临时存放I/O操作的数据
- 操作过程：
- 写操作：将数据送至缓冲区，直到装满或需要写出，待适当时候系统将缓冲区内容写到设备上
- 读操作：系统将设备上的物理记录读至缓冲区，根据要求将当前所需要的数据从缓冲区中读出并传送给进程
单缓冲技术
操作系统在主存系统区中开设一个缓冲区
输入：先把数据读至缓冲区，再把缓冲区数据送至用户区，应用程序处理数据；如此往复，系统继续读入后继数据
输出：把数据从用户区传送到缓冲区，再将数据输出到设备，应用程序继续请求输出
双缓冲技术
操作系统在主存系统区开设两个缓冲区
输入：先把数据输入缓冲区1，再从缓冲区1把数据传到用户区，供应用程序处理；(同时设备可将数据传送到缓冲区2)
输出：先将数据从用户区传送到缓冲区1，再将数据传送到设备；(同时应用程序可 将数据传送到缓冲区2)
循环缓冲技术
OS分配一组缓冲区，每个缓冲区有指向下个缓冲区的链接指针，构成循环缓冲
继续调节设备和进程速度不匹配问题
4.3 独占型外围设备的分配
4.3.1 设备独立性
问题的提出
- 作业执行前对设备提出申请时，指定某台具体物理设备会让设备分配变得简单
- 微型计算机OS多采用这种方式
- 缺点：但如果所指定设备出现故障，即便计算机系统中有同类设备也不能运行
设备独立性及其实现
- 设备独立性：用户通常不指定物理设备，而是指定逻辑设备，使得用户作业和物理设备分离开来，再通过其它途径建立逻辑设备和物理设备之间的映射
- 设备管理中需要将逻辑设备名转换为物理设备名，为此系统需要提供逻辑设备名和物理设备名的对应表以供转换使用
设备独立性的优点
- 应用程序与具体物理设备无关，系统增减或变更设备时不需要修改源程序
- 易于应对I/O设备故障，提高系统可靠性
- 增加设备分配的灵活性，有利于更加有效地利用设备资源，实现多道程序设计
4.3.2 独占型外围设备的分配
设备分配方式
独占型外围设备：一次只能由一个进程独占使用
分配方式：
静态分配：进程运行前申请
- 实现简单，能够防止系统发生死锁，但会降低设备利用率
动态分配：进程随用随申请
- 提高设备利用率
设备分配的数据结构
- 设备类表
- 每类设备对应于设备类表中的一栏
- 包括：设备类，总台数，空闲台数，设备表起始地址等
- 支持设备独立性时才会使用
- 设备表
- 每类设备都有各自的设备表，用来登记这类设备中的每台物理设备
- 包括：物理设备名，逻辑设备名，占有设备的进程，分配标志，好/坏标志等
4.4 共享型外围设备的驱动
4.4.1 磁盘的物理结构
磁盘结构
- 磁盘一般由多个盘片组成
- 每个盘片一般有两个盘面
- 盘面包括多个同心圆结构的磁道，不同盘面上位于相同位置的磁道构成柱面
每个磁道分为固定的多个扇区，相邻扇区组合成簇
物理块地址
- 柱面号、磁头号、扇区号
- 0 道 0 面 1 扇区：面指磁头/不是柱面
磁盘读写数据的方式
- 读写数据时，磁头必须定位到指定磁道上的指定扇区的开始处。过程如下：
- 寻道：控制移动臂到达指定柱面
- 旋转：等待要读写的扇区旋转到磁头下
- 选择磁头号，进行数据传送
磁盘存取时间
磁盘完成数据读写所需要的时间
寻道时间、旋转延迟、传送时间的总和
为了读或者写，磁头必须定位到指定的磁道(track)和该磁道中指定的扇区(sector)的开始处
- 寻道时间 (记为Ts)
- 将磁盘磁头臂移动指定磁道所需要的时间
- 旋转延迟 (Rotational delay or rotational latency)
- 要读写的扇区到达磁头的旋转时间
- 传送时间
4.4.2 磁盘的驱动调度
磁盘调度
- 磁盘可能同时接收到若干I/O请求
- 随机响应I/O请求，会得到很坏的性能
- 驱动调度：OS的磁盘调度策略，即按照最佳次序执行处理访问磁盘的多个I/O请求，以减少磁盘访问的总处理时间
- 驱动调度策略包括
- 移臂调度
- 旋转调度
移臂调度及算法
目的：使移动臂的移动时间最短，从而减少寻道总时间
移臂调度算法
- 先来先服务：移臂距离大，性能不好
- 最短查找时间优先(最小短距法)
- 先执行查找时间最短的请求，具有较好的寻道性能
- 存在“饥饿”现象
移臂调度的扫描算法
- 单向扫描：移动臂向一个方向扫描，归途不提供服务，适用于不断有均匀分布的大量柱面请求的情形
- 双向扫描，移动臂每次向一个方向移动，遇到最近的I/O请求便进行处理，到达最后一个柱面后再向相反方向移动
- 电梯调度：双向扫描的改进，当前移动方向没有访问请求时，就改变移动方向
旋转调度
- 目的：使得旋转延迟的总时间最少
- 循环排序
- 通过优化I/O请求排序，在最少旋转圈数内完成位于同一柱面的访问请求
- 旋转位置测定硬件和多磁头同时读写技术有利于提高旋转调度的效率
优化分布
通过信息在存储空间的排列方式来减少旋转延迟
交替排序：由于磁盘匀速运转，可能处理当前扇区数据时，下个扇区已经跳过。因此，可对扇区间隔编号，如交叉因子为 n:1 表示相邻编号间会间隔 n-1 个扇区
- 把相邻扇区集中成簇读写
- 按柱面集中存储数据(另一种集簇方式)，可以减少数据读写时的移臂操作
4.5 虚拟设备
4.5.1 SPOOLing系统
虚拟设备技术
- 使用一类物理设备模拟另一类物理设备的技术
- 通常是使用共享型外围设备模拟独占型外围设备
- 示例
- 内存卡模拟磁盘
- 块设备模拟字符设备
- 输入输出重定向
- …
一个经典的SPOOLing系统
SPOOLing(外部设备联机并行操作)，即 Simultaneous Peripheral Operations On-Line 的缩写，它是关于慢速字符设备如何与计算机主机交换信息一种技术，通常称为“假脱机技术”。
用高速的磁盘设备来模拟慢速的字符设备，缩短进程在内存中的驻留时间
- 慢速输出设备先输出到(输出井)
- 进程运行过程中只从输入井读入数据，只向输出井输出信息，使得全部 I/O 都基于磁盘
- 加快进程周转时间，提高系统吞吐量
该SPOOLing系统的软件组成
- 预输入程序：预先把数据从输入设备传送到磁盘输入井
- 缓输出程序：把数据从磁盘输出井传送到输出设备
- 井管理程序：控制进程和井之间的数据交换(事实上是 I/O 重定向)
SPOOLing系统的示意图
打印SPOOLing系统
- 打印机守护进程和 SPOOLing 打印目录
- 守护进程是唯一有特权使用打印机设备的进程
- 打印文件前，用户进程先产生完整的待输出文件，并存放在打印目录下
- 打印机空闲时，启动守护进程，打印待输出文件
4.5.2 批处理系统的作业管理
SPOOLing系统与作业管理
多道批处理OS的作业管理
- 作业说明语言：用于作业控制的语言
- 作业说明书：刻画具体作业的控制方式
- 作业状态：输入状态(预输入)、后备状态(空闲)、运行状态(运行)、完成状态(缓输出)
- 作业调度：从后备状态作业中选择部分进入运行状态(前提是资源满足)
- 作业调度算法：优先数、短作业、响应比、设备搭配、等等
作业调度与进程调度的关系
补充内容
1. I/O硬件
I/O设备控制器
- 控制器(或适配器) 是用于操作端口、总线或设备的一组电子器件，它是可插入主板扩充槽的印刷电路板，机械部件则是设备本身
- 例如，IDE接口设备、SCSI接口设备
- 操作系统与控制器打交道，微机和小型机采用单总线模型，实现CPU和控制器间的数据传送，中、大型机则采用多总线结构和多通道方式，以提高并行操作程度
- 如果没有控制器，复杂操作必须由操作系统来解决，引入控制器后，通过传递简单参数就可进行I/O操作，大大简化系统的设计，有利于计算机系统对各类控制器和设备的兼容性
PC中的设备I/O的端口位置(部分)
I/O模块框图
Pentium处理器的中断向量表
I/O功能的演化
- 处理器直接控制外围设备
- 增加了控制器或者I/O模块
- 处理器使用非中断的可编程I/O
- 处理器开始从外围设备接口的具体细节中分离出来
- 采用中断方式的控制器或者I/O模块
- 处理器无需花费等待执行一个I/O操作所需的时间，因而提高了效率
- I/O模块通过DMA直接控制存储器
- 可以在没有处理器参与的情况下，从主存中移出或者往主存中移入一块数据，仅仅在传送开始和结束时需要用到处理器
- I/O模块被增强为单独的处理器，有专门为I/O设计的指令集
- I/O处理器在没有CPU干涉的情况下取指令并执行这些指令，使得CPU可以指定一系列I/O活动，并只有当整个序列执行完成后CPU才被中断
- I/O模块有自己的局部存储器，其本身就是一台计算机
DMA
- 替代 CPU, DMA 控制内存与磁盘之间数据传输
- 周期窃取是指利用 CPU 不访问存储器的那些周期来实现 DMA 操作，此时 DMA 可以使用总线而不用通知 CPU 也不会妨碍 CPU 的工作
- 周期挪用并不减慢 CPU 的操作，但可能需要复杂的时序电路，而且数据传送过程是不连续的和不规则的
- 在这种方法中，每当I/O设备发出DMA请求时，I/O设备便挪用或窃取总线占用权一个或几个主存周期，而DMA不请求时，CPU仍继续访问主存
- 不发生中断
- 不保存上下文
指令周期中DMA和中断的断点
具有通道的I/O系统
- 具有通道的计算机系统，I/O程序设计涉及：
- CPU执行I/O指令
- 通道执行通道命令
- CPU和通道之间的通信
- 通道状态字(CSW, Channel Status Word)
- 通道状态字是存放在内存固定单元的控制字，专门用于记录通道和设备执行操作的情况
- 输入输出中断
- 输入输出指令
- 启动输入输出指令(SIO)
- 查询输入输出指令(TIO)
- 查询通道指令(TCH)
- 停止输入输出指令(HIO)
- 停止设备指令(HDV)
通道地址字(CAW)
- 通道地址字是存放在内存固定单元的控制字，专门用于存放通道程序首地址
处理步骤
- 组织通道程序，通道程序首地址送CAW
- 执行启动输入输出指令，启动通道工作
- 通道根据自身状态形成条件码；若通道可用，从CAW中取得通道程序首地址，得到第一条通道指令，启动设备控制器；设备控制器再检查设备状态；若设备不忙，则告知通道释放CPU
- 通道独立执行通道程序，控制外设进行输入输出
- 通道完成输入输出后，形成CSW和置中断字寄存器，发出输入输出中断，请求CPU处理
通道命令和通道程序
通道命令
- 通道，具有自己的指令系统，它的指令常称通道命令。
- 通道命令字CCW (Channel Command Word)是通道从主存取出并控制I/O设备执行I/O操作的命令字，用通道命令编写的程序称通道程序，通道程序由多条通道命令组成，每次启动可以完成复杂的I/O控制
- IBM370及后继产品IBM S/390均采用通道技术，IBM370系统的通道命令为双字长
IBM370系统的通道命令
- 命令码
- 数据传输类(读、反读、写、取状态)，通道转移类(转移)，设备控制类(随设备类不同执行不同控制)
- 数据主存地址
- 对数据传输类命令，规定本条通道命令访问的主存数据区起始或末尾；而“传送字节个数”指出数据区的大小；对通道转移类命令，用来规定转移地址
- 标志码
- 用来定义通道程序的链接方式或标志通道命令的特点
- 传送字节个数
- 对数据传输类命令，规定本次交换的字节个数；对通道转移类命令，规定填一个非0数
2. I/O缓冲
I/O缓冲
- 使用缓冲的原因
- 进程经常需要等I/O完成才能继续后续的执行
- 在存储管理中使用分页机制，那么需要将包括目标地址单元的页锁定在主存中
- 面向块 (Block-oriented)
- 数据存储和传送以块为单位，块的大小通常是固定的
- 通常可以通过块号访问数据
- 例如：磁盘和磁带
- 面向流 (Stream-oriented)
- 设备以字节流的方式传输数据
- 例如：终端、打印机、通信端口、鼠标和其他指示设备以及大多数非辅存的其他设备
单缓冲
- 操作系统在主存中为I/O请求分配一个缓冲区
- 面向块 (Block-oriented)
- 输入传送的数据被放到缓冲区中
- 当传送完成时，进程把该块移动到用户空间，并立即请求另一块，这种方式成为超前(预先输入)
- 面向流 (Stream-oriented)
- 单缓冲方案可以以每次传送一行的方式或者每次传送一个字节的方式使用
- 每次传送一行的方式适合于滚动方式的终端(哑终端)
- 对于这类终端，用户每次输入一行，用回车符表示到达行尾，并且输出到终端时也是类似的每次输出一行
- 行式打印机是这类设备的另一个例子
- 还有其他许多外设，如传感器和控制器都属于这种类型
双缓冲
- 最多两个缓冲
- 在一个进程往一个缓冲区中传送数据(从这个缓冲区取数据)的同时，操作系统正在清空(或者填充)另一个缓冲区
循环缓冲
- 使用两个以上的缓冲区
- 使得I/O操作能跟得上进程的执行
3. 独占型外围设备的分配
设备分配
- 从设备的特性来看，可以把设备分成独占设备、共享设备和虚拟设备三类
- 相应的管理和分配外围设备的技术可分成：独占方式、共享方式和虚拟方式
设备分配算法
- 根据设备类查设备类表
- 若无空闲设备则等待设备
- 取得设备表首地址
- 查设备表发现空闲设备栏
- 若未发现空闲设备栏则等待设备
- 填占用进程号，逻辑设备名，分配设备
4. 共享型设备的驱动调度
磁盘调度策略
先进先出 First-in, first-out (FIFO)
- 按顺序处理请求
- 对于所有进程是公平的
优先级 (Priority)
- 这种方法并不会优化磁盘的使用率，但可以满足操作系统的其他目标
- 通常比较短的批作业和交互作业的优先级较高，而较长计算时间的长作业优先级低，这就使得大量短作业能够迅速地通过系统，并且可以提供比较好的交互响应时间
- 但是长作业不得不等待很长的时间
后进先出(Last-in, first-out)
- 在事务处理系统中，把设备资源提供给最近的用户，会导致磁头臂在一个顺序文件中移动时移动得很少，甚至不移动
- 利用这种局部性可以提高吞吐量，减少队列长度
- 只要一个作业积极地使用文件系统，它就可以尽可能快地得到处理
- 如果由于工作量大而磁盘保持忙状态，就有可能出现饿死的情况
- 当一个作业已经往队列中送入一个I/O请求，并且错过了可以提供服务的位置时，该作业就有可能永远得不到服务，除非它之前的队列变为空
最短服务时间优先(SSTF, Shortest ServiceTimeFirst)
- 选择使磁头臂从当前位置开始移动最少的磁盘I/O请求，因此SSTF策略总是选择导致最小寻道时间的请求
- 总是选择最小寻道时间并不能保证平均寻道时间最小，但是，它的性能比FIFO更好
扫描 (SCAN)
- 要求磁头臂仅仅沿一个方向移动，并在途中满足所有为完成的请求，直到它到达这个方向上的最后一个磁道，或者在这个方向上没有其他请求为止，后一种改进有时候称为LOOK策略 (又称为电梯调度算法)
- 接着反转服务方向，沿着相反方向扫描，同样按顺序完成所有请求
电梯调度算法
循环扫描 (C-SCAN)
- 把扫描限定在一个方向
- 当访问到沿某个方向的最后一个磁道时，磁头臂返回到磁盘相反方向磁道的末端，并再次开始扫描
N-step-SCAN
- 进程重复请求同一磁道会垄断整个设备，”造成磁头臂的粘性”，采用分步扫描可避免这类问题
- 把磁盘请求队列分成长度为 N 的子队列，每一次用SCAN处理一个子队列
- 在处理一个队列时，新请求必须添加到其他某个队列中
- 如果在扫描的最后剩下的请求数小于N，则它们全部将在下一次扫描时处理
- 当N很大时，N-step-SCAN的性能接近SCAN；当N=1时，实际上是FIFO
FSCAN
- 使用两个子队列
- 当开始扫描时，所有请求都在一个队列中，而另一个队列为空
- 在扫描过程中，所有新到的请求都被放入另一个队列中
- 因此，对新请求的服务延迟到处理完成所有老请求之后
旋转调度(Rotation Schedule)
- 循环排序：在最少旋转圈数内完成位于同一柱面的访问请求；旋转位置测定硬件和多磁头同时读写技术有利于提高旋转调度的效率
- 优化分布
- 交替地址
循环排序
- 方法1：按照I/O请求次序读记录4、3、2、1，平均用1/2周定位，再加上1/4周读出记录，总处理时间等于1/2 + 1/4 + 3 * 3/4 = 3周，即60毫秒
- 方法2：如果次序为读记录1、2、3、4，总处理时间等于1/2 + 1/4 + 3 * 1/4 = 1.5周，即30毫秒。
- 方法3：如果知道当前读位置是记录3，则采用次序为读记录4、1、2、3，总处理时间等于4 * 1/4＝1周，即20毫秒。
优化分布
按照下面方式对信息优化分布
RAID
RAID 0
- RAID0-连续的数据条带(每个条带可规定为1个或多个扇区)以轮转方式写到全部磁盘上，然后采用并行交叉存取，减少I/O请求排队时间，适用于大数据量的I/O请求，但并无冗余校验功能，可靠性较差
RAID 1 (镜像)
- RAID1-采用镜像盘双份所有数据来提高容错性，读请求拥有最小寻道时间，写请求可并行完成。缺点是容量下降一半，故成本很高
RAID 2 (通过海明码冗余)
- RAID2-采用数据字或字节交叉存放，并行存取获得高性能，使用海明校验码，适合大量顺序数据访问。由于使用多个冗余盘，成本较高
RAID 3 (交错位奇偶校验)
- RAID3是RAID2的简化版本，差别是它仅用一只冗余盘，采用奇偶校验技术
RAID 4 (块奇偶校验)
- RAID 4 采用独立存取磁盘阵列，数据条带交叉存放，访问请求可并行地获得满足，适合有较高I/O请求速度的应用场合，使用一只冗余盘存放奇偶校验码
RAID 5 (块分布奇偶校验)
- RAID5与RAID4的组织类似，但奇偶校验码循环分布在每个盘上使容错性更好
RAID 6 (双重冗余)
- RAID 6 采用双重冗余技术，P和Q是两种不同的数据校验算法，其中一种是 RAID 4 和 RAID 5 所使用是异或计算，另一种是独立数据校验算法，即使有两个数据磁盘发生错误，也可重新生成数据
磁盘 Cache
- 磁盘高速缓存是主存中为磁盘扇区设置的一个缓冲区
- 包含磁盘中某些扇区的副本
- 利用局部性原理，可以减少平均存储器存取时间
替换策略.LRU
- 替换在高速缓存中未被访问的时间最长的块
- 逻辑上，高速缓存有一个关于块的栈组成，最近访问过的块在栈顶，当高速缓存中的一个块被访问到时，它从栈中当前的位置移到栈顶
- 当一个块从辅存中取入时，把位于栈顶的那一块移出，并把新到来的块压入栈顶
- 并不需要在主存中真正移动这些块，有一个栈指针与高速缓存相关联
替换策略.LFU
- 替换集合中被访问次数最少的块
- LFU可以通过给每个块关联一个计数器来实现
- 当一个块被读入时，它的计数器被指定为1；当每次访问到这一块时，它的计数器增1
- 当需要替换时，选择计数器值最小的块
- 直觉上，LFU比LRU更适合，因为LFU使用了关于每个块的更多的相关信息
5. 虚拟设备
- 脱机同时外围设备操作
- 井是用作缓冲的存储区域，采用井的技术能调节供求之间的矛盾，消除人工干预带来的损失
- 预输入程序
- 操作系统将一批作业从输入设备上预先输入到磁盘的输入缓冲区中暂时保存，这称为“预输入”，此后，由作业调度程序调度作业执行，作业使用数据时不必再启动输入设备，只要从磁盘的输入缓冲区中读入
- 缓输出程序
- 作业执行中不必直接启动输出设备，只要将作业的输出数据暂时保存到磁盘的输出缓冲区，当作业执行完毕后，由操作系统组织信息成批输出
- 井管理程序
6. I/O设备管理的实现与层次
I/O软件的设计目标和原则
- 设备无关性。
- 访问文件数据的程序时，与具体的物理设备无关
- 出错处理。
- 数据传输中的错误应该在尽可能靠近硬件的地方处理，低层软件能够解决的错误就不让高层软件感知。
- 同步(阻塞)—异步(中断驱动)传输。
- 异步传输: CPU在启动I/O操作后既可继续执行其他工作，直到中断到达；
- 同步传输: 阻塞方式，让启动I/O操作的进程阻塞等待，直到数据传输完成。
- 独占性外围设备和共享性外围设备。
- 建立数据缓冲区，让数据到达与离去率相匹配，以提高系统吞吐率。
阻塞与非阻塞I/O
独立于设备的I/O软件
功能
对设备驱动程序的统一接口
设备命名和设备保护
提供与设备无关的块尺寸
缓冲区管理
块设备的存储分配
独占性外围设备的分配和释放
出错处理和报告
设备命名和设备保护
设备都被看作文件，通过路径名进行寻址，每个设备具有一个文件名、inode、文件所有者、权限位等属性
设备不仅具有文件名，且支持与文件相关的所有系统调用,如open、close、read、write、stat及lseek等
设备文件依赖于inode来实现，文件目录并不能区分文件名是代表一个磁盘文件或设备文件，但inode的内容是不同的，磁盘文件的inode包含指向数据块的指针，而设备文件的inode则包含指向内核设备驱动程序的指针，用来控制设备的I/O。
设备保护需要检查用户是否有权访问所申请的设备，多数大中型计算机系统中，用户进程对I/O设备的直接访问是绝对禁止的，I/O指令定义为特权指令，通过系统调用的方式间接地供用户使用
此外，在UNIX/Linux中还使用一种灵活的方法，对应于I/O设备的特别文件采用rwx保护机制，以判断文件所有者和组成员是否有权向设备发送和读取数据的权限。Windows中设备作为命名对象出现在文件系统中，对文件的保护规则也适用于I/O设备。
提供与设备无关的块尺寸
- 屏蔽不同磁盘扇区大小并向高层软件提供统一大小的逻辑块
- 缓冲区管理
- 通过缓冲区来消除填满速率和清空速率之间的影响，块设备和字符设备都需要缓冲技术，可通过在主存建立缓冲区的方法来解决
- 设备分配和状态跟踪
- 静态、动态、虚拟分配
- 错误处理和报告
- 错误处理多数由驱动程序完成。低层软件处理不了的情况，交给高层软件处理，在许多情况下，错误恢复可在低层透明地得到解决，而高层软件甚至不知道存在错误。
用户空间的I/O软件
- 库函数实现的I/O系统调用
- I/O系统调用通常先是库函数调用
count=write(fd，buffer，nbytes);
- 所调用的库函数write将与应用程序链接在一起，形成可执行代码装入主存，这些库函数显然也是I/O系统的一部分。
- 库函数所做的工作只是将系统调用时所用的参数放在合适的位置，然后执行访管指令来陷入内核，再由内核函数实现真正的I/O操作。
I/O操作执行步骤
- 进程对已打开文件的文件描述符执行读库函数
- 与设备无关的I/O软件检查参数正确性。高速缓存中有要读的信息块，从缓冲区直接读到用户区，完成I/O请求
- 若数据不在缓冲区，执行物理I/O，实现将设备逻辑名转换成物理名，检查对设备操作的权限，将I/O请求排队，阻塞进程且等待I/O完成
- 内核启动设备驱动程序，分配存放读出块的缓冲区，准备接收数据，且向设备控制寄存器发启动命令，或建立DMA传输，启动I/O
- 设备控制器操作设备，执行数据传输
- DMA控制器控制一块传输完成，硬件产生I/O结束中断
- CPU响应中断，转向磁盘中断处理程序
- 当应用进程被再次调度执行时，从I/O系统调用的断点恢复执行。
Windows的I/O管理
Windows的设备管理
- 设备驱动程序
- 即插即用结构
