517_设备的分配与回收
# 5.1_7_设备的分配与回收
各位同学大家好，在之前的小节中，我们介绍了 IO 核心子系统需要实现的一些功能。上一个小节，我们介绍了在用户层软件需要实现的 SPOOLing 技术，从这个小节开始，我们会开始介绍设备独立性软件这一层需要实现的两个功能，一个是设备的分配与回收，下一节会讲缓冲区的管理
在这个小节中，我们首先会介绍设备分配的时候应该考虑哪些因素，之后会介绍两种很常用的分配策略，静态分配与动态分配。
再之后我们会介绍设备分配的时候，操作系统用来管理这些设备资源需要使用的数据结构，并且介绍设备分配的具体步骤，最后我会介绍一种设备分配步骤的改进方法，我们会让从上至下的顺序依次讲解。
# 设备分配时应该考虑哪些因素
首先来看一下设备分配时应该考虑哪些因素，我们应该考虑设备的固有属性，设备的分配算法，还有设备分配中的安全性
设备的固有属性可以分为这样的三种，独占设备，共享设备和虚拟设备
- 独占设备就是一个时间段内只能分配给一个进程使用的那些设备。比如说咱们很熟悉的打印机
- 共享设备，可以同时分配给多个进程使用的那种设备，比如说像磁盘，但是所谓的这种共享其实是宏观上共享，但微观上各个进程有可能是交替的使用这个设备的。
- 虚拟设备其实就是我们上个小节介绍的，采用 SPOOLing 技术，把独占设备改造成虚拟的共享设备，在采用了 SPOOLing 技术之后，我们可以把独占式的打印机改造成共享打印机，并且把它同时分配给多个进程使用，这是我们需要考虑的设备的固有属性。
如果从设备的分配算法这个角度来看的话，可以有很多我们很熟悉的算法来进行设备的分配，比如说先来先服务或者优先级高者优先，短任务优先等等。这些算法的具体策略，其实通过算法的名字就可以判断，所以这儿就不再展开赘述。
如果从设备分配的安全性角度来考虑的话，可以有这样的两种分配方式，一种叫安全分配方式，也就是为一个进程分配了设备之后，就一定会把进程阻塞，直到进程释放 IO 设备之后才会把它唤醒，让它继续往下执行。
我们来考虑一下进程请求打印机打印输出的例子，如果采用的是安全分配方式的话，那么一个进程在请求使用打印机，并且把打印机分配给他之后，进程就必须先阻塞等待。虽然按理来说进程只需要把数据丢给打印机，它其实就不用再管打印机那个设备，它还可以继续往下执行。但是由于我们采用的是安全分配的这种方式，所以进程不得不阻塞，一直到打印结束之后，进程才会被再次唤醒，继续往下执行。
所以采用安全分配方式的话，在一个时间段内，每个进程只能使用一个设备，它的优点就是破坏了我们之前学过的请求和保持条件，所以不会导致死锁，所以它才叫安全分配方式，但是缺点也很明显。就是对于一个进程来说，它的 CPU 和 IO 设备只能串行的工作，因此系统资源的利用率低，并且进程的执行效率也会降低。
与这种分配方式相反的，另一种叫做不安全分配方式，就是进程发出 IO 请求之后，系统为其分配 IO 设备，这个进程不会被阻塞，它可以继续往下执行，之后还可以发出更多的新的 IO 请求，一直到某一个 IO 请求得不到满足的时候，才会把进程阻塞。
还是以请求打印机打印输出为例子，假如说采用的是不安全分配方式的话，那么一个进程在请求打印机的服务之后，系统会把打印机资源分配给他，但是进程把数据丢给打印机之后，它其实就不需要再管打印机的打印输出过程，可以继续往下执行，甚至在之后的执行过程中，它还可以申请使用别的 IO 设备，比如说像扫描仪等等，所以如果采用的是不安全分配方式的话，那么一个进程可以同时使用多个设备，这种方式的优点就是效率高，进程的计算任务和 lO 任务可以并行的执行。但是缺点就像这个名字所说的这样，它不安全有可能会发生死锁。
我们在第二章中学过，如果采用的是这种方式的话，可以用死锁避免，也就是银行家算法来避免系统进入不安全状态。这是在设备分配的时候需要考虑的三个角度的问题。
# 静态分配和动态分配
接下来我们来看两种我们很熟悉的设备分配方式，静态分配和动态分配，所谓静态分配就是指进程运行之前就为其分配它所需要的全部资源，一直到进程运行结束之后，才把资源归还给系统。而如果说进程在运行之前，他所需要的全部资源，暂时得不到完全的满足的话，那么进程就暂时不能投入运行，这也是我们在死锁章节学过的内容。
其实静态分配方式就是破坏了请求和保持条件，所以采用这种分配方式的话是不会发生死锁的。讲到这里，希望大家也可以再回忆一下死锁发生的 4 个必要条件，分别可以用什么样的方法破坏这 4 个必要条件呢？这是大家需要思考和复习的地方
与静态分配方式相对的。另一种分配方式叫做动态分配方式，就是进程在运行过程当中动态的申请设备资源，并不是刚开始就得到全部的资源，这两种方式咱们在死锁小节当中也讲过，所以这就不再展开。
# 设备分配管理当中的数据结构
接下来我们来看一下设备分配管理当中需要用到哪些数据结构，讲这些数据结构之前，我们先来复习一下设备控制器还有通道之间的关系。
一个通道可以控制多个控制器，而一个控制器又可以控制多个设备，所以我们可以把它们之间的关系理解为一个树的这种形状。
从另一个角度来说，每一个设备它肯定会有一个它所从属的控制器，而每一个控制器也肯定会有一个它所从属的通道。这里需要注意一个系统中可能会有多个通道，由于要控制一个设备，肯定需要找到这个设备的控制器，而要控制一个控制器，肯定又需要找到控制器所从属的通道，所以设备分配管理中的数据结构需要表示出这种从属的关系。
那系统会为每一个设备配置一张设备控制表 DCT，用于记录设备的使用情况，一个设备分配表当中可能会有这样的一些常用的字段
- 设备类型指的是这个设备到底是打印机还是扫描仪还是键盘等等。
- 而设备标识符其实就是我们之前提到过很多次的所谓的物理设备名，它是这个设备的唯一 ID，系统中各个不同的设备，它的设备标识符都是不同的。
- 设备状态字段又是用来区分设备此时是处于忙碌空闲，还是故障等等这些不同的状态
- 而指向控制器表的指针，这个就是咱们刚才提到的用于找到一个设备，它所从属的控制器到底是哪一个
- 重复执行次数或时间，这个字段是用来干什么的？因为设备也有很多机械零件，所以设备故障的几率其实是很大的，比如说使用打印机或者复印机的时候，经常会出现卡纸的现象，不过并不是说执行此 IO 操作失败之后，就认为这个此 IO 操作真的失败了，系统会重复执行多次 IO 操作，这个字段用于记录它到底失败了几次，只有重复执行多次之后仍然不成功，那才认为这次 IO 是失败的。
- 最后一个字段，设备队列的队首指针，这个字段其实就是用于指向此时正在等待着使用这个设备的进程队列的，这个队列由进程的 PCB 组成，还记不记得咱们之前在进程管理章节当中曾经提到过，系统会根据各个进程阻塞原因的不同，将进程的 PCB 挂到不同的阻塞队列当中。假如说我们的进程此时是正在等待某一个 IO 设备的分配，而这个 IO 设备又暂时没法分配给他的话，那么进程就会挂到 IO 设备控制表所指向的等待队列的对位。所以这个队列指针其实指向的就是相应的阻塞队列
这是系统中需要配置的第一种数据结构，设备控制表。
第二种数据结构叫做控制器控制表，coct。每一个设备控制器都会对应一张设备控制表，系统会根据设备控制表当中的信息，对设备控制器进行相应的操作和管理。这个表当中也会有一些很常用的字段，比如说控制器的标识符，这个就是各控制器的唯一 ID，另外还需要记录设备控制器的状态，比如说忙碌还是空闲，再者每个设备控制器都会有一个它所从属的通道，所以在设备控制器的控制表当中，也会有一个指向通道表的指针，系统可以根据指针找到它所从属的通道，最后还需要有一个队首指针和一个队尾指针，队列其实指向了正在等待设备控制器的进程，这是需要配置的第二个数据结构控制器控制表。
第三个数据结构是通道控制表，chct 每个通道都会对应一张通道控制表，那么操作系统会根据这个表的信息对通道进行相应的操作和管理，
与之前的两个数据结构很类似，通道标识符指的是这个通道的唯一 ID，通道状态就是指明它是忙碌空闲还是故障。而第三个与通道连接的控制器表的首址，操作系统可以根据这个字段找到这个通道控制的所有的控制器相关的信息，也就是找到这些控制器控制表的集合。
如果说通道此时暂时不能为一个进程服务，那么进程依然是需要等待通道的服务，所以最后的这两个字段就是用于指向等待通道的那些进程队列的，这是通道控制表的一个作用。
第四个需要设置的数据结构叫系统设备表，sdt，这个表当中记录了系统中全部设备的情况，每一个设备会对应一个表目，那么一个表目中又会记录这个表目所对应的设备类型，比如说它是打印机还是扫描仪还是键盘，也会记录这个设备的标识符，也就是它的物理设备名唯一的 ID。
当然这个表目中还包含着这个设备的控制表 DCT，最后还记录了这个设备的驱动程序的入口地址。再次强调系统设备表当中记录的是系统中全部设备的情况，所以其实当用户用设备名请求使用某一个设备的时候，操作系统是可以从系统控制表当中来找到用户指定的设备到底是哪一个的。
# 设备分配的步骤
接下来我们来分析一下设备分配的具体步骤。
第一步，操作系统会根据进程提出的物理设备名，查找 sdt 也就是系统设备表。用户在编程的时候需要提供物理设备名作为系统调用的参数，操作系统用某种方式来查找系统控制表的时候，就会把各个表目当中记录的设备标识服务和用户提供的物理设备名进行比对，然后找到这两个参数相匹配的一个表项之后，就可以找到设备对应的设备控制表 DCT 了，
于是接下来会根据 DCT 当中记录的信息来判断此时这个设备是否空闲。如果设备空闲的话，就可以把设备分配给进程，而如果这个设备此时是忙碌的话，那么就需要把进程挂到设备对应的等待队列阻塞队列当中，一直到设备空闲，并且把设备分配给该进程之后，才会把进程重新唤醒。
除了分配设备之外，还需要把这个设备对应的控制器也分配给进程，所以系统会根据字段找到这个设备对应的控制器控制表，也就是 coct 那与刚才类似，首先会检查控制器此时是不是空闲，如果空闲的话可以把控制器分配给进程，如果控制器忙碌，那就需要把进程放到控制器的阻塞队列当中
分配了控制器之后，还需要给进程分配相应的通道，于是又会根据指针找到相应的通道控制表，也就是 chct 这个过程也和刚才类似，首先会判断通道的状态，如果通道空闲的话，那么可以把通道分配给进程，如果通道忙碌的话，就需要把进程挂到通道的阻塞队列当中，只有设备控制器和通道这三个东西都分配成功的时候，这次设备分配才算成功，之后就可以开始启动 IO 设备进行数据传送了，这是设备分配的一个步骤：
但我们来思考一下分配过程有什么缺点，还记不记得我们刚才说的采用这种分配方式的话，用户在编程的时候其实是需要提供物理设备名作为系统调用的参数的，所以这种方式对用户编程来说是很不方便的。假如说用户使用的物理设备名叫 a，而之后物理设备又进行了更换，把物理设备 a，换成了物理设备 b，但是由于用户在编程的时候使用的依然是 a 这个物理设备名，因此只要物理设备更换了，那么用户之前所写的程序就无法运行了。他在请求使用物理设备 a 的时候，肯定是没办法给他分配成功的。
除了这个缺点之外，当一个进程他请求的物理设备正在忙碌的时候，即使系统当中还有同类型的设备，当然进程依然是必须阻塞等待的。比如说我们一台电脑上连了三台打印机，如果说进程请求使用的是第一台打印机，那么虽然第二台和第三台打印机此时有可能是空闲的，但只要第一台打印机此时是忙碌的，进程依然是需要阻塞等待，但是显然其实可以把进程的打印任务把它分配给第二台和或者第三台打印机进行。
因此采用这种方式的话，也会导致设备的利用率不高的问题。解决这个问题的方法，其实咱们在之前谈到过，就是可以建立逻辑设备名与物理设备名之间的映射机制，用户编程的时候使用的是逻辑设备名，然后由操作系统来负责完成逻辑设备名到物理设备名的转换。
引入这种机制之后，进程在请求使用某种设备的时候，只需要提供逻辑设备名。所谓的逻辑设备名其实就是指明他所要使用的设备类型，比如说他想使用的是打印机这种类型的设备，由于系统控制表当中有一个字段，它就是记录的设备的类型因此，操作系统可以根据用户提供的逻辑设备名，也就是设备类型来依次查找系统控制表，然后找到一个指定类型的，并且空闲的设备把它分配给进程。只有这个类型的设备全部都处于忙碌状态的时候，才需要把进程阻塞，
把这个设备分配给进程之后，操作系统还需要在逻辑设备表 lut 当中新增一个表项，逻辑设备表就是用于记录逻辑设备名到物理设备名的一个映射关系的一张表，除了映射关系之外，还需要记录这个设备对应的驱动程序的入口地址，之后的操作就和之前一样了，可以根据设备控制表找到相应的控制器控制表，然后把控制器分配给设备之后，又再根据控制器控制表找到通道控制表，把通道分配给设备，只有进程第一次通过逻辑设备名申请使用一个设备的时候，操作系统才会来查询系统控制表。
如果之后进程再次以相同的逻辑设备名来请求使用设备的话，那么操作系统首先做的是会在逻辑设备表当中查找逻辑设备对应的物理设备，然后找到相应的表项之后，就可以找到这个设备对应的驱动程序了
有这样的两种方式设置逻辑设备表，第一种就是整个系统中只有一张逻辑设备表，这样的话各个用户所使用的逻辑设备名是不允许重复的，所以这种方式只适合用于单用户操作系统。
第二种的话每个用户设置一张逻辑设备表，这样的话不同用户的逻辑设备名可以重复，它可以适用于多用户的操作系统，这一点咱们在之前的小节当中也提到过。
# 小结
那么小节我们介绍了设备的分配与回收问题，主要介绍的是设备的分配，其实设备的回收无非就是把那些数据结构再把它改回来就行了。
在设备分配的时候，我们应该考虑这样的三种因素，其中不太容易记忆的是安全分配方式和不安全分配方式。大家在复习到相应概念的时候稍微留个心眼，在选择题当中有可能进行考察。
另外静态分配和动态分配这两个术语也要有印象，其实静态分配方式就是破坏了请求和保持这一个产生死锁的必要条件，而动态分配方式效率更高，但是有可能产生死锁。一般来说我们可以用银行家算法来避免死锁，或者结合资源分配图来对死锁进行检测和解除。银行家算法的规则，还有死锁的检测和解除，这也是大家需要回顾的知识点。
我们之后还介绍设备分配管理当中所需要用到的数据结构，这些数据结构其实并不需要死记硬背，设备控制表、控制器控制表，还有通道控制表，他们分别对应设备，控制器，还有通道这三种东西，我们其实只需要理解这三种东西的一个对应关系，我们就可以知道这些数据结构他们大致是需要做什么事情的了。一个通道会控制多个控制器，一个控制器又会控制多个设备，所以它们之间的关系是一种树形的关系。
而无论是设备还是控制器还是通道，他们都会有一个字段叫做等待队列的指针。其实就是当这种资源暂时不能分配给某个进程的时候，需要把进程的 PCB插入到相应资源等待队列当中。系统设备表集中了所有的设备相关的信息操作系统，可以通过这个表来统一的对设备进行查询检索。
基于这些数据结构，我们介绍了设备分配的具体步骤，我们需要知道的是如果采用的是物理设备名来请求使用一个设备的话，它会存在一些很明显的缺点，并且这些缺点可以用逻辑设备名和物理设备名映射的这种方式来解决，这个地方是大家需要着重理解的点，很有可能在选择题当中进行考察。
