手把手教你理解银行家算法：从山大操作系统考题到实际代码实现

手把手教你理解银行家算法从理论到代码实现银行家算法是操作系统中用于避免死锁的经典算法由Edsger Dijkstra于1965年提出。这个算法之所以被称为银行家算法是因为它模拟了银行家如何安全地分配资金给客户确保银行永远不会进入无法满足所有客户需求的状态。在操作系统中资源相当于银行的资金进程相当于客户算法确保系统永远不会进入不安全状态。1. 银行家算法核心概念1.1 资源分配的基本模型在操作系统中资源可以分为可抢占资源和不可抢占资源。银行家算法主要处理的是不可抢占资源即一旦资源被分配给某个进程在该进程释放前不能被系统或其他进程强行夺走。系统中有三类关键数据结构可用资源向量(Available)表示系统中每类资源当前可用的数量最大需求矩阵(Max)表示每个进程对每类资源的最大需求量分配矩阵(Allocation)表示当前已分配给每个进程的每类资源数量通过这些数据结构我们可以计算出需求矩阵(Need)Need[i][j] Max[i][j] - Allocation[i][j]其中Need[i][j]表示进程i还需要资源j的数量。1.2 安全状态与安全序列安全状态是指系统能按某种顺序为每个进程分配资源并避免死锁。具体来说如果存在一个安全序列P1, P2, ..., Pn使得对于每个PiPi仍然可以请求的资源能被当前可用资源加上所有Pj(ji)持有的资源满足那么系统处于安全状态。判断系统是否安全的算法步骤如下初始化Work AvailableFinish[i] false (对所有i)寻找一个i使得Finish[i] falseNeed[i] Work如果找到这样的i则Work Work Allocation[i]Finish[i] true 返回步骤2如果所有Finish[i] true则系统处于安全状态2. 银行家算法的具体步骤2.1 资源请求算法当进程Pi发出资源请求Request[i]时系统执行以下步骤如果Request[i] Need[i]转到步骤2否则报错进程请求超过其声明的最大需求如果Request[i] Available转到步骤3否则Pi必须等待资源不足系统假装分配资源给PiAvailable Available - Request[i]Allocation[i] Allocation[i] Request[i]Need[i] Need[i] - Request[i]检查系统是否仍处于安全状态如果是则实际分配资源如果否则Pi必须等待并恢复原来的资源分配状态2.2 算法实例分析考虑一个系统有3类资源(A,B,C)总量为(10,5,7)。有5个进程P0-P4初始分配如下进程AllocationMaxAvailableA B CA B CA B CP00 1 07 5 33 3 2P12 0 03 2 2P23 0 29 0 2P32 1 12 2 2P40 0 24 3 3首先计算Need矩阵进程NeedA B CP07 4 3P11 2 2P26 0 0P30 1 1P44 3 1安全序列检查过程Work (3,3,2)P1的Need(1,2,2) Work(3,3,2) → 选择P1Work (3,3,2) (2,0,0) (5,3,2)Work (5,3,2)P3的Need(0,1,1) Work(5,3,2) → 选择P3Work (5,3,2) (2,1,1) (7,4,3)Work (7,4,3)P4的Need(4,3,1) Work(7,4,3) → 选择P4Work (7,4,3) (0,0,2) (7,4,5)Work (7,4,5)P2的Need(6,0,0) Work(7,4,5) → 选择P2Work (7,4,5) (3,0,2) (10,4,7)Work (10,4,7)P0的Need(7,4,3) Work(10,4,7) → 选择P0Work (10,4,7) (0,1,0) (10,5,7)因此安全序列为P1, P3, P4, P2, P0系统处于安全状态。3. Python实现银行家算法class BankersAlgorithm: def __init__(self, available, max_claim, allocation): self.available available self.max_claim max_claim self.allocation allocation self.n_process len(allocation) self.n_resource len(available) self.need [[max_claim[i][j] - allocation[i][j] for j in range(self.n_resource)] for i in range(self.n_process)] def is_safe(self): work self.available.copy() finish [False] * self.n_process safe_seq [] while len(safe_seq) self.n_process: found False for i in range(self.n_process): if not finish[i] and all(self.need[i][j] work[j] for j in range(self.n_resource)): work [work[j] self.allocation[i][j] for j in range(self.n_resource)] finish[i] True safe_seq.append(i) found True break if not found: return False, [] return True, safe_seq def request_resources(self, process_id, request): if any(request[j] self.need[process_id][j] for j in range(self.n_resource)): return False, Error: Request exceeds maximum claim if any(request[j] self.available[j] for j in range(self.n_resource)): return False, Process must wait, resources not available # Try to allocate for j in range(self.n_resource): self.available[j] - request[j] self.allocation[process_id][j] request[j] self.need[process_id][j] - request[j] # Check if system is still safe is_safe, _ self.is_safe() if not is_safe: # Rollback for j in range(self.n_resource): self.available[j] request[j] self.allocation[process_id][j] - request[j] self.need[process_id][j] request[j] return False, System would be unsafe, process must wait return True, Resources allocated successfully4. C语言实现关键部分#include stdbool.h #include stdio.h #define PROCESSES 5 #define RESOURCES 3 bool isSafe(int available[RESOURCES], int max[PROCESSES][RESOURCES], int allocation[PROCESSES][RESOURCES]) { int work[RESOURCES]; bool finish[PROCESSES] {false}; int safeSeq[PROCESSES]; int count 0; // Calculate need matrix int need[PROCESSES][RESOURCES]; for (int i 0; i PROCESSES; i) for (int j 0; j RESOURCES; j) need[i][j] max[i][j] - allocation[i][j]; // Initialize work available for (int j 0; j RESOURCES; j) work[j] available[j]; while (count PROCESSES) { bool found false; for (int i 0; i PROCESSES; i) { if (!finish[i]) { bool canProceed true; for (int j 0; j RESOURCES; j) if (need[i][j] work[j]) { canProceed false; break; } if (canProceed) { for (int j 0; j RESOURCES; j) work[j] allocation[i][j]; finish[i] true; safeSeq[count] i; found true; } } } if (!found) return false; } return true; }5. 银行家算法的实际应用与局限性5.1 适用场景银行家算法特别适合以下场景资源类型固定且数量有限的系统进程数量和资源需求可预测的环境需要高可靠性的系统如航空控制系统、金融交易系统等5.2 局限性尽管银行家算法理论上很完美但在实际应用中存在一些限制需要预先知道最大资源需求进程必须事先声明其最大资源需求这在实际中往往难以准确预估进程数量固定算法假设进程数量不变而现实中进程可能动态创建和终止资源数量固定算法假设资源数量不变但实际系统中资源可能故障或新增性能开销每次资源请求都需要执行安全性检查可能带来显著性能开销5.3 现代系统中的替代方案由于银行家算法的限制现代操作系统通常采用其他策略来应对死锁死锁预防通过破坏死锁四个必要条件之一死锁检测与恢复允许死锁发生但能检测并恢复忽略死锁如Unix/Linux等通用操作系统通常采用这种方式在实际项目中使用银行家算法时我发现最大的挑战是准确预估进程的最大资源需求。一个实用的技巧是为进程设置合理的资源使用上限并留出足够的缓冲资源。