5.输入输出系统
输入输出系统
I/O设备的概念和分类
I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件
按使用特性分类：人机交互类，存储设备，网络通信设备
按信息交换的单位分类：块设备(可寻址)，字符设备(不可寻址，中断驱动)
I/O控制器
概念
控制器分为机械部件和电子部件，机械部件主要用来执行具体的I/O操作，电子部件通常是一块插入主板扩充槽的印刷电路板
I/O控制器：CPU无法直接控制I/O设备的机械部件，因此I/O设备还要有一个电子部件作为CPU和I/O设备机械部件之间的中介，用于实现CPU对设备的控制，这个电子部件就是I/O控制器，又称设备控制器
功能
接受和识别CPU发出的命令
如CPU发来的read/wirte命令，I/O控制器中会有相应的控制寄存器来存放命令和参数
向CPU报告设备的状态
I/O控制器中会有相应的状态寄存器，用于记录I/O设备的当前状态
数据交换
I/O控制器中会设置相应的数据寄存器，输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备，输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据
地址识别
类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的地址，I/O控制器通过CPU提供的地址来判断CPU要读写的是哪个寄存器
组成
由CPU与控制器的接口，I/O逻辑，控制器与设备的接口
I/O逻辑负责接收和识别CPU的各种命令，并负责对设备发出命令
CPU与控制器的接口用于实现CPU与控制器之间的通信，CPU通过控制线发出命令，通过地址线指明要操作的设备，通过数据线来取出数据或放入数据
控制器与设备的接口，用于实现控制器与设备之间的通信
注意：一个I/O控制器可能会对应多个设备
既然I/O控制器可以对应多个设备，那么自然也会有多个寄存器，且这些寄存器都要有相应的地址，才能方便CPU操作，有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O；另一些计算机则采用I/O专用地址，即寄存器独立编址
如果采用内存映像I/O，优点是简化了指令，可以采用对内存进行操作的指令来对控制器进行操作
采用寄存器独立编址，缺点是需要专门的指令来实现对寄存器的操作，不仅要指明寄存器的地址，还要指明控制器的编号
I/O控制方式
程序直接控制方式
完成一次读写操作的流程
- CPU向控制器发出读指令，并且将状态寄存器设为1(未就绪)
- 轮询检查控制器状态
- 输入设备准备好数据后将数据传给控制器，并报告自身状态
- 控制器将输入的数据放到数据寄存器中，并将状态改为0
- CPU从数据寄存器中读出数据
CPU干预的频率：很频繁，I/O操作开始之前，完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断轮询检查
数据传输的单位：每次读写一个字
数据的流向：读操作：从I/O设备到CPU到内存，每个字的读写都需要CPU的帮助
优点：实现简单，在读写指令之后，加上实现循环检查的一系列指令即可
缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于忙等状态，CPU利用率低
中断驱动方式
引入中断机制，由于I/O设备速度很慢，因此在CPU发出读写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。
当I/O完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。
处理中断的过程中，CPU从I/O控制器读一个字的数据到CPU寄存器，再写入主存。接着，CPU恢复等待I/O的进程的运行环境，然后继续执行
CPU会在每个指令周期的末尾检查中断
中断处理过程中需要保存，恢复进程的运行环境，这个过程需要一定的时间开销，如果中断发生的频率过高，也会降低系统性能
CPU干预的频率：I/O操作开始之前，完成之后需要CPU介入，在等待I/O完成的过程中CPU可以切换到别的进程执行
数据传输的单位：每次读写一个字
数据的流向：读操作：从I/O设备到CPU到内存，每个字的读写都需要CPU的帮助
优点：CPU和I/O设备可以并行工作，CPU利用率得到提升
缺点：每个字在I/O设备与内存之间的运输，都要经过CPU，而频繁的中断处理会消耗较多的CPU时间
DMA方式
DMA方式(Direct Memory Access ,直接存储器存取)，主要用于块设备的I/O控制
- 数据的传送单位是 块 不再是字传送
- 数据的流向是从设备直接放入内存，或者是内存直接到设备，不再需要CPU中转
- 仅在传送一个或多个数据块开始和结束时，才需要CPU干预
在DMA控制器中，有4个寄存器：
DR(Data Reigster,数据寄存器)：暂存从设备到内存，或从内存到设备的数据
MAR(Memory Address Register,内存地址寄存器)：在输入时，MAR表示数据应放到内存中的什么位置
DC(Date Counter 数据计数器)：表示剩余要读/写的字节数
CR(Command Register,命令状态寄存器)：用于存放CPU发来的I/O命令，或设备状态
执行过程：
- 初始化DMA控制器并启动磁盘
- 从磁盘传输一块数据到内存缓冲区
- DMA控制器发送中断请求
- 执行DMA结束中断服务程序
CPU干预的频率：仅在传送一个或多个数据块的开始和结束时才需要CPU干预
数据传输的单位：每次读写一个或多个块(每次读写只能是连续多个块，且这些读入内存中也必须连续的)
数据的流向：读操作：从I/O设备直接到内存，
优点：数据传输以块为单位，CPU介入频率进一步降低，传输效率进一步增加
缺点：CPU每发出一条I/O指令，只能读写一个或多个数据块，如果要读写多个离散存储的数据块，或者要讲数据块写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成
通道控制方式
通道：一种硬件，通道可以识别并执行一系列通道指令
执行过程：
- CPU向通道发出I/O指令，指明通道程序在内存中的位置，并指明要操作的是哪个I/O设备，之后CPU就切换到其他进程执行了
- 通道执行内存中的通道程序(其中指明了要读写多少数据，读写的数据应放在内存中的什么位置)
- 通道执行完规定任务后，向CPU发出中断信号，之后CPU对中断进行处理
通道可以识别一系列通道指令，但是可以执行的指令很单一，并且通道程序是放在主机内存中的，也就是说通道和CPU共享内存
CPU干预的频率：极低，通道会根据CPU的指示执行相应的通道程序，只有完成一组数据块的读写后才需要发出中断信号
数据传输的单位：每次读写一组数据块
数据的流向：读操作：从I/O设备直接到内存
优点：CPU，通道，I/O设备可以并行工作，资源利用率很高
缺点：实现复杂，需要专门的通道硬件支持
总结
I/O软件的层次结构
越上面的层次越接近用户，越下面的层次越接近硬件，中间的三层属于操作系统内核部分
用户层软件
实现了与用户交互的接口，用户可直接使用该层提供的，与I/O操作相关的库函数对设备进行操作
用户层软件将用户请求翻译成格式化的I/O请求，并通过系统调用请求操作系统内核的服务
设备独立性软件
又称设备无关性软件，与设备的硬件特性无关的功能都在这一层实现
主要功能是
- 向上层提供统一的调用接口
- 同时实现对设备的保护
- 设备独立性软件要对一些设备的错误进行处理
- 设备的分配和回收
- 数据缓冲区管理
- 建立逻辑设备名到物理设备名的映射关系，根据设备类型选择调用相应的驱动程序，需要通过逻辑设备表(LUT)来确定物理设备名
设备驱动程序
主要负责对硬件设备的具体控制，将上层发出的一系列命令转化为特定设备能听得懂的一系列操作，包括设置设备寄存器，检测设备状态等
一般以一个独立进程方式存在
中断处理程序
当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。中断处理程序的处理流程如下：
总体结构示意图
功能实现示意图
I/O管理
输入输出应用程序接口
用户层的应用程序无法用一个统一的系统调用接口来完成所有类型设备的I/O
所以需要根据不同的设备设置不同的接口以方便系统调用
字符设备(键盘)接口
get/put 系统调用：向字符设备读/写一个字符
块设备(磁盘)接口
read/write 系统调用：向块设备的读写指针位置读写多个字符
seek系统调用：修改读写指针的位置
网络设备接口
socket系统调用：创建一个网络套接字，需指明网络协议
bind:将套接字绑定到某个本地端口
connect：将套接字连接到远程地址
read/write：从套接字读写数据
阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态，比如字符设备接口，从键盘读一个字符
非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待，比如块设备接口，往磁盘写数据write
设备驱动程序接口
如果各个公司开发的设备驱动程序接口不统一，则操作系统很难调用设备驱动程序，所以需要操作系统会要求厂商遵循一个统一的标准
假脱机技术
用软件的方式模拟脱机技术
输入井用于收容I/O设备输入的数据
输出井用于收容I/O设备输出的数据
在输入进程的控制下，输入缓冲区用于暂存从输入设备输入的数据，之后再转存到输入井中
在输出进程的控制下，输出缓冲区用于暂存从输出设备输出的数据，之后再转存到输出井中
假如有一台打印机，当多个用户进程提出输出打印的请求时，系统都会答应他们的要求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：
- 在磁盘输出井中为进程申请一个空闲缓冲区，并将要打印的数据送入其中
- 为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中，在将该表挂到假脱机文件队列上
当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印
设备的分配和回收
设备的固有属性
可以分为三种：独占设备，共享设备，虚拟设备
独占设备：一个时段只能分配给一个进程
共享设备：可同时分配给多个进程使用，各进程往往是宏观上同时使用设备，而微观上交替使用
虚拟设备：采用SPOOLing技术将独占设备改造成虚拟的共享设备，可以给多个设备
设备分配算法
安全分配：$为进程分配一个设备后就将进程阻塞$，本次I/O完成后才将进程唤醒，不会死锁，但是CPU和I/O设备只能串行工作
不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行
静态分配：进程运行前就分配全部所需资源，运行结束后归还资源
动态分配：进程运行过程中动态申请设备资源
设备分配管理中的数据结构
设备控制表(DCT)：系统为每个设备配置一张DCT，用于记录设备情况
控制器控制表(COCT)：每个设备控制器对应一张DCT，操作系统根据COCT信息对通道进行操作和管理
通道控制表(CHCT)：每个通道都会对应一张CHCT，操作系统根据CHCT的信息对通道进行操作和管理
系统设备表(SDT)：记录了系统中全部设备的情况，每个设备对应一个表目
设备分配的步骤
- 根据进程请求的物理设备名查找SDT
- 根据SDT找到DCT，若设备忙碌则将PCB挂到设备等待队列中，不忙碌则将设备分配给进程
- 根据DCT找COCT，若控制器忙碌则将PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程
- 根据COCT找CHCT，若通道忙碌则将PCB挂到通道等待队列中，不忙碌则将通道分配给进程
缺点：用户编程必须使用物理设备名，不方便编程，若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待
改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需要提供逻辑设备名
即在第2步的时候，查找SDT，找到用户进程指定类型的，并且空闲的设备，将其分配给该进程，操作系统在逻辑设备表中新增一个表项
如果之后用户进程再次通过相同的逻辑设备名请求设备，通过LUT表就可以知道对应的是什么物理设备，并且也知道该设备的驱动程序入口地址
缓冲区管理
概念
缓冲区是一个存储区域，可以用专门的硬件寄存器组成，也可利用内存作为缓冲区
使用硬件作为缓冲区的成本较高，容量也较小，一般仅用于对速度要求非常高的场合
一般用内存作为缓冲区，设备独立性软件的缓冲区管理就是要组织好这些缓冲区
作用
缓和CPU和I/O设备之间速度不匹配的矛盾
减少对CPU中断频率，放宽对CPU中断响应时间的限制
解决数据粒度不匹配的问题
提高CPU与I/O设备的并行性
策略
单缓冲：当用户进程请求某种块设备读入若干块的数据，若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区
当缓冲区数据非空时，不能往缓冲区加入数据，只能传出；当缓冲区为空时，可以往其中加入数据，但必须充满后，才能从缓冲区把数据传出
假定一个初始状态，分析下次到达相同状态需要多少时间，这就是处理一块数据平均所需时间
采用单缓冲策略，处理一块数据平均耗时$Max(C,T)+M$
双缓冲
采用双缓冲策略，进程会在主存中为其配置两个缓冲区
采用双缓冲策略，处理一个数据块的平均耗时是$Max(T,C+M)$
使用单/双缓冲在通信时的区别
如果两台通信的机器只设置单缓冲区的话，在任一时刻只能实现数据的单向传输
管道通信中的管道其实就是缓冲区，要实现数据的双向通信，必须设置两个管道
循环缓冲区
将多个大小相等的缓冲区链接成一个循环队列
缓冲池
缓冲池由系统中共用的缓冲区组成，缓冲区可以分为空缓冲队列，输入队列，输出队列
根据一个缓冲区在实际运算中扮演的功能不同，又设置了4种工作缓冲区，用于收容输入数据的工作缓冲区，用于提取输入数据的工作缓存区，用于收容输出数据的工作缓存区，用于提取输出数据的工作缓存区
磁盘存储器的管理
磁盘的结构
磁盘：表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据
磁道：磁盘的盘面被划分成一个个磁道，这样的一个圈就是一个磁道
扇区：一个磁道又被划分为一个个扇区，每个扇区就是一个磁盘块，每个磁盘块存放的数据量相同
最内侧磁道上的扇区面积最小，所以数据密度最大
将磁头移动到想要读写的扇区所在的磁道，磁盘会转起来，让目标扇区在磁头下面划过，完成对扇区的读写
盘面：一个盘片可以有两个盘面，所有的磁头都连在同一个磁臂上，因此所有磁头只能共进退
柱面：所有盘面中相对位置相同的磁道组成柱面
磁盘的物理地址：可以使用(柱面号，盘面号，扇区号)来定位任意一个磁盘块。
磁盘的分类：磁头可以移动的称为活动头磁盘，磁头不能移动的称为固定头磁盘，这种磁盘中每个磁道有一个磁头
磁盘调度算法
一次磁盘读写需要的时间
寻找时间$T_S$：在读写数据前，将磁头移动到指定磁道所花的时间
- 启动磁头臂需要的时间，假设为s
- 移动磁头需要的时间，假设磁头匀速移动，每跨越一个磁道耗时为m,总共需要跨越n条磁道
寻找时间$T_S=s+m×n$
延迟时间$T_R$：通过旋转磁盘，使磁头定位转到目标扇区所需要的时间
假设磁盘转速为$r$，则平均延迟时间为$1/2r$
传输时间：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为$r$，读写的字节数为$b$，每个磁道上的字节数为$N$
传输时间$T_t=b/(rN)$
可以得知延迟时间和传输时间都和磁盘的转速线性相关，操作系统无法进行优化，所以磁盘调度算法的操作主要是影响寻找时间
先来先服务算法(最先)
根据进程请求访问磁盘的先后顺序进行调度
优点：公平，如果请求访问的磁道比较集中的话，性能还算好
缺点：如果有大量进程竞争使用磁道，请求访问的磁道很分散，则FCFS在性能上很差，寻到时间长
最短寻找时间优先算法(最近)
SSTF算法会优先处理与当前磁头最近的磁道，可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短
优点：性能较好，平均寻道时间短
缺点：可能会饥饿
扫描算法(单向)
只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动，也叫电梯算法
优点：性能较好，平均寻道时间较短，不会产生饥饿
缺点：只有到达最边上磁道才会改变移动方向，对于各个位置磁道的相应频率不平均
LOOK调度算法
在SCAN的基础上，增加了一个特性，如果磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向
循环移动算法(C-SCAN)
SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题，规定只有磁头朝向某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求
C-LOOK调度算法
结合LOOK和循环移动，如果磁头移动方向上没有磁道访问请求了，就立刻让磁头返回，并且磁头只需要返回到有磁道访问请求的位置
如果题目未具体说明，则SCAN就是LOOK，C-SCAN就是C-LOOK
减少磁盘延迟时间的方法
交替编号，让逻辑上相邻的扇区在物理上有一定的间隔，可以让读取连续的逻辑扇区所需要的延迟时间更小
读取地址连续的磁盘块时，采用(柱面号，盘面号，扇区号)的地址结构可以减少磁头移动消耗的时间
磁盘管理
磁盘初始化
进行物理格式化，将磁盘的各个磁道划分为扇区，同时初始化扇区的数据结构
将磁盘分区，每个分区由若干个柱面组成
- 进行逻辑格式化，创建文件系统。包括创建文件系统的根目录，初始化存储空间管理所用的数据结构
引导块
计算机开机时需要进行一系列初始化工作，这么工作是通过执行初始化程序完成的
在ROM中存放很小的自举装入程序，完整的自举程序放在磁盘的启动块上，启动块位于磁盘的固定位置
坏块的管理
无法正常使用的扇区就是坏块，属于硬件故障，操作系统无法修复，应该标记出来，避免使用
对于简单磁盘，可以在逻辑格式化的时候进行检查，表明哪些是坏扇区
对于复杂磁盘，可以保留一些备用扇区用于替换坏块
提高磁盘I/O速度的方法
采用磁盘高速缓存
提前读
如果采用顺序访问方式，可以预知下一次要读的盘块，在读当前块的时候，同时将下一个盘块中的数据也读入缓冲区
延迟写
指缓冲区A中的数据本应立即写回磁盘，但是考虑到缓冲区中的数据可能会在不久之后再被访问，所以并不立即将缓冲区A中的数据写入磁盘，而是将它挂到空闲缓冲队列的末尾
优化物理块的分布
虚拟盘
调整I/O请求次序
