bank.cpp

模拟银行家算法,有详细的输出说明,可用于演示银行及算法,附带输入的示例文件.

//============================================================================
// Name        : BANK.cpp
// Author      : wcpeter
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

int ResourceNum;
int ProcNum;
int GTime;
bool UseBank;

class ResoReqData       //资源申请记录
{
public:
        int ProcId;
        int Time;
        int Res;
        int ResNum;
        bool operator < (const ResoReqData &a)const {
                return Time<a.Time;
        }
};

//bool CompResoData(const ResoData & a,const ResoData & b);
class ProcData          //进程记录
{
public:
        string ProcName;
        int lasttime;
        vector <int> ResoGet;
        vector <int> ResoMax;
        bool Bigger(vector<int> & a);
        void ModAllReso(vector<int> & a);
        void ModOSReso(vector<int> & a);
        void ModResoGet (int ResId,int ModNum);
        bool runflag;
};
void ProcData::ModResoGet (int ResId,int ModNum)
{
        ResoGet[ResId]+=ModNum;
}
bool ProcData::Bigger(vector<int> & a)
{
        vector<int>::iterator i,j,k;
        for (i=ResoGet.begin(),j=a.begin(),k=ResoMax.begin();i!=ResoGet.end();i++,j++,k++)
        {
                if (*i+*j<*k)
                        return false;
        }
        return true;
}

void ProcData::ModAllReso(vector<int> & a)
{
        vector<int>::iterator i,j;
        for (i=ResoGet.begin(),j=a.begin();i!=ResoGet.end();i++,j++)
        {
                *i+=*j;
        }
}

void ProcData::ModOSReso(vector<int> & a)
{
        vector<int>::iterator i,j;
        for (i=ResoGet.begin(),j=a.begin();i!=ResoGet.end();i++,j++)
        {
                *j+=*i;
        }
}

bool ReadData(vector <int> &ResOSRemain,vector <ProcData> &ProcTotal,
                          vector <ResoReqData> &ReqQueue)//读
{
        cout << "USE ... ?" <<endl;
        string tmpString,formatString="tTyY";
        cin >> tmpString;
        if (tmpString.find_first_of(formatString)!=string::npos)
        {
                cout << "USE ...al"<<endl;
                UseBank=true;
        }
        else
        {
                cout << "USE ....al"<<endl;
                UseBank=false;
        }
        cout << "Resource Number"<<endl;
        cin >>  ResourceNum;
        cout << "OS Resource Remain" << endl;
        for (int i=0;i<ResourceNum;i++)
        {
                int tmpInt;
                cin >> tmpInt;
                ResOSRemain.push_back(tmpInt);
        }
        cout << "Proc Number"<<endl;
        cin >> ProcNum;
        for (int i=0;i<ProcNum;i++)
        {
                ProcData tmpProcData;
                cout << "input ProcData"<<endl;
                cout << "name : ";
                cin >> tmpProcData.ProcName;
                cout << "running time : ";
                cin >> tmpProcData.lasttime;
                cout << "Resource Get : ";
                for (int j=0;j<ResourceNum;j++)
                {
                        int tmpInt;
                        cin >> tmpInt;
                        tmpProcData.ResoGet.push_back(tmpInt);
                }
                cout << "Resource Max : ";
                for (int j=0;j<ResourceNum;j++)
                {
                        int tmpInt;
                        cin >> tmpInt;
                        tmpProcData.ResoMax.push_back(tmpInt);
                }
                tmpProcData.runflag=false;
                ProcTotal.push_back(tmpProcData);
                cout << "Resource Request Data : ";
                int ResoReqNum;
                cin >> ResoReqNum;
                for (int j=0;j<ResoReqNum;j++)
                {
                        ResoReqData tmpResoReqData;
                        tmpResoReqData.ProcId=i;
                        cin >> tmpResoReqData.Res;
                        cin >> tmpResoReqData.ResNum;
                        cin >> tmpResoReqData.Time;
                        ReqQueue.push_back(tmpResoReqData);
                }
        }
        return true;
}

