银行家算法的实验报告

一、实验内容

银行家算法是避免死锁的一种重要方法，本实验要求编写和调试一个简单的银行家算法程序。

1．设计进程对各类资源最大申请表示及初值的确定。
2．设定系统提供资源的初始状况。
3．设定每次某个进程对各类资源的申请表示。
4．编制程序，依据银行家算法，决定其资源申请是否得到满足。
5．显示资源申请和分配时的变化情况。

二、背景知识

1．死锁的相关知识。在多道程序环境中，多个进程可以竞争有限数量的资源。当一个进程申请资源时，如果这时没有可用资源，那么这个进程进入等待状态。有时，如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态。这种情况称为死锁。

2．银行家算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

3．系统安全性检查。

1）设置两个向量：
工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;
工作向量Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］=false; 当有足够资源分配给进程时， 再令Finish［i］=true。

2）从进程集合中找到一个能满足下述条件的进程： 
Finish［i］=false;
Need［i,j］≤Work［j］；若找到，执行 (3)，否则，执行 (4)

3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work［j］=Work［i］+Allocation［i,j］;
Finish［i］=true;
go to step 2;

4）如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态;

三、思路

四、核心代码(添加注释)

#include <malloc.h> 
#include <string.h>
#include <iostream> 
using namespace std;

struct p {
    int Max[100][100];//最大需求矩阵 
    int Allocation[100][100];//分配矩阵 
    int Need[100][100];//需求矩阵 
    int Available[100];//可利用资源 
    int Resource[100];//总资源 
    int Work[100];//正工作资源 
    int Finish[100]; //判断进程是否已完成 
    int List[100];//存放安全序列的下标序列 
};
class yinhangjia {
public:
    void initial(int N, int M, struct p* s); //输入数据 
    void printState(int N, int M, struct p* s);//输出当前状态表 
    int isfinish(int N, int M, struct p* s, int C);//判断是否满足资源更换条件 
    int issafe(int N, int M, struct p* s);//判断是否为合法资源 
    void printList(int N, int M, struct p* s);//输出安全序列表 
    void reqresource(int N, int M, struct p* s, int i, int Request[]);//输入更改资源，并判断是否合法 
};



void yinhangjia :: initial(int N, int M, struct p* s)
//创建初始状态：先输入 Resource、Max和 Allocation，再计算出 Need、Available。   
{
    int i, j;
    cout << "Resource--输入M种资源的总数量:\n";
    for (i = 0; i < M; i++)
    {
        cin >> s->Resource[i];
        s->Available[i] = s->Resource[i];
    }
    cout << "Max--输入N个进程分别对M种资源的最大需求量:\n";
    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            cin >> s->Max[j][i];
    cout << "Allocation--输入N个进程获得M种资源的数量:\n";
    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            cin >> s->Allocation[j][i];
    /****************************************/
    for (j = 0; j < N; j++)//求出需求need量 ，通过最大需求量-已经占用的资源数量 
        for (i = 0; i < M; i++)
            s->Need[j][i] = s->Max[j][i] - s->Allocation[j][i];
    for (j = 0; j < M; j++)//求出可用Available量  
        for (i = 0; i < N; i++)
            s->Available[j] = s->Available[j] - s->Allocation[i][j];
}

void yinhangjia ::printState(int N, int M, struct p* s)
//输出当前的状态表|Process     |Max         |Allocation  |Need         |Available   | 
{
    int j, i;
    cout << "\n状态表如下:\n";
    cout << "|Process     ";
    cout << "|Max";
    for (int k = 0; k < M * 4 - 3; k++)
        cout << " ";
    cout << "|Allocation";
    for (int k = 0; k < M * 4 - 10; k++)
        cout << " ";
    cout << "|Need";
    for (int k = 0; k < M * 4 - 4; k++)
        cout << " ";
    cout << "|Available";
    for (int k = 0; k < M * 4 - 9; k++)
        cout << " ";
    cout << "|\n";
    for (i = 0; i < N; i++)
    {
        cout << i;
        for (int k = 0; k < M; k++)
            cout << s->Max[i][k];
        cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Allocation[i][k];
        cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Need[i][k];
        cout << "|";
        if (i == 0) {
            for (int k = 0; k < M; k++)
                cout << s->Available[k];
            cout << "|";
        }
        cout << endl;
    }
}

int yinhangjia :: isfinish(int N, int M, struct p* s, int C)
//返回同时满足两个条件{①Finish[i]=false;  ②Need[i][j]≤Work[j]}的进程下标 i(修改Finish[i]=true)，否则返回-1。 
{
    int i, j, count, b = 0;
    static int k = 0;
    //printf("%d\n",k);
    cout << k << endl;
    for (i = C; i < N; i++)
    {
        for (j = 0, count = 0; j < M; j++)//判断单个进程是否符合安全序列 
            if (s->Finish[i] == 0 && s->Need[i][j] <= s->Work[j])
            {
                count++;
            }
        if (count == M)
        {
            for (j = 0; j < M; j++)
                s->Work[j] += s->Allocation[i][j];//进程完成后，释放的空间加到现在闲置的空间内 
            s->Finish[i] = 1;//将进程修改为已完成状态 
            k++;
            if (k == N)
                k = 0;
            //printf("%d\n",k);
            cout << k << endl;
            return i;
        }
        if (i == N - 1 && k < N) {
            i = -1;
            b++;
        }
        if (b == 2)
            break;
    }
    return -1;
}

