linux——操作系统之实现银行家算法

linux

死锁问题

现如今的操作系统基本上都实现了多任务以及并发机制，由此，带来了一个明显的问题——进程资源分配的问题。假设有两个进程a、b，a完成任务需要资源R1、R2，b完成任务也需要资源R1、R2，系统的R1、R2资源数目都是1；这个时候，由于分配的原因，a进程只拿到了R1资源，b只拿到了R2资源；为了完成各自的任务，a进程在不放弃原有的R1资源下向系统申请R2资源，b进程在不放弃原有的R2资源下向系统申请R1资源，整个资源申请的图如下所示

资源申请图

由于a进程占有着R1资源去向系统申请R2资源，但是R2资源被需要R1资源的b进程所占有，两个进程占有着对方完成任务所需的剩余资源，同时又不放弃自身已有的资源，因此就出现了死锁问题。

银行家算法

银行家算法是提前判断当前资源分配是否会出现死锁情况。整个算法大致思路如下：

  1. 建立各个进程完成任务需要的资源情况表：Max[进程数目][资源种类数目]
  2. 建立各个进程已经获得的资源情况表：Allocation[进程数目][资源种类数目]
  3. 建立各个进程还需要的资源情况表：Need[进程数目][资源种类数目]
  4. 建立各个资源剩余情况表：Avliable[资源种类数目]
  5. 判断Avliable表满足Need表中的那一个进程(重要)
  6. 为满足的进程分配需要的资源，进程完成任务(重要)
  7. 回收进程完成任务的占有资源(重要)
  8. 判断是否所有进程都已完成各自的任务，若存在未完成任务的进程，则当前的进程资源分配一定存在死锁现象(重要)

银行家算法最主要的就是第5步骤到第8步骤，对剩余资源和各个进程还需资源进行比较、分配；分配的先后顺序可能会导致死锁，也可能使各个进程能够完成各自任务；能够使各个进程完成各自任务的资源分配顺序成为安全序列，因此也可以说银行家算法是判断是否存在一个安全序列使得进程完成各自任务。

为了判断能否得到安全序列，就要不断尝试各种资源分配顺序，在尝试的过程中，需要对Avliable表进行副本保存，用来恢复原始的Avliable表；同时设置worker数组，用于记录进程完成任务情况。

银行家算法实现

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <cstring>
using namespace std;

bool isEnough(int i, int a[], int b[])
{
    cout << i << " : " << a[0] << a[1] << a[2] << a[3] << endl;
    bool b1 = (a[0] <= b[0]);
    bool b2 = (a[1] <= b[1]);
    bool b3 = (a[2] <= b[2]);
    bool b4 = (a[3] <= b[3]);
    if (b1 && b2 && b3 && b4)
    {
        return true;
    }
    return false;
}

bool isFinish(bool worker[]) {
    return (worker[0] && worker[1] && worker[2] && worker[3]);
}

int getUnFinish(bool worker[], int loc) {
    int i = 0;
    while (!isFinish(worker)) {
        if ((!worker[i]) && (i != loc)) {
            return i;
        }
        i ++;
        if (i == 4) {
            i = 0;
        }
    }
    return -1;
}

int* addResource(int *Avliable, int Allocation[]) {
    int *ans = new int[4];
    for (int i = 0; i < 4; i ++) {
        ans[i] = Avliable[i] + Allocation[i];
    }
    return ans;
}

bool safe(int Allocation[][4], int Need[][4], int Avliable[])
{
    int tmp_avliable[4];
    copy(Avliable, Avliable + 4, tmp_avliable);
    bool worker[4] = {false, false, false, false};
    bool judge = false;
    for (int i = 0; i < 4; i++)
    {
        if (isEnough(i, Need[i], Avliable))
        {
            Avliable = addResource(Avliable, Allocation[i]);
            int count = 0;
            worker[i] = true;
            int un_worker = getUnFinish(worker, -1);
            while (!isFinish(worker)) {
                if (count > 5) {
                    break;
                }
                if (un_worker == -1) {
                    judge = true;
                    break;
                }
                if (isEnough(un_worker, Need[un_worker], Avliable)) {
                    Avliable = addResource(Avliable, Allocation[un_worker]);
                    worker[un_worker] = true;
                    un_worker = getUnFinish(worker, -1);
                } else {
                    un_worker = getUnFinish(worker, un_worker);
                }
                count += 1;
            }
        }
        if (isFinish(worker) || judge) {
            judge = true;
            break;
        }
        copy(tmp_avliable, tmp_avliable + 4, Avliable);
        memset(worker, false, 4);
    }
    if (judge) {
        cout << "存在安全序列" << endl;
        return true;
    }
    cout << "不存在安全序列，存在死锁情况" << endl;
    return false;
}

int main()
{
    // 各个进程已经拿到的资源情况
    int Allocation[4][4] = {{0, 0, 1, 2},
                            {1, 0, 0, 0},
                            {1, 3, 5, 4},
                            {0, 0, 1, 4}};
    // 各个进程完成各自任务所需要的资源数
    int Max[4][4] = {{0, 1, 1, 2},
                     {1, 7, 5, 0},
                     {2, 3, 5, 6},
                     {0, 6, 5, 6}};
    // 各个进程在已经得到资源的基础上，为了完成任务还需要的资源数量
    int Need[4][4] = {{0, 1, 0, 0},
                      {0, 7, 5, 0},
                      {1, 0, 0, 2},
                      {0, 6, 4, 2}};
    // 资源剩余量
    int Avliable[4] = {1, 0, 4, 0};
    safe(Allocation, Need, Avliable);
    return 0;
}