银行家算法模拟程序.txt

银行家算法的具体实现

银行家
#include <iostream.h>
#define MAX 100
class YHJ
{
	int numOfPro;
	int numOfTyp;
	int Available[MAX];
	int Max[MAX][MAX];
	int Allocation[MAX][MAX];
	int Need[MAX][MAX];
	int Save[MAX];
public:
	void ProTypInsert()
	{
		cout<<"请输入系统进程个数:";
		cin>>numOfPro;
		cout<<"请输入资源类型的种类数:";
		cin>>numOfTyp;
	}
	
	void Set()
	{
		int i,j;
		for(i=0;i<numOfPro;i++)
		{
			cout<<"请输入第"<<i<<"号进程现在所分配的各种资源类型的实例数量:";
			for(j=0;j<numOfTyp;j++)
				cin>>Allocation[i][j];
			cout<<"其各资源最大需求为:";
			for(j=0;j<numOfTyp;j++)
				cin>>Max[i][j];
		}
		
		cout<<"请输入各资源现有实例数量:";
		for(i=0;i<numOfTyp;i++)
			cin>>Available[i];

		for(i=0;i<numOfPro;i++)
			for(j=0;j<numOfTyp;j++)
				Need[i][j]=Max[i][j]-Allocation[i][j];
	}

	int Compare(int a[],int b[])
	{
		int i;
		int temp=1;

		for(i=0;i<numOfTyp;i++)
			if(a[i]>b[i])
			{
				temp=0;
				break;
			}
			
		return temp;
	}

	void CheckSave()
	{
		int Work[MAX],Finish[MAX];
		int i,j,k;
		int worning=0;
		int Temp;

		for(i=0;i<numOfTyp;i++)
			Work[i]=Available[i];

		for(i=0;i<numOfPro;i++)
			Finish[i]=0;

		for(i=0;i<numOfPro;i++)
		{
			for(j=0;j<numOfPro;j++)                  //逐个检查进程
			{
				if(Finish[j]==0&&Compare(Need[j],Work)==1)
				{
					for(k=0;k<numOfTyp;k++)                  //为下个进程的检查准备
						Work[k]=Work[k]+Allocation[j][k];
					Finish[j]=1;
					Temp=j;
					break;
				}

			}

			Save[i]=Temp;
		}
		for(i=0;i<numOfPro;i++)
		{
			if(Finish[i]==0)
				cout<<"注意!当前系统处于非安全状态!"<<endl;
			break;
		}
		cout<<"当前系统处于安全状态!"<<endl;

		Disp();
	}

	void Disp()
	{
		int i;

		cout<<"安全序例为:";
		for(i=0;i<numOfPro;i++)
			cout<<Save[i];
		cout<<endl;
	}

	void Request()
	{
		int Pro,Typ[MAX];
		int i;

		cout<<"请输入几号进程发出资源请求:";
		cin>>Pro;
		cout<<"请输入其各资源请求量:";
		for(i=0;i<numOfTyp;i++)
			cin>>Typ[i];

		for(i=0;i<numOfTyp;i++)
			if(Typ[i]>Need[Pro][i])
			{
				cout<<"资源请求量大于其需求量了!"<<endl;
				break;
			}

		for(i=0;i<numOfTyp;i++)
			if(Typ[i]<=Available[i])
			{
				Available[i]=Available[i]-Typ[i];
				Allocation[Pro][i]=Allocation[Pro][i]+Typ[i];
				Need[Pro][i]=Need[Pro][i]-Typ[i];
			}
			else
			{
				cout<<"目前尚无这么多资源可供分配,请等待!"<<endl;
				break;
			}

		cout<<"分配所申请的资源后,";
		CheckSave();		
	}
};

void main()
{
	YHJ yhj;
	int i;
	do
	{
		cout<<"                            请选择欲要进行操作的序号       "<<endl;
		cout<<"                           1.初始化系统资源"<<endl;
		cout<<"                           2.检测系统资源分配安全性"<<endl;
		cout<<"                           3.进程对资源发出请求"<<endl;
		cout<<"                           0.退出程序"<<endl;
		cin>>i;

		switch(i)
		{
		case 1:
			yhj.ProTypInsert();
			yhj.Set();			
			break;
		case 2:
			yhj.CheckSave();
			break;
		case 3:
			yhj.Request();
			break;
		case 0:
			break;
		}
	}while(i!=0);
}
存储空间分配
#include <stdio.h>
#include <iostream.h>
#include <iomanip.h>
#define ERR_NOFREEAREA 1
#define ERR_NOADEQUACYAREA 2
#define ERR_ALLOCATED 4
#define ERR_NOJOBS 1
#define ERR_NOSUCHJOB 2
#define ERR_RECLAIMED 4