bool SafeState(vector <int> ResOSRemain,vector <ProcData> ProcTotal)//检测状态
{
        vector<ProcData>::iterator i;
        for (i=ProcTotal.begin();i!=ProcTotal.end();)
        {
                if (i->runflag)
                {
                        ProcTotal.erase(i);
                        i=ProcTotal.begin();
                        continue;
                }
                if (i->Bigger(ResOSRemain))
                {
                        for (int j=0;j<ResourceNum;j++)
                        {
                                ResOSRemain[j]+=i->ResoGet[j];
                        }
                        ProcTotal.erase(i);
                        if (!ProcTotal.empty())
                                i=ProcTotal.begin();
                        else
                        {
                                return true;
                        }
                }
                else
                        i++;
        }
        return false;
}
bool IsAllDone(vector <ProcData> &ProcTotal)
{
        for (vector<ProcData>::iterator i=ProcTotal.begin();i!=ProcTotal.end();i++)
        {
                if (!i->runflag)
                        return false;
        }
        return true;
}
void PrintResource(vector<int> &N)
{
        for (vector<int>::iterator i=N.begin();i!=N.end();i++)
        {
                cout << *i << ' ';
        }
}
bool ClearProc(vector <ProcData> &ProcTotal,vector <ProcData> & ResoRls)//处理进程将可以开始
                                                                                                                                                //运行的任务放入运行队列
{
        bool flag=false;
        for (vector <ProcData>::iterator ii=ProcTotal.begin();ii!=ProcTotal.end();)
        {
                if (ii->runflag)
                {
                        ii++;
                        continue;
                }
                int j;
                for (j=0;j<ResourceNum;j++)
                {
                        if (ii->ResoGet[j] < ii->ResoMax[j])
                                break;
                }
                if (j==ResourceNum)
                {
                        cout << "Process "<<ii->ProcName<<" Get All The Resource Need . Start Running ";
                        ii->lasttime=GTime+ii->lasttime;
                        cout << "Will End At "<<ii->lasttime<<endl;
                        ResoRls.push_back(*ii);
                        ii->runflag=true;
                        ii=ProcTotal.begin();
                        flag=true;
                }
                else
                        ii++;
        }
        return flag;
}
bool TimeRound(vector <int> &ResOSRemain,vector <ProcData> & ProcTotal,
                           vector <ResoReqData> & ReqQueue,vector <ProcData> & ResoRls)//模拟时间
{
        GTime=0;
        while (true)
        {
                if (IsAllDone(ProcTotal))
                {
                        cout << "Done" <<endl;
                        return true;
                }
                else
                {
                        if (ReqQueue.empty()&&ResoRls.empty())
                        {
                                cout << "Input Proc Data Might Be Wrong" <<endl<< "Can Not Run To The End"<<endl;
                                return false;
                        }
                }
                if (!ResoRls.empty())
                {
                        for (vector <ProcData>::iterator i=ResoRls.begin();i!=ResoRls.end();)
                        {
                                if (i->lasttime<=GTime)
                                {
                                        cout << "Process "<<i->ProcName<<" Run To The END"<<endl;
                                        cout << "Pay Back OSResource"<<endl;
                                        cout << "OSResource :" ;
                                        i->ModOSReso(ResOSRemain);
                                        PrintResource(ResOSRemain);
                                        cout << endl;
                                        ResoRls.erase(i);
                                        i=ResoRls.begin();
                                }
                                else
                                        i++;
                        }
                }
                if (!ReqQueue.empty())
                {
                        int CanotAns=0;
                        for (vector <ResoReqData>::iterator i=ReqQueue.begin();i!=ReqQueue.end();)
                        {
                                if (i->Time<=GTime)
                                {
                                        cout << ProcTotal[i->ProcId].ProcName <<" Ask For Resource "<< i->Res << " number="<<i->ResNum<<" at time "<<GTime<<endl;
                                        cout << "Try Answer It"<<endl;
                                        ResOSRemain[i->Res]-=i->ResNum;
                                        ProcTotal[i->ProcId].ResoGet[i->Res]+=i->ResNum;
                                        if (ResOSRemain[i->Res]<0)
                                        {
                                                cout << "Try Refused"<<endl;
                                                ResOSRemain[i->Res]+=i->ResNum;
                                                ProcTotal[i->ProcId].ResoGet[i->Res]-=i->ResNum;
                                                i++;
                                                CanotAns++;
                                                continue;
                                        }
                                        if (UseBank&&!SafeState(ResOSRemain,ProcTotal))
                                        {
                                                cout << "Try Refused"<<endl;
                                                ResOSRemain[i->Res]+=i->ResNum;
                                                ProcTotal[i->ProcId].ResoGet[i->Res]-=i->ResNum;
                                                i++;
                                        }
                                        else
                                        {
                                                cout << "Try Accepted"<<endl;
                                                cout << "OSResource = ";
                                                PrintResource(ResOSRemain);
                                                cout << endl;
                                                ReqQueue.erase(i);
                                                i=ReqQueue.begin();
                                                CanotAns=0;
                                        }
                                        if (ClearProc(ProcTotal,ResoRls))
                                        {
                                                i=ReqQueue.begin();
                                                CanotAns=0;
                                        }
                                }
                                else
                                        break;
                        }
                        if (!UseBank&&ResoRls.empty()&&CanotAns==ReqQueue.size())
                        {
                                cout << "Death Lock Happen" <<endl;
                                return false;
                        }

                }
                ++GTime;
        }
        return true;
}
int main(void) {
        vector <int> ResOSRemain;
        vector <ProcData> ProcTotal;
        vector <ResoReqData> ReqQueue;
        vector <ProcData> ResoRls;
        ReadData(ResOSRemain,ProcTotal,ReqQueue);
        sort(ReqQueue.begin(),ReqQueue.end());
        if (!SafeState(ResOSRemain,ProcTotal))
                cout << "Death Lock Can Not BE AVOID!!!"<<endl;
        else
                TimeRound(ResOSRemain,ProcTotal,ReqQueue,ResoRls);
        system ("pause");
        return 0;
}