操作系統—銀行家演算法

參考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 }

原博主使用了goto函數，我覺得這個函數還是儘量少用。我對此進行了修改。

測試：在網上找了道銀行家演算法的題，在這裡坐下測試；

在銀行家演算法中，若出現下述資源分配情況，試問：

1）該狀態是否安全？

2）若進程P2提出請求Request（1,2,2,2）後，系統能否將資源分配？