面试题：设备管理之高级难度：I/O设备分配与死锁处理

Question

在一个多道程序设计系统中，有三类I/O设备（打印机、磁带机、磁盘），有三个进程P1、P2、P3，它们对设备的请求和使用情况如下：P1请求打印机、使用一段时间后请求磁带机；P2请求磁带机、使用一段时间后请求磁盘；P3请求磁盘、使用一段时间后请求打印机。请设计一种合理的I/O设备分配策略，避免死锁的发生，并阐述该策略的原理及实现步骤。

Answer 1

分配策略

采用资源分配图算法中的银行家算法的思想来设计I/O设备分配策略。

1. 资源分配状态记录：记录每个进程对各类I/O设备的需求（最大需求）、已分配到的设备以及当前可用的设备。
   • 例如，设打印机为R1，磁带机为R2，磁盘为R3。记录每个进程对这三种资源的最大需求数（如P1对R1需求1，对R2需求1，对R3需求0），已分配给每个进程的资源数（如P1已分配到R1为0，R2为0，R3为0），当前系统可用资源数（如当前R1可用1，R2可用1，R3可用1）。
2. 安全性检查：当一个进程提出资源请求时，系统先假设为其分配资源，然后检查此时系统状态是否安全。所谓安全状态，是指系统能找到一个进程执行序列，使得每个进程都能在有限时间内获得所需资源并完成运行，释放其所占资源。
3. 分配决策：如果假设分配资源后系统处于安全状态，则实际为该进程分配资源；否则，拒绝分配。

原理

银行家算法的核心原理是通过对资源分配的预测和安全性检查，确保系统始终处于安全状态，从而避免死锁。它通过提前知晓每个进程对资源的最大需求，在每次资源请求时，评估分配资源后系统是否仍能保证所有进程都能顺利完成，避免因资源分配不当导致进程相互等待资源而形成死锁。

实现步骤

1. 初始化状态：
   • 记录每个进程对打印机、磁带机、磁盘的最大需求。
   • 记录当前系统中打印机、磁带机、磁盘的可用数量。
   • 记录每个进程已分配到的打印机、磁带机、磁盘数量。
2. 进程请求资源：
   • 当进程P提出资源请求时，检查其请求的资源数是否超过它所声明的最大需求，如果超过则拒绝请求。
   • 检查系统当前可用资源是否能满足进程P的请求，如果不能满足则拒绝请求。
3. 假设分配：
   • 如果上述检查都通过，系统假设为进程P分配其所请求的资源，更新系统可用资源数量和进程P已分配资源数量。
4. 安全性检查：
   • 尝试寻找一个安全序列。从所有进程中，找出一个进程，其所需资源小于等于当前系统可用资源。
   • 如果找到这样的进程，则假设该进程运行完成并释放其占用的资源，更新系统可用资源。
   • 重复上述步骤，尝试找出所有进程的一个执行序列（安全序列）。
5. 实际分配或拒绝：
   • 如果能找到安全序列，说明假设分配后系统处于安全状态，则实际为进程P分配资源。
   • 如果找不到安全序列，说明假设分配后系统处于不安全状态，撤销假设分配，拒绝进程P的资源请求。