操作系统入门（九） IO系统篇之设备分配管理、IO缓冲区管理 和 假脱机技术SPOOLing

上一节我们介绍了IO系统的分层、IO的控制方式、数据传输和IO控制器的构成。详情见：

操作系统入门（八） IO系统篇之IO控制器、IO控制方式、IO设备分类和IO系统分层

本节将介绍 IO设备分配、缓冲区管理以及假脱机技术SPOOLing。

01 IO设备分配

设备分配是IO系统中设备独立性软件层（也就是内核层）要做的事情。设备分配应考虑的因素包括：设备的属性、分配算法、安全性。安全性是指按照这种分配方式分配的话，进程是否会死锁。

设备属性包含独占设备、共享设备和虚拟设备，根据不同属性实行不同的分配方式。

安全分配和不安全分配

IO设备分配从进程运行的安全考虑，可分为：安全分配和不安全分配方式。

安全分配方式：为进程分配一个设备后（如打印机）就将进程阻塞，本次I/O完成后才将进程唤醒。好处是进程阻塞后就不会请求其他IO设备，不会死锁。缺点是进程和IO设备串行工作，并发度降低。

不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求；只有某个I/O请求得不到满足时才将进程阻塞；有可能发生死锁。

静态分配和动态分配

静态分配：进程运行前为其分配所有所需资源（如果有一个资源未就绪，就会阻塞进程），运行结束后归还。

动态分配：进程运行过程中动态分配资源。

我们知道，IO控制器能接收和识别CPU发出的命令，根据命令控制IO设备的读写行为，完成数据在CPU和设备间的交换。

CPU和I/O设备之间增加了设备控制器后，减少了CPU对I/O的干预，但当有很多外设时，CPU的负担仍然很重，所以IO通道就出现了。

I/O通道是一种特殊的处理机，它能够帮CPU执行I/O指令，并通过执行通道程序来控制I/O操作。

I/O通道可以使数据的传输独立于CPU，也使I/O操作的组织、管理及其结束处理尽量独立，以保证CPU有更多的 时间去进行数据处理。

操作系统为了完成IO设备分配会 为每个物理设备配置一个 设备控制表 ，为一个IO控制器配置一个 控制器控制表 ，为一个通道配置一个 通道控制表
，为IO系统中所有的设备分配一个 系统设备表 。