typedef struct tagUsedNode
{
	long address;
	long length;
	int flag; 
	struct tagUsedNode *next;
} USED_AREA , *USED_TABLE;
typedef struct tagFreeNode
{
	long address;
	long length;
	struct tagFreeNode *next;
} FREE_AREA , *FREE_TABLE;

USED_TABLE usedTable = NULL;
FREE_TABLE freeTable = NULL;

int Allocate( int jobname , long jobsize )
{
	//如果没有空闲区
	if( freeTable == NULL )
		return ERR_NOFREEAREA;
	FREE_TABLE p = freeTable;
	FREE_TABLE q = p;
	//找首次适应空闲区
	while( p != NULL && p->length < jobsize )
	{
		q = p;
		p = p->next;
	}
	//如果找不到有足够空间的分区
	if( p == NULL )
		return ERR_NOADEQUACYAREA;
	USED_TABLE x = new USED_AREA;
	x->address = p->address;
	x->length = jobsize;
	x->flag = jobname;
	x->next = NULL;
	//如果该分区大于作业需求，空间大小减去作业大小
	if( p->length > jobsize )
	{
		p->length -= jobsize;
		p->address += jobsize;
	}
	//如果该分区等于作业大小，删除该分区
	else
	{
		if( p == freeTable )
			freeTable = NULL;
		else
			q->next = p->next;
		delete p;
	}
	//作业加入“作业表”中
	USED_TABLE r = usedTable;
	USED_TABLE t = r;
	while( r != NULL && r->address < x->address )
	{
		t = r;
		r = r->next;
	}
	
	if( usedTable == NULL )
		usedTable = x;
	else
	{
		x->next = r;
		t->next = x;
	}
	return ERR_ALLOCATED;
}

//回收作业空间
int Reclaim( int jobname )
{
	if( usedTable == NULL )
		return ERR_NOJOBS;
	USED_TABLE p = usedTable;
	USED_TABLE q = p;
	while( p != NULL && p->flag != jobname )
	{
		q = p;
		p = p->next;
	}
	//如果没有该作业
	if( p == NULL )
		return ERR_NOSUCHJOB;
	//回收后的空间加入到空闲区
	FREE_TABLE r = freeTable;
	FREE_TABLE t = r;
	FREE_TABLE x;
	while( r != NULL && r->address < p->address )
	{
		t = r;
		r = r->next;
	}
	x = new FREE_AREA;
	x->address = p->address;
	x->length = p->length;
	x->next = NULL;
	if( r == freeTable )
	{
		x->next = r;
		freeTable = x;
		t = freeTable;
	}
	else
	{
		x->next = r;
		t->next = x;
	}
	//合并分区
	while( t->next != NULL && t->address + t->length == t->next->address )
	{
		t->length += t->next->length;
		r = t->next;
		t->next = t->next->next;
		delete r;
	}
	//删除该作业
	if( p == usedTable )
	{
		usedTable = usedTable->next;
	}
	else
		q->next = p->next;
	delete p;
	return ERR_RECLAIMED;
}
int Init()
{
	freeTable = new FREE_AREA;
	freeTable->address = 0;
	freeTable->length = 1024;
	freeTable->next = NULL;
	return 1;
}

void jobrequest()
{
	int jobname;
	int jobsize;
	printf("-----------------------\n");
	printf("作业名(只能为数字):");
	scanf("%d",&jobname);
	printf("作业长度: ");
	scanf("%d",&jobsize);
	if( Allocate( jobname , jobsize ) == ERR_ALLOCATED )
		printf("该作业已成功获得所需空间!\n");
	else
		printf("该作业没有获得所需空间!\n");
}

void jobreclaim()
{
	int jobname;
	printf("作业名: ");
	scanf("%d",&jobname);
	int result = Reclaim( jobname );
	if(  result == ERR_RECLAIMED )
		printf("该作业已成功回收");
	else if( result == ERR_NOSUCHJOB || result == ERR_NOJOBS )
		printf("系统没有作业或该作业不存在");
}

