乐趣区

关于操作系统:OS大作业三实现银行家算法

jiezi

数据定义：

  • E：Existing Resource 示意以后资源总量
  • A：Available Resource 示意以后可分配资源
  • MaxR：示意每种资源须要的最大需求量
  • C：Current Resource 示意以后已调配的资源
  • R：每种资源的最大可能申请
  • N：以后过程申请的资源

数据间的关系：

$$R = maxR – C$$
$$\sum{C}+ A = E$$

采纳的数据结构：

假如资源品种有 RNum 种，过程数量共有 PNum 个

则 E、A、N 均为大小为 RNum 的向量，含意为：
E[i]：示意第 i 种资源的资源总量
A[i]：示意第 i 种资源的以后残余资源，即为以后可分配资源
N[i]：示意以后提出申请的过程，对第 i 种资源的申请量

因而，以上三种数据的数据结构均用一维数组示意即可

maxR、C、R 为二维矩阵，矩阵的行示意过程的各种资源量，矩阵的列代表不同过程，如下表：

maxR C R
P1 (70,40,60) (20,20,20) (50,20,40)
P2 (40,40,50) (10,10,10) (30,30,40)
P3 (50,30,60) (30,30,30) (20,0,30)

各数据的定义如下：

int E[MAX_RNUM],A[MAX_RNUM],PNum,RNum;
int maxR[MAX_PNUM][MAX_RNUM],
       C[MAX_PNUM][MAX_RNUM],
       R[MAX_PNUM][MAX_RNUM];

设计思路：

要在过程调配时防止死锁，采纳如下实现思路：
在每次过程分配资源之前，对以后零碎进行死锁检测，判断零碎是否有可能产生死锁，若可能，则回绝此次资源分配。

要进行死锁检测，采纳银行家算法：
银行家算法的根本思维是分配资源之前，判断零碎是否是平安的；若是，才调配。它是最具备代表性的防止死锁的算法。
根据上述的数据结构，进行如下操作：
设过程 Pi 提出申请 N[i]，则银行家算法按如下规定进行判断。
(1)如果 N[i] [j]<= Ri，则转 (2)；否则，出错。
(2) 如果 N[i] [j]<= A[j]，则转 (3)；否则，期待。
(3) 零碎试探分配资源，批改相干数据：
A[j]-=Ni;
Ci+=Ni;
Ri-=Ni;
(4)零碎执行安全性查看，如平安，则调配成立；否则试探险性调配作废，零碎恢复原状，过程期待。

咱们采纳一个标记数组 finished[PNum]来标记过程 P[i]是否通过上述试探性调配
如果所有过程全副都通过试探性调配，即所有过程都被标记，阐明系统安全，并可依据资源分配的程序，输入此时零碎的安全性序列 Order。否则，未被标记的过程（即 Finished[i] = false）是可能产生死锁的过程。

因而，只有所有过程都被标记，FinishedNum == PNum 时，死锁检测算法能力返回 true，否则返回 false。

int Safe(FILE * fp){int FinishedNum = 0,i,Finished[MAX_PNUM] = {0};
    int testA[MAX_RNUM];
    for(int i = 1;i <= RNum;i++){testA[i] = A[i];
    }
    int Order[MAX_PNUM] = {0},k = 0;
    
    while(FinishedNum != PNum){for(i = 1;i <= PNum;i++){if(Finished[i] == 0 && find(R[i], testA)){for(int j = 1;j <= RNum;j++){testA[j] += C[i][j];
                }
                Finished[i] = 1;
                Order[k++] = i;// 记录
                FinishedNum++;
                if(FinishedNum == PNum){
                    // 输入 Order 到文件
                    fprintf(fp,"Process Safe Order:");
                    for(i = 0;i < PNum;i++){fprintf(fp,"%d",Order[i]);
                    }
                    fprintf(fp,"\n");
                    break;
                }
                break;
            }
        }
        if(i > PNum){return -1;}
        
    }
    return 1;
}

若死锁检测为真，则依据以后过程 P[i]提出的资源申请 N[RNum]进行资源分配，更新数据结构。
代码如下：

void ProcessAsk(int k,int *N,FILE * fp){// 过程 P_k 想要申请 N 个资源
    if(Safe(fp) == 1){printf("SYSTEM SAFE! Resource Allocating...\n");
        if(in_Scale(A,N) && in_Scale(R[k],N)){//A-N>=0 && R[k] - N >= 0
            for(int j = 1;j <= RNum;j++){C[k][j] += N[j];
            }
            for(int j = 1;j <= RNum;j++){R[k][j] -= N[j];
            }
            if(isZero(R[k])){for(int j = 1;j <= RNum;j++){A[j] += maxR[k][j];
                }
                printf("Process%d have released Resource!\n",k);
            }
            for(int j = 1;j <= RNum;j++){A[j] -= N[j];
            }
            fprintf(fp,"Allocate P%d SUCCESS!\n",k);
            printf("Allocate P%d SUCCESS!\n",k);
            showInfo();
//            write2File(fp);
        }else{printf("FAILED！Resource OverScale!\n");
        }
    }else{printf("SYSTEM WARNING!");
        showInfo();
        fprintf(fp,"Allocate P%d FAILED!\n",k);
    }
}

残缺代码

#include <stdio.h>
#include <stdlib.h>
#define MAX_PNUM 501
#define MAX_RNUM 100


int E[MAX_RNUM],A[MAX_RNUM],PNum,RNum;
int maxR[MAX_PNUM][MAX_RNUM],C[MAX_PNUM][MAX_RNUM],R[MAX_PNUM][MAX_RNUM];

