// banker.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
using namespace std;
#define MAXPROCESS 50                        /*最大進程數*/
#define MAXRESOURCE 100                        /*最大資源數*/
int AVAILABLE[MAXRESOURCE];                    /*可用資源數組*/
int MAX[MAXPROCESS][MAXRESOURCE];            /*最大需求矩陣*/
int ALLOCATION[MAXPROCESS][MAXRESOURCE];    /*分配矩陣*/
int NEED[MAXPROCESS][MAXRESOURCE];            /*需求矩陣*/
int REQUEST[MAXPROCESS][MAXRESOURCE];        /*進程需要資源數*/
bool FINISH[MAXPROCESS];                        /*系統是否有足夠的資源分配*/
int p[MAXPROCESS];                             /*記錄序列*/
int m,n;                                    /*m個進程,n個資源*/

void Init();
bool Safe();
void Bank();
void main()//
{
    Init();
    Safe();
    Bank();
}

void Init()                /*初始化算法*/
{
   int i,j;
    cout<<"\t---------------------------------------------------"<<endl;
    cout<<"\t||                                               ||"<<endl;
    cout<<"\t||                 銀行家算法                    ||"<<endl;
    cout<<"\t||                                               ||"<<endl;
    cout<<"\t||               旦小梅  04281184                ||"<<endl;
    cout<<"\t||                                               ||"<<endl;
    cout<<"\t||                                               ||"<<endl;
    cout<<"\t---------------------------------------------------"<<endl;
    cout<<"請輸入進程的數目:";
    cin>>m;
    cout<<"請輸入資源的種類:";
    cin>>n;
   cout<<"請輸入每個進程最多所需的各資源數,按照"<<m<<"x"<<n<<"矩陣輸入"<<endl;
    for(i=0;i<m;i++)
    for(j=0;j<n;j++)
    cin>>MAX[i][j];
    cout<<"請輸入每個進程已分配的各資源數,也按照"<<m<<"x"<<n<<"矩陣輸入"<<endl;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>ALLOCATION[i][j];
            NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];
            if(NEED[i][j]<0)
            {
                cout<<"您輸入的第"<<i+1<<"個進程所擁有的第"<<j+1<<"個資源數錯誤,請重新輸入:"<<endl;
                j--;
                continue;
            }
        }
    }
    cout<<"請輸入各個資源現有的數目:"<<endl;
    for(i=0;i<n;i++)
    {
        cin>>AVAILABLE[i];
    }
}

void Bank()                /*銀行家算法*/
{
    int i,cusneed;
    char again;
    while(1)
    {
        cout<<"請輸入要申請資源的進程號(注:第1個進程號為0,依次類推)"<<endl;
        //cin>>cusneed;
		cusneed=rand()%5;
		printf("隨機生成申請資源的進程號：%d\n",cusneed);
        //cout<<"請輸入進程所請求的各資源的數量"<<endl;
        for(i=0;i<n;i++)
        {
            //cin>>REQUEST[cusneed][i];
			REQUEST[cusneed][i]=rand()%4;
        }
		printf("隨機生成進程所請求的各資源的數量：\n");
		for(i=0;i<n;i++)
			printf("%d ",REQUEST[cusneed][i]);
		printf("\n");
        for(i=0;i<n;i++)
        {
            if(REQUEST[cusneed][i]>NEED[cusneed][i])
            {
                cout<<"您輸入的請求數超過進程的需求量!請重新輸入!"<<endl;
                continue;
            }
            if(REQUEST[cusneed][i]>AVAILABLE[i])
            {
                cout<<"您輸入的請求數超過系統有的資源數!請重新輸入!"<<endl;
                continue;
            }
        }
        for(i=0;i<n;i++)
        {
            AVAILABLE[i]-=REQUEST[cusneed][i];
            ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
            NEED[cusneed][i]-=REQUEST[cusneed][i];
        }
        if(Safe())
        {
            cout<<"同意分配請求!"<<endl;
        }
        else
        {
            cout<<"您的請求被拒絕!"<<endl;
            for(i=0;i<n;i++)
            {
                AVAILABLE[i]+=REQUEST[cusneed][i];
                ALLOCATION[cusneed][i]-=REQUEST[cusneed][i];
                NEED[cusneed][i]+=REQUEST[cusneed][i];
            }
        }
        for(i=0;i<m;i++)
        {
            FINISH[i]=false;
        }
        cout<<"您還想再次請求分配嗎?是請按y/Y,否請按其它鍵"<<endl;
        cin>>again;
        if(again=='y'||again=='Y')
        {
            continue;
        }
        break;
        }
}

bool Safe()                                    /*安全性算法*/
{
    int i,j,k,l=0;
    int Work[MAXRESOURCE];                    /*工作數組*/
    for(i=0;i<n;i++)
    Work[i]=AVAILABLE[i];
    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]+=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;
}