void freeTablePrint()
{
	cout<<setw(10)<<"address"<<setw(10)<<"length"<<setw(10)<<"state"<<endl<<endl;
	FREE_TABLE p = freeTable;
	USED_TABLE q = usedTable;
	int x , y;
	while( p || q )
	{
		if( p )
			x = p->address;
		else
			x = 0x7fffffff;
		if( q )
			y = q->address;
		else
			y = 0x7fffffff;
		if( x < y )
		{
			cout<<setw(10)<<p->address<<setw(10)<<p->length<<setw(10)<<"空闲"<<endl;
			p = p->next;
		}
		if( x > y )
		{
			cout<<setw(10)<<q->address<<setw(10)<<q->length<<setw(10)<<"已分配"<<setw(10)<<"ID="<<q->flag<<endl;
			q = q->next;
		}
	}
	cout<<"........................................"<<endl;
}
void main()
{
	Init();
	int choose;
	bool exitFlag = false;
	while( !exitFlag )
	{
		printf("                     1.分配内存             \n");
		printf("                     2.回收内存             \n");
		printf("                     3.显示内存情况         \n");
		printf("                     0.退出                 \n");
		printf("********************************************\n");
		printf("请选择:");
		scanf("%d",&choose);
		switch( choose )
		{
		case 0:
			exitFlag = true;
			break;
		case 1:
			jobrequest();
			break;
		case 2:
			jobreclaim();
			break;
		case 3:
			freeTablePrint();
			break;
		}
	}
}
时间片
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
enum state{
    ready,
    execute,
    block,
    finish
};

struct pcb{
    char name[4];
    int priority;
    int cputime;
    int needtime;
    int count;
    int round;
    enum state process;
    struct pcb * next;
};

void  display(struct pcb *p){
    printf("name    cputime    needtime    priority    state\n");
    while(p){
    printf(" %s          %d          %d           %d        ",p->name,p->cputime,p->needtime,p->priority);

        switch(p->process){
            case ready:printf("ready\n");break;
            case execute:printf("execute\n");break;
            case block:printf("block\n");break;
            case finish:printf("finish\n");break;
    	}
        p=p->next;
    }
}

int process_finish(struct pcb *q)
{
    int bl=1;
    while(bl&&q){
        bl=bl&&q->needtime==0;
        q=q->next;
    }
    return bl;
}


void display_menu()
{
    printf("1 时间片轮转算法\n");
    printf("2 退出\n");
}


struct pcb * get_process_round()
{
    struct  pcb *q;
    struct  pcb *t;
    struct  pcb *p;
    int n,i=0;
	printf("输入进程数(n<=10):\n");
	scanf("%d",&n);
    printf("输入进程名和运行时间：(中间用空格键隔开)\n");

    while (i<n){
        q=(struct pcb *)malloc(sizeof(struct pcb));
        scanf("%s",&q->name);
        scanf("%d",&q->needtime);
        q->cputime=0;
        q->round=0;
        q->count=0;
        q->process=ready;
        q->next=NULL;
        if (i==0){
        	p=q;
        	t=q;
    	}
        else{
            t->next=q;
        	t=q;
    	}
        i++;
    }
    return p;
}

struct pcb * get_next(struct pcb * k,struct pcb * head){
    struct pcb * t;
    t=k;
    do{
     t=t->next;
    }
    while (t && t->process==finish);
    if(t==NULL)
	{
        t=head;
        while (t->next!=k && t->process==finish)
		{
            t=t->next;
    	}
    }
    return t;
}
void set_state(struct pcb *p){
    while(p){
        if (p->needtime==0){
            p->process=finish;

    	}
        if (p->process==execute){
            p->process=ready;
    	}
        p=p->next;
    }
}
void display_round(struct pcb *p){
    printf("NAME  CPUTIME  NEEDTIME  COUNT  ROUND  STATE\n");
    while(p){
    printf(" %s        %d        %d       %d      %d     ", p->name,p->cputime,p->needtime,p->count,p->round);

        switch(p->process){
            case ready:printf("ready\n");break;
            case execute:printf("execute\n");break;
            case finish:printf("finish\n");break;
    	}
        p=p->next;
    }
}

void round_cal()
{
    int cpu,time,b;
    struct pcb * p;
    struct  pcb * r;
    cpu=0;
    p=get_process_round();
    r=p;	
	printf("输入时间片的长度：\n");
	scanf("%d",&time);
    while(!process_finish(p))
	{     
		b=r->needtime;
        r->needtime-=time;
        if(r->needtime<0) 
		{
            r->needtime=0;
			cpu+=b;
			r->cputime+=b;
		}
		else
		{
			cpu+=time;
			r->cputime+=time;
		}
        r->count++;
        r->round++;
        r->process=execute;

        r=get_next(r,p);
        printf("cpu   %d \n",cpu);
        display_round(p);
        set_state(p);
    }
    getch();
}

void main()
{
    int k;
    display_menu();
	printf("输入你要进行的操作：");
    scanf("%d",&k);
    switch(k){
            case 1:round_cal();break;
            case 2:break;

    }
}