1. 银行家算法概述与核心思想
银行家算法是操作系统中用于避免死锁的经典算法,由著名计算机科学家Edsger Dijkstra于1965年提出。这个算法最初是为银行系统设计的资金分配方案,后来被移植到操作系统的资源分配场景中。其核心思想是通过预判资源分配后系统是否处于安全状态,来决定是否满足进程的资源请求。
在实际操作系统中,进程对资源(如CPU时间、内存、I/O设备等)的竞争可能导致死锁。银行家算法通过以下四个关键数据结构来维护系统状态:
- Available向量:表示系统中每类资源当前可用的数量
- Max矩阵:记录每个进程对每类资源的最大需求量
- Allocation矩阵:记录当前已分配给每个进程的各类资源数量
- Need矩阵:表示每个进程还需要的各类资源数量(Need = Max - Allocation)
重要提示:银行家算法要求进程预先声明其最大资源需求,这在现实系统中可能难以精确预估,因此算法更适合理论研究和教学场景。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 算法执行流程与安全状态判定
2.1 算法基本步骤
银行家算法的执行可以分为以下几个关键步骤:
-
请求检查:当进程提出资源请求时,系统首先检查请求是否小于等于该进程声明的Need值。如果超过,直接拒绝请求。
-
资源可用性检查:系统检查可用资源是否能满足当前请求。如果不足,进程必须等待。
-
假设分配:系统假设分配请求的资源给进程,并临时修改各数据结构:
- Available = Available - Request
- Allocation[i] = Allocation[i] + Request
- Need[i] = Need[i] - Request
-
安全性检查:系统执行安全性算法,判断假设分配后系统是否仍处于安全状态。
2.2 安全状态判定算法
安全状态判定的核心是寻找一个安全序列——即一个进程执行顺序,使得系统可以按此顺序为每个进程分配资源并完成它们的执行,而不会导致死锁。具体步骤如下:
- 初始化:
- Work = Available (复制当前可用资源)
- Finish = [false, false, ..., false]
