操作系统实验二死锁避免之银行家算法的模拟

admin 管理员组

文章数量: 887021

文章目录

死锁

 （1）定义

 （2）死锁产生的原因

 （3）死锁产生的必要条件

 （4）死锁的处理策略

银行家算法

 （1）核心思想

 （2）数据结构

 （3）算法描述

   (4)  安全性检查算法

银行家算法的模拟

（1）数据结构

（2）完整代码

（3）测试

死锁

（1）定义

所谓死锁，是指多个进程因为竞争资源而导致的一种互相循环等待的“僵局”，若无外力作用调整，这些进程都无法向前推进运行。

如下图所示，在十字路口，甲车在等着乙车来让道给自己通行，但乙车司机脾气暴躁就是不让也在等待着甲车让道给自己通行，互相等待，谁都不让道，从而造成一种拥堵的僵局现象，这就是生活中常见的死锁现象。

 （2）死锁产生的原因

• 系统资源的竞争
• 进程推进的顺序非法
• 信号量使用不当

（3）死锁产生的必要条件

• 互斥条件：进程要求对所分配的资源进行排他性使用，即在某段时间内某种资源只能被一种进程独自使用
• 不可剥夺条件：进程在获得资源后不能被其它进程强行夺走，而是由自己主动释放
• 请求并保持条件：进程已经保持了一种资源，但又提出了新的资源请求，而该资源已经被其它进程所占用，此时请求进程被阻塞，但对自己已经获得的资源保持不放
• 循环等待条件：存在一种进程资源的循环等待链，链中的每个进程所获得的资源同时被下一个资源所请求。如上图2-15所示

（4）死锁的处理策略

• 死锁预防：设置某些限制条件，破坏产生死锁4个必要条件中的一个或几个
• 死锁避免：在资源的动态分配中，用某种方法防止系统进入不安全状态
• 死锁的检测与解除：无需采用任何的限制性措施，允许进程发生死锁。通过系统的检测机制来检测到死锁，并采取某种措施来解除死锁

而下面所讲的银行家算法就属于死锁避免算法的一种。

银行家算法

（1）核心思想

        银行家算法是最著名的死锁避免算法，其思想是:把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

（2）数据结构

• 可用资源向量Available：长度为n的数组表示系统中n类资源的当前可用数目。如果Available[j]=k，表示系统中现有Rj类资源为k个。

• 最大需求矩阵Max：m×n矩阵定义m个进程对n类资源的最大需求量。如Max[i,j]=k，表示进程Pi运行期间最多需求Rj资源的数目为k个。

• 已分配资源矩阵Allocation：m×n矩阵定义了每个进程现在已分配到的各类资源的实际数目。如果Allocation [i,j]=k，表示进程Pi当前分到k个Rj类资源。

•  需求矩阵Need：m×n矩阵表示每个进程还需要的各类资源的数目。如果Need [i, j]=k，表示进程Pi尚需k个Rj类资源才能完成其任务。很显然，Need[i,j]=Max[i,j] - Allocation[i,j]，因而，这些数据结构的大小和值会随着时间而改变。

 其中，Need=Max-Allocation

 （3）算法描述

设Requesti表示进程Pi的资源申请向量。如Requesti[j]= k，表示进程Pi动态申请k个Rj类资源。当进程Pi申请资源时，就执行下列动作（试探性分配）:

1. 若Requesti[j]＞Need[i,j]，产生出错条件，因为进程Pi对资源的请求量已超过其说明的最大数量；否则，转到步骤2。

2. 如果Requesti[j]＞Available[j]，则进程Pi必须等待，这是因为系统现在没有可用的资源；否则，转到步骤3。

3. 如果系统可以给进程Pi分配所请求的资源，则应对有关数据结构进行修改：
           Available[j] = Available[j]-Requesti[j];   (j=1,2,……,n)
           Allocation[i,j] = Allocation[i,j] + Requesti[j];   (i=1,2,……,m)
           Need[i,j] = Need[i,j] - Requesti[j];

