面试题：并发与同步之资源图状态转换基础

Question

在操作系统中，资源图从安全状态转换到不安全状态通常会因为什么原因？请举例说明如何通过资源分配算法避免这种转换。

Answer 1

原因

1. 资源分配不当：当系统分配资源时，如果没有考虑到进程未来对资源的需求以及系统现有资源总量，盲目地将资源分配给进程，可能导致后续进程无法获取足够资源完成任务，从而使系统从安全状态转变为不安全状态。例如，假设系统有3个进程P1、P2、P3，有10个同类资源。P1已占有5个资源，还需3个；P2已占有2个资源，还需6个；P3已占有3个资源，还需2个。若此时将剩余的0个资源分配给P2（不合理分配），那么P1和P3都无法获取足够资源完成任务，系统进入不安全状态。
2. 进程动态申请资源：进程在运行过程中动态申请资源，若系统对这种动态申请处理不当，也会导致状态转换。比如，一个原本处于安全状态的系统，某进程突然申请大量额外资源，而系统为了满足其请求，过度分配资源，使得其他进程后续无法正常获取资源完成，导致系统进入不安全状态。

避免转换的资源分配算法举例 - 银行家算法

1. 数据结构：
   • Available：一个向量，表示系统中各类资源的可用数量。例如，若系统有三种资源A、B、C，Available = [3, 3, 2] 表示A资源有3个可用，B资源有3个可用，C资源有2个可用。
   • Max：一个矩阵，Max[i][j] 表示进程 i 对资源 j 的最大需求量。例如，Max[1][2] 表示进程1对资源2的最大需求量。
   • Allocation：一个矩阵，Allocation[i][j] 表示进程 i 当前已分配到的资源 j 的数量。
   • Need：一个矩阵，Need[i][j] = Max[i][j] - Allocation[i][j]，表示进程 i 还需要的资源 j 的数量。
2. 资源请求处理步骤：
   • 当进程 Pi 发出资源请求 Requesti 时，首先检查 Requesti 是否小于等于 Needi。若不满足，则出错，因为进程请求的资源超过了它声明的最大需求量。
   • 然后检查 Requesti 是否小于等于 Available。若不满足，说明当前系统没有足够资源分配给该进程，Pi 需等待。
   • 若以上两个条件都满足，系统尝试进行资源分配，即修改Available = Available - Requesti；Allocation[i] = Allocation[i] + Requesti；Need[i] = Need[i] - Requesti。
   • 分配后，系统执行安全性检查算法，通过尝试找到一个安全序列（即所有进程都能在有限时间内获取足够资源完成任务的进程执行顺序）。如果能找到安全序列，说明此次资源分配是安全的，允许分配；若找不到安全序列，则撤销刚才的分配，让 Pi 等待。例如，假设有进程P1、P2、P3，系统资源向量Available = [2, 3, 3]，进程P1请求资源Request1 = [1, 0, 2]，经过上述步骤检查和分配后，再进行安全性检查，若能找到如<P1, P2, P3>这样的安全序列，就完成分配，否则撤销分配，避免系统进入不安全状态。