オペレーティングシステム実験2-銀行家アルゴリズム
22438 ワード
一、実験目的1、オペレーティングシステムの安全状態と不安全状態とは何かを理解する.2、システムのデッドロックを避ける方法を理解する.3、銀行家のアルゴリズムを理解することは最も代表的なデッドロックを避けるアルゴリズムであり、その実現原理と実現過程を把握する.
二、実験内容は銀行家アルゴリズムの基本思想に基づいて、動的資源分配を実現するシミュレーションプログラムを編纂し、デバッグし、デッドロックの発生を効果的に回避することができる.三、実験原理プロセスが資源を申請する時、システムは一定のアルゴリズムを通じて今回の申請がデッドロック(安全状態)を発生できないかどうかを判断する.デッドロックが発生する可能性がある場合(安全でない場合)、デッドロックを回避するために、今回のリソース割り当ては保留されます.アルゴリズムには有名な銀行家のアルゴリズムがある.1、システムの安全状態と不安全状態とは何ですか.セキュリティ状態とは、システムに何らかのプロセスシーケンス
割り当てバグが見つかりました.変更後:
二、実験内容は銀行家アルゴリズムの基本思想に基づいて、動的資源分配を実現するシミュレーションプログラムを編纂し、デバッグし、デッドロックの発生を効果的に回避することができる.三、実験原理プロセスが資源を申請する時、システムは一定のアルゴリズムを通じて今回の申請がデッドロック(安全状態)を発生できないかどうかを判断する.デッドロックが発生する可能性がある場合(安全でない場合)、デッドロックを回避するために、今回のリソース割り当ては保留されます.アルゴリズムには有名な銀行家のアルゴリズムがある.1、システムの安全状態と不安全状態とは何ですか.セキュリティ状態とは、システムに何らかのプロセスシーケンス
が存在し、システムがそのシーケンスに従って各プロセスに必要なリソースを割り当て、最大の需要に至るまで、最終的に各プロセスを円滑に完了させることができることを意味し、そのプロセスシーケンス
をセキュリティシーケンスと呼ぶ.このようなセキュリティシーケンスが存在しない場合、システムは非セキュリティ状態にあると言います.2、銀行家アルゴリズムはオペレーティングシステムを銀行家と見なし、オペレーティングシステムが管理する資源は銀行家が管理する資金に相当し、プロセスがオペレーティングシステムに資源の分配を要求するのはユーザーが銀行家に融資することに相当する.資金の安全を保証するために、銀行家は、(1)顧客の資金に対する最大需要量が銀行家の既存の資金を超えない場合、その顧客を受け入れることができる.(2)顧客は分割ローンができるが、ローンの総数は最大需要量を超えてはならない.(3)銀行家の既存の資金が顧客がまだ必要とする貸付額を満たすことができない場合、顧客に対する貸付は支払いを遅らせることができるが、いつも顧客に限られた時間で貸付を得ることができる.(4)お客様が必要な資金を全部手に入れた後、必ず限られた時間ですべての資金を返すことができます.
オペレーティングシステムは銀行家が制定した規則に従って設計した銀行家アルゴリズムは:(1)プロセスが初めて資源の分配を申請する:システムの現存資源がそのプロセスの最大需要量を満たすことができるならば、現在の申請量によって資源を分配して、さもなくば分配を延期する.(2)プロセスは実行中にリソースの割り当てを申請し続ける:プロセスが占有したリソースと今回申請したリソースの和がリソースに対する最大需要量を超えず、現存するリソースがプロセスに必要な最大資源量を満たすことができる場合、現在の申請量によってリソースを割り当て、いいえ、割り当てを延期する.(3)少なくとも1つのプロセスは完了することができる:少なくとも1つのプロセスが必要なすべてのリソースを得て終了するまで実行できることをいつでも保証する.銀行家アルゴリズムは、システム内のリソースの割り当て状況とプロセスのリソースに対する需要状況を動的に検出することによって、リソースをどのように割り当てるかを決定し、システムが安全な状態にあることを確保したときにリソースを申請者に割り当てることができ、システムのデッドロックを回避することができる.
四.実験手順及び結果
#include
#include
#include
#define true 1
#define false 0
#define processNum 5
#define resourceNum 3
#define MAXINT 9999
typedef int bool;
int available[resourceNum]={3,3,2};
int maxRequest[processNum][resourceNum]={7,5,3,3,2,2,9,0,2,2,2,2,4,3,3};
int allocation[processNum][resourceNum]={0,1,0,2,0,0,3,0,2,2,1,1,0,0,2};
int need[processNum][resourceNum]={7,4,3,1,2,2,6,0,0,0,1,1,4,3,1};
bool Finish[processNum];
int safeSeries[processNum]={MAXINT, MAXINT , MAXINT , MAXINT , MAXINT};
int request[resourceNum];
bool Finish1[processNum];// true， false
void randon_init() //
{
int i, j;
srand((unsigned) (time(NULL))); //
//scanf("%d %d",&processNum,&resourceNum);
printf(" 、
");
printf("%d %d",processNum,resourceNum);
printf("
");
for(i = 0; i < resourceNum; i++){
available[i] = rand() % 2 + 2;
printf("%d ",available[i]);
}
printf("
");
for(i = 0; i < processNum; i++){
for(j = 0; j < resourceNum; j++){
maxRequest[i][j] = (rand() % 6 + 2);
printf("%d ",maxRequest[i][j]);
}
printf("
");
}
printf("
");
for(i = 0; i < processNum; i++){
for(j = 0; j < resourceNum; j++){
allocation[i][j] = rand() % 4 +1;
if (allocation[i][j] > maxRequest[i][j])
{
allocation[i][j] =0;
}
printf("%d ",allocation[i][j]);
}
printf("
");
}
printf("
");
for(i = 0; i < processNum; i++){
for(j = 0; j < resourceNum; j++){
need[i][j] = maxRequest[i][j] - allocation[i][j];
printf("%d ",need[i][j]);
}
printf("
");
}
}
void showInfo()
{
int i,j;
printf(" ：");
for(j = 0; j < resourceNum; j++){
printf("%d ",available[j]);
}
printf("
");
printf(" PID\t Max\t\tAllocation\tNeed
");
for(i = 0; i < processNum; i++){
printf(" P%d\t",i);
for(j = 0; j < resourceNum; j++){
printf("%d ",maxRequest[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){
printf("%d ",allocation[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){
printf("%d ",need[i][j]);
}
printf("
");
}
}
bool isSafe()
{
int i,j,k;
int trueFinished = 0;
int work[resourceNum];
for(i = 0; i < resourceNum; i++){
work[i]=available[i];
}
for(i = 0; i < processNum; i++){
Finish[i]=false;
}
i = 0;
int temp=0,temp0=0,flag=0;
while(trueFinished != processNum){
int j =0;
if(Finish[i]!= true){
for(j = 0; j < resourceNum; j++){
if(need[i][j] > work[j]){break;}
}
}
if(j == resourceNum){
Finish[i]=true;
SafeInfo(work,i);
for(k = 0; k < resourceNum; k++){
work[k]+=allocation[i][k];
}
safeSeries[trueFinished++] = i;
}
i++;
if(i >= processNum)
{
if(flag==0)
{
temp=trueFinished;
temp0=trueFinished;
}
i = i % processNum;
if(flag==1){
temp=trueFinished;
if(temp == temp0)
break;
else
temp0=temp;
}
flag=1;
}
temp = trueFinished;
}
if(trueFinished == processNum){
printf("
！
：");
for(i = 0; i < processNum; i++){
printf("%d ",safeSeries[i]);
}
return true;
}
printf("****** ！******
");
return false;
}
void SafeInfo(int *work, int i)
{
int j;
printf(" P%d\t",i);
for(j = 0; j < resourceNum; j++){
printf("%d ",work[j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){
printf("%d ",need[i][j]);
}
printf("\t ");
for(j = 0; j < resourceNum; j++){
printf("%d ",allocation[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){
printf("%d ",allocation[i][j]+work[j]);
}
printf("
");
}
void resource_release(int curProcess)
{
for(int i = 0; i < resourceNum; i++){
available[i] += maxRequest[curProcess][i];
maxRequest[curProcess][i] = 0;
allocation[curProcess][i]=0;
}
Finish1[curProcess] = true;
}
//
int main()
{
int i,j,curProcess;
int wheInit = 0;
printf(" ？0 ，1 ：");
scanf("%d",&wheInit);
if(wheInit)
randon_init(); // ，
printf("---------------------------------------------------------
");
showInfo();
printf("
");
printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation
");
if(isSafe()){
printf("
---------------------------------------------------------
");
printf("
：");
scanf("%d",&curProcess);
while(!Finish1[curProcess])
{
printf("
P%d ：",curProcess);
for(j = 0; j < resourceNum; j++){
scanf("%d", &request[j]);
}
for(j = 0; j < resourceNum; j++){
if(request[j] <= need[curProcess][j])continue;
else{printf("ERROR！
");break;}
}
if(j == resourceNum){
for(j = 0; j < resourceNum; j++){
if(request[j] <= need[curProcess][j])continue;
else{printf(" ， ！
");break;}
}
if(j == resourceNum){
for(j = 0; j < resourceNum; j++){
available[j] -= request[j];
allocation[curProcess][j] += request[j];
need[curProcess][j] -= request[j];
}
printf("
");
printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation
");
if(isSafe()){
printf(" ！
");
showInfo();
printf("P%d
",curProcess);
resource_release(curProcess); //
showInfo();
}else{
for(j = 0; j < resourceNum; j++){
available[j] += request[j];
allocation[curProcess][j] -= request[j];
need[curProcess][j] += request[j];
}
printf(" ！
");
showInfo();
}
}
}
if(Finish[curProcess]==Finish1[curProcess])
{
int r=curProcess;
printf("
0-4 , :");
scanf("%d",&curProcess);
if(r==curProcess)
{
printf("
0-4 , ， :");
scanf("%d",&curProcess);
}
if(curProcess>4||curProcess<0) return 0;}
}
}
}
/*
：
？0 ，1 ：1
、
5 3
3 2 3
5 4 6
3 6 5
3 4 4
6 7 4
5 7 7
1 3 3
3 3 2
2 1 2
3 4 1
3 4 1
4 1 3
0 3 3
1 3 2
3 3 3
2 3 6
---------------------------------------------------------
：3 2 3
PID Max Allocation Need
P0 5 4 6 1 3 3 4 1 3
P1 3 6 5 3 3 2 0 3 3
P2 3 4 4 2 1 2 1 3 2
P3 6 7 4 3 4 1 3 3 3
P4 5 7 7 3 4 1 2 3 6
PID Work Need Allocation Work+Allocation
****** ！******
：
？0 ，1 ：1
、
5 3
2 3 2
2 3 6
6 2 6
4 2 3
3 3 6
4 4 3
1 3 1
4 0 4
2 0 2
1 3 2
1 1 3
1 0 5
2 2 2
2 2 1
2 0 4
3 3 0
---------------------------------------------------------
：2 3 2
PID Max Allocation Need
P0 2 3 6 1 3 1 1 0 5
P1 6 2 6 4 0 4 2 2 2
P2 4 2 3 2 0 2 2 2 1
P3 3 3 6 1 3 2 2 0 4
P4 4 4 3 1 1 3 3 3 0
PID Work Need Allocation Work+Allocation
P1 2 3 2 2 2 2 4 0 4 6 3 6
P2 6 3 6 2 2 1 2 0 2 8 3 8
P3 8 3 8 2 0 4 1 3 2 9 6 10
P4 9 6 10 3 3 0 1 1 3 10 7 13
P0 10 7 13 1 0 5 1 3 1 11 10 14
！
：1 2 3 4 0
---------------------------------------------------------
：1
P1 ：2 2 2
PID Work Need Allocation Work+Allocation
P1 0 1 0 0 0 0 6 2 6 6 3 6
P2 6 3 6 2 2 1 2 0 2 8 3 8
P3 8 3 8 2 0 4 1 3 2 9 6 10
P4 9 6 10 3 3 0 1 1 3 10 7 13
P0 10 7 13 1 0 5 1 3 1 11 10 14
！
：1 2 3 4 0 ！
：0 1 0
PID Max Allocation Need
P0 2 3 6 1 3 1 1 0 5
P1 6 2 6 6 2 6 0 0 0
P2 4 2 3 2 0 2 2 2 1
P3 3 3 6 1 3 2 2 0 4
P4 4 4 3 1 1 3 3 3 0
P1
：6 3 6
PID Max Allocation Need
P0 2 3 6 1 3 1 1 0 5
P1 0 0 0 0 0 0 0 0 0
P2 4 2 3 2 0 2 2 2 1
P3 3 3 6 1 3 2 2 0 4
P4 4 4 3 1 1 3 3 3 0
0-4 , :2
P2 ：2 2 1
PID Work Need Allocation Work+Allocation
P0 4 1 5 1 0 5 1 3 1 5 4 6
P1 5 4 6 0 0 0 0 0 0 5 4 6
P2 5 4 6 0 0 0 4 2 3 9 6 9
P3 9 6 9 2 0 4 1 3 2 10 9 11
P4 10 9 11 3 3 0 1 1 3 11 10 14
！
：0 1 2 3 4 ！
：4 1 5
PID Max Allocation Need
P0 2 3 6 1 3 1 1 0 5
P1 0 0 0 0 0 0 0 0 0
P2 4 2 3 4 2 3 0 0 0
P3 3 3 6 1 3 2 2 0 4
P4 4 4 3 1 1 3 3 3 0
P2
：8 3 8
PID Max Allocation Need
P0 2 3 6 1 3 1 1 0 5
P1 0 0 0 0 0 0 0 0 0
P2 0 0 0 0 0 0 0 0 0
P3 3 3 6 1 3 2 2 0 4
P4 4 4 3 1 1 3 3 3 0
0-4 , :3
P3 ：2 0 4
PID Work Need Allocation Work+Allocation
P1 6 3 4 0 0 0 0 0 0 6 3 4
P2 6 3 4 0 0 0 0 0 0 6 3 4
P3 6 3 4 0 0 0 3 3 6 9 6 10
P4 9 6 10 3 3 0 1 1 3 10 7 13
P0 10 7 13 1 0 5 1 3 1 11 10 14
！
：1 2 3 4 0 ！
：6 3 4
PID Max Allocation Need
P0 2 3 6 1 3 1 1 0 5
P1 0 0 0 0 0 0 0 0 0
P2 0 0 0 0 0 0 0 0 0
P3 3 3 6 3 3 6 0 0 0
P4 4 4 3 1 1 3 3 3 0
P3
：9 6 10
PID Max Allocation Need
P0 2 3 6 1 3 1 1 0 5
P1 0 0 0 0 0 0 0 0 0
P2 0 0 0 0 0 0 0 0 0
P3 0 0 0 0 0 0 0 0 0
P4 4 4 3 1 1 3 3 3 0
0-4 , :4
P4 ：3 3 0
PID Work Need Allocation Work+Allocation
P0 6 3 10 1 0 5 1 3 1 7 6 11
P1 7 6 11 0 0 0 0 0 0 7 6 11
P2 7 6 11 0 0 0 0 0 0 7 6 11
P3 7 6 11 0 0 0 0 0 0 7 6 11
P4 7 6 11 0 0 0 4 4 3 11 10 14
！
：0 1 2 3 4 ！
：6 3 10
PID Max Allocation Need
P0 2 3 6 1 3 1 1 0 5
P1 0 0 0 0 0 0 0 0 0
P2 0 0 0 0 0 0 0 0 0
P3 0 0 0 0 0 0 0 0 0
P4 4 4 3 4 4 3 0 0 0
P4
：10 7 13
PID Max Allocation Need
P0 2 3 6 1 3 1 1 0 5
P1 0 0 0 0 0 0 0 0 0
P2 0 0 0 0 0 0 0 0 0
P3 0 0 0 0 0 0 0 0 0
P4 0 0 0 0 0 0 0 0 0
0-4 , :0
P0 ：1 0 5
PID Work Need Allocation Work+Allocation
P0 9 7 8 0 0 0 2 3 6 11 10 14
P1 11 10 14 0 0 0 0 0 0 11 10 14
P2 11 10 14 0 0 0 0 0 0 11 10 14
P3 11 10 14 0 0 0 0 0 0 11 10 14
P4 11 10 14 0 0 0 0 0 0 11 10 14
！
：0 1 2 3 4 ！
：9 7 8
PID Max Allocation Need
P0 2 3 6 2 3 6 0 0 0
P1 0 0 0 0 0 0 0 0 0
P2 0 0 0 0 0 0 0 0 0
P3 0 0 0 0 0 0 0 0 0
P4 0 0 0 0 0 0 0 0 0
P0
：11 10 14
PID Max Allocation Need
P0 0 0 0 0 0 0 0 0 0
P1 0 0 0 0 0 0 0 0 0
P2 0 0 0 0 0 0 0 0 0
P3 0 0 0 0 0 0 0 0 0
P4 0 0 0 0 0 0 0 0 0
0-4 , :0
0-4 , ， :0
*/
割り当てバグが見つかりました.変更後:
#include
#include
#include
#define true 1
#define false 0
#define processNum 5
#define resourceNum 3
#define MAXINT 9999
typedef int bool;
int available[resourceNum]={3,3,2};
int maxRequest[processNum][resourceNum]={7,5,3,3,2,2,9,0,2,2,2,2,4,3,3};
int allocation[processNum][resourceNum]={0,1,0,2,0,0,3,0,2,2,1,1,0,0,2};
int need[processNum][resourceNum]={7,4,3,1,2,2,6,0,0,0,1,1,4,3,1};
bool Finish[processNum];
int safeSeries[processNum]={MAXINT, MAXINT , MAXINT , MAXINT , MAXINT};
int request[resourceNum];
bool Finish1[processNum];// true， false
void randon_init() //
{
int i, j;
srand((unsigned) (time(NULL))); //
//scanf("%d %d",&processNum,&resourceNum);
printf(" 、
");
printf("%d %d",processNum,resourceNum);
printf("
");
for(i = 0; i < resourceNum; i++){
available[i] = rand() % 2 + 2;
printf("%d ",available[i]);
}
printf("
");
for(i = 0; i < processNum; i++){
for(j = 0; j < resourceNum; j++){
maxRequest[i][j] = (rand() % 6 + 2);
printf("%d ",maxRequest[i][j]);
}
printf("
");
}
printf("
");
for(i = 0; i < processNum; i++){
for(j = 0; j < resourceNum; j++){
allocation[i][j] = rand() % 4 +1;
if (allocation[i][j] > maxRequest[i][j])
{
allocation[i][j] =0;
}
printf("%d ",allocation[i][j]);
}
printf("
");
}
printf("
");
for(i = 0; i < processNum; i++){
for(j = 0; j < resourceNum; j++){
need[i][j] = maxRequest[i][j] - allocation[i][j];
printf("%d ",need[i][j]);
}
printf("
");
}
}
void showInfo()
{
int i,j;
printf(" ：");
for(j = 0; j < resourceNum; j++){
printf("%d ",available[j]);
}
printf("
");
printf(" PID\t Max\t\tAllocation\tNeed
");
for(i = 0; i < processNum; i++){
printf(" P%d\t",i);
for(j = 0; j < resourceNum; j++){
printf("%d ",maxRequest[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){
printf("%d ",allocation[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){
printf("%d ",need[i][j]);
}
printf("
");
}
}
bool isSafe()
{
int i,j,k;
int trueFinished = 0;
int work[resourceNum];
for(i = 0; i < resourceNum; i++){
work[i]=available[i];
}
for(i = 0; i < processNum; i++){
Finish[i]=false;
}
i = 0;
int temp=0,temp0=0,flag=0;
while(trueFinished != processNum){
int j =0;
if(Finish[i]!= true){
for(j = 0; j < resourceNum; j++){
if(need[i][j] > work[j]){break;}
}
}
if(j == resourceNum){
Finish[i]=true;
SafeInfo(work,i);
for(k = 0; k < resourceNum; k++){
work[k]+=allocation[i][k];
}
safeSeries[trueFinished++] = i;
}
i++;
if(i >= processNum)
{
if(flag==0)
{
temp=trueFinished;
temp0=trueFinished;
}
i = i % processNum;
if(flag==1){
temp=trueFinished;
if(temp == temp0)
break;
else
temp0=temp;
}
flag=1;
}
temp = trueFinished;
}
if(trueFinished == processNum){
printf("
！
：");
for(i = 0; i < processNum; i++){
printf("%d ",safeSeries[i]);
}
return true;
}
printf("****** ！******
");
return false;
}
void SafeInfo(int *work, int i)
{
int j;
printf(" P%d\t",i);
for(j = 0; j < resourceNum; j++){
printf("%d ",work[j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){
printf("%d ",need[i][j]);
}
printf("\t ");
for(j = 0; j < resourceNum; j++){
printf("%d ",allocation[i][j]);
}
printf("\t\t");
for(j = 0; j < resourceNum; j++){
printf("%d ",allocation[i][j]+work[j]);
}
printf("
");
}
void resource_release(int curProcess)
{
for(int i = 0; i < resourceNum; i++){
available[i] += maxRequest[curProcess][i];
maxRequest[curProcess][i] = 0;
allocation[curProcess][i]=0;
}
Finish1[curProcess] = true;
}
void bank()
{
int i,j,curProcess;
int wheInit = 0;
printf(" ？0 ，1 ：");
scanf("%d",&wheInit);
if(wheInit)
randon_init(); // ，
printf("---------------------------------------------------------
");
showInfo();
printf("
");
printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation
");
if(isSafe()){
printf("
---------------------------------------------------------
");
printf("
：");
scanf("%d",&curProcess);
while(!Finish1[curProcess])
{
printf("
P%d ：",curProcess);
for(j = 0; j < resourceNum; j++){
scanf("%d", &request[j]);
}
for(j = 0; j < resourceNum; j++){
if(request[j] <= need[curProcess][j])continue;
else{printf("ERROR！
");break;}
}
if(j == resourceNum){
for(j = 0; j < resourceNum; j++){
if(request[j] <= need[curProcess][j])continue;
else{printf(" ， ！
");break;}
}
if(j == resourceNum){
for(j = 0; j < resourceNum; j++){
available[j] -= request[j];
allocation[curProcess][j] += request[j];
need[curProcess][j] -= request[j];
}
printf("
");
printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation
");
if(isSafe()){
printf(" ！
");
showInfo();
printf("P%d
",curProcess);
int all=1;
for(j = 0; j < resourceNum; j++){
if( allocation[curProcess][j]< maxRequest[curProcess][j]) all=0;
}
if(all)
{
resource_release(curProcess); //
showInfo();
}
}else{
for(j = 0; j < resourceNum; j++){
available[j] += request[j];
allocation[curProcess][j] -= request[j];
need[curProcess][j] += request[j];
}
printf(" ！
");
showInfo();
}
}
}
if(Finish[curProcess]==Finish1[curProcess])
{
int r=curProcess;
printf("
0-4 , :");
scanf("%d",&curProcess);
if(r==curProcess)
{
printf("
0-4 , ， :");
scanf("%d",&curProcess);
}
if(curProcess>4||curProcess<0) return 0;
}
else
{
printf("
：");
scanf("%d",&curProcess);
Finish1[curProcess]=false;
}
}
}}
int main()
{
bank();
}