4. 系统执行安全性检查，查看此时系统状态是否安全。如果安全，就给进程Pi 实际分配资源；否则，即系统是不安全的，则Pi等待，作废本次试探性分配，并且把资源分配状态恢复成3之前的情况。

(4)安全性检查算法

        安全性检查算法是银行家算法的核心，在银行家算法的习题中，一般会有某个进程发出一个资源请求向量，我们只需要执行上面银行家算法的前三步，就会得到一个更新后的Allocation和Need矩阵，再按照上例的安全性算法进行判断，此时系统是否处于安全状态，就能直到系统是否能立即满足该进程提出的资源请求。

一般步骤如下：

1. 设置两个向量：工作向量Work：表示系统可提供给进程继续运行所需要的各类资源数目，长度为n；进程完成标志向量Finish：长度为m，表示各个进程是否能够得到足够的资源并运行完成。两个向量初始化：Work=Available，Finish[i]=false (i=1,2,...m)

2. 从进程集合中搜寻满足下列条件的进程（找安全进程序列）：Finish[i] ==false且Need[i，j]≤Work[j]。如果找到这样的进程，执行3；否则，则转向步骤4。

3. 修改数据值:Work[j]=Work[j] + Allocation[i,j]（进程Pi释放所占的全部资源）；Finish[i]=true；返回步骤2

4. 安全状态的判定：如果所有进程的Finish[i] ==true都成立（找着安全序列），则系统处于安全状态；否则，系统处于不安全状态。

银行家算法的模拟

（1）数据结构

