banker.cpp

银行家算法的基本思想是分配资源之前,判断系统是否是安全的 若是,才分配。它是最具有代表性的避免死锁的算法

#include <iostream.h>
#include <stdlib.h>

#define True 1
#define False 0

#define max 100

int m,n;

int Available[max];
int Max[max][max];
int Allocation[max][max];
int Need[max][max];
int Request[max][max];
int Finish[max];
int p[max];
int work[max];
int Available1[max];
int Allocation1[max][max];
int Need1[max][max];


void init();
void bank();
int safe();

void main( )
{
	init();
	bank();
}

void init()
{
	int i,j;
	cout<<"请输入进程数：";
	cin>>m;
	cout<<"请输入系统的资源种类：";
	cin>>n;

	
    cout<<"进程对资源的最大需求，按"<<m<<"×"<<n<<"的矩阵输入:"<<endl;
	for (i=0;i<m;i++)
	{
		for (j=0;j<n;j++)
		{
			cin>>Max[i][j];
			
		}
		
	}
    
	cout<<"进程的已分配资源，按"<<m<<"×"<<n<<"的矩阵输入:"<<endl;
	for (i=0;i<m;i++)
	{
		for (j=0;j<n;j++)
		{
			cin>>Allocation[i][j];
			if (Allocation[i][j]>Max[i][j])
			{
				cout<<"你的输入大于进程P"<<i<<"对资源R"<<j<<"的最大需求，请从新输入！";
				j--;
				continue;
			}
			else
			{
				Need[i][j]=Max[i][j]-Allocation[i][j];				
			}
		}
	}

	for (j=0;j<n;j++)
	{
		cout<<"R"<<j<<"的资源现有的数目：";
		cin>>Available[j];
	}

	for (i=0;i<m;i++)
	{
		Finish[i]=False;
	}
	
	///////
    cout<<endl<<"当前系统资源情况:"<<endl<<"资源号  ";
	for (j=0;j<n;j++)
	{
		cout.width(4); 
        cout<<j; 
	}
	cout<<endl<<"可用资源";

	for (j=0;j<n;j++)
	{
		
		cout.width(4); 
        cout<<Available[j]; 
	
	}
	cout<<endl<<"分配情况:"<<endl;
	for (i=0;i<m;i++)
	{
		cout<<"进程";
		cout.width(3); 
            cout<<"p"<<i; 
		for (j=0;j<n;j++)
		{
			cout.width(4); 
            cout<<Allocation[i][j]; 
		}
		cout<<endl;
	}
    cout<<endl;

	cout<<endl<<"需求"<<endl;
	for (i=0;i<m;i++)
	{
		cout<<"进程";
		cout.width(3); 
            cout<<"p"<<i; 
		for (j=0;j<n;j++)
		{
			cout.width(4); 
            cout<<Need[i][j]; 
		}
		cout<<endl;
	}
    cout<<endl;

	safe();

} 

void bank()
{
	int i,j,cusneed;
    char ch;
    while(1)
    {
        cout<<"当前系统进程数为"<<m<<",请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl;
        cin>>cusneed;

		if (cusneed>m)
		{
			cout<<"你输入的进程号超过系统进程数,请重新输入!"<<endl;
			continue;
		}
        cout<<endl<<"请输入进程所请求的各资源的数量"<<endl;

        for(j=0;j<n;j++)
        {
			cout<<"对资源r"<<j<<"的请求:";
            cin>>Request[cusneed][j];
			if (Request[cusneed][j]>Need[cusneed][j])
            {
                cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl;
                continue;
            }
            if (Request[cusneed][j]>Available[j])
            {
                cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl;
                continue;
            }
        }
        
        for(j=0;j<n;j++)
        {
            Available[j]=Available[j]-Request[cusneed][j];
            Allocation[cusneed][j]=Allocation[cusneed][j]+Request[cusneed][j];
            Need[cusneed][j]=Need[cusneed][j]-Request[cusneed][j];
        }
		
        if(safe()==True)
        {
            cout<<"同意分配请求!"<<endl;
        }
        else
        {
            cout<<"您的请求被拒绝!"<<endl;
            for(j=0;j<n;j++)
            {
                Available[j]=Available[j]+Request[cusneed][i];
                Allocation[cusneed][j]=Allocation[cusneed][j]-Request[cusneed][j];
                Need[cusneed][j]=Need[cusneed][j]+Request[cusneed][j];
            }
        }
        for(i=0;i<m;i++)
        {
            Finish[i]=False;
        }
        cout<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl;
        cin>>ch;
        if(ch=='y'||ch=='Y')
        {
            continue;
        }
        break;
        }
		
}

int safe()
{	int i,j,k,l=0;
    for(j=0;j<n;j++)
    work[j]=Available[j];
    for(i=0;i<m;i++)
    {
        Finish[i]=False;
    }
    for(i=0;i<m;i++)
    {    
        if(Finish[i]==True)
        {
            continue;
        }
        else
        {
            for(j=0;j<n;j++)
            {
                if(Need[i][j]>work[j])
                {
                    break;
                }
            }
            if(j==n)
            { 
                Finish[i]=True;
                for(k=0;k<n;k++)
                {
                    work[k]=work[k]+Allocation[i][k];
                }
                p[l++]=i;
                i=-1;
            }
            else
            {
                continue; 
            }
        }
        if(l==m)
        {
            cout<<"系统是安全的"<<endl;
            cout<<"安全序列:"<<endl;
            for(i=0;i<l;i++)
            {
                cout<<p[i];
                if(i!=l-1)
                {
                    cout<<"-->";
                }
            }
            cout<<""<<endl;
            return True;
        }
    }
    cout<<"系统是不安全的"<<endl;
    return False;	
}

/*
int safe()
{
	int i,j,k,l=0;
	for(j=0;j<n;j++)
    work[j]=Available[j];
    for(i=0;i<m;i++)
    {
        Finish[i]=False;
		for(j=0;j<n;j++)
		{
			Allocation1[i][j]=Allocation[i][j];
		}
    }
	for (k=0;k<m;k++)
	{
		for (i=0;i<m;i++)
		{
			for(j=0;j<n&&Finish[i]==False;j++)
			{
				if (Need[i][j]>work[j])
					break;
			}
			while (Finish[i]==False&&j==n&&Need[i][j-1]<work[j-1])
			{
				Finish[i]=True;
				p[l]=i;
				l++;
				for(j=0;j<n+1;j++)
				{
					work[j]=work[j]+Need[i][j];
					Allocation1[i][j]=0;
				}

			}
				
		}
	}

	for (i=0;i<m&&Finish[i]==True;i++)
	{}
	if (i=m&&Finish[i-1]==True)
	{
		cout<<"系统是安全的"<<endl;
            cout<<"安全序列:"<<endl;
            for(i=0;i<l;i++)
            {
                cout<<p[i];
                if(i!=l-1)
                {
                    cout<<"-->";
                }
            }
            cout<<""<<endl;
            return True;
	}
	else
	{
		cout<<"系统是不安全的"<<endl;
        return False;
	}

}*/