【操作系统】：一文带你完全了解银行家算法
一、前言
🔥 银行家算法（Banker’s Algorithm）是操作系统中用于避免死锁 的一种资源分配策略。它由艾兹赫尔·戴克斯特拉（Edsger Dijkstra）提出，常用于多道程序系统中对资源进行安全分配。
死锁：多个进程在执行过程中，因为竞争资源会造成相互等待的局面。如果没有外力作用，这些进程将永远无法向前推进。此时称系统处于死锁状态或者系统产生了死锁。
- 安全序列：系统按某种顺序并发进程，并使它们都能达到获得最大资源而顺序完成的序列为安全序列
- 安全状态：能找到安全序列的状态称为安全状态，安全状态不会导致死锁
- 不安全状态：在当前状态下不存在安全序列，则系统处于不安全状态
银行家算法只允许系统进入安全状态，防止进入不安全状态。
二、简介
1. 基本思想
⛵️ 银行家算法顾名思义，其灵感来源于 银行的借贷业务。银行拥有一定数量的本金，需要满足多个客户的借贷周转。为了防止银行家资金无法周转而倒闭，银行在发放贷款前，会仔细评估客户能否最终还清所有贷款，以保证银行不会破产。
在操作系统中研究资源分配策略时，也面临类似的问题。系统中有限的资源需要供多个进程使用。我们必须确保获得资源的进程能够在有限的时间内归还资源，以便其他进程能够继续使用。如果资源分配不当，就可能发生进程循环等待资源的现象，导致所有进程都无法继续执行，这就是我们所说的死锁现象。银行家算法正是为了解决这个问题而设计的。
2. 相关概念
为了实现银行家算法，我们需要定义几个关键概念：
- 资源类型： 系统中存在若干种不同类型的资源（例如，CPU、内存、打印机、磁带机等），每种资源都有一定的数量。
- 进程需求： 每个进程在运行过程中都需要申请资源。但是，一个关键的前提是，每个进程必须事先声明其最大资源需求。这是银行家算法能够运作的基础。
- 可用资源向量（Available）： 这是一个长度为 m 的一维数组（其中 m 是资源类型的数量）。
Available[j]表示当前系统中第 j 类资源的剩余数量。 - 最大需求矩阵（Max）： 这是一个 n×m 的矩阵（其中 n 是进程的数量）。
Max[i][j]表示进程 Pi 在其整个执行过程中对第 j 类资源可能需要的最大实例数量。 - 已分配矩阵（Allocation）： 这是一个 n×m 的矩阵。
Allocation[i][j]表示当前已分配给进程 Pi 的第 j 类资源的实例数量。 - 需求矩阵（Need）： 这是一个 n×m 的矩阵。
Need[i][j]表示进程 Pi 还需要多少第 j 类资源才能完成其执行。它的计算方式是：
这个矩阵对于算法来说至关重要，因为它告诉我们每个进程还需要多少资源。
3. 银行家算法步骤
银行家算法主要包含两个核心部分：安全性检查算法和资源请求处理算法。
步骤 1：数据初始化
在任何资源请求发生之前，系统需要初始化以下数据：
- 可用资源向量 (
Available)：系统当前每种资源的可用数量。 - 已分配矩阵 (
Allocation)：当前资源在各个进程之间的分配情况。 - 最大需求矩阵 (
Max)：每个进程可能需要的最大资源量。
根据这些数据，计算出需求矩阵 (Need)：Need[i][j] = Max[i][j] - Allocation[i][j]。这一步是为后续的算法执行设置系统当前状态
步骤 2：安全性检查算法（Safety Algorithm）
这个算法是银行家算法的核心，用于判断系统当前状态是否安全。
1）初始化：
- 创建一个名为
Work的向量，它最初与Available向量相等（即Work = Available）。Work代表了系统当前可以使用的资源总量（如果所有进程都释放了它们已分配的资源）。 - 创建一个名为
Finish的布尔型数组，大小为 n（进程数量），并将其所有元素初始化为False（即Finish[i] = False对于所有进程 i）。Finish[i]用于标记进程 Pi 是否能够顺利完成其执行。
2）寻找安全序列的迭代过程：
- 循环： 重复以下步骤，直到无法再找到满足条件的进程为止。
- 寻找进程：
遍历所有进程，寻找一个索引 i，使得同时满足以下两个条件：
Finish[i] == False（表示进程 Pi 尚未完成其执行）。Need[i] <= Work（表示进程 Pi 剩余的资源需求可以由当前Work向量中的资源满足）。
- 如果找不到这样的 i： 跳出循环。这意味着在当前
Work资源下，没有更多进程可以安全地执行。 - 如果找到这样的 i：
- 假定将所需的资源分配给 Pi。
- 模拟 Pi 完成执行并释放资源：更新
Work = Work + Allocation[i]。这意味着进程 Pi 所占用的资源已经被释放，并回到了系统的可用资源池中。 - 将进程 Pi 标记为已完成：
Finish[i] = True。
3）最终检查：
- 循环结束后，如果所有进程的
Finish[i] == True，那么系统处于安全状态，并且在迭代过程中找到的进程顺序构成了一个安全序列。 - 否则，如果至少有一个
Finish[i] == False，那么系统处于不安全状态。
步骤 3：资源请求处理算法（Resource Request Algorithm）
当一个进程
提出资源请求时，银行家算法会执行以下步骤来决定是否为其分配资源：
- 检查请求合法性：
- 令
Request为进程
P_k 提出的资源请求向量。
- 第一步： 检查请求是否超过该进程的最大需求 (
Need)。如果Request[j] > Need[k][j]对于任何资源类型 j 成立，说明进程请求的资源超过了它之前声明的最大需求，这是一个错误，算法会拒绝此请求 - 第二步： 检查系统当前是否有足够资源可用 (
Available)。如果Request[j] > Available[j]对于任何资源类型 j 成立，说明系统当前没有足够的资源来满足请求，算法会拒绝此请求，并通常会阻塞该进程（使其等待资源）
- 令
- 试探性分配：
- 如果上述检查都通过，系统会试探性地将资源分配给该进程，模拟一个新的系统状态。
- 更新
Available：Available = Available - Request - 更新
Allocation：Allocation[k] = Allocation[k] + Request - 更新
Need：Need[k] = Need[k] - Request
- 调用安全性检查：
- 在新状态下，调用**安全性检查算法（步骤 2）**来判断这个试探性分配后的系统是否处于安全状态。
- 如果安全： 说明这个请求可以被满足且不会导致死锁。系统将正式分配资源给进程
P_k ，并保持当前的新状态。
- 如果不安全： 说明如果满足这个请求，系统将进入不安全状态，可能导致死锁。在这种情况下，系统会回滚之前的试探性分配（将
Available、Allocation和Need恢复到请求前的状态），拒绝该进程的请求，并通常会阻塞该进程，使其等待资源。
三、实例理解🌮
假设有 5 个进程 P0~P4，3 种资源 A、B、C，初始情况如下：
进程 | Allocation(A,B,C) | Max(A,B,C) |
|---|---|---|
P0 | (0,1,0) | (7,5,3) |
P1 | (2,0,0) | (3,2,2) |
P2 | (3,0,2) | (9,0,2) |
P3 | (2,1,1) | (2,2,2) |
P4 | (0,0,2) | (4,3,3) |
系统当前可用资源：Available = (3,3,2)，此时 我们可以通过银行家算法来判断某个资源请求是否可以被接受。
步骤如下：
首先，我们需要计算出 Need 矩阵： Need[i][j] = Max[i][j] - Allocation[i][j]
进程 | Need (A,B,C) |
|---|---|
P0 | (7-0, 5-1, 3-0) = (7,4,3) |
P1 | (3-2, 2-0, 2-0) = (1,2,2) |
P2 | (9-3, 0-0, 2-2) = (6,0,0) |
P3 | (2-2, 2-1, 2-1) = (0,1,1) |
P4 | (4-0, 3-0, 3-2) = (4,3,1) |
现在，我们通过银行家算法来判断某个资源请求是否可以被接受。
例：假设进程 P1 请求资源 Request = (1,0,2)
- 检查请求合法性：
- P1 的
Need是 (1,2,2)。请求 (1,0,2)<= Need (1,2,2)，满足条件 (1<=1, 0<=2, 2<=2)。 - 当前
Available是 (3,3,2)。请求 (1,0,2)<= Available (3,3,2)，满足条件 (1<=3, 0<=3, 2<=2)。 - 请求合法。
- P1 的
- 试探性分配：
- 更新
Available:(3,3,2) - (1,0,2) = (2,3,0) - 更新
Allocationfor P1:(2,0,0) + (1,0,2) = (3,0,2) - 更新
Needfor P1:(1,2,2) - (1,0,2) = (0,2,0)
新的系统状态：
Available = (2,3,0)Allocationfor P1 becomes(3,0,2)Needfor P1 becomes(0,2,0) - 更新
- 调用安全性检查算法：
Work = (2,3,0)Finish = [F, F, F, F, F]- 寻找进程 P0：
Need[P0]=(7,4,3)，Work=(2,3,0)，Need[P0]不<= Work。 - 寻找进程 P1：
Need[P1]=(0,2,0)，Work=(2,3,0)，Need[P1]<= Work。- 满足！将 P1 标记为
Finish[P1]=T。 Work = Work + Allocation[P1] = (2,3,0) + (3,0,2) = (5,3,2)。Finish = [F, T, F, F, F]。
- 满足！将 P1 标记为
- 再次寻找进程：
Work=(5,3,2) - 寻找进程 P2：
Need[P2]=(6,0,0)，Work=(5,3,2)，Need[P2]不<= Work。 - 寻找进程 P3：
Need[P3]=(0,1,1)，Work=(5,3,2)，Need[P3]<= Work。- 满足！将 P3 标记为
Finish[P3]=T。 Work = Work + Allocation[P3] = (5,3,2) + (2,1,1) = (7,4,3)。Finish = [F, T, F, T, F]。
- 满足！将 P3 标记为
- 再次寻找进程：
Work=(7,4,3) - 寻找进程 P0：
Need[P0]=(7,4,3)，Work=(7,4,3)，Need[P0]<= Work。- 满足！将 P0 标记为
Finish[P0]=T。 Work = Work + Allocation[P0] = (7,4,3) + (0,1,0) = (7,5,3)。Finish = [T, T, F, T, F]。
- 满足！将 P0 标记为
- 再次寻找进程：
Work=(7,5,3) - 寻找进程 P2：
Need[P2]=(6,0,0)，Work=(7,5,3)，Need[P2]<= Work。- 满足！将 P2 标记为
Finish[P2]=T。 Work = Work + Allocation[P2] = (7,5,3) + (3,0,2) = (10,5,5)。Finish = [T, T, T, T, F]。
- 满足！将 P2 标记为
- 再次寻找进程：
Work=(10,5,5) - 寻找进程 P4：
Need[P4]=(4,3,1)，Work=(10,5,5)，Need[P4]<= Work。- 满足！将 P4 标记为
Finish[P4]=T。 Work = Work + Allocation[P4] = (10,5,5) + (0,0,2) = (10,5,7)。Finish = [T, T, T, T, T]。
- 满足！将 P4 标记为
- 所有进程
Finish都为True。所以，这个请求是安全的！（P1 -> P3 -> P0 -> p2 ->p4）
结论： 进程 P1 的资源请求 (1,0,2) 可以被接受，系统将正式完成资源的分配。
四、 优缺点
✅ 优点：
- 有效避免死锁： 这是银行家算法最核心的优势，它通过预判资源分配的安全性来从根本上避免死锁的发生。
- 确保系统安全： 在已知每个进程的最大资源需求的前提下，算法能够保证系统始终处于安全状态，从而避免了因资源分配不当而导致的系统崩溃或停滞。
❌ 缺点：
- 必须提前知道每个进程的最大资源需求： 在实际的操作系统环境中，进程在启动时很难准确预测其运行过程中可能需要的最大资源量。这大大限制了银行家算法在通用操作系统中的广泛应用。
- 算法效率较低： 尤其当系统中的进程数量和资源种类很多时，每次请求都需要进行安全性检查，涉及矩阵操作和循环，这会消耗较多的计算资源，导致算法效率相对较低。
- 不适用于实时系统或动态变化大的系统： 实时系统对响应时间有严格要求，银行家算法的计算开销可能无法满足这些要求。同时，对于资源需求频繁变化或进程动态创建/销毁的系统，算法的开销会变得更大，且难以维持其前提假设。
- 资源利用率可能不高： 为了确保安全，银行家算法有时会拒绝一些本来可以满足的请求，因为满足这些请求会使系统进入不安全状态。这可能导致资源处于空闲状态，但却无法被进程使用，从而降低了资源的利用率。
五、代码实现
本实验的目的是通过编写和调试一个模拟系统动态分配资源的银行家算法程序，有效地避免死锁发生。具体要求如下：
- 初始化系统资源： 程序启动时，应允许用户或预设方式定义系统拥有的各类资源总量。
- 动态申请资源： 提供用户通过键盘输入的方式，允许进程动态地提出资源申请。例如，指定哪个进程申请多少哪种资源。
- 试探性分配与安全性判断： 当进程提出请求时，程序应根据银行家算法的“资源请求处理算法”进行试探性分配。然后，调用“安全性检查算法”来判断新状态是否安全。
- 正式分配或拒绝：
- 如果试探性分配后系统处于安全状态，则程序应修改系统的
Available、Allocation和Need矩阵，正式分配资源给请求进程，并提示成功。 - 如果试探性分配后系统处于不安全状态，则程序应提示不能满足请求，并将
Available、Allocation和Need矩阵恢复到请求前的原状态，同时可以模拟阻塞该进程（例如，将其加入等待队列）。
- 如果试探性分配后系统处于安全状态，则程序应修改系统的
1. 基本构造
class Banker {
private:
int num_processes; // 进程数量
int num_resources; // 资源类型数量
std::vector<int> available; // 可用资源向量
std::vector<std::vector<int>> max_demand; // 最大需求矩阵
std::vector<std::vector<int>> allocation; // 已分配矩阵
std::vector<std::vector<int>> need; // 需求矩阵
// waiting_queue 存储 pair: {process_id, request_vector}
std::vector<std::pair<int, std::vector<int>>> waiting_queue;
// 检查向量A的每个元素是否都小于等于向量B对应元素
bool is_less_equal(const std::vector<int>& a, const std::vector<int>& b) const {}
// 向量加法
std::vector<int> add_vectors(const std::vector<int>& a, const std::vector<int>& b) const {}
// 向量减法
std::vector<int> subtract_vectors(const std::vector<int>& a, const std::vector<int>& b) const {}
// 通用的整数输入函数
int get_int_input(const std::string& prompt, int min_val = 0) const {}
// 修正后的向量输入函数：确保每次提示都完整，并在无效输入后清除状态
std::vector<int> get_vector_input(const std::string& prompt, int size) const {}
// 检查并处理等待队列
void check_waiting_queue(){}
void Destroy() {
num_processes = 0;
num_resources = 0;
available.clear();
max_demand.clear();
allocation.clear();
need.clear();
waiting_queue.clear();
}
public:
// 构造函数
Banker() : num_processes(0), num_resources(0) {}
~Banker() { Destroy(); }
// 1. 初始化系统状态
void initialize_system() {}
// 2. 打印当前系统状态 (const 成员函数，不修改对象状态)
void print_current_state() const {}
// 3. 安全性检查算法 (const 成员函数，因为它只读取状态，不修改对象自身)
bool is_safe_state(const std::vector<int>& current_available,
const std::vector<std::vector<int>>& current_allocation,
const std::vector<std::vector<int>>& current_need,
std::vector<int>& safe_sequence) const {
}
// 4. 处理资源请求 (用户接口)
void handle_request() {}
// 5. 模拟进程释放资源 (用户接口)
void handle_release() {}
};2. 私有辅助函数实现
2.1 is_less_equal
bool is_less_equal(const std::vector<int>& a, const std::vector<int>& b) const {
if (a.size() != b.size()) {
std::cerr << "错误：向量大小不匹配！\n";
return false;
}
for (size_t i = 0; i < a.size(); ++i) {
if (a[i] > b[i]) {
return false;
}
}
return true;
}功能： 检查向量 a 的每个元素是否都小于或等于向量 b 的对应元素。在银行家算法中，它被广泛用于资源向量的比较，例如判断 Request <= Need (请求资源是否小于等于进程还需要多少资源) 和 Request <= Available
思路:
- 前提条件检查: 确保两个向量的尺寸相同。如果不同，逐元素比较没有意义，直接报错并返回
false。 - 逐元素比较: 遍历向量的每个位置。
- 短路返回: 一旦发现
a中有任何一个元素大于b中对应元素，立即判断条件不满足，返回false。 - 全部满足: 如果循环完整执行完毕，说明所有元素都满足条件，则返回
true。
C++ 知识点:
const std::vector<int>&: 参数以 常量引用 传递。const保证函数不会修改原始向量，&避免了不必要的向量拷贝，提高了效率。std::cerr: 标准错误输出流，通常用于打印错误信息。与std::cout相比，std::cerr通常是无缓冲的，确保错误信息立即显示。size_t: 无符号整型，常用于表示容器大小或循环计数，由std::vector::size()
2.2 add_vectors
std::vector<int> add_vectors(const std::vector<int>& a, const std::vector<int>& b) const {
if (a.size() != b.size()) {
std::cerr << "错误：向量大小不匹配！\n";
return {};
}
std::vector<int> result(a.size());
for (size_t i = 0; i < a.size(); ++i) {
result[i] = a[i] + b[i];
}
return result;
}功能: 对两个整数向量执行逐元素的加法操作，返回一个新的向量。
思路:
- 尺寸检查: 与
is_less_equal类似，首先检查两个输入向量的尺寸是否匹配。不匹配则报错并返回一个空向量。 - 结果向量初始化: 创建一个与输入向量相同大小的新向量
result，用于存储加法结果。 - 逐元素加法: 遍历向量，将对应位置的元素相加并存入
result。 - 返回结果: 返回包含所有元素和的
result向量。
C++ 知识点:
return {}: C++11 起的初始化列表语法，用于返回一个默认构造的空std::vector<int>。std::vector<int> result(a.size()): 在创建result向量时指定其大小，避免了在循环中使用push_back，当向量大小已知时，这通常更高效。
2.3 subtract_vectors
std::vector<int> subtract_vectors(const std::vector<int>& a, const std::vector<int>& b) const {
if (a.size() != b.size()) {
std::cerr << "错误：向量大小不匹配！\n";
return {};
}
std::vector<int> result(a.size());
for (size_t i = 0; i < a.size(); ++i) {
result[i] = a[i] - b[i];
}
return result;
}功能: 对两个整数向量执行逐元素的减法操作 (a[i] - b[i])，返回一个新的向量。
思路: 逻辑上与 add_vectors 完全一致，只是将加法操作替换为减法
2.4 get_int_input
int get_int_input(const std::string& prompt, int min_val = 0, int max_val = std::numeric_limits<int>::max()) const {
int value;
while (true) {
std::cout << prompt;
std::cin >> value;
if (std::cin.fail() || value < min_val || value > max_val) {
std::cout << "无效输入，请重新输入一个介于 " << min_val << " 和 " << (max_val == std::numeric_limits<int>::max() ? "∞" : std::to_string(max_val)) << " 之间的数字。\n";
std::cin.clear(); // 清除错误标志
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 忽略当前行剩余输入
}
else {
// 成功读取整数后，清空输入缓冲区，以便后续的 getline 不受影响
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
return value;
}
}
}功能：提供一个健壮的通用整数输入函数，包含输入验证。它确保用户输入的是一个有效的整数，并且该整数在指定的最小值和最大值范围内。
思路:
- 循环输入: 使用一个
while(true)循环，直到用户提供有效输入。 - 提示与读取: 打印提示信息，然后尝试从
std::cin读取一个整数。 - 验证:
检查以下三种情况：
std::cin.fail(): 输入流是否处于失败状态（例如，用户输入了非数字字符）。value < min_val: 输入值是否小于允许的最小值。value > max_val: 输入值是否大于允许的最大值。
- 错误处理:
如果输入无效：
- 打印错误消息，指导用户如何正确输入。
std::cin.clear(): 清除std::cin的错误状态标志。如果std::cin处于失败状态，它会拒绝后续的输入操作，所以必须清除。std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');: 忽略输入缓冲区中剩余的字符，直到遇到换行符。这防止了错误的输入（例如 “abc 123”）对后续的std::cin操作产生影响。
- 成功处理:
如果输入有效：
- 再次调用
std::cin.ignore(...)清除输入缓冲区中剩余的换行符。这是为了避免当下一个输入操作使用std::getline时，它会立即读取这个残留的换行符，导致读取到一个空行。 - 返回读取到的有效整数。
- 再次调用
C++ 知识点:
- 默认参数:
min_val = 0,max_val = std::numeric_limits<int>::max()允许调用者省略这些参数，使用预设的默认值（非负数，不限制上限）。 std::numeric_limits<int>::max():limits头文件中定义的模板类，用于获取特定数据类型（如int）的各种属性，这里是获取int的最大值。std::streamsize::max():iosfwd或iostream头文件中定义的类型，表示流可以读取或写入的最大字符数。与ignore配合使用时，通常用于“忽略直到行尾”的效果。std::to_string(): 将数字类型转换为std::string类型，方便在输出提示中拼接字符串。- 流错误状态管理:
std::cin.fail(),std::cin.clear(),std::cin.ignore()是进行健壮 C++ 控制台输入验证的经典三件套。
2.5 get_vector_input
std::vector<int> get_vector_input(const std::string& prompt, int size) const {
std::vector<int> vec(size);
std::string line;
while (true) {
std::cout << prompt; // 每次循环都打印完整的提示
std::getline(std::cin, line); // 读取整行输入
std::istringstream iss(line); // 创建字符串流来解析行
bool valid_input = true;
for (int i = 0; i < size; ++i) {
int value;
if (!(iss >> value) || value < 0) { // 尝试从流中读取数字，并检查是否为负
valid_input = false;
break;
}
vec[i] = value;
}
// 检查是否读取了所有预期数量的数字，并且行末没有额外非数字字符
if (valid_input && iss.eof()) {
return vec;
}
else {
std::cout << "输入格式错误或数量不匹配。请在一行内输入 " << size << " 个非负数字，并用空格分隔。\n";
// 无需在这里清除 cin 错误，因为我们使用的是 getline 和 istringstream
// istringstream 内部的错误状态不会影响 std::cin
}
}
}功能: 这是一个改进后的向量输入函数，它能确保每次都打印完整的提示信息，并且能从用户输入的一行中读取多个以空格分隔的整数，同时进行基本的格式和数量验证。
思路:
- 循环获取输入: 使用
while(true)循环直到获得有效输入。 - 读取整行: 使用
std::getline(std::cin, line);读取用户输入的整行内容。这允许用户一次性输入多个数字并用空格分隔，而不是每次输入一个数字。 - 字符串流解析: 创建一个
std::istringstream iss(line);。std::istringstream是一个字符串输入流，可以将字符串当作输入流来操作，就像std::cin一样。这使得我们可以方便地从用户输入的字符串中提取数字。 - 逐个提取与验证: 循环 size 次，每次尝试从 iss 中提取一个整数。同时检查：
!(iss >> value): 是否成功提取了整数（防止非数字输入）。value < 0: 提取的数字是否为负。- 如果任何一个检查失败，则
valid_input设为false并跳出内层循环。
- 最终验证: 成功提取所有数字后，检查两个条件：
valid_input是否为true(所有数字都有效且非负)。iss.eof(): 字符串流是否已经到达末尾。这确保用户输入了恰好size个数字，没有多余的字符（例如，输入了 “1 2 3 extra”）。
- 返回或重试: 如果满足所有条件，返回填充好的
vec。否则，打印错误信息，循环继续，重新提示用户输入。
C++ 知识点:
std::getline(std::cin, line): 用于从输入流中读取一整行文本（直到换行符），包括其中的空格。这是处理多值一行输入的关键。std::istringstream: 非常重要的类，位于<sstream>头文件。它允许你将一个std::string当作一个输入流来处理，可以像使用std::cin那样使用operator>>来从字符串中提取数据。iss.eof(): 检查std::istringstream是否已经读取到字符串的末尾。在解析多值输入时，这可以用来确保输入数量正确。- 流分离处理:
get_vector_input使用std::getline读取行，然后用std::istringstream解析行。这种方式的好处是，std::istringstream内部的错误状态不会影响全局的std::cin状态，避免了复杂的std::cin.clear()和std::cin.ignore()操作。
2.6 check_waiting_queue()
void check_waiting_queue()
{
if (waiting_queue.empty()) {
return;
}
std::cout << "\n--- 检查等待队列中的进程 ---\n";
// 使用一个循环来不断尝试，直到没有进程可以被满足或队列为空
bool processed_any_request; // 标志本轮循环中是否有请求被处理
do {
processed_any_request = false;
std::vector<std::pair<int, std::vector<int>>> new_waiting_queue; // 用于存储本轮未被处理的请求
for (const auto& entry : waiting_queue) {
int pid = entry.first;
const std::vector<int>& req = entry.second;
// 重新检查请求是否合法 (特别是Need，它可能因进程自身完成而变化)
if (!is_less_equal(req, need[pid])) {
std::cout << "注意：进程 P" << pid << " 的请求 (" << req[0] << "," << req[1] << "," << req[2] << ") 不再满足其 Need 约束，可能进程已完成部分工作。将其保留在等待队列。\n";
new_waiting_queue.push_back(entry); // 不再合法，放回新队列
continue;
}
if (is_less_equal(req, available)) { // 检查系统是否有足够资源可用
// 试探性分配
std::vector<int> temp_available = available;
std::vector<std::vector<int>> temp_allocation = allocation;
std::vector<std::vector<int>> temp_need = need;
temp_available = subtract_vectors(temp_available, req);
temp_allocation[pid] = add_vectors(temp_allocation[pid], req);
temp_need[pid] = subtract_vectors(temp_need[pid], req);
std::vector<int> safe_seq;
if (is_safe_state(temp_available, temp_allocation, temp_need, safe_seq)) {
std::cout << "进程 P" << pid << " 的请求现在可以被满足，分配成功！\n";
available = temp_available;
allocation = temp_allocation;
need = temp_need;
std::cout << "新的安全序列为: ";
for (size_t j = 0; j < safe_seq.size(); ++j) {
std::cout << "P" << safe_seq[j] << (j == safe_seq.size() - 1 ? "" : " -> ");
}
std::cout << "\n";
processed_any_request = true; // 标记本轮有请求被处理
// **优化点 4: 进程完成任务后自动释放资源（此处也适用）**
// 如果进程现在完成了任务（need变为全0），则自动释放其所有资源
if (std::all_of(need[pid].begin(), need[pid].end(), [](int val) { return val == 0; })) {
std::cout << "进程 P" << pid << " 已完成任务，自动释放其所有资源。\n";
available = add_vectors(available, allocation[pid]);
std::fill(allocation[pid].begin(), allocation[pid].end(), 0); // 清空allocation
// need[pid] 已经是全0，无需修改
}
}
else {
// 试探性分配后不安全，放回新队列
std::cout << "进程 P" << pid << " 的请求暂时仍无法满足（不安全状态）。\n";
new_waiting_queue.push_back(entry);
}
}
else {
// 资源不足，放回新队列
std::cout << "进程 P" << pid << " 的请求暂时仍无法满足（资源不足）。\n";
new_waiting_queue.push_back(entry);
}
}
waiting_queue = new_waiting_queue; // 更新等待队列为未能满足的请求
} while (processed_any_request && !waiting_queue.empty()); // 只要本轮有处理且队列非空，就继续尝试
std::cout << "等待队列检查完毕，没有更多可满足的请求。\n";
}功能: 检查并尝试满足 等待队列 中的进程资源请求。这是一个核心函数，尤其在资源释放后被调用，目的是唤醒之前因资源不足或安全性问题而被阻塞的进程。它会持续循环检查，直到没有更多请求可以被满足。
思路:
- 空队列检查: 如果等待队列为空，直接返回。
- 外层循环 (
do-while):- 引入
processed_any_request标志，记录本轮遍历中是否有任何请求被成功处理。 - 每次
do-while循环开始时，创建一个新的临时等待队列new_waiting_queue。 - 循环体结束时，用
new_waiting_queue替换掉原waiting_queue。 do-while循环条件：只要本轮有请求被处理 (processed_any_request为true) 并且 等待队列仍不为空，就继续下一轮尝试。这很重要，因为它处理了 连锁反应：一个进程释放资源可能使得另一个甚至多个被阻塞的进程现在可以被满足。
- 引入
- 内层循环 (遍历
waiting_queue):- 对于队列中的每个请求 (
pid,req)： - 合法性重新检查: 首次检查
req是否仍然小于等于need[pid]。这是因为进程可能在等待期间通过其他方式（例如，自身内部的资源释放）改变了其Need状态。如果不满足，则将其放回new_waiting_queue。 - 资源可用性检查: 检查
req是否小于等于available。如果资源不足，将其放回new_waiting_queue。 - 试探性分配与安全性检查: 如果资源充足，进行 试探性分配：
- 创建当前系统状态（
available,allocation,need）的副本 (temp_available,temp_allocation,temp_need)。 - 根据请求，更新这些临时副本：
temp_available减少，temp_allocation[pid]增加，temp_need[pid]减少。 - 调用
is_safe_state函数，传入这些临时状态的副本，检查系统是否仍处于安全状态。
- 创建当前系统状态（
- 处理结果:
- 安全:如果系统仍安全，则 实际执行分配（将临时状态的值赋给全局的 available, allocation, need）。设置processed_any_request = true。
- 进程完成自动释放: 额外检查
need[pid]是否变为全零（即进程已完成任务）。如果是，自动释放该进程的所有已分配资源，更新available和allocation。
- 进程完成自动释放: 额外检查
- 不安全: 如果系统将进入不安全状态，则不进行实际分配，并将该请求放回
new_waiting_queue。 - 不满足条件: 如果请求不合法或资源不足，直接放回
new_waiting_queue。
- 安全:如果系统仍安全，则 实际执行分配（将临时状态的值赋给全局的 available, allocation, need）。设置processed_any_request = true。
- 对于队列中的每个请求 (
C++ 知识点:
std::pair<int, std::vector<int>>:waiting_queue存储的是pair，其中first是进程 ID (int)，second是请求向量 (std::vector<int>)。- 迭代器与
const auto&: 使用范围for循环 (for (const auto& entry : waiting_queue)) 遍历waiting_queue，const auto&保证高效且不修改元素。 - 临时变量副本: 在进行试探性分配时，创建
temp_available、temp_allocation、temp_need是关键。这使得is_safe_state函数可以基于假设的未来状态进行检查，而不会影响到当前系统的真实状态。如果检查失败，可以直接丢弃这些临时变量，实现“回滚”效果。 std::all_of: 算法库 (<algorithm>) 中的一个非常方便的函数。它用于检查一个范围内的 所有 元素是否都满足某个条件。在这里，std::all_of(need[pid].begin(), need[pid].end(), [](int val) { return val == 0; })检查进程pid的need向量中是否所有元素都为 0，从而判断进程是否完成。- Lambda 表达式
[](int val) { return val == 0; }:std::all_of的第三个参数是一个谓词（predicate），这里使用了一个匿名函数（lambda 表达式）来定义检查条件：判断val是否为0。 std::fill: 算法库 (<algorithm>) 中的另一个有用函数，用于将一个范围内（从begin()到end()）的所有元素填充为指定的值。这里用于将allocation[pid]清零。
3. 共有辅助函数实现
Banker() (构造函数)
- 功能:
Banker类的构造函数，用于初始化类的成员变量。 - 思路: 简单地将
num_processes和num_resources初始化为 0，表示系统在创建Banker对象时尚未初始化。 - C++ 知识点:
- 构造函数: 类的特殊成员函数，在创建对象时自动调用，用于初始化对象的状态。
3.1 initialize_system()
void initialize_system() {
// 重置所有状态，以便重新初始化
Destroy();
num_processes = get_int_input("请输入进程数量: ", 1); // 至少1个进程
num_resources = get_int_input("请输入资源类型数量: ", 1); // 至少1种资源
available.resize(num_resources);
max_demand.resize(num_processes, std::vector<int>(num_resources));
allocation.resize(num_processes, std::vector<int>(num_resources));
need.resize(num_processes, std::vector<int>(num_resources));
// 调整对 get_vector_input 的调用，确保完整提示
available = get_vector_input("请输入 Available 资源数量 (R0 R1 ... R" + std::to_string(num_resources - 1) + "): ", num_resources);
std::cout << "\n请输入 Max 矩阵 (每个进程的最大需求，例如 P0: R0 R1 ...):\n";
for (int i = 0; i < num_processes; ++i) {
max_demand[i] = get_vector_input("进程 P" + std::to_string(i) + " 的 Max: ", num_resources);
}
std::cout << "\n请输入 Allocation 矩阵 (每个进程已分配的资源，例如 P0: R0 R1 ...):\n";
for (int i = 0; i < num_processes; ++i) {
while (true) { // 循环检查直到输入合法的 Allocation
allocation[i] = get_vector_input("进程 P" + std::to_string(i) + " 的 Allocation: ", num_resources);
// 检查 Allocation 是否超过 Max
if (!is_less_equal(allocation[i], max_demand[i])) {
std::cerr << "错误：进程 P" << i << " 的初始 Allocation 超过了其 Max 需求！请重新初始化。\n";
}
else {
break; // 输入合法, 跳出循环
}
}
}
// 计算 Need 矩阵
for (int i = 0; i < num_processes; ++i) {
for (int j = 0; j < num_resources; ++j) {
need[i][j] = max_demand[i][j] - allocation[i][j];
}
}
std::cout << "系统初始化完成！\n";
}功能: 引导用户输入银行家算法所需的所有初始系统参数，包括进程数量、资源类型数量、初始可用资源向量 (Available)、进程最大需求矩阵 (Max) 和进程已分配资源矩阵 (Allocation)。它还会根据这些输入自动计算 Need 矩阵。此外，它包含对初始 Allocation 是否超过 Max 的检查。
思路:
- 重置状态 (假设
Destroy()存在): 调用Destroy()（如果存在）来清空之前可能存在的任何系统状态，确保完全重新初始化。 - 获取基本数量: 使用
get_int_input获取进程和资源的数量，并强制它们至少为 1。 - 调整向量/矩阵大小: 根据输入的数量，使用
resize()方法为available向量和max_demand,allocation,need矩阵（std::vector<std::vector<int>>）预分配内存。 - 获取 Available 向量: 使用
get_vector_input获取初始Available资源。 - 获取 Max 矩阵: 循环遍历每个进程，使用
get_vector_input获取每个进程的Max需求向量。 - 获取 Allocation 矩阵并验证: 循环遍历每个进程，使用
get_vector_input获取每个进程的Allocation向量。使用一个while(true)循环来包裹get_vector_input和随后的验证。如果allocation[i]超过了max_demand[i]（通过is_less_equal检查），则打印错误信息并让用户重新输入该进程的Allocation，而不是直接退出函数。这大大提升了用户体验。 - 计算 Need 矩阵: 根据公式
Need[i][j] = Max[i][j] - Allocation[i][j]，计算并填充Need矩阵。
C++ 知识点:
std::vector::resize(): 用于改变std::vector的大小。如果新大小大于当前大小，会添加默认初始化的元素；如果小于，则会移除多余元素。- 输入验证与循环重试: 在
Allocation输入环节采用while(true)循环和条件判断结合的方式，是实现用户友好型输入的常见模式。
3.2 print_current_state() const
void print_current_state() const {
if (!is_initialized()) {
std::cout << "系统尚未初始化，请先初始化系统。\n";
return;
}
std::cout << "\n--- 当前系统状态 ---\n";
// 打印资源类型标题
std::cout << std::setw(10) << "资源类型:";
for (int j = 0; j < num_resources; ++j) {
std::cout << " R" << j << " ";
}
std::cout << "\n";
// 打印 Available 向量
std::cout << std::setw(10) << "Available:";
for (int j = 0; j < num_resources; ++j) {
std::cout << std::setw(3) << available[j];
}
std::cout << "\n\n";
// 打印 Max 矩阵
std::cout << std::setw(10) << "进程" << std::setw(10) << "Max";
for (int j = 0; j < num_resources; ++j) {
std::cout << " R" << j << " ";
}
std::cout << "\n";
for (int i = 0; i < num_processes; ++i) {
std::cout << std::setw(10) << "P" << i << std::setw(10) << "";
for (int j = 0; j < num_resources; ++j) {
std::cout << std::setw(3) << max_demand[i][j];
}
std::cout << "\n";
}
std::cout << "\n";
// 打印 Allocation 矩阵
std::cout << std::setw(10) << "进程" << std::setw(10) << "Allocation";
for (int j = 0; j < num_resources; ++j) {
std::cout << " R" << j << " ";
}
std::cout << "\n";
for (int i = 0; i < num_processes; ++i) {
std::cout << std::setw(10) << "P" << i << std::setw(10) << "";
for (int j = 0; j < num_resources; ++j) {
std::cout << std::setw(3) << allocation[i][j];
}
std::cout << "\n";
}
std::cout << "\n";
// 打印 Need 矩阵
std::cout << std::setw(10) << "进程" << std::setw(10) << "Need";
for (int j = 0; j < num_resources; ++j) {
std::cout << " R" << j << " ";
}
std::cout << "\n";
for (int i = 0; i < num_processes; ++i) {
std::cout << std::setw(10) << "P" << i << std::setw(10) << "";
for (int j = 0; j < num_resources; ++j) {
std::cout << std::setw(3) << need[i][j];
}
std::cout << "\n";
}
std::cout << "\n";
// 打印等待队列
if (!waiting_queue.empty()) {
std::cout << "--- 等待队列 ---\n";
for (const auto& entry : waiting_queue) {
std::cout << "进程 P" << entry.first << " 请求: (";
for (size_t j = 0; j < entry.second.size(); ++j) {
std::cout << entry.second[j] << (j == entry.second.size() - 1 ? "" : ",");
}
std::cout << ")\n";
}
}
else {
std::cout << "等待队列为空。\n";
}
std::cout << "\n";
}功能: 清晰地打印出当前银行家算法系统的所有关键状态信息，包括 Available 向量、Max 矩阵、Allocation 矩阵、Need 矩阵以及当前等待队列中的进程请求。
思路:
- 初始化检查: 首先调用
is_initialized()确认系统是否已初始化。如果未初始化，打印提示并返回。 - 结构化输出: 使用
std::cout打印各种矩阵和向量的标题以及内容。 - 格式化输出: 使用
std::setw()(来自<iomanip>头文件) 来设置输出宽度，确保各列对齐，使表格更易读。 - 遍历与打印: 针对每个矩阵和向量，使用嵌套循环遍历其元素并打印。
- 等待队列打印: 特别处理等待队列，如果队列不为空，则遍历并打印每个阻塞进程的 ID 及其请求的资源向量。
C++ 知识点:
std::setw(int n): 操纵符 (manipulator)，用于设置下一个输出字段的宽度为n。需要<iomanip>头文件。它只对紧随其后的一个输出项有效，所以每次打印元素前都需要重新设置。const方法: 函数声明后的const关键字表示这是一个常量成员函数，它保证不会修改类的任何成员变量（除了mutable成员）。这对于只读取数据并打印的函数是最佳实践。
3.3 is_safe_state(…) const
bool is_safe_state(const std::vector<int>& current_available,
const std::vector<std::vector<int>>& current_allocation,
const std::vector<std::vector<int>>& current_need,
std::vector<int>& safe_sequence) const { // 注意这里是const
safe_sequence.clear(); // 清空之前的安全序列
std::vector<int> work = current_available;
std::vector<bool> finish(num_processes, false);
int count = 0; // 用于统计已完成的进程数量
while (count < num_processes) {
bool found_process_in_this_pass = false; // 标记本轮是否找到进程
for (int i = 0; i < num_processes; ++i) {
if (!finish[i] && is_less_equal(current_need[i], work)) {
// 找到一个可以执行的进程
work = add_vectors(work, current_allocation[i]); // work = work + allocation[i]
finish[i] = true;
safe_sequence.push_back(i); // 将进程ID加入安全序列
count++;
found_process_in_this_pass = true;
// 找到一个后，重新从头遍历进程，以确保任何新能满足的进程都被发现
break; // 跳出内层 for 循环，外层 while 循环会再次检查
}
}
if (!found_process_in_this_pass) {
// 本轮没有找到任何可以满足的进程，系统处于不安全状态
return false;
}
}
// 所有进程都能完成，系统处于安全状态
return true;
}功能: 实现银行家算法的核心 安全性检查 部分。它模拟资源分配和回收过程，通过迭代查找可执行进程，模拟资源释放，直到所有进程完成或无法找到下一个可执行进程。判断系统是否能找到一个执行序列，使得所有进程都能顺利完成并释放其资源。如果找到安全序列，返回 true 并填充 safe_sequence 向量；否则返回 false。
思路:
- 初始化:
safe_sequence.clear(): 清空传入的安全序列向量，确保每次调用都是干净的。work = current_available: 初始化Work向量，它代表当前可用的资源，最初等于系统的Available资源。finish向量: 一个布尔向量，大小与进程数相同，初始化为false，表示所有进程尚未完成。count: 记录已完成进程的数量，初始为 0。
- 外层循环 (
while (count < num_processes)): 持续循环，直到所有进程都已完成（count达到num_processes）。 - 内层循环 (查找可执行进程):
- 设置
found_process_in_this_pass = false。 - 遍历所有进程 (从 i = 0到 num_processes - 1)：
- 条件判断: 如果进程
i尚未完成 (!finish[i]) 并且 其Need资源小于等于当前的Work资源 (is_less_equal(current_need[i], work))，则表示该进程可以执行。 - 模拟执行:
work = add_vectors(work, current_allocation[i]): 模拟进程i执行完毕并释放其已分配资源，将这些资源加回Work。finish[i] = true: 标记进程i为已完成。safe_sequence.push_back(i): 将进程i的 ID 添加到安全序列中。count++: 已完成进程数量加一。found_process_in_this_pass = true: 标记本轮找到了可执行进程。break;: 关键步骤。一旦找到一个可执行进程，就跳出内层for循环。这样做的原因是，一个进程的完成会释放资源，可能会使之前不可满足的进程现在变得可满足。因此，需要重新从头开始遍历所有进程，以确保能够发现这些新可满足的进程。
- 条件判断: 如果进程
- 设置
- 不安全状态判断: 如果内层
for循环完整执行完毕，但found_process_in_this_pass仍为false（即本轮没有找到任何可以执行的进程），说明系统无法找到下一个可执行进程来推进状态，因此系统处于不安全状态，返回false。 - 安全状态返回: 如果外层
while循环正常结束 (count == num_processes)，表示所有进程都找到了一个执行路径，系统处于安全状态，返回true。
C++ 知识点:
- 参数传递副本:
current_available,current_allocation,current_need以const&传入，但在函数内部通过赋值创建了它们的副本 (work,temp_allocation,temp_need在check_waiting_queue和handle_request中)，这样is_safe_state在模拟分配时不会修改到主程序的实际状态。
3.4 handle_request()
void handle_request() {
if (!is_initialized()) {
std::cout << "系统尚未初始化，请先初始化系统。\n";
return;
}
int process_id = get_int_input("请输入请求资源的进程ID (P0-" + std::to_string(num_processes - 1) + "): ", 0, num_processes - 1);
if (process_id < 0 || process_id >= num_processes) { // 额外的边界检查
std::cout << "无效的进程ID。\n";
return;
}
std::vector<int> request = get_vector_input("请输入进程 P" + std::to_string(process_id) + " 请求的资源数量 (R0 R1 ... R" + std::to_string(num_resources - 1) + "): ", num_resources);
// 检查请求是否超过Need
if (!is_less_equal(request, need[process_id])) {
std::cout << "错误：请求的资源超过了进程 P" << process_id << " 的最大需求 (Need)！请求被拒绝。\n";
return;
}
// 检查系统是否有足够资源可用
if (!is_less_equal(request, available)) {
std::cout << "系统资源不足，进程 P" << process_id << " 的请求暂时无法满足。请求被拒绝，进程将被阻塞。\n";
waiting_queue.push_back({ process_id, request }); // 将请求加入等待队列
return;
}
// --- 试探性分配 ---
std::vector<int> temp_available = available;
std::vector<std::vector<int>> temp_allocation = allocation;
std::vector<std::vector<int>> temp_need = need;
// 更新临时状态
temp_available = subtract_vectors(temp_available, request);
temp_allocation[process_id] = add_vectors(temp_allocation[process_id], request);
temp_need[process_id] = subtract_vectors(temp_need[process_id], request);
std::vector<int> current_safe_sequence;
if (is_safe_state(temp_available, temp_allocation, temp_need, current_safe_sequence)) {
std::cout << "系统处于安全状态。资源分配成功！\n";
available = temp_available;
allocation = temp_allocation;
need = temp_need;
std::cout << "安全序列为: ";
for (size_t i = 0; i < current_safe_sequence.size(); ++i) {
std::cout << "P" << current_safe_sequence[i] << (i == current_safe_sequence.size() - 1 ? "" : " -> ");
}
std::cout << "\n";
}
else {
std::cout << "试探性分配后系统将进入不安全状态。资源分配被拒绝，进程 P" << process_id << " 被阻塞并加入等待队列。\n";
waiting_queue.push_back({ process_id, request }); // 将请求加入等待队列
// 回滚操作不需要显式写，因为我们操作的是临时变量，全局变量未被修改
}
}功能: 处理进程的资源请求。它是银行家算法中处理资源请求的核心逻辑。它会经过一系列检查，判断请求是否合法、资源是否充足，并最终进行安全性检查来决定是否实际分配资源。
思路:
- 初始化检查: 确认系统已初始化。
- 获取请求信息: 使用
get_int_input获取请求资源的进程 ID，并使用get_vector_input获取该进程请求的资源数量。 - 第一层检查 (Request <= Need): 使用
is_less_equal检查进程请求的资源量是否超过了其声明的Need（最大需求减去已分配）。如果超过，说明请求不合法，直接拒绝。 - 第二层检查 (Request <= Available): 使用
is_less_equal检查系统当前是否有足够的Available资源来满足该请求。如果资源不足，请求不能立即满足，进程被阻塞，并将其请求添加到waiting_queue。 - 试探性分配: 如果通过了前两层检查，系统并不立即分配资源，而是进行 试探性分配：
- 创建当前
available,allocation,need状态的 临时副本。 - 在这些临时副本上，模拟执行资源分配操作：
temp_available减少request，temp_allocation[pid]增加request，temp_need[pid]减少request。
- 创建当前
- 安全性检查: 调用
is_safe_state函数，传入这些 临时状态的副本，判断模拟分配后系统是否仍然处于安全状态。 - 实际分配或阻塞:
- 安全: 如果
is_safe_state返回true，说明系统在分配后仍能保持安全。此时，将临时状态的值 实际更新 到全局的available,allocation,need变量中，表示资源分配成功。并打印出新的安全序列。 - 不安全: 如果
is_safe_state返回false，说明模拟分配会导致系统进入不安全状态。此时，不执行实际分配（因为操作的是临时副本，主变量未被修改），拒绝请求，并将该进程的请求加入waiting_queue。
- 安全: 如果
C++ 知识点:
- 防御性编程: 在函数开始处进行
is_initialized()检查，避免在未初始化状态下执行操作。 - 临时变量的利用: 通过创建
available,allocation,need的副本 (temp_...)，可以在不修改全局状态的情况下进行“假设”操作，并在确定安全后再提交更改。这是银行家算法实现的关键。
3.5 handle_release()
void handle_release() {
if (!is_initialized()) {
std::cout << "系统尚未初始化，请先初始化系统。\n";
return;
}
int process_id = get_int_input("请输入释放资源的进程ID (P0-" + std::to_string(num_processes - 1) + "): ", 0, num_processes - 1);
if (process_id < 0 || process_id >= num_processes) {
std::cout << "无效的进程ID。\n";
return;
}
std::vector<int> release_vector = get_vector_input("请输入进程 P" + std::to_string(process_id) + " 释放的资源数量 (R0 R1 ... R" + std::to_string(num_resources - 1) + "): ", num_resources);
// 检查释放量是否超过已分配量
if (!is_less_equal(release_vector, allocation[process_id])) {
std::cout << "错误：进程 P" << process_id << " 试图释放超出其当前拥有量的资源！\n";
return;
}
// 执行资源释放
available = add_vectors(available, release_vector);
allocation[process_id] = subtract_vectors(allocation[process_id], release_vector);
need[process_id] = add_vectors(need[process_id], release_vector); // 释放资源后，Need会增加 (因为Max不变，Allocation减少)
std::cout << "进程 P" << process_id << " 成功释放资源。\n";
// 尝试满足等待队列中的进程
check_waiting_queue();
}功能: 模拟进程释放资源的操作。它更新系统的 Available、Allocation 和 Need 矩阵以反映资源的变化，然后调用 check_waiting_queue 来尝试唤醒之前被阻塞的进程。
思路:
- 初始化检查: 确认系统已初始化。
- 获取释放信息: 获取要释放资源的进程 ID 及其释放的资源数量。
- 合法性检查: 使用
is_less_equal检查进程试图释放的资源量是否超过了它当前实际拥有的已分配资源 (release_vector <= allocation[process_id])。如果超过，则拒绝释放。 - 执行资源释放:
available = add_vectors(available, release_vector);: 将释放的资源加回系统的Available资源。allocation[process_id] = subtract_vectors(allocation[process_id], release_vector);: 从进程pid的Allocation中减去释放的资源。need[process_id] = add_vectors(need[pid], release_vector);: 重要且容易被忽视的细节。当一个进程释放资源时，它的Allocation减少，而Max保持不变，因此它对资源的Need应该相应地 增加 (Need = Max - New_Allocation)。
- 检查等待队列: 资源释放后，系统中的
Available资源增多，这可能使得等待队列中一些原先无法满足的请求现在可以被满足。因此，立即调用check_waiting_queue()来尝试处理这些阻塞的请求。
C++ 知识点:
- 资源释放对 Need 的影响: 理解
Need矩阵的更新逻辑 (Need = Max - Allocation) 在资源释放时的反向变化是关键。 - 联动效应: 资源释放后立即检查等待队列，体现了操作系统中资源管理对进程调度可能产生的联动效应。
3.6 is_initialized() const
bool is_initialized() const {
return num_processes > 0 && num_resources > 0;
}功能: 简单地检查系统是否已经通过 initialize_system 函数进行了初始化。
思路: 判断表示进程数量和资源数量的成员变量 num_processes 和 num_resources 是否都大于 0。如果它们都被正确地设置为正值，则认为系统已初始化。
4. 设计思路
（1）数据结构
num_processes(int): 系统中的进程数量。num_resources(int): 系统中资源的类型数量。available(std::vector): 一个一维向量，长度为num_resources。它表示当前系统中每种类型可用的资源数量。- 例如，
available[j]表示资源类型j当前可用的实例数量。
- 例如，
max_demand(std::vector<std::vector>): 一个二维矩阵，大小为num_processesxnum_resources。它定义了每个进程对每种资源类型可能需要的最大实例数量。- 例如，
max_demand[i][j]表示进程i对资源类型j的最大需求量。
- 例如，
allocation(std::vector<std::vector>): 一个二维矩阵，大小为num_processesxnum_resources。它表示当前已分配给每个进程的每种资源类型的实例数量。- 例如，
allocation[i][j]表示进程i当前已分配到的资源类型j的实例数量。
- 例如，
need(std::vector<std::vector>): 一个二维矩阵，大小为num_processesxnum_resources。它表示每个进程还需要每种资源类型的实例数量才能完成其执行。- 计算方式：
Need[i][j] = Max_demand[i][j] - Allocation[i][j]。
- 计算方式：
waiting_queue(std::vector<std::pair<int, std::vector>>): 一个用于存储被阻塞进程请求的队列。每个元素是一个std::pair，其中first是被阻塞进程的 ID，second是该进程请求的资源向量
（2）算法流程
① 初始化：系统在开始运行前需要进行初始化，设置资源的初始状态和进程的最大需求。
- 获取用户输入: 引导用户输入系统中的进程数量和资源类型数量。
- 动态调整数据结构: 根据输入的数量，动态调整
available向量和max_demand、allocation、need矩阵的大小。 - 输入初始资源和需求: 接收用户输入的初始 Available 资源 向量，以及每个进程的 Max 矩阵 和 Allocation 矩阵。
- 验证初始分配: 检查每个进程的初始 Allocation 是否超过了其对应的 Max 需求。如果超过，会提示用户重新输入，直到合法为止。
- 计算 Need 矩阵: 根据
Need = Max - Allocation的公式，自动计算并填充Need矩阵
② 安全性检查：安全性检查是银行家算法的核心，用于判断当前系统状态是否安全（即是否存在一个序列，使得所有进程都能完成执行）。
- 状态参数: 接收当前系统的
Available、Allocation和Need状态的副本作为输入，并准备一个空的safe_sequence向量来存储安全序列。 - 初始化工作: 创建一个
Work向量，初始化为当前Available资源；创建一个Finish向量（布尔类型），所有进程初始化为未完成 (false)。 - 迭代查找可执行进程:
- 在一个循环中，尝试查找一个尚未完成 (
Finish[i]为false) 且其所需资源 (Need[i]) 小于等于当前可用资源 (Work) 的进程i。 - 如果找到这样的进程，模拟该进程执行完成并释放其所有已分配资源：将
Allocation[i]加到Work中，并将Finish[i]设置为true。同时，将进程i的 ID 加入safe_sequence。 - 关键点: 找到一个可执行进程后，会重新从头开始遍历所有进程，因为新释放的资源可能使得之前无法满足的进程现在变得可满足。
- 在一个循环中，尝试查找一个尚未完成 (
- 不安全状态判断: 如果在一轮遍历中没有找到任何可以执行的进程，而仍有进程未完成，则表明系统处于不安全状态，返回
false。 - 安全状态确认: 如果所有进程都找到了一个执行路径并被标记为完成，则系统处于安全状态，返回
true并输出safe_sequence。
③ 请求资源：当一个进程请求资源时，系统会执行以下步骤来判断是否可以分配：
- 获取请求: 获取请求资源的进程 ID 和其请求的资源数量。
- 检查请求合法性:
- Request <= Need: 检查进程请求的资源量是否超过了其声明的
Need。如果超过，请求被拒绝。 - Request <= Available: 检查系统当前是否有足够的
Available资源来满足该请求。如果资源不足，请求被拒绝，并将进程阻塞并加入等待队列。
- Request <= Need: 检查进程请求的资源量是否超过了其声明的
- 试探性分配:
如果上述检查都通过，系统不会立即分配资源，而是进行一次 “假想”分配：
- 创建当前系统状态 (
Available,Allocation,Need) 的临时副本。 - 在这些临时副本上，模拟执行资源分配，更新
temp_Available(减少),temp_Allocation(增加),temp_Need(减少)。
- 创建当前系统状态 (
- 执行安全性检查: 调用安全性检查算法 (
is_safe_state)，传入这些临时状态的副本。 - 实际分配或阻塞:
- 安全: 如果安全性检查表明分配后系统仍处于安全状态，则将临时状态的更新 实际应用 到全局的
Available,Allocation,Need变量中，表示资源分配成功。 - 不安全: 如果安全性检查表明分配后系统将进入不安全状态，则拒绝此次分配。由于是操作临时副本，全局变量未被修改，实现“回滚”效果。该进程的请求会被加入等待队列。
- 安全: 如果安全性检查表明分配后系统仍处于安全状态，则将临时状态的更新 实际应用 到全局的
④ 释放资源：当一个进程完成对某些资源的使用后，它会释放这些资源。
- 获取释放信息: 获取释放资源的进程 ID 和其释放的资源数量。
- 检查释放合法性: 检查进程试图释放的资源量是否超过了它当前实际拥有的已分配资源 (
Release <= Allocation)。如果超过，则拒绝释放。 - 更新系统状态:
Available向量增加释放的资源。Allocation矩阵中该进程的已分配资源减少。Need矩阵中该进程的所需资源 增加 (因为Need = Max - Allocation，Allocation减少导致Need增加)。
- 检查等待队列: 资源释放后，系统中可用资源可能增加，这可能使得等待队列中原先被阻塞的请求现在可以被满足。因此，立即调用
check_waiting_queue()函数，遍历等待队列，尝试满足其中的请求。如果一个请求被满足，它将从等待队列中移除；如果一个进程在等待队列中，其Need发生变化，它可能仍然被保留在队列中。
（3）关键代码
以下是实现上述算法流程中的一些关键函数及其作用：
is_less_equal(const std::vector<int>& a, const std::vector<int>& b):- 功能: 检查向量
a的每个元素是否都小于或等于向量b的对应元素。 - 作用: 在判断
Request <= Need、Request <= Available和Release <= Allocation等条件时广泛使用。
- 功能: 检查向量
add_vectors(const std::vector<int>& a, const std::vector<int>& b):- 功能: 执行两个向量的逐元素加法。
- 作用: 更新
Available资源（当进程释放资源时）和Allocation矩阵（当进程获得资源时）。
subtract_vectors(const std::vector<int>& a, const std::vector<int>& b):- 功能: 执行两个向量的逐元素减法。
- 作用: 更新
Available资源（当进程请求资源并被分配时）和Need/Allocation矩阵。
get_int_input(const std::string& prompt, int min_val, int max_val):- 功能: 通用的整数输入函数，包含输入验证和范围限制。
- 作用: 用于获取进程数量、资源数量和进程 ID 等单个整数输入。
get_vector_input(const std::string& prompt, int size):- 功能: 健壮的向量输入函数，能够读取一行中的多个整数，并进行格式和数量验证。
- 作用: 用于获取
Available、Max、Allocation和Request/Release向量。
is_safe_state(const std::vector<int>& current_available, const std::vector<std::vector<int>>& current_allocation, const std::vector<std::vector<int>>& current_need, std::vector<int>& safe_sequence):- 功能: 银行家算法的安全性检查核心。判断给定系统状态是否安全，并返回安全序列。
- 作用: 在处理资源请求时进行预判，确保分配不会导致系统进入不安全状态；也在资源释放后用于检查是否有阻塞进程可以被唤醒。
check_waiting_queue():- 功能: 检查并尝试满足等待队列中的进程请求。
- 作用: 在资源释放后或任何可能改变系统可用资源状态的操作后调用，以尝试唤醒之前被阻塞的进程。它会循环处理，直到没有更多请求可以被满足。
initialize_system():- 功能: 引导用户输入并初始化银行家算法所需的所有系统参数。
- 作用: 在程序开始时建立初始的资源和进程状态。
handle_request():- 功能: 处理进程的资源请求。
- 作用: 封装了资源请求的合法性检查、可用性检查、试探性分配和安全性检查逻辑。
handle_release():- 功能: 模拟进程释放资源。
- 作用: 更新系统资源状态，并在资源释放后触发等待队列的检查。
print_current_state():- 功能: 打印当前系统的所有关键状态信息。
- 作用: 帮助用户直观了解系统当前的资源分配情况和进程状态。
（4）算法流程图
5. 结果测试
int main() {
Banker my_banker; // 创建 Banker 类的实例
int choice;
do {
std::cout << "\n--- 银行家算法模拟系统 ---\n";
std::cout << "1. 初始化系统\n";
std::cout << "2. 打印当前状态\n";
std::cout << "3. 进程请求资源\n";
std::cout << "4. 进程释放资源\n";
std::cout << "0. 退出\n";
std::cout << "请选择操作: ";
// 使用更健壮的输入处理
while (!(std::cin >> choice)) {
std::cout << "无效输入，请输入一个数字选项。\n";
std::cin.clear(); // 清除错误标志
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 忽略当前行剩余输入
}
// 对于整数输入后，需要清除缓冲区中的换行符，以便后续的 `getline` 不受影响
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
switch (choice) {
case 1:
my_banker.initialize_system();
break;
case 2:
my_banker.print_current_state();
break;
case 3:
my_banker.handle_request();
break;
case 4:
my_banker.handle_release();
break;
case 0:
std::cout << "退出系统。再见！\n";
break;
default:
std::cout << "无效选择，请重新输入。\n";
break;
}
} while (choice != 0);
return 0;
}结果如下：
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 1
请输入进程数量: 5
请输入资源类型数量: 3
请输入 Available 资源数量 (R0 R1 ... R2): 3 3 2
请输入 Max 矩阵 (每个进程的最大需求，例如 P0: R0 R1 ...):
进程 P0 的 Max: 7 5 3
进程 P1 的 Max: 3 2 2
进程 P2 的 Max: 9 0 2
进程 P3 的 Max: 2 2 2
进程 P4 的 Max: 4 3 3
请输入 Allocation 矩阵 (每个进程已分配的资源，例如 P0: R0 R1 ...):
进程 P0 的 Allocation: 0 1 0
进程 P1 的 Allocation: 2 0 0
进程 P2 的 Allocation: 3 0 2
进程 P3 的 Allocation: 2 1 1
进程 P4 的 Allocation: 0 0 2
系统初始化完成！
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 2
--- 当前系统状态 ---
资源类型: R0 R1 R2
Available: 3 3 2
进程 Max R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
进程Allocation R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
进程 Need R0 R1 R2
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
等待队列为空。
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 3
请输入请求资源的进程ID (P0-4): 1
请输入进程 P1 请求的资源数量 (R0 R1 ... R2): 1 0 2
系统处于安全状态。资源分配成功！
安全序列为: P1 -> P3 -> P0 -> P2 -> P4
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 2
--- 当前系统状态 ---
资源类型: R0 R1 R2
Available: 2 3 0
进程 Max R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
进程Allocation R0 R1 R2
P0 0 1 0
P1 3 0 2
P2 3 0 2
P3 2 1 1
P4 0 0 2
进程 Need R0 R1 R2
P0 7 4 3
P1 0 2 0
P2 6 0 0
P3 0 1 1
P4 4 3 1
等待队列为空。
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 3
请输入请求资源的进程ID (P0-4): 0
请输入进程 P0 请求的资源数量 (R0 R1 ... R2): 2 3 0
试探性分配后系统将进入不安全状态。资源分配被拒绝，进程 P0 被阻塞并加入等待队列。
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 2
--- 当前系统状态 ---
资源类型: R0 R1 R2
Available: 2 3 0
进程 Max R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
进程Allocation R0 R1 R2
P0 0 1 0
P1 3 0 2
P2 3 0 2
P3 2 1 1
P4 0 0 2
进程 Need R0 R1 R2
P0 7 4 3
P1 0 2 0
P2 6 0 0
P3 0 1 1
P4 4 3 1
--- 等待队列 ---
进程 P0 请求: (2,3,0)
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 3
请输入请求资源的进程ID (P0-4): 3
请输入进程 P3 请求的资源数量 (R0 R1 ... R2): 0 1 0
系统处于安全状态。资源分配成功！
安全序列为: P1 -> P3 -> P0 -> P2 -> P4
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 2
--- 当前系统状态 ---
资源类型: R0 R1 R2
Available: 2 2 0
进程 Max R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
进程Allocation R0 R1 R2
P0 0 1 0
P1 3 0 2
P2 3 0 2
P3 2 2 1
P4 0 0 2
进程 Need R0 R1 R2
P0 7 4 3
P1 0 2 0
P2 6 0 0
P3 0 0 1
P4 4 3 1
--- 等待队列 ---
进程 P0 请求: (2,3,0)
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 4
请输入释放资源的进程ID (P0-4): 1
请输入进程 P1 释放的资源数量 (R0 R1 ... R2): 3 0 2
进程 P1 成功释放资源。
--- 检查等待队列中的进程 ---
等待队列检查完毕，没有更多可满足的请求。
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 2
--- 当前系统状态 ---
资源类型: R0 R1 R2
Available: 5 2 2
进程 Max R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
进程Allocation R0 R1 R2
P0 0 1 0
P1 0 0 0
P2 3 0 2
P3 2 2 1
P4 0 0 2
进程 Need R0 R1 R2
P0 7 4 3
P1 3 2 2
P2 6 0 0
P3 0 0 1
P4 4 3 1
--- 等待队列 ---
进程 P0 请求: (2,3,0)
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 3
请输入请求资源的进程ID (P0-4): 4
请输入进程 P4 请求的资源数量 (R0 R1 ... R2): 0 0 0
系统处于安全状态。资源分配成功！
安全序列为: P1 -> P3 -> P0 -> P2 -> P4
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 2
--- 当前系统状态 ---
资源类型: R0 R1 R2
Available: 5 2 2
进程 Max R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
进程Allocation R0 R1 R2
P0 0 1 0
P1 0 0 0
P2 3 0 2
P3 2 2 1
P4 0 0 2
进程 Need R0 R1 R2
P0 7 4 3
P1 3 2 2
P2 6 0 0
P3 0 0 1
P4 4 3 1
--- 等待队列 ---
进程 P0 请求: (2,3,0)
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 4
请输入释放资源的进程ID (P0-4): 3
请输入进程 P3 释放的资源数量 (R0 R1 ... R2): 2 2 1
进程 P3 成功释放资源。
--- 检查等待队列中的进程 ---
进程 P0 的请求现在可以被满足，分配成功！
新的安全序列为: P0 -> P1 -> P2 -> P3 -> P4
等待队列检查完毕，没有更多可满足的请求。
--- 银行家算法模拟系统 ---
1. 初始化系统
2. 打印当前状态
3. 进程请求资源
4. 进程释放资源
0. 退出
请选择操作: 2
--- 当前系统状态 ---
资源类型: R0 R1 R2
Available: 5 1 3
进程 Max R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
进程Allocation R0 R1 R2
P0 2 4 0
P1 0 0 0
P2 3 0 2
P3 0 0 0
P4 0 0 2
进程 Need R0 R1 R2
P0 5 1 3
P1 3 2 2
P2 6 0 0
P3 2 2 2
P4 4 3 1
等待队列为空。分析：
- 进程 P0 最初被阻塞，是因为尽管系统有足够的当前可用资源来满足它的请求，但在试探性分配之后，系统进入了不安全状态——这意味着无法找到一个进程完成的顺序，使得所有进程都能最终完成并释放其资源。
- 直到后来，进程 P3 释放了大量资源 (2, 2, 1)，使得系统总的 Available 资源显著增加到 (7, 4, 3)。有了这些额外的资源，当系统再次检查等待队列时，发现现在不仅可以满足 P0 的请求，而且在为 P0 分配资源后，系统仍然能够找到一个安全序列，从而避免了死锁。这正是银行家算法的核心思想：只有当资源分配能保证系统处于安全状态时，才会进行实际的分配
六、应用场景
尽管银行家算法有其局限性，但在特定场景下它仍然具有重要的应用价值：
- 多任务操作系统中的资源管理： 尤其是在对死锁避免要求极高的系统或子系统中，银行家算法可以作为一种严格的资源分配策略。
- 数据库事务并发控制： 在某些数据库管理系统中，为了保证事务的原子性、一致性、隔离性和持久性（ACID 特性），可以借鉴银行家算法的思想来管理并发事务对共享资源的访问，以避免死锁。例如，在事务预先声明其所需的所有锁时，可以应用类似安全性检查的机制。
- 实时系统中的资源调度： 虽然算法本身效率可能不高，但在一些对确定性要求极高的实时系统中，如果可以预知所有任务的最大资源需求，并且系统设计允许一定的计算开销，银行家算法可以用来保证关键任务的死锁避免。
七、完整代码&小结
#include <iostream>
#include <vector>
#include <numeric>
#include <iomanip>
#include <limits>
#include <string>
#include <sstream>
#include <algorithm>
// Banker 类定义
class Banker {
private:
int num_processes; // 进程数量
int num_resources; // 资源类型数量
std::vector<int> available; // 可用资源向量
std::vector<std::vector<int>> max_demand; // 最大需求矩阵
std::vector<std::vector<int>> allocation; // 已分配矩阵
std::vector<std::vector<int>> need; // 需求矩阵
// waiting_queue 存储 pair: {process_id, request_vector}
std::vector<std::pair<int, std::vector<int>>> waiting_queue;
// --- 辅助函数（私有成员函数） ---
// 检查向量A的每个元素是否都小于等于向量B对应元素
bool is_less_equal(const std::vector<int>& a, const std::vector<int>& b) const {
if (a.size() != b.size()) {
std::cerr << "错误：向量大小不匹配！\n";
return false;
}
for (size_t i = 0; i < a.size(); ++i) {
if (a[i] > b[i]) {
return false;
}
}
return true;
}
// 向量加法
std::vector<int> add_vectors(const std::vector<int>& a, const std::vector<int>& b) const {
if (a.size() != b.size()) {
std::cerr << "错误：向量大小不匹配！\n";
return {};
}
std::vector<int> result(a.size());
for (size_t i = 0; i < a.size(); ++i) {
result[i] = a[i] + b[i];
}
return result;
}
// 向量减法
std::vector<int> subtract_vectors(const std::vector<int>& a, const std::vector<int>& b) const {
if (a.size() != b.size()) {
std::cerr << "错误：向量大小不匹配！\n";
return {};
}
std::vector<int> result(a.size());
for (size_t i = 0; i < a.size(); ++i) {
result[i] = a[i] - b[i];
}
return result;
}
// 通用的整数输入函数
// std::numeric_limits<int>::max() 获取 int 类型所能表示的最大值
int get_int_input(const std::string& prompt, int min_val = 0, int max_val = std::numeric_limits<int>::max()) const {
int value;
while (true) {
std::cout << prompt;
std::cin >> value;
if (std::cin.fail() || value < min_val || value > max_val) {
std::cout << "无效输入，请重新输入一个介于 " << min_val << " 和 " << (max_val == std::numeric_limits<int>::max() ? "∞" : std::to_string(max_val)) << " 之间的数字。\n";
std::cin.clear(); // 清除错误标志
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 忽略当前行剩余输入
}
else {
// 成功读取整数后，清空输入缓冲区，以便后续的 getline 不受影响
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
return value;
}
}
}
// 修正后的向量输入函数：确保每次提示都完整，并在无效输入后清除状态
std::vector<int> get_vector_input(const std::string& prompt, int size) const {
std::vector<int> vec(size);
std::string line;
while (true) {
std::cout << prompt; // 每次循环都打印完整的提示
std::getline(std::cin, line); // 读取整行输入
std::istringstream iss(line); // 创建字符串流来解析行
bool valid_input = true;
for (int i = 0; i < size; ++i) {
int value;
if (!(iss >> value) || value < 0) { // 尝试从流中读取数字，并检查是否为负
valid_input = false;
break;
}
vec[i] = value;
}
// 检查是否读取了所有预期数量的数字，并且行末没有额外非数字字符
if (valid_input && iss.eof()) {
return vec;
}
else {
std::cout << "输入格式错误或数量不匹配。请在一行内输入 " << size << " 个非负数字，并用空格分隔。\n";
// 无需在这里清除 cin 错误，因为我们使用的是 getline 和 istringstream
// istringstream 内部的错误状态不会影响 std::cin
}
}
}
// 检查并处理等待队列
void check_waiting_queue()
{
if (waiting_queue.empty()) {
return;
}
std::cout << "\n--- 检查等待队列中的进程 ---\n";
// 使用一个循环来不断尝试，直到没有进程可以被满足或队列为空
bool processed_any_request; // 标志本轮循环中是否有请求被处理
do {
processed_any_request = false;
std::vector<std::pair<int, std::vector<int>>> new_waiting_queue; // 用于存储本轮未被处理的请求
for (const auto& entry : waiting_queue) {
int pid = entry.first;
const std::vector<int>& req = entry.second;
// 重新检查请求是否合法 (特别是Need，它可能因进程自身完成而变化)
if (!is_less_equal(req, need[pid])) {
std::cout << "注意：进程 P" << pid << " 的请求 (" << req[0] << "," << req[1] << "," << req[2] << ") 不再满足其 Need 约束，可能进程已完成部分工作。将其保留在等待队列。\n";
new_waiting_queue.push_back(entry); // 不再合法，放回新队列
continue;
}
if (is_less_equal(req, available)) { // 检查系统是否有足够资源可用
// 试探性分配
std::vector<int> temp_available = available;
std::vector<std::vector<int>> temp_allocation = allocation;
std::vector<std::vector<int>> temp_need = need;
temp_available = subtract_vectors(temp_available, req);
temp_allocation[pid] = add_vectors(temp_allocation[pid], req);
temp_need[pid] = subtract_vectors(temp_need[pid], req);
std::vector<int> safe_seq;
if (is_safe_state(temp_available, temp_allocation, temp_need, safe_seq)) {
std::cout << "进程 P" << pid << " 的请求现在可以被满足，分配成功！\n";
available = temp_available;
allocation = temp_allocation;
need = temp_need;
std::cout << "新的安全序列为: ";
for (size_t j = 0; j < safe_seq.size(); ++j) {
std::cout << "P" << safe_seq[j] << (j == safe_seq.size() - 1 ? "" : " -> ");
}
std::cout << "\n";
processed_any_request = true; // 标记本轮有请求被处理
// 优化点 4: 进程完成任务后自动释放资源（此处也适用）
// 如果进程现在完成了任务（need变为全0），则自动释放其所有资源
// std::all_of 用于检查 范围 [first, last) 中的所有元素 是否都满足某个条件（由谓词 p 判断）
if (std::all_of(need[pid].begin(), need[pid].end(), [](int val) { return val == 0; })) {
std::cout << "进程 P" << pid << " 已完成任务，自动释放其所有资源。\n";
available = add_vectors(available, allocation[pid]);
std::fill(allocation[pid].begin(), allocation[pid].end(), 0); // 清空allocation
// need[pid] 已经是全0，无需修改
}
}
else {
// 试探性分配后不安全，放回新队列
std::cout << "进程 P" << pid << " 的请求暂时仍无法满足（不安全状态）。\n";
new_waiting_queue.push_back(entry);
}
}
else {
// 资源不足，放回新队列
std::cout << "进程 P" << pid << " 的请求暂时仍无法满足（资源不足）。\n";
new_waiting_queue.push_back(entry);
}
}
waiting_queue = new_waiting_queue; // 更新等待队列为未能满足的请求
} while (processed_any_request && !waiting_queue.empty()); // 只要本轮有处理且队列非空，就继续尝试
std::cout << "等待队列检查完毕，没有更多可满足的请求。\n";
}
void Destroy() {
num_processes = 0;
num_resources = 0;
available.clear();
max_demand.clear();
allocation.clear();
need.clear();
waiting_queue.clear();
}
public:
// 构造函数
Banker() : num_processes(0), num_resources(0) {}
~Banker() { Destroy(); }
// 1. 初始化系统状态
void initialize_system() {
// 重置所有状态，以便重新初始化
Destroy();
num_processes = get_int_input("请输入进程数量: ", 1); // 至少1个进程
num_resources = get_int_input("请输入资源类型数量: ", 1); // 至少1种资源
available.resize(num_resources);
max_demand.resize(num_processes, std::vector<int>(num_resources));
allocation.resize(num_processes, std::vector<int>(num_resources));
need.resize(num_processes, std::vector<int>(num_resources));
// 调整对 get_vector_input 的调用，确保完整提示
available = get_vector_input("请输入 Available 资源数量 (R0 R1 ... R" + std::to_string(num_resources - 1) + "): ", num_resources);
std::cout << "\n请输入 Max 矩阵 (每个进程的最大需求，例如 P0: R0 R1 ...):\n";
for (int i = 0; i < num_processes; ++i) {
max_demand[i] = get_vector_input("进程 P" + std::to_string(i) + " 的 Max: ", num_resources);
}
std::cout << "\n请输入 Allocation 矩阵 (每个进程已分配的资源，例如 P0: R0 R1 ...):\n";
for (int i = 0; i < num_processes; ++i) {
while (true) { // 循环检查直到输入合法的 Allocation
allocation[i] = get_vector_input("进程 P" + std::to_string(i) + " 的 Allocation: ", num_resources);
// 检查 Allocation 是否超过 Max
if (!is_less_equal(allocation[i], max_demand[i])) {
std::cerr << "错误：进程 P" << i << " 的初始 Allocation 超过了其 Max 需求！请重新初始化。\n";
}
else {
break; // 输入合法, 跳出循环
}
}
}
// 计算 Need 矩阵
for (int i = 0; i < num_processes; ++i) {
for (int j = 0; j < num_resources; ++j) {
need[i][j] = max_demand[i][j] - allocation[i][j];
}
}
std::cout << "系统初始化完成！\n";
}
// 2. 打印当前系统状态 (const 成员函数，不修改对象状态)
void print_current_state() const {
if (!is_initialized()) {
std::cout << "系统尚未初始化，请先初始化系统。\n";
return;
}
std::cout << "\n--- 当前系统状态 ---\n";
// 打印资源类型标题
std::cout << std::setw(10) << "资源类型:";
for (int j = 0; j < num_resources; ++j) {
std::cout << " R" << j << " ";
}
std::cout << "\n";
// 打印 Available 向量
std::cout << std::setw(10) << "Available:";
for (int j = 0; j < num_resources; ++j) {
std::cout << std::setw(3) << available[j];
}
std::cout << "\n\n";
// 打印 Max 矩阵
std::cout << std::setw(10) << "进程" << std::setw(10) << "Max";
for (int j = 0; j < num_resources; ++j) {
std::cout << " R" << j << " ";
}
std::cout << "\n";
for (int i = 0; i < num_processes; ++i) {
std::cout << std::setw(10) << "P" << i << std::setw(10) << "";
for (int j = 0; j < num_resources; ++j) {
std::cout << std::setw(3) << max_demand[i][j];
}
std::cout << "\n";
}
std::cout << "\n";
// 打印 Allocation 矩阵
std::cout << std::setw(10) << "进程" << std::setw(10) << "Allocation";
for (int j = 0; j < num_resources; ++j) {
std::cout << " R" << j << " ";
}
std::cout << "\n";
for (int i = 0; i < num_processes; ++i) {
std::cout << std::setw(10) << "P" << i << std::setw(10) << "";
for (int j = 0; j < num_resources; ++j) {
std::cout << std::setw(3) << allocation[i][j];
}
std::cout << "\n";
}
std::cout << "\n";
// 打印 Need 矩阵
std::cout << std::setw(10) << "进程" << std::setw(10) << "Need";
for (int j = 0; j < num_resources; ++j) {
std::cout << " R" << j << " ";
}
std::cout << "\n";
for (int i = 0; i < num_processes; ++i) {
std::cout << std::setw(10) << "P" << i << std::setw(10) << "";
for (int j = 0; j < num_resources; ++j) {
std::cout << std::setw(3) << need[i][j];
}
std::cout << "\n";
}
std::cout << "\n";
// 打印等待队列
if (!waiting_queue.empty()) {
std::cout << "--- 等待队列 ---\n";
for (const auto& entry : waiting_queue) {
std::cout << "进程 P" << entry.first << " 请求: (";
for (size_t j = 0; j < entry.second.size(); ++j) {
std::cout << entry.second[j] << (j == entry.second.size() - 1 ? "" : ",");
}
std::cout << ")\n";
}
}
else {
std::cout << "等待队列为空。\n";
}
std::cout << "\n";
}
// 3. 安全性检查算法 (const 成员函数，因为它只读取状态，不修改对象自身)
bool is_safe_state(const std::vector<int>& current_available,
const std::vector<std::vector<int>>& current_allocation,
const std::vector<std::vector<int>>& current_need,
std::vector<int>& safe_sequence) const { // 注意这里是const
safe_sequence.clear(); // 清空之前的安全序列
std::vector<int> work = current_available;
std::vector<bool> finish(num_processes, false);
int count = 0; // 用于统计已完成的进程数量
while (count < num_processes) {
bool found_process_in_this_pass = false; // 标记本轮是否找到进程
for (int i = 0; i < num_processes; ++i) {
if (!finish[i] && is_less_equal(current_need[i], work)) {
// 找到一个可以执行的进程
work = add_vectors(work, current_allocation[i]); // work = work + allocation[i]
finish[i] = true;
safe_sequence.push_back(i); // 将进程ID加入安全序列
count++;
found_process_in_this_pass = true;
// 找到一个后，重新从头遍历进程，以确保任何新能满足的进程都被发现
break; // 跳出内层 for 循环，外层 while 循环会再次检查
}
}
if (!found_process_in_this_pass) {
// 本轮没有找到任何可以满足的进程，系统处于不安全状态
return false;
}
}
// 所有进程都能完成，系统处于安全状态
return true;
}
// 4. 处理资源请求 (用户接口)
void handle_request() {
if (!is_initialized()) {
std::cout << "系统尚未初始化，请先初始化系统。\n";
return;
}
int process_id = get_int_input("请输入请求资源的进程ID (P0-" + std::to_string(num_processes - 1) + "): ", 0, num_processes - 1);
if (process_id < 0 || process_id >= num_processes) { // 额外的边界检查
std::cout << "无效的进程ID。\n";
return;
}
std::vector<int> request = get_vector_input("请输入进程 P" + std::to_string(process_id) + " 请求的资源数量 (R0 R1 ... R" + std::to_string(num_resources - 1) + "): ", num_resources);
// 检查请求是否超过Need
if (!is_less_equal(request, need[process_id])) {
std::cout << "错误：请求的资源超过了进程 P" << process_id << " 的最大需求 (Need)！请求被拒绝。\n";
return;
}
// 检查系统是否有足够资源可用
if (!is_less_equal(request, available)) {
std::cout << "系统资源不足，进程 P" << process_id << " 的请求暂时无法满足。请求被拒绝，进程将被阻塞。\n";
waiting_queue.push_back({ process_id, request }); // 将请求加入等待队列
return;
}
// --- 试探性分配 ---
std::vector<int> temp_available = available;
std::vector<std::vector<int>> temp_allocation = allocation;
std::vector<std::vector<int>> temp_need = need;
// 更新临时状态
temp_available = subtract_vectors(temp_available, request);
temp_allocation[process_id] = add_vectors(temp_allocation[process_id], request);
temp_need[process_id] = subtract_vectors(temp_need[process_id], request);
std::vector<int> current_safe_sequence;
if (is_safe_state(temp_available, temp_allocation, temp_need, current_safe_sequence)) {
std::cout << "系统处于安全状态。资源分配成功！\n";
available = temp_available;
allocation = temp_allocation;
need = temp_need;
std::cout << "安全序列为: ";
for (size_t i = 0; i < current_safe_sequence.size(); ++i) {
std::cout << "P" << current_safe_sequence[i] << (i == current_safe_sequence.size() - 1 ? "" : " -> ");
}
std::cout << "\n";
}
else {
std::cout << "试探性分配后系统将进入不安全状态。资源分配被拒绝，进程 P" << process_id << " 被阻塞并加入等待队列。\n";
waiting_queue.push_back({ process_id, request }); // 将请求加入等待队列
// 回滚操作不需要显式写，因为我们操作的是临时变量，全局变量未被修改
}
}
// 5. 模拟进程释放资源 (用户接口)
void handle_release() {
if (!is_initialized()) {
std::cout << "系统尚未初始化，请先初始化系统。\n";
return;
}
int process_id = get_int_input("请输入释放资源的进程ID (P0-" + std::to_string(num_processes - 1) + "): ", 0, num_processes - 1);
if (process_id < 0 || process_id >= num_processes) {
std::cout << "无效的进程ID。\n";
return;
}
std::vector<int> release_vector = get_vector_input("请输入进程 P" + std::to_string(process_id) + " 释放的资源数量 (R0 R1 ... R" + std::to_string(num_resources - 1) + "): ", num_resources);
// 检查释放量是否超过已分配量
if (!is_less_equal(release_vector, allocation[process_id])) {
std::cout << "错误：进程 P" << process_id << " 试图释放超出其当前拥有量的资源！\n";
return;
}
// 执行资源释放
available = add_vectors(available, release_vector);
allocation[process_id] = subtract_vectors(allocation[process_id], release_vector);
need[process_id] = add_vectors(need[process_id], release_vector); // 释放资源后，Need会增加 (因为Max不变，Allocation减少)
std::cout << "进程 P" << process_id << " 成功释放资源。\n";
// 尝试满足等待队列中的进程
check_waiting_queue();
}
// 检查系统是否已初始化
bool is_initialized() const {
return num_processes > 0 && num_resources > 0;
}
};
// 测试
int main() {
Banker my_banker;
int choice;
do {
std::cout << "\n--- 银行家算法模拟系统 ---\n";
std::cout << "1. 初始化系统\n";
std::cout << "2. 打印当前状态\n";
std::cout << "3. 进程请求资源\n";
std::cout << "4. 进程释放资源\n";
std::cout << "0. 退出\n";
std::cout << "请选择操作: ";
// 使用更健壮的输入处理
while (!(std::cin >> choice)) {
std::cout << "无效输入，请输入一个数字选项。\n";
std::cin.clear(); // 清除错误标志
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 忽略当前行剩余输入
}
// 对于整数输入后，需要清除缓冲区中的换行符，以便后续的 `getline` 不受影响
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
switch (choice) {
case 1:
my_banker.initialize_system();
break;
case 2:
my_banker.print_current_state();
break;
case 3:
my_banker.handle_request();
break;
case 4:
my_banker.handle_release();
break;
case 0:
std::cout << "退出系统。再见！\n";
break;
default:
std::cout << "无效选择，请重新输入。\n";
break;
}
} while (choice != 0);
return 0;
}小结：
银行家算法通过维护和更新四个主要的数据结构来实现其功能：
- 可用资源（Available）：当前系统中每种类型可用的资源数量。
- 最大需求（Max）：每个进程对各类资源的最大需求量。
- 已分配资源（Allocation）：每个进程当前已分配到的各类资源数量。
- 仍需资源（Need）：每个进程还需要多少资源才能完成任务，计算方式为
Need = Max - Allocation。
算法的运行主要围绕以下三个核心环节：
- 系统初始化：设定初始的可用资源、进程的最大需求和初始分配情况，并据此计算出每个进程的
Need矩阵。 - 安全性检查：这是算法的心脏。它模拟资源分配和回收的过程，尝试找出一条能够使所有进程都能顺利完成的执行序列（即安全序列）。如果存在这样的序列，系统就处于安全状态，否则处于不安全状态。安全性检查通常通过一个
Work向量和Finish向量来迭代进行。 - 资源请求处理：当进程发出资源请求时，系统不会立即分配。首先，它会检查请求是否合法（
Request <= Need）以及是否有足够的可用资源（Request <= Available）。如果这些初步条件满足，算法会进行一次试探性分配，然后立即调用安全性检查。如果试探性分配后系统仍处于安全状态，才真正进行资源分配；否则，请求被拒绝，进程进入等待队列。 - 资源释放处理：当进程完成任务或主动释放资源时，系统会更新
Available和Allocation矩阵。值得注意的是，进程释放资源后，其Need也会相应增加。资源释放后，系统会重新检查等待队列，尝试唤醒那些因资源不足而被阻塞的进程
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-06-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