//定义银行家算法的数据结构 
int Available[3]={3,3,2};//系统可用资源 
int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//进程最大资源需求量 
int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系统已经给进程分配的资源 
int Need[5][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//进程的资源最大需求量 
int Work[3];//安全性检查算法中的工作向量 
int Finish[5]={0,0,0,0,0};//进程执行完成的标志 
int SafeArray[5];//安全序列 
int Request[3];//请求资源向量 

（2）完整代码

/*
	模拟银行家算法，进行死锁的避免 
*/
#include<iostream>
using namespace std;
//定义银行家算法的数据结构 
int Available[3]={3,3,2};//系统可用资源 
int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//进程最大资源需求量 
int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系统已经给进程分配的资源 
int Need[5][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//进程的资源最大需求量 
int Work[3];//安全性检查算法中的工作向量 
int Finish[5]={0,0,0,0,0};//进程执行完成的标志 
int SafeArray[5];//安全序列 
int Request[3];//请求资源向量 

void ShowSafe(int i);
//打印当前系统资源的分配情况 
void Show(){
    cout<<"T0时刻的系统资源分配情况如下："<<endl;
    cout<<"进程名\tMax\t\tAllocation\tNeed\t\tAvailable"<<endl;
    for(int i=0;i<5;i++){
        cout<<"P"<<i<<"\t";
        for(int j=0;j<3;j++){
            cout<<Max[i][j]<<" ";
        }
        cout<<"\t\t";
        for(int j=0;j<3;j++){
            cout<<Allocation[i][j]<<" ";
        }
        cout<<"\t\t";
        for(int j=0;j<3;j++){
            cout<<Need[i][j]<<" ";
        }
        cout<<"\t\t";
        if(i==0){
            for(int j=0;j<3;j++){
                cout<<Available[j]<<" ";
            }
        }
        cout<<endl;
    }
}
//安全性检查中判断需求矩阵与工作向量关系 
int NeedLessWork(int i){
    for(int j=0;j<3;j++){
        if(Need[i][j]>Work[j]){
            return 0;
        }
    }
    return 1;
}
//打印安全序列 
void SafeLine(){
    cout<<"当前系统处于安全状态..."<<endl;
    cout<<"其中一个安全序列为：" ;
    for(int i=0;i<5;i++){
    	if(i==4)cout<<"P"<<SafeArray[i];
    	else cout<<"P"<<SafeArray[i]<<"-->";
    }
    cout<<endl;
    for(int i=0;i<5;i++){
        Finish[i]=0;
    }
}

//安全性检查算法 
void IsSafe(int index){
    for(int i=0;i<5;i++){
        int temp=NeedLessWork(i);
        if(Finish[i]==0&&temp){
            SafeArray[index]=i;
            index++;
            Finish[i]=1;
            ShowSafe(i);
            for(int j=0;j<3;j++){
                Work[j]=Work[j]+Allocation[i][j];
            }
            break;
        }
    }
    int mult=1;
    //如果五个标志都为1即都已经完成，则打印安全序列，否则继续执行安全性检查算法 
    for(int k=0;k<5;k++){
        mult*=Finish[k];
    }
    if(mult==0){
        IsSafe(index);
    }else{
        SafeLine();
    }
}
void ShowSafe(int i){
    cout<<"P"<<i<<"\t";
    for(int j=0;j<3;j++){
        cout<<Work[j]<<" ";
    }
    cout<<"\t\t";
    for(int j=0;j<3;j++){
        cout<<Need[i][j]<<" ";
    }
    cout<<"\t\t";
    for(int j=0;j<3;j++){
        cout<<Allocation[i][j]<<" ";
    }
    cout<<"\t\t";
    for(int j=0;j<3;j++){
        cout<<Work[j]+Allocation[i][j]<<" ";
    }
    cout<<"\t\t";
    cout<<Finish[i];
    cout<<endl;

}
void SafeCheck(){
    cout<<"试探着将资源分配给它后，系统安全情况分析如下："<<endl;
    cout<<"进程\tWork\t\tNeed\t\tAllocation\tWork+Allocation\tFinish"<<endl;
    for(int i=0;i<3;i++){
        Work[i]=Available[i];
    }
    IsSafe(0);
}

int RequestLessNeed(int i){
    for(int j=0;j<3;j++){
        if(Request[j]>Need[i][j]){
            return 0;
        }
    }
    return 1;
}
int RequestLessAvailable(int i){
    for(int j=0;j<3;j++){
        if(Request[j]>Available[j]){
            return 0;
        }
    }
    return 1;
}

//处理进程发出的资源请求 
void RequestResourse(){
    cout<<"请输入发出资源请求的进程：";
    int n;
	cin>>n;
    cout<<"请依次输入所请求的资源数量：";
    for(int i=0;i<3;i++){
        cin>>Request[i];
    }
    if(RequestLessNeed(n)){
    	if(RequestLessAvailable(n)){
    		for(int j=0;j<3;j++){
            Available[j]=Available[j]-Request[j];
            Allocation[n][j]=Allocation[n][j]+Request[j];
            Need[n][j]=Need[n][j]-Request[j];
           }
            SafeCheck();//试探着将资源分配给请求进程，并进行安全性检查 
    	}else{
    		cout<<"P"<<n<<"请求的资源向量已超过系统可用资源向量，请求失败！让其继续等待..."<<endl;
    		cout<<"-------------------------------------------------------------------"<<endl; 
            return ;
    	}
    }else{
    	 cout<<"P"<<n<<"请求的资源向量已超过其最大需求向量，请求失败！让其继续等待..."<<endl;
    	 cout<<"-------------------------------------------------------------------"<<endl; 
         return ;
    }
}


int main(){
    cout<<"*************************银行家算法的模拟*************************"<<endl;
    cout<<"    \t\t\t1.显示当前系统资源情况"<<endl;
    cout<<"    \t\t\t2.进程发出请求向量"<<endl;
    cout<<"    \t\t\t3.退出系统"<<endl;
    cout<<"******************************************************************"<<endl; 
    while(true){
        int choose;
        cout<<"请选择你要执行的操作：";
        cin>>choose;
        switch (choose){
            case 1 :
                Show();//展示当前系统资源分配情况 
                break;
            case 2:
                RequestResourse();//处理进程发出的资源请求 
                break;
            case 3:
                cout<<"已退出系统！"<<endl;
                return 0;
            default:
                cout<<"输入错误，请重新输入！"<<endl;
                continue;
        }
    }
}

（3）测试

 综上。

本文标签： 死锁 银行家 算法 操作系统