操作系统—银行家算法

银行家算法

参考http://blog.csdn.net/yaopeng_2005/article/details/6935235　　

对小鹏_加油的代码进行了部分修改，并加入了自己的文档注释

定义全局变量，以及主函数main

 1 #include <iostream>
 2 using namespace std;
 3 #define MAXPROCESS 50                        //最大进程数
 4 #define MAXRESOURCE 100                      //最大资源数
 5 int AVAILABLE[MAXRESOURCE];                  //可用资源数组
 6 int MAX[MAXPROCESS][MAXRESOURCE];            //最大需求矩阵
 7 int ALLOCATION[MAXPROCESS][MAXRESOURCE];     //分配矩阵
 8 int NEED[MAXPROCESS][MAXRESOURCE];           //需求矩阵
 9 int REQUEST[MAXPROCESS][MAXRESOURCE];        //进程需要资源数
10 bool FINISH[MAXPROCESS];                     //系统是否有足够的资源分配
11 int p[MAXPROCESS];                           //记录序列
12 int m,n;                                     //m个进程,n个资源
13 void Init();    //初始化变量
14 bool Safe();    //安全检测
15 void Bank();    //银行家算法
16 void showdata(int,int);    //显示输出系统信息
17 int main()
18 {
19     Init();
20     Safe();
21     Bank();
22 }

初始化变量Init函数

 1 /*初始化变量*/
 2 void Init()                
 3 {
 4     int i,j;
 5     cout << "请输入进程的数目:";
 6     cin >> m;
 7     cout << "请输入资源的种类:";
 8     cin >> n;
 9     cout << "请输入每个进程最多所需的各资源数,按照" << m << "x" << n << "矩阵输入" << endl;
10     for(i=0;i<m;i++)
11         for(j=0;j<n;j++)
12             cin >> MAX[i][j];
13     cout << "请输入每个进程已分配的各资源数,也按照" << m << "x" << n << "矩阵输入" << endl;
14     for(i = 0; i < m; i++)
15         for(j = 0; j < n; j++)
16         {
17             cin >> ALLOCATION[i][j];
18             NEED[i][j] = MAX[i][j] - ALLOCATION[i][j];
19             if(NEED[i][j] < 0)
20             {
21                 cout << "您输入的第" << i+1 << "个进程所拥有的第" << j+1 << "个资源数错误,请重新输入:" << endl;
22                 j--;
23                 continue;
24             }
25         }
26         cout << "请输入各个资源现有的数目:" << endl;
27         for(i = 0; i < n; i++)
28             cin >> AVAILABLE[i];
29 }

