操作系统学习笔记（八）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调度的一种。
高速缓存与缓冲区
磁盘高速缓存（Disk Cache）
操作系统中使用磁盘高速缓存技术来提高磁盘的I/O速度，对高速缓存复制的访问要比原始数据访问更快。例如正在运行的进程指令既存储在磁盘上，又存储在物理内存上，也被复制到CPU的二级和一级高速缓存中。
不过，磁盘高速缓存不同于通常意义下的介于CPU与内存之间的小容量高速存储器，而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。
因此，磁盘高速缓存逻辑上属于磁盘，物理上则是驻留在内存中的盘块。
高速缓存在内存中分为两种形式，
一种是在内存中开辟单独的一块存储空间来作为磁盘高速缓存，大小固定；
另一种是把未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘I/O共享。
缓冲区
在设备管理子系统中，引入缓冲区的主要目的如下：
- 缓和CPU和I/O设备间速度不匹配的问题。
- 减少CPU的中断频率，放宽对CPU中断响应时间的限制。
- 解决基本数据单元大小不匹配问题
- 提高CPU和I/O设备之间的并行性
其实现方法如下：
- 采用硬件缓冲器，但是成本太高，只在一些关键部位使用。
- 采用缓冲区（在内存中）
缓冲区有一个特点，即当缓冲区数据非空时，不能像缓冲区冲入数据，只能从缓冲区读取数据。当缓冲区为空时，可以往缓冲区冲入数据，但是必须把缓冲区充满后，才能从中读取数据。
根据系统设置缓冲器的个数，缓冲技术可以分为如下几种：
单缓冲
在设备和处理机之间设置一个缓冲区，设备和处理机交换数据时，先把被交换的数据写入缓冲区，然后需要数据的设备或处理机从中取走数据。
在块设备输入时，假定从磁盘把一块数据输入缓冲区的时间为T，操作系统从中取走数据的时间为M，CPU对这块数据的处理时间为C。
我们在研究各种缓冲技术处理每块数据的时间时，假定一种初始状态，然后计算下一次到达相同状态的时间，就是处理一块数据的时间（如果没有明确说明，以一般认为缓冲区大小与工作区是相同的）。
我们假定T > C，初始状态工作区满，缓冲区空。
当工作区处理完数据后，时间为C，但是缓冲区还没充满。
等缓冲区充满了，从时间为T，停止冲入数据。
然后数据从缓冲区传入工作区，用时为M，当工作区满了，缓冲区也空了，到达下一个状态，这个哥过程用时为M+T。
如果T<C，同理，用时为M+C
所以单缓冲处理每块数据的时间为max(C,T) + M。
双缓冲
根据单缓冲特点，CPU在传送时间M内处于空闲状态，由此引入双缓冲
我们假定的初始状态是，工作区空，其中一个缓冲区满，另一个空，可以再次计算。
我们分为T<M+C和T>M+C两种情况讨论。
结论为双缓冲处理一块数据的用时为max(C + M, T)。
若T>M+C，我们可以使用块设备连续输入；若T<M+C，则可以使CPU不必等待设备输入。
对于字符设备，若采用行输入，则采用双缓冲可以是用户在输入第一行后，在CPU执行第一行命令时，用户可以向第二缓冲输入下一行数据。
若两台机器之间只设置了单缓冲，则它们在任意时刻，只能实现单向的数据传输。为了实现双向数据传输，则必须再设置一个缓冲区，一个作为发送缓冲区，一个作为接收缓冲区。
循环缓冲
包含多个大小相同的缓冲区，每个缓冲区有一个链接指针指向下一个缓冲区，最后一个缓冲区指向第一个缓冲区，多个缓冲区构成一个环形。
循环缓冲用于输入输出时，还需要两个指针in和out。对于输入而言，首先要从设备接收数据到缓冲区，in指针指向可以输入数据的第一个空缓冲区，out指针指向可以提取数据的第一个满缓冲区。输出则相反（？）。
缓冲池
由多个系统公用的缓冲区组成，缓冲区按照其使用情况可以分为三个队列：
- 空缓冲队列
- 装满输入数据的缓冲队列（输入队列）
- 装满输出数据的缓冲队列（输出队列）
还应该有四种缓冲区：
- 用于收容输入数据的工作缓冲区
- 用于提取输入数据的工作缓冲区
- 用于收容输出数据的工作缓冲区
- 用于提取输出数据的工作缓冲区
当输入进程需要输入数据时，从空缓冲队列队首摘下一个空缓冲区，作为收容输入的工作缓冲区，然后向其中输入数据，装满后挂到输入队列队尾。
当计算进程需要输入数据时，从输入队列获得一个缓冲区作为提取输入数据的工作缓冲区，提取完成后放回空缓冲队列队尾。
高速缓存和缓冲区的对比
设备的分配与回收
设备分配概述
设备分配时指根据用户的I/O请求分配所需的设备。分配的总原则是充分发挥设备的使用效率，尽可能让设备忙碌，又要避免由于不合理的分配方法造成的进程死锁。
从设备特性来看，采用下述三种使用方式的设备分别称为独占设备，共享设备和虚拟设备：
- 独占式使用设备
- 分时共享设备，如磁盘的I/O，各进程的每次I/O操作请求可以通过分时来交替进行
- 以SPOOLing方式使用外部设备。该技术是是在批处理操作系统时代引入的，即假脱机I/O技术，这种技术对设备的操作，其实就是对I/O操作进行批处理，是一种以空间换时间的技术。
设备分配的数据结构
设备分配依据的主要数据结构有设备控制表（DCT），控制器控制表（COCT），通道控制表（CHCT）和系统设备表（SDT）
设备控制表（DCT）：我们可以认为，一个设备控制表就象征一个设备，而这个控制表的表项就是设备的各个属性。如图
我们前面学了4种I/O控制方式，通道方式显然要比其他几种方式更加优越，因此现代操作系统的I/O控制采用的都是通道控制。
设备控制器控制设备与内存交换数据，而设备控制器有需要请求通道为其服务，因此每个COCT必定有一个表项存放指向相应通道控制表（CHCT）的指针，而一个通道可为多个设备控制器服务，因此CHCT中必定有一个指针，指向一个表，这个表上的信息表达的是CHCT提供服务的那几个设备控制器。CHCT与COCT的关系是一对多的关系。
系统设备表（SDT）：整个系统只有一个SDT，它记录已连接到系统中的所有物理设备的情况，每个物理设备占用一个表目。
由于在多道程序系统中，进程数多于资源数，会引起资源的竞争，因此要有一套合理的分配原则，主要考虑的因素有：I/O设备的固有属性，I/O设备的分配算法，I/O设备分配的安全性，以及I/O设备的独立性。
设备分配的策略
- 设备分配原则。设备分配应根据设备特性，用户要求和系统配置情况。分配的总原则是：既要充分发挥设备的使用效率，又要避免造成进程死锁。还要将用户程序和具体设备隔离开。
- 设备分配方式。分为静态分配和动态分配两种。
静态分配主要用于对独占设备的分配，它在用户作业开始执行前一次性分配完该作业要求的全部设备，控制器（如通道等），一旦分配，这些设备，控制器（和通道）就一直为该作业拥有，直到该作业被撤销。静态分配不会死锁，但是效率低，不符合总原则。
动态分配是在进程执行过程中根据需要分配，动态分配需要合适的分配算法。
- 设备分配算法。常见的动态设备分配算法有先请求先分配，优先级高者优先等。
这里可以联系进程调度中的临界资源分配，如何避免死锁，如银行家算法？
设备分配的安全性
指的是设备分配过程中应该避免死锁
- 安全分配方式。每当进程发出I/O请求后便进入阻塞态，直到其他I/O操作完成时才被唤醒，这样，一旦进程获得某种设备后便阻塞，不能再请求任何资源，而且在它阻塞时也不保持任何资源。优点是设备分配安全，但是CPU和I/O是串行的（对于同一个进程而言）。
- 不安全的分配方式。进程在发出I/O请求后继续运行，需要时又发出第二个，第三个I/O请求。仅当进程所请求的设备已经被另一个进程占用时，才进入阻塞态。优点是可以同时操作多个设备，从而快速推进进程，缺点是可能有死锁（因为进入阻塞的时候没有释放资源）。
逻辑设备名到物理设备名的映射
为了提高设备分配的灵活性和设备的利用率，方便实现I/O重定向，引入了设备独立性。它指的是应用程序独立于具体使用的物理设备。
为了实现设备独立性，在应用程序中使用逻辑设备名来请求使用某类设备。
在系统中设置一张逻辑设备表（Logic Unit Table, LUT），用于将逻辑设备名映射为物理设备名。LUT表项包括逻辑设备名，物理设备名和设备驱动程序入口地址。
当进程用逻辑设备明请求分配设备时，系统为它分配相应的物理设备，并在LUT中建立一个表项，以后进程再利用逻辑设备名请求I/O操作系统时，系统通过查找LUT找到相应的物理设备和驱动。
可以有两种方式建立LUT：
- 在整个系统中只设置一张LUT。主要适用于单用户系统
- 每个用户一个LUT。当用户登录时，系统为该用户建立一个进程，以及一个LUT，并把LUT存放到进程的PCB中。
SPOOLing技术（假脱机技术）
为了缓和CPU的高速性和I/O设备的低速性之间的矛盾，引入了脱机I/O技术。
该技术利用专门的外围控制机，将低速I/O设备上的数据传送到高速磁盘上，或者相反。
SPOOLing的意思是外部设备同时联机操作，又称假脱机输入/输出操作，是操作系统中采用的一项独占设备改造成共享设备的技术。
- 输入井和输出井
输入井和输出井指的是在磁盘上开辟的两个存储区域。输入井模拟脱机输入时的磁盘用于收容I/O设备输入的数据。输出井模拟脱机输出时的磁盘，用于收容用户程序的输出数据。
- 输入缓冲区和输出缓冲区
是在内存中开辟的两个缓冲区。输入缓冲区用于暂存由输入设备送来的数据，以后再送到输入井。输出缓冲区用来暂存从输出井送来的数据，以后再送到输出设备。
- 输入进程和输出进程
输入进程模拟脱机输入是的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井。当CPU需要输入数据时，直接将数据从输入井读入内存。
输出进程模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井，待输出设备空闲时，在将输出井中的数据经过输出缓冲区送到输出设备
为什么要从输入机到输入缓冲区（内存）到输入井（磁盘），然后CPU需要时，再从磁盘读会内存，绕一圈？
为了CPU当前可能并不需要这个数据，提前输入好？
共享打印机是使用SPOOLing技术的一个实例，这项技术已经被广泛用于多用户系统和局域网。当用户进程请求打印输出时，SPOOLing系统同意打印，但并不是立即把打印机分配给该用户进程，而是为它做了两件事。
- 由输出进程在输出井中为之申请一块空闲磁盘块，并将要打印的数据送入
- 输出进程再为用户进程申请一个空白的用户请求打印表，并将用户的打印请求填入其中，再将该表挂到请求打印队列中。