银行家算法及其实现

银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的算法。

背景

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。（维基百科）

察看银行家算法的历史，它于 1965 年由 Dijkstra 和学生所设计，打算应用到 THE 系统中的。作为那个时代的产物，这个算法或许当时在避免死锁上取得了很好的效果，而技术发展日新月异，需求的变化和性能的差异使得它今天的价值主要体现在教学和思想的传播了吧。

一道题

我们简单地以一个习题来说明。

假定系统中有5个进程｛ $P_0$ ， $P_1$ ， $P_2$ ， $P_3$ ， $P_4$ ｝和四类资源｛A，B，C，D｝，在 $T_0$ 时刻的资源分配情况如下表所示：（四个数字表示进程对四类资源的影响）

进程 Allocation Need Available

$P_0$ 0 0 3 2 0 0 1 2 1 6 2 2

$P_1$ 1 0 0 0 1 7 5 0

$P_2$ 1 3 5 4 2 3 5 6

$P_3$ 0 3 3 2 0 6 5 2

$P_4$ 0 0 1 4 0 6 5 6

进程能否执行？应该按什么样的顺序执行？

进程	Allocation	Need	Available
$P_0$	0 0 3 2	0 0 1 2	1 6 2 2
$P_1$	1 0 0 0	1 7 5 0
$P_2$	1 3 5 4	2 3 5 6
$P_3$	0 3 3 2	0 6 5 2
$P_4$	0 0 1 4	0 6 5 6

算法步骤是：不断地从进程列表中取 Need 满足 Available 的进程执行，然后释放它申请的资源，也同时释放它产生的资源（ Allocation ）。

如该题中，我们从上往下看， $P_0$ 可以执行，执行完时资源向量为 (1, 6, 5, 4)。再看它满足 $P_3$ 的执行需求，接着是 $P_4$ 、 $P_1$ 、 $P_2$ 。

不断尝试的过程中，可能遇到多个进程都可以执行的情况。因为进程对资源的影响（Allocation）都是正数，且进程所用的资源（Need）都会还给系统，所以资源数始终会变多。在这种情况下，任选一个进程即可。

关于为负的情况，有空再补充吧。

伪代码

这里贴一下维基百科中提供的伪代码。

P - 进程的集合

Mp - 进程p的最大的请求数目

Cp - 进程p当前被分配的资源

A - 当前可用的资源

while (P != ∅) {
    found = FALSE;
    foreach (p ∈ P) {
        if (Mp − Cp ≤ A) {
             // p可以获得他所需的资源。假设他得到资源后执行;
             // 执行终止，并释放所拥有的资源。 
             A = A + Cp ;
             P = P − {p};
             found = TRUE;
        }
    }
    if (!found) return FAIL;
}
return OK;

C++实现

为了模拟真实系统中的环境（虽然真实系统中不太可能会用C++），我们对各个实体进行抽象，然后再编写具体代码。

可以对资源定义如下，其中 R::first 表示资源 ID，R::second 表示当前资源的数目：

1 2	using Resource = pair<int, size_t>; using R = Resource;

// 单个进程的结构
struct SingleProcess
{
    int  pid;
    // 进程需要的资源数量 <id, count>
    vector<Resource>  need;
    // 进程执行后将释放的资源数 <id, count>
    vector<Resource>  allocation;
    // 是否执行完成
    bool  is_finish = false;
};

接下来“自顶向下”实现银行家算法的代码。参考伪代码：

using  CallbackFunc = function<void(SingleProcess&)>;

bool  do_banker_algorithm(map<int, size_t>  &resources, 
                          vector<SingleProcess>  &processes, 
                          const CallbackFunc& process_callback)
{
    while (true)
    {
        auto  updated = false;
        for (auto process = processes.begin(); process != processes.end(); ++process)
        {
            // 寻找未执行的进程，如果当前资源满足需求，执行
            if (!(process->is_finish) && meet_resource_need(resources, *process))
            {
                run_process(resources, *process, process_callback);
                updated = true;
            }
        }
        // 每次对进程列表的遍历都应至少执行一个进程
        // 如果没有执行, 可能队列不安全，或算法执行完毕
        if (!updated)
        {
            return is_processes_finished(processes);
        }
    }
}