银行家算法Bank函数

 1 /*银行家算法*/
 2 void Bank()               
 3 {
 4     int i,cusneed,flag = 0;    //cousneed资源进程号
 5     char again;    //键盘录入一个字符用于判断是否继续请求资源
 6     while(1)
 7     {
 8         showdata(n,m);
 9         cout << endl;
10         /*请求资源*/
11         while(true)
12         {
13             cout << "请输入要申请资源的进程号(注:第1个进程号为0,依次类推)" << endl;
14             cin >> cusneed;
15             if (cusneed > m)
16             {
17                 cout << "没有该进程，请重新输入" << endl;
18                 continue;
19             }
20             cout << "请输入进程所请求的各资源的数量" << endl;
21             for(i = 0; i < n; i++)
22                 cin >> REQUEST[cusneed][i];
23             for(i = 0; i < n; i++)
24             {
25                 if(REQUEST[cusneed][i] > NEED[cusneed][i])    //如果用户选择的线程的第i个资源请求数＞该线程该资源所需的数量
26                 {
27                     cout << "您输入的请求数超过进程的需求量!请重新输入!" << endl;
28                     continue;
29                 }
30                 if(REQUEST[cusneed][i] > AVAILABLE[i])    //如果用户选择的线程的第i个资源请求数＞系统现有的第i个资源的数量
31                 {
32                     cout << "您输入的请求数超过系统有的资源数!请重新输入!" << endl;
33                     continue;
34                 }
35             }
36             break;
37         }
38         /*如果请求合理，那么开始银行家算法计算*/
39         /*先将申请的资源进行分配*/
40         for(i = 0; i < n; i++)
41         {
42             AVAILABLE[i] -= REQUEST[cusneed][i];            //系统可用资源减去申请了的
43             ALLOCATION[cusneed][i] += REQUEST[cusneed][i];    //线程被分配的资源加上已申请了的
44             NEED[cusneed][i] -= REQUEST[cusneed][i];        //线程还需要的资源减去已申请得到的
45         }
46         /*判断分配申请资源后的系统是否安全；如果不安全则将分配的申请资源还回系统*/
47         if(Safe())    //AVAILABLE  ALLOCATION  NEED变动之后，是否会导致不安全
48             cout << "同意分配请求!" << endl;
49         else
50         {
51             cout << "您的请求被拒绝!" << endl;
52             /*资源还回系统*/
53             for(i = 0; i < n; i++)
54             {
55                 AVAILABLE[i] += REQUEST[cusneed][i];
56                 ALLOCATION[cusneed][i] -= REQUEST[cusneed][i];
57                 NEED[cusneed][i] += REQUEST[cusneed][i];
58             }
59         }
60         /*对进程的需求资源进行判断；是否还需要资源；即NEED数组是否为0*/
61         for (i = 0; i < n; i++)
62             if (NEED[cusneed][i] <= 0)
63                 flag++;
64         if (flag == n)    //如果该进程各资源都已满足条件，则释放资源
65         {
66             for (i = 0; i < n; i++)
67             {
68                 AVAILABLE[i] += ALLOCATION[cusneed][i];
69                 ALLOCATION[cusneed][i] = 0;
70                 NEED[cusneed][i] = 0;
71             }
72             cout << "线程" << cusneed << " 占有的资源被释放！" << endl;
73             flag = 0;
74         }
75         for(i = 0; i < m; i++)    //分配好了以后将进程的标识FINISH改成false
76             FINISH[i] = false;
77         /*判断是否继续申请*/
78         cout << "您还想再次请求分配吗?是请按y/Y,否请按其它键" << endl;
79         cin >> again;
80         if(again == \'y\' || again == \'Y\')
81             continue;
82         break;
83     }
84 }

安全性算法Safe函数

 1 /*安全性算法*/
 2 bool Safe() 
 3 {
 4     int i, j, k, l = 0;
 5     int Work[MAXRESOURCE];    //工作数组
 6     /*工作数组赋值，与AVAILABLE数组相同*/
 7     for (i = 0; i < n; i++)
 8         Work[i] = AVAILABLE[i];
 9     /*FINISH数组赋值，初始为全部false*/
10     for (i = 0; i < m; i++)
11         FINISH[i] = false;    //FINISH记录每个进程是否安全
12     while (l < m)    //正常的话，共执行m次
13     {
14         int init_index = l;
15         for (i = 0; i < m; i++)
16         {
17             if (FINISH[i] == true)    //如果这个进程安全则继续下一个循环
18                 continue;
19             for (j = 0; j < n; j++)
20                 if (NEED[i][j] > Work[j])
21                     break;
22             if (j == n)
23             {
24                 FINISH[i] = true;
25                 for (k = 0; k < n; k++)
26                     Work[k] += ALLOCATION[i][k];
27                 p[l++] = i;//记录进程号    
28             }
29             else    //如果超过继续循环下一个进程
30                 continue;
31         }
32         if (l==init_index)
33         {
34             cout << "系统是不安全的" << endl;
35             return false;
36         }
37     }
38     cout << "系统是安全的" << endl;
39     cout << "安全序列:" << endl;
40     for (i = 0; i < l; i++)
41     {
42         cout << p[i];
43         if (i != l - 1)
44             cout << "-->";
45     }
46     cout << endl;
47     return true;
48 }

显示showdata函数

 1 /*显示*/
 2 void showdata(int n,int m)
 3 {
 4     int i,j;
 5     cout << endl << "-------------------------------------------------------------" << endl;  
 6     cout << "系统可用的资源数为:    ";
 7     for (j = 0; j < n; j++)
 8         cout << "    " << AVAILABLE[j];         
 9     cout << endl << "各进程还需要的资源量:" << endl; 
10     for(i = 0; i < m; i++)   
11     {
12         cout << "    进程" << i << ":";   
13         for(j = 0; j < n; j++)
14             cout << "     " << NEED[i][j];   
15         cout << endl;   
16     }   
17     cout << endl << "各进程已经得到的资源量:    " << endl << endl;
18     for (i = 0; i < m; i++)   
19     {
20         cout << "    进程" << i << ":";   
21         for (j = 0; j < n; j++)
22             cout << "     " << ALLOCATION[i][j];
23         cout << endl;   
24     }  
25     cout << endl; 
26 }