从银行家算法看程序构建

好久没看数据结构方面的东西，有些生.

如题：

分析：

这个考点，不止OS,数据结构，软考都是重要考点。当时备考时，肯定是理解了的。那就再复习下吧。

基本知识：

什么是银行家算法？

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，

进程向操作系统请求分配资源相当于用户向银行家贷款。

为保证资金的安全，银行家规定：

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；

(2)顾客可以分期贷款，但贷款的总数不能超过最大需求量；

(3)当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；

(4)当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.

操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配

程序设计

基本的原理是有了，但如何实现呢？先从规定中看有哪些需求？

1. 顾客的最大需求量。现有的资金。

2. 分期贷款

3. 延迟支付？这个如何实现？

这些问题在软考考点之死锁资源数计算,有所阐述了，主要对比看看如何用程序的方式写出来。

如何考虑到的四种数据结构呢？

首先得明白，银行家算法是站在银行家的角度上，去看如何分配资源的问题。当有三个人同时跟我借钱时，根据手中钱的多少，如何能在及时的借给出去，使得每个人都能得到部分钱，直到得到所需要全部金额。是供给侧的算法。跟现实中实际的贷款及银行算法，还是有一定的差距。

从问题看数据结构设计

银行家算法需要解决的问题：使申请资源的进程能均衡的得到资源，如果能脑补出整个分配资源的过程，那么程序就可以被抽象出来，进而考虑下内考如何操作，就可以设计出相应的数据结构。

那么这个分配的过程如下：

当前分配给进程的资源，还需要的资源数，最大需求，放到了同一个结构体中了，相当于创建了一个进程（客户）类。并初始了三个进程。

如果某个线程本次分配（本次分配的资源数并不等同于还需要的资源数，可分期贷款）资源数大于可分配的资源数，肯定挂起。所以这里还需要一个可分配的资源数，如题所示，就用一个变量表示。rest=12;

如果本次分配大于了还需要的资源数，那可以分配。如题所示：AC结构体可知，每个进程只需要一种类型的资源或设备。

可分配的资源数=rest-d;同时，当前的已分配的资源+d;还需要分配的资源数-d;

还需要判断下，现在已分配的资源数是不是已经等于了最大需求的资源数。如果是，那就要释放掉资源。

所有的分配操作，基本上就是操作的进程类相关的数据结构，可见数据结构还是挺重要的。

题目考的也是分配算法，相对来说还是简单的。答案如下所示：题目中bank()函数。

扩展：其实题目还要求程序运行的截图

这个是有难度的，尤其考试的环境下，这个其实要看对这个算法的熟悉度了。银行家算法的核心还有一个安全检测。

思想是这样的，给出一个分配的序列，如果按照这个序列分配资源，看是不是可以把所有的进程都运行完。如题目给出的ac[]数组就是分配矩阵。如果可以运行完就是安全的序列，可以调用分配进程。如果不能使等待资源的进程运行完就先不分配资源。

#include 
int rest = 12;//最大资源数
struct MX {
    int won;//已经分配的资源数
    int want;//还需要的资源数
    int most;//最大需求数
};
struct MX mx[] = {{0, 9, 9}, {0, 10, 10}, {0, 4, 4}};//三个进程的最大需求资源数
struct AC {
    int pid ;
    int dem;//资源数
};
struct AC ac[] = {{0, 2}, {1, 5}, {2, 2}, {0, 1}, {2, 2}, {0, 6}, {2, 5}};//分配矩阵
int bank(int i, int d)//银行家算法，i为进程号，d为资源需求数
{
    if (d <= mx[i].want && d <= rest) {
        rest -= d;//rest=12
        mx[i].won = mx[i].won + d;
        mx[i].want -= d;
        if (mx[i].won == mx[i].most) {
            rest = rest + mx[i].won;
        }
        return mx[i].won;
    } else return -1;//不分期贷款，很容易造成资源分配不平衡，所发直接放弃这样的分法了。
}
int allot(struct AC *a, int d)
{
    int i, sum = 0;
    for (i = 0; i < 7; i++) {
        i = bank(ac[i].pid, ac[i].dem);
        if (i != -1) {
            sum = sum + i;
            if (sum >= 12) break;
        } else {
            printf("bank alo is failed\n");
        }
    }
}

int main()
{
    allot(ac, 7);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45