一个通道对应多个控制器，一个控制器可以对应多个设备，因此一个通道控制表下有多个控制器控制表(以链表形式组织），一个控制器控制表下有多个设备控制表（以链表形式组织）。

设备分配管理中的数据结构

1、设备控制表（DCT）

2、控制器控制表（COCT）

3、通道控制表（CHCT）

4、系统设备表（SDT）

记录了系统中全部设备的情况，每个设备对应一个表目。

设备分配步骤

1、IO请求到达“设备独立性软件层”后，系统根据IO系统调用中的物理设备名参数查找系统设备表。以物理设备名找到系统设备表中符合的一个表项，获取表项中的设备控制表地址，也获取其驱动程序入口，以便设备最终分配成功后执行驱动程序。

2、读取到设备控制表后，若设备忙碌则将进程PCB挂到设备控制表的设备等待队列中，不忙碌则将设备分配给进程。

3、查询设备控制表找到控制器控制表，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配 给进程。

4、根据控制器控制表找到通道控制表，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。

一层层的从设备找到控制器再找到通道。

只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送。

该分配方式是假设用户编程使用物理设备名对设备请求，有以下缺点：

A 如果主机换了一个物理设备（找不到这个物理设备了），则程序无法运行。

B 如果进程请求的物理设备在忙，即使系统中还有同类型的设备 ，进程也会阻塞等待
（例如电脑有3台打印机，进程A请求打印机1，进程B也请求打印机1，B就阻塞了，所以最好是有个逻辑设备名可以代表这3台物理设备）。

改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名。

注意：逻辑设备名不是指代具体某一台设备，而是同一类型的所有物理设备，例如 /dev/printer 这个逻辑设备名指代所有打印机。

实际上，系统设备表表项中的“设备类型”字段就是逻辑设备名。

系统会为每个用户维护一个逻辑设备表（LUT），记录着某个用户使用的逻辑设备名所对应的物理设备名或者物理设备对应的系统设备表表项指针。不同LUT中相同逻辑设备名可以对应到不同物理设备。

用户进程第一次使用设备时要根据逻辑设备名遍历系统设备表，建立LUT的表项。之后通过逻辑设备名查LUT表即可知道用户进程实际要使用的是哪个物理设备以及它的系统设备表表项位置。

02 IO缓冲管理

IO缓冲区管理也是由“设备独立性软件层”实现的。缓冲区是一个缓存区域，可以用专门的硬件寄存器作为缓冲区，也可用内存作为缓冲区。IO缓冲主要是内存。

输出数据时CPU可以把输出数据快速放到缓冲区，然后CPU就开始做别的事，与此同时慢速的IO设备可以慢慢从缓冲区取走数据；输入数据时同理。

缓冲区作用：

1、缓和CPU和IO设备速度不匹配的矛盾，提高CPU和IO的并行性。

2、减少CPU中断频率，放宽CPU响应中断的时间（对于字符设备而言，增设缓冲区可以减少CPU中断频率）

3、解决数据粒度不匹配问题（如输出进程每次可以产出以块为单位的数据，但IO设备每次只能按字符或字节输出或接收数据）。

缓冲区的特点是，缓冲区必须要充满之后才能从缓冲区把数据传出到其他地方。缓冲区的数据传出的过程中，不能往缓冲区传入数据。

也就是说，一个缓冲区在被输入满之前他只能是一个输入缓冲区，不能输出。一个缓冲区在输出为空缓冲区之前它只能是一个输出缓冲区，不能接受其他输入数据。

单缓冲

假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（大小为一个块，block）。

首先，块设备的一块数据进入到缓冲区之后（填满缓冲区），数据还只是在内核的内存中，缓冲区满了之后，数据会从缓冲区拷贝到用户进程的内存（假设用户进程的工作区大小也是一个块数据那么大），随后用户进程处理这块数据，处理完之后用户进程清空工作区。

假设块设备拷贝一块数据到缓冲区花费时间 T。

缓冲区拷贝所有数据（缓冲区大小是一块数据）到用户进程的时间是 M，CPU处理用户进程的一块数据时间为 C。

那么每处理一块数据平均需要时间N为多少？假设初始状态是工作区满，缓冲区空，则N等于下一次工作区满，缓冲区空所花的时间。

因为工作区满足一个块，所以用户进程可以开始处理数据；因为缓冲区空，所以块设备可以向缓冲区传输数据。这两个动作是并行的。有以下几种情况：

1、T >
C时，用户进程先处理完数据，并把工作区清空（当前时刻为C），但缓冲区还未填满，因此还不能向用户进程传输。等到缓冲区清空了才能往用作区输送数据（当前时刻为T）。缓冲区传送完数据到用作区之后，就回到了初始状态。因此
N = T+M。

2、T<C时，由于缓冲区充满要早于CPU处理用户进程中的数据，因此缓冲区充满数据后暂时不能向用户进程传输数据（因为工作区内存大小只有一个块），块设备也不能向缓冲区继续充入下一块数据，
必须等待CPU处理结 束后将数据从缓冲区 传送到工作区。
该情况下 N = C + M

结论：在工作区内存大小等于缓冲区内存大小的情况下，采用单缓冲策略，处理一块数据平均耗时 Max(C, T)+M。

双缓冲区

假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（假設一个缓冲区的大小就是一个块，block）。

此时块设备既可以往缓冲区1输入数据，也可以往缓冲区2输入数据，但两者只能是串行的。假如缓冲区1满了，接下来要向工作区输送数据，则块设备会继而往缓冲区2发送数据，这与缓冲区1往工作区发送数据是并行的。

使用单/双缓冲在通信时的区别：

两台机器（或者两个进程）之间通信时，如果为每个通信进程配置一个单缓冲区用于数据的发送和接受，那么在任一时刻只能实现数据的单向传输。

A在缓冲发送数据的时候，由于A的缓冲区中有数据，因此B无法发送数据给A，否则B到达A的数据和A准备发送给B的数据会在A的缓冲区中混在一起，必须A发送完数据给B之后，B才能发送数据给A。而且B的缓冲区也必须没有数据，A才能发送数据到B的缓冲区。

若两个相互通信的机器设置双缓冲区，则同一时刻可以实现双向的数据传输。

循环缓冲区

循环缓冲区是指分配多个缓冲区，这些缓冲区链接成一个成环的队列，维护两个指针，in指针表示下一个可以充入数据的空缓冲区，out指针是下一个可以取出数据的满缓冲区。

缓冲池

在用户进程进行IO操作的时候，IO系统将分配多个缓冲区给该用户进程，这些缓冲区分为3类：空缓冲区们组成空缓冲队列，装满了数据待输出的缓冲区们组成了输出队列，装满了输入数据的缓冲区们组成了输入队列。

此外，系统会分配一个缓冲池给该用户进程，该缓冲池包含4个缓冲区指针。

1、当用户进程请求输入，系统从空缓冲队列移除一个空缓冲区队首节点，并让hin指向该空缓冲区节点。IO设备会将输入数据输入到hin指针所指的缓冲区中。

当这个hin指针所指的缓冲区被填满之后，该节点会被转移到输入缓冲区队列的尾部。如果IO设备的数据还没传输完，它会继续从空缓冲队列弹出一个新空缓冲区节点，IO设备继续往该缓冲区节点填充数据。

如果用户进程想要获取输入数据，它会从sin指针所指的一个缓冲区取出数据，sin指针指向输入队列的队首缓冲区节点。当队首缓冲区的数据被取走后，该缓冲区节点会转移到空缓冲区队列的队尾。sin指针移动到输入队列的新队首，用户进程继续从新队首中取出数据。

2、当用户进程想要将准备好的数据冲入缓冲区，以及用户进程请求输出数的过程和上述过程相似，hout指向空缓冲队列的缓冲区，sout指向输出队列的首部缓冲区。提高了IO操作过程中数据拷贝的并行性。

03 假脱机技术 (SPOOLing)

在介绍假脱机技术前，需要先了解IO设备可以按是否能共享分成 共享IO设备 和 独占IO设备。

独占式设备——只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求。

共享设备——允许多个进程“同时”使用的设备（宏观上同时使用，微观上可能是交替使用）。可以同时满足多个进程的使用请求。

我们知道如果多个进程需要申请使用一个独占的IO设备，这个独占的IO设备在被一个进程A使用的时候，其他进程需要等待进程A使用完这个IO设备并将其释放之后，才能获取到该IO设备的使用权，这些进程在阻塞和等待的过程中无法继续完成手里的工作，这无疑会降低程序执行的并发度。

Spooling 是缓存多个进程对某个（独占）设备的IO请求以及IO数据（缓存到磁盘中），使得多个用户可以共享一台（独占）设备的技术。

这种技术降低了进程排队等待设备被释放的时间，把一台物理设备虚拟为多台逻辑IO设备，提高了设备的利用率（就和多道程序设计利用时分复用性将一个物理CPU虚拟化为多个逻辑CPU一样的道理）。

一个SPOOLing系统可以向多个IO设备发送IO请求；SPOOLing系统是软件，属于IO系统的用户层（最顶层）。

SPOOLing系统的具体组成如下：

我们可以认为SPOOLing系统内保存着一个个待完成的IO任务，用户进程懒得排队等IO设备处理前面的IO请求，所以把IO任务以及数据先交给假脱机系统，由它把IO任务组织成队列慢慢处理，用户进程可以做别的事。

下面我们介绍下图中 SPOOLing系统的各个组成部分，需要注意的是，图中的输入输出进程不是用户进程，而是负责辅助SPOOLing系统工作的两个进程。

IO数据的传输路径如下：

输入数据：输入设备->输入缓冲区1->输入井->输入缓冲区2->用户进程。

输出数据： 用户进程 ->输出缓冲区2->输出井->输出缓冲区1-> 输出设备 。

IO数据存储在输入/输出井中，是存储在磁盘内；

IO请求存储在SPOOLing系统的内存中；

1、输入井和输出井是磁盘上的两个存储区用来缓存IO数据，之所以用磁盘是因为IO数据可能太大，内存缓冲区放不下。 输入井缓存IO设备->主机的数据。
输出井缓存用户进程->IO设备的数据。

输入井/输出井的数据以文件形式组织，被称为 井文件
，一批用户进程->IO设备的数据就是一个井文件，一批用户进程<-IO设备的数据也是一个井文件。井文件按照用户进程的IO请求顺序组织成队列（输入井和输出井各一个队列）。

2、假脱机任务队列（图中未画出）保存SPOOLing系统内的IO任务请求，该队列保存在SPOOLing系统的内存中。

3、输入缓冲区（有2个）和输出缓冲区（有2个）是在内存中开辟的两个缓冲区。

当要输出数据时，输出进程将用户进程的输出数据从内存拷贝到输出井，等输出设备空闲时，SPOOLing系统再把数据从输出井送到输出设备。

假脱机技术的使用场景是优化用户进程对低速IO设备的IO操作。

SPOOLing系统优点有二：

提高了IO速度：原本全部数据在CPU与低速设备间交付完才算完成IO操作。现在优化成与高速的磁盘（输入输出井）交付。

将独占设备改造为共享设备：SPOOLing中，实际没有为任何进程分配目标IO设备，用户进程把IO请求交付给共享设备磁盘（输入输出井），没有直接交付给实际处理IO请求的独占设备。因此用户进程无需等待独占设备的释放，像是在并发的使用独占设备一样。