银行家算法--申请资源-Toy模板网

这篇具有很好参考价值的文章主要介绍了银行家算法--申请资源。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

银行家算法–申请资源

问题描述：
输入N个进程(N<=100)，以及M类资源（M<=100），初始化各种资源的总数，T0时刻资源的分配情况。例如：假定系统中有5个进程{P0，P1，P2，P3，P4}和三类资源{A,B,C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配图如下：
银行家算法--申请资源
输入申请资源的进程以及申请各类资源的数目，判断是否分配。若分配，输出”可以找到安全序列，可以分配。“并输出分配后的系统状态。若不分配，输出”找不到安全序列，不予分配。“并输出当前系统状态。

输入格式:
第一行输入进程数量N，第二行输入资源类数M，第三行输入M类资源个类资源的总数，以下N行分别输入每个进程的名字，该进程对M类资源的最大需求以及已分配资源。最后一行输入申请进程的名字和申请各类资源的数目。

输出格式:
若分配，输出”可以找到安全序列，可以分配。“并输出分配后的系统状态。

若不分配，给出不分配的原因：

若输入的进程的名字不正确，输出”查无此进程。“并输出当前系统状态。
若申请的资源数目大于最大需求，输出”需求不合理，不予分配。“并输出当前系统状态。
若申请的资源数目大于剩余资源，输出”剩余资源不足，不予分配。“并输出当前系统状态。
若找不到安全序列，输出”找不到安全序列，不予分配。“并输出当前系统状态。

输入样例1:
在这里给出一组输入。例如：

5
3
10 5 7
P0 7 5 3 0 1 0
P1 3 2 2 2 0 0
P2 9 0 2 3 0 2
P3 2 2 2 2 1 1
P4 4 3 2 0 0 2
P1 1 0 2

输出样例1:
在这里给出相应的输出。例如：

可以找到安全序列，可以分配。
name max allocation need available
P0 7 5 3 | 0 1 0 | 7 4 3 | 2 3 0
P1 3 2 2 | 3 0 2 | 0 2 0 |
P2 9 0 2 | 3 0 2 | 6 0 0 |
P3 2 2 2 | 2 1 1 | 0 1 1 |
P4 4 3 2 | 0 0 2 | 4 3 0 |

输入样例2:
在这里给出一组输入。例如：

5
3
10 5 7
P0 7 5 3 0 1 0
P1 3 2 2 2 0 0
P2 9 0 2 3 0 2
P3 2 2 2 2 1 1
P4 4 3 2 0 0 2
P5 1 0 2

输出样例2:
在这里给出相应的输出。例如：

查无此进程。
name max allocation need available
P0 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2
P1 3 2 2 | 2 0 0 | 1 2 2 |
P2 9 0 2 | 3 0 2 | 6 0 0 |
P3 2 2 2 | 2 1 1 | 0 1 1 |
P4 4 3 2 | 0 0 2 | 4 3 0 |

代码实现（C语言）：

#include<stdio.h>
#include<string.h>
typedef struct process{
    char name[2];
    int max[4],allocation[4],need[4];
    bool flag;
}p;

void countNeed(p pro[],int available[],int available_01[],int proNumber,int sourNumber);
int checkSafe(p pro[],int available[],int available_01[],int proNumber,int sourNumber,char requireName[],int requireSource[]);
void printAll(p pro[],int available[],int proNumber,int sourNumber);

int main(){
    int proNumber,sourNumber,flag,i,j;
    scanf("%d",&proNumber);
    scanf("%d",&sourNumber);
    int available[sourNumber],available_01[sourNumber],requireSource[sourNumber];
    p pro[proNumber];
    char requireName[2];
    //初始化资源总数
    for(i=0;i<sourNumber;i++){
        scanf("%d",&available[i]);
    }
    //初始化进程的资源使用情况
    for(i=0;i<proNumber;i++){
        scanf("%s",&pro[i].name);
        pro[i].flag = false;
        for(j=0;j<sourNumber;j++){
            available_01[j] = available[j];
            scanf("%d",&pro[i].max[j]);
        }
        for(j=0;j<sourNumber;j++){
            scanf("%d",&pro[i].allocation[j]);
        }
    }
    //初始化请求进程及其资源请求数
    scanf("%s",&requireName);
    for(j=0;j<sourNumber;j++){
            scanf("%d",&requireSource[j]);
        }
    
    countNeed(pro,available,available_01,proNumber,sourNumber);
    
    flag = checkSafe(pro,available,available_01,proNumber,sourNumber,requireName,requireSource);
    if(flag == 0){
        printf("可以找到安全序列，可以分配。\n");
        printAll(pro,available_01,proNumber,sourNumber);
    }
    if(flag == 1){
        printf("查无此进程。\n");
        printAll(pro,available_01,proNumber,sourNumber);
    }
    if(flag == 2){
        printf("需求不合理，不予分配。\n");
        printAll(pro,available_01,proNumber,sourNumber);
    }
    if(flag == 3){
        printf("剩余资源不足，不予分配。\n");
        printAll(pro,available_01,proNumber,sourNumber);
    }
    if(flag == 4){
        printf("找不到安全序列，不予分配。\n");
        printAll(pro,available_01,proNumber,sourNumber);
    }
    
    return 0;
}

void countNeed(p pro[],int available[],int available_01[],int proNumber,int sourNumber){
    int i,j;
    for(i=0;i<proNumber;i++){
        for(j=0;j<sourNumber;j++){
            pro[i].need[j] = pro[i].max[j] - pro[i].allocation[j];
            available[j] -= pro[i].allocation[j];
            available_01[j] = available[j];
        }
    }
}

int checkSafe(p pro[],int available[],int available_01[],int proNumber,int sourNumber,char requireName[],int requireSource[]){
    int i,j,sum=0,sum1=0,sum2=0,count=0,countRequire=-1;
    bool flagAll = false,flagAll_01 = false;
    //进行名称和请求资源数和need资源数的比较
    for(i=0;i<proNumber;i++){
        if(strcmp(requireName,pro[i].name) == 0) {
            countRequire=i;
            for(j=0;j<sourNumber;j++){
                if(requireSource[j]<=pro[i].need[j]) sum1++;
                if(requireSource[j]<=available[j]) sum2++;
        }
    }
}
    //printf("%d %d %d \n",countRequire,sum1,sum2);
    
    //countRequire != -1存在进程名称相等的进程
    if(countRequire != -1&&sum1 == sourNumber &&sum2 == sourNumber){
    	//对请求的进程进行初始化 
    	for(j=0;j<sourNumber;j++){
    		    available[j] -= requireSource[j];
                pro[countRequire].allocation[j] += requireSource[j];
                pro[countRequire].need[j] -= requireSource[j];
        }
        
        while(sum<proNumber){
         for(i=0;i<proNumber;i++){
         	sum1 = 0;
            if(pro[i].flag == false){
                 for(j=0;j<sourNumber;j++){
                    if(pro[i].need[j]<=available[j]) sum1++;
                    }
            
            if(sum1 == sourNumber) {
                    for(j=0;j<sourNumber;j++)
                    available[j] += pro[i].allocation[j];
                    
            pro[i].flag = true;
            sum++;
        } 
      }
    }
        count+=6;
        if(count == 54) break;
  }
    }
    else if(countRequire == -1){
        return 1; //1.若输入的进程的名字不正确，输出”查无此进程。“并输出当前系统状态。
    }else if(sum1 != sourNumber) return 2; //2.若申请的资源数目大于最大需求，输出”需求不合理，不予分配。“并输出当前系统状态。
    else if(sum2 != sourNumber) return 3; //3.若申请的资源数目大于剩余资源，输出”剩余资源不足，不予分配。“并输出当前系统状态。
 
    if(sum == proNumber) {
    	 for(j=0;j<sourNumber;j++){
    	 	available_01[j] -=  requireSource[j];
		 }
                
		return 0;  //给人家分配！
}
    else if(sum != proNumber) {
    	for(j=0;j<sourNumber;j++){
    	 	pro[countRequire].allocation[j] -= requireSource[j];
            pro[countRequire].need[j] += requireSource[j];
		 }
	return 4; //4.若找不到安全序列，输出”找不到安全序列，不予分配。“并输出当前系统状态。
    
}
}
 

void printAll(p pro[],int available[],int proNumber,int sourNumber){
    printf("name max allocation need available\n");
    int i,j;
    for(i=0;i<proNumber;i++){
        printf("%s ",pro[i].name);
        for(j=0;j<sourNumber;j++){
            printf("%d ",pro[i].max[j]);
        }
        printf("| ");
        for(j=0;j<sourNumber;j++){
            printf("%d ",pro[i].allocation[j]);
        }
        printf("| ");
        for(j=0;j<sourNumber;j++){
            printf("%d ",pro[i].need[j]);
        }
        if(i == 0){
            printf("| ");
            for(j=0;j<sourNumber;j++){
                if(j == sourNumber-1)
            printf("%d",available[j]);
                else printf("%d ",available[j]);
        }
       }else printf("|");
        printf("\n");
    }
}