void Init(){
    int i;
    
    printf("Input the Resource Num:");
    scanf("%d",&RNum);
    
    printf("Input the Existing Resource:");
    for(int i = 1;i <= RNum;i++){scanf("%d",&E[i]);
    }
    
    for(int i = 1;i <= RNum;i++){A[i] = E[i];
    }
    
    printf("Input the Num of Process:");
    scanf("%d",&PNum);
    
    printf("Input the MAX_Need Resource of every Process:");
    for(i = 1;i <= PNum;i++){for(int j = 1;j <= RNum;j++){scanf("%d",&maxR[i][j]);
            C[i][j] = 0;
            R[i][j] = maxR[i][j];
        }
    }
}

int find(int * Ri,int * A){for(int i = 1;i <= RNum;i++){if(Ri[i] > A[i]) return 0;
    }
    return 1;
}

int Safe(FILE * fp){int FinishedNum = 0,i,Finished[MAX_PNUM] = {0};
    int testA[MAX_RNUM];
    for(int i = 1;i <= RNum;i++){testA[i] = A[i];
    }
    int Order[MAX_PNUM] = {0},k = 0;
    
    while(FinishedNum != PNum){for(i = 1;i <= PNum;i++){if(Finished[i] == 0 && find(R[i], testA)){for(int j = 1;j <= RNum;j++){testA[j] += C[i][j];
                }
                Finished[i] = 1;
                Order[k++] = i;// 记录
                FinishedNum++;
                if(FinishedNum == PNum){
                    // 输入 Order 到文件
                    fprintf(fp,"Process Safe Order:");
                    for(i = 0;i < PNum;i++){fprintf(fp,"%d",Order[i]);
                    }
                    fprintf(fp,"\n");
                    break;
                }
                break;
            }
        }
        if(i > PNum){return -1;}
        
    }
    return 1;
}

void printVector(int * vector,int n){printf("(");
    for(int i = 1;i <= n;i++){printf("%d",vector[i]);
    }
    printf(")");
}

void showInfo(){
    int i;
    printf("*********************************************\n");
    printf("Existing Resource:");
    printVector(E, RNum);
    printf(",Available Resource:");
    printVector(A, RNum);
    printf("\n");
    
    printf("maxR:\n");
    for(int i = 1;i <= PNum;i++){for(int j = 1;j <= RNum;j++){printf("%d",maxR[i][j]);
        }
        printf("\n");
    }
    
    printf("CurrentR\n");
    for(int i = 1;i <= PNum;i++){for(int j = 1;j <= RNum;j++){printf("%d",C[i][j]);
        }
        printf("\n");
    }
    
    printf("Request:\n");
    for(int i = 1;i <= PNum;i++){for(int j = 1;j <= RNum;j++){printf("%d",R[i][j]);
        }
        printf("\n");
    }
    
    printf("*********************************************\n");
}

//void write2File(FILE * fp){
//    int i;
//    fprintf(fp, "*********************************************\n");
//    fprintf(fp, "Existing Resource:%d, Available Resource:%d\n",E,A);
//    fprintf(fp,"maxR\tCurrentR\tRequest\n");
//    for(i = 1;i <= PNum;i++){//        fprintf(fp,"%d\t\t%d\t\t\t%d\n",maxR[i],C[i],R[i]);
//    }
//    fprintf(fp,"*********************************************\n");
//    
//}

int in_Scale(int * vector,int * N){for(int j = 1;j <= RNum;j++){if(vector[j] < N[j]) return 0; 
    }
    return 1;
}

int isZero(int *Rk){for(int j = 1;j <= RNum;j++){if(Rk[j] != 0) return 0;
    }
    return 1;
}

void ProcessAsk(int k,int *N,FILE * fp){// 过程 P_k 想要申请 N 个资源
    if(Safe(fp) == 1){printf("SYSTEM SAFE! Resource Allocating...\n");
        if(in_Scale(A,N) && in_Scale(R[k],N)){//A-N>=0 && R[k] - N >= 0
            for(int j = 1;j <= RNum;j++){C[k][j] += N[j];
            }
            for(int j = 1;j <= RNum;j++){R[k][j] -= N[j];
            }
            if(isZero(R[k])){for(int j = 1;j <= RNum;j++){A[j] += maxR[k][j];
                }
                printf("Process%d have released Resource!\n",k);
            }
            for(int j = 1;j <= RNum;j++){A[j] -= N[j];
            }
            fprintf(fp,"Allocate P%d SUCCESS!\n",k);
            printf("Allocate P%d SUCCESS!\n",k);
            showInfo();
//            write2File(fp);
        }else{printf("FAILED！Resource OverScale!\n");
        }
    }else{printf("SYSTEM WARNING!");
        showInfo();
        fprintf(fp,"Allocate P%d FAILED!\n",k);
    }
}

int main(int argc, char *argv[]) {Init();
    FILE * fp;
    int i;
    if((fp=fopen("test.txt", "w+")) == NULL){fprintf(stdout, "Can't open \"test\" file.\n ");
        exit(EXIT_FAILURE);
    }
    showInfo();
//    write2File(fp);
    while(1){int k,N[RNum];
        printf("\nInput the ProcessNum and the Ask for Resource:");
        scanf("%d",&k);
        printf("Input the ask for Resource:");
        for(int i = 1;i <= RNum;i++){scanf("%d",&N[i]);
        }
        
        if(k <= 0 || k > PNum){printf("Process NOT exist!\n");
            break;
        }else{//            fprintf(fp, "\nProcess%d asking for %d Resource\n",k,N);
        }
        ProcessAsk(k, N, fp);
    }
    
    
    return 0;
}
退出移动版