当 $P \neq \emptyset$ （P为进程列表）时算法不断地执行，考虑到对 vector<SingleProcess>操作会横生许多代码，这里用 while (true) 代替。如果某次遍历找不到一个可执行的进程，算法一定结束：可能是找到最终结果，或执行不下去（队列不安全）。下面补充其他函数：

// 判断当前环境的资源是否能执行特定进程 p
bool  meet_resource_need(map<int, size_t>  &resources, SingleProcess  &process)
{
    try
    {
        // 依次检查进程所需资源是否能得到满足
        for (auto res_need: process.need)
        {
            // 这里节省行数写到了一起
            // 如果所需资源的数量小于进程所需，返回 false
            if (resources.at(res_need.first) < res_need.second) return false;
        }
    }
    // http://www.cplusplus.com/reference/map/map/at/
    // 捕获 “所需资源不存在” 的异常
    catch(out_of_range  &e)
    {
        return false;
    }
    return true;
}

// 执行进程
void  run_process(map<int, size_t>& resources, SingleProcess& process, const CallbackFunc &process_callback)
{
    // 从资源列表中扣除所需资源，待进程结束后释放申请的资源，与它释放的资源
    // 这里只是向环境中加上进程额外释放的资源 SingleProcess::allocation
    for (auto  res_to_alloc : process.allocation)
    {
        try
        {
            // 向环境中抛出资源
            resources[res_to_alloc.first] += res_to_alloc.second;
        }
        catch (out_of_range &e)
        {
            // 如果抛出的资源，环境中本身不存在（那一类）
            // 用 insert 函数添加一个
            resources.insert(res_to_alloc);
        }
    }
    process_callback(process);
    process.is_finish = true;
}


bool is_processes_finished(vector<SingleProcess>  &processes)
{
    for (auto &process: processes)
    {
        if (!process.is_finish)
        {
            return false;
        }
    }
    return true;
}

最后执行试试：

int main()
{
    // <资源 ID, 资源数量>
    map<int, size_t>  resources;
    // 需要申请资源的进程
    vector<SingleProcess>  processes;

    resources[1] = 1;
    resources[2] = 6;
    resources[3] = 2;
    resources[4] = 2;
    
    processes.push_back(SingleProcess{ 0, 
        {R(3, 1), R(4, 2)}, {R(3, 3), R(4, 2)}});
    processes.push_back(SingleProcess{ 1,
        {R(1, 1), R(2, 7), R(3, 5)}, {R(1, 1)} });
    processes.push_back(SingleProcess{ 2, 
        {R(1, 1), R(2, 1), R(3, 3), R(4, 4) }, { R(1, 2), R(2, 5), R(3, 7), R(4, 6) } });
    processes.push_back(SingleProcess{ 3,
        {R(2, 6), R(3, 5), R(4, 2)}, {R(2, 3), R(3, 3), R(4, 2)} });
    processes.push_back(SingleProcess{ 4,
        {R(2, 6), R(3, 5), R(4, 6)}, {R(3, 1), R(4, 4)} });

    bool  result = do_banker_algorithm(resources, processes, [](SingleProcess &p) -> void
    {
        cout << "执行进程 " << p.pid << endl;
    });

    if (result)
    {
        cout << "找到安全队列" << endl;
    }
    else
    {
        cout << "队列一定会出现死锁" << endl;
    }

    return 0;
}

代码比单纯用数组写复杂了许多，但是可移植性、可扩展性还是挺好的，自以为思路也很清晰。上课听老师讲不如手写一遍，权当记录吧。

代码下载地址：Banker-Algorithm.cpp

优秀参考资料

写回, 银行家算法实例, https://blog.csdn.net/weixin_41282397/article/details/84552840
唯心不易, 银行家算法学习笔记, https://www.cnblogs.com/chuxiuhong/p/6103928.html
维基百科, 银行家算法, https://zh.wikipedia.org/wiki/银行家算法