int yinhangjia :: issafe(int N, int M, struct p* s)
//判定当前状态是否为安全状态 （返回 true 或 false），把安全序列的下标放入 List[N]数组。 
{
    int i, a, count = 0, C = 0;
    for (i = 0; i < M; i++)
        s->Work[i] = s->Available[i];//工作资源数 
    for (i = 0; i < N; i++)
        s->Finish[i] = 0;
    for (i = 0; i < N; i++)
    {
        a = isfinish(N, M, s, C);
        //printf("%d ?a\n",a);
        //cout << a << endl;
        if (a != -1)
        {
            s->List[i] = a;
            C = a;
            count++;
            //printf("%d  ,\n",count);
            //cout << count << endl;
        }
        else if (a == -1) C = 0;
    }
    if (count == N)
        return 1;
    else
        return 0;
}

void yinhangjia :: printList(int N, int M, struct p* s)
//输出安全序列表|Process |Work  |Need   |Allocation  |Work+Alloc   |Finish  | 
{
    int i, j;
    cout << "\n安全序列表如下:\n";
    cout << "|Process     ";
    cout << "|Work";
    for (int k = 0; k < M * 4 - 4; k++)
        cout << " ";
    cout << "|Need";
    for (int k = 0; k < M * 4 - 4; k++)
        cout << " ";
    cout << "|Allocation";
    for (int k = 0; k < M * 4 - 10; k++)
        cout << " ";
    cout << "|Work+Alloc";
    for (int k = 0; k < M * 4 - 10; k++)
        cout << " ";
    cout << "|Finish";
    for (int k = 0; k < M * 4 - 6; k++)
        cout << " ";
    cout << endl;
    for (j = 0; j < M; j++)
    {
        s->Work[j] = s->Available[j];
    }
    for (i = 0; i < N; i++)
    {
        cout << s->List[i];
        for (int k = 0; k < M; k++)
            cout << s->Work[k];
            cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Need[s->List[i]][k];
            cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Allocation[s->List[i]][k];
            cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Work[k] + s->Allocation[s->List[i]][k];
            cout << "|true";
        for (int k = 0; k < M * 4 - 4; k++)
            cout << " ";
            cout << "|\n";
        for (j = 0; j < M; j++)
            s->Work[j] += s->Allocation[s->List[i]][j];
    }
}

void yinhangjia :: reqresource(int N, int M, struct p* s, int i, int Request[])
//表示第 i个进程请求 M类资源 request[M] 
{
    int flag, count1, count2;
    int j;
    //Step1:  判断条件 Request[j]≤Need[i][j] 
    for (j = 0, count1 = 0; j < M; j++)
        if (Request[j] <= s->Need[i][j])
            count1++;
    //Step2:  判断条件 Request[j]≤Available[j]
    for (j = 0, count2 = 0; j < M; j++)
        if (Request[j] <= s->Available[j])
            count2++;
    if (count2 != M)  
        cout << "\n尚无足够的资源，第" << i << "个进程堵塞。\n";
    //Step3:  预先分配 
    if (count2 == M && count1 == M)
    {
        for (j = 0; j < M; j++)
        {
            s->Available[j] = s->Available[j] - Request[j];
            s->Allocation[i][j] = s->Allocation[i][j] + Request[j];
            s->Need[i][j] = s->Need[i][j] - Request[j];
            //printf("%d %d %d\n",s->Available[j],s->Allocation[i][j],s->Need[i][j]);
            //cout << s->Available[j];
            //cout << s->Allocation[i][j];
            //cout << s->Need[i][j];
            //cout << endl;
        }
        if (issafe(N, M, s) == 0)
        { 
            cout << "\n不存在安全序列，不是安全状态。\n";
            for (j = 0; j < M; j++)
            {
                s->Available[j] = s->Available[j] + Request[j];
                s->Allocation[i][j] = s->Allocation[i][j] - Request[j];
                s->Need[i][j] = s->Need[i][j] + Request[j];
            }
        }
        else
        {
            cout << "\n是安全序列分配成功!\n";
        yinhangjia:printList(N, M, s);
        }
    }
}
int main(void)
{
    int reqid = -1, j, req[100];
    struct p s;
    int N, M;
    cout << "please input MAX resources and MAX processes :";
    cin >> M >> N;
    yinhangjia a;//构造银行家类a
    a.initial(N, M, &s); //创建数据 
    if (a.issafe(N, M, &s) == 0)
    {
        printf("Initial state is unsafe!\n");
    }
    else
    {
       a.printState(N, M, &s); //输出当前状态表 
        cout << "\nInitial state is safe!\n" << endl;
        a.printList(N, M, &s); //输出安全序列表 
        cout << "Input the id of request process:"  ;
        cin >> reqid;
        while (reqid >= 0 && reqid < N)   //输入进程 id是否合法 
        {  
            cout << "Input request resources:";
                for (j = 0; j < M; j++)
                {
                    cin >> req[j];
                }
            a.reqresource(N, M, &s, reqid, req);
            a.printState(N, M, &s);
            cout << "Input the id of request process:";
            cin >> reqid;
        }
        cout << "\n输入错误，退出程序!\n";
    }
    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
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292

五、运行结果

输出状态表和安全序列表

若有足够的资源给请求的资源，则输出新的状态表

若没有足够的资源给请求的资源，则显示进程堵塞并输出状态表

六、结论
1.银行家算法是一种用来避免操作系统死锁出现的有效算法。

2.死锁：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

3.死锁的发生必须具备以下四个必要条件：

1）互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。

2）请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

3）不抢占条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

4）循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

4.银行家算法是避免死锁的一种重要方法，防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。

5.为实现银行家算法，系统必须设置若干数据结构，同时要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

6.安全序列:是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

7.安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。

8.安全状态一定是没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