banker.cpp

银行家算法

#include "stdafx.h"
#define RE_ACC 5	//资源数
#define PROC_ACC 5	//进程数

int available[RE_ACC];	//资源可用向量
int claim[PROC_ACC][RE_ACC];	//最大需求矩阵
int allocation[PROC_ACC][RE_ACC];	//已分配资源矩阵

class request{
public:
	int resource[RE_ACC];

	request(){
		for(int i=0 ; i< RE_ACC;i++){
			request::resource[i] = rand()% 5;
		}
	}

	void printSelf(){
		printf("============================================\n");
		printf("resource");
		for(int i =0 ; i<RE_ACC ; i++){
			printf("\tR%d",i);
		}
		printf("\n");

		printf("request:");
		for(int i =0 ; i<RE_ACC ; i++){
			printf("\t%d",resource[i]);
		}
		printf("\n");

		printf("available:");
		for(int i =0 ; i<RE_ACC ; i++){
			printf("\t%d",available[i]);
		}
		printf("\n");
		printf("============================================\n\n");

		
	}
};

class PCB{
public:
    int identifier;
    PCB* next;
    int level;
    int CPUAccessTime;
    int ProcessNeedTime;
    char status ;

public :
    PCB(int ident,int level,PCB* nex,int ptime){
        PCB::identifier = ident;
        PCB::next = nex;
        PCB::level = level;
        PCB::CPUAccessTime = 0;
        PCB::ProcessNeedTime = ptime;
        PCB::status = 'w';   
    }
};

PCB* run ;
PCB* head;
PCB* tail;

PCB* proc1 ;
PCB* proc2;
PCB* proc3 ;
PCB* proc4 ;
PCB* proc5 ;


void process1(void){
    int i=9;
    i*i*i;
}

void process2(void){
    double i,j;
    i = 99.33;
    j = 38.4;
    i/j;
}

void process3(void){
    for(int i=0 ; i< 100; i++){
        int j=83;
    }
}

void process4(void){
    int i=10;
    while(i--){
        int j = 9/9*2;
    }
}

void process5(void){
    if(3<8){
        int i=9;
    }
}

void undoAllocate(request* req){
	int process = run->identifier - 1;
	for(int i=0 ; i< RE_ACC ; i++){
		allocation[process][i] -= req->resource[i];
		available[i] += req->resource[i];
		
	}
}

bool preAllocate(request* req){
	int process = run->identifier - 1;
	bool failed = false;
	for(int i=0 ; i< RE_ACC ; i++){
		if(req->resource[i] > claim[process][i]-allocation[process][i]){
			//printf("over request!");
			allocation[process][i] += req->resource[i];
			available[i] -= req->resource[i];
			failed = true;
		}
		else if(req->resource[i] > available[i]){
			printf("not enough resource%d for process%d\n",i, run->identifier );
			allocation[process][i] += req->resource[i];
			available[i] -= req->resource[i];
			failed = true;
		}
		else{
			allocation[process][i] += req->resource[i];
			available[i] -= req->resource[i];
		}
	}
	
	if( failed ){
		undoAllocate(req);
		return false;
	}else{
		return true;
	}
}

bool safe(){
	int free[RE_ACC];
	bool unfinish[PROC_ACC]  ;

	for(int i=0 ; i<RE_ACC; i++){
		free[i] = available[i];
	}
	
	for(PCB* temp=run;temp!= NULL;temp = temp->next){
		unfinish[temp->identifier -1] = "true";
	}

	for(int i=0; i<PROC_ACC ; i++){
		if(!unfinish[i]){
			for(int j=0; j<RE_ACC ; j++){
				available[i] += allocation[i][j];
				allocation[i][j] = 0;
			}
		}
	}

	bool foundFree = false;
	do{
		/*if(findFreeProcess())
			release();
		else 
			return false;*/
		foundFree = false;
		for(int i=0 ; i<PROC_ACC ; i++){
			if(!unfinish[i])
				continue;

			bool canEnd = true;
			for(int j=0 ; j<RE_ACC ; j++){
				if(claim[i][j]-allocation[i][j] > free[j]){
					canEnd = false;
					break;
				}
			}

			if(canEnd){
				for(int k=0 ; k< RE_ACC; k++){
					free[k] += allocation[i][k];
				}
				unfinish[i] = false;
				foundFree = true;
				break;
			}else{
				foundFree = false;
			}

		}

	}while(foundFree);

	for(int i=0 ; i< PROC_ACC ; i++){
		if(unfinish[i])
			
			return false;
	}

	return true;
}




void allocate(){
	request* req = new request(); 
	while(!preAllocate(req)){
		req = new request(); 
	}

	if(!safe()){
		undoAllocate(req);
	}else{
		req->printSelf();
	}
}

void runProcess(void){
    if(run == NULL)
        return;

	allocate();
    switch (run->identifier){
        case 1:
            process1();
            break;
        case 2:
            process2();
            break;
        case 3:
            process3();
            break;
        case 4:
            process4();
            break;
        case 5:
            process5();
    }
   
   
}

PCB* find(void){
    //所有进程都运行结束
    if(run == NULL)
        return NULL;

   
    run->ProcessNeedTime --;
    run->level -= 3;
   


    //当前进程运行结束，将等待队列首个进程设为运行状态
    if( run->ProcessNeedTime <= 0){
        run->status = 'f';
  run->next = NULL;
        run = head;
        if(run != NULL){
            head = run->next;
            run->status = 'r';
        }else{
            head = NULL;
        }
        return run;
    }

    //如果只有一个进程在运行
    if(run->next == NULL){
        return run;
    }
   
    //当前进程优先级大于等待队列首进程优先级
    if(run->level >= head->level){   
        run->status = 'r';
        return run;
    }
    //当前进程优先级小于等待队列首进程优先级，按照优先级插入等待队列
    else{
        PCB* temp = head;
       
        while(temp != tail){
            if(temp->next->level <= run->level){
                run->next = temp->next;
                temp->next = run;
                run->status = 'w';
                break;
            }else{
                temp = temp->next;
            }
        }
   
        if(temp == tail){
            tail->next = run;
            tail = run;
            run->status = 'w';
            run->next = NULL;
        }
       
        run = head;
        head = run->next;
        run->status = 'r';

        return run;

      
    }

    return NULL;
}

void init(void){
    proc1 = new PCB(1,1,NULL,5);
    proc2 = new PCB(2,proc1->level+1,proc1,2);
    proc3 = new PCB(3,proc2->level+2,proc2,3);
    proc4 = new PCB(4,proc3->level+1,proc3,1);
    proc5 = new PCB(5,proc4->level+1,proc4,4);
    head = proc4;
    run = proc5;
    tail = proc1;
    run->status = 'r';

	for(int i=0 ; i<PROC_ACC ; i++){
		for(int j=0 ; j<RE_ACC ; j++){
			claim[i][j] = rand()%20;
			allocation[i][j] = 0;
		}
	}

	for(int i=0 ; i<RE_ACC ; i++){
		available[i] = 20 + rand()%40+1;
	}
   
}

int _tmain(int argc, _TCHAR* argv[])
{
    init();  

    while(find() != NULL){
		runProcess();
    }

    getchar();
    return 0;
}