www.pudn.com > 032812036.rar > manege1.cpp

/******************************** 
内存管理模拟程序 
*******************************/ 
#include 
#include 
#include 
#include 
#include  
#include  
/*定义宏*/ 
#define TotalMemSize 1024  /*划分的物理块的大小，地址范围0~1023*/ 
#define MinSize   2     /*规定的不再分割的剩余分区的大小*/ 
#define getpch(type) (type*)malloc(sizeof(type))  
 
/*定义内存块*/ 
typedef struct memBlock 
{ 
	struct memBlock *next;/*指向下一个块*/ 
	int stAddr;           /*分区块的初始地址*/ 
	int memSize;           /*分区块的大小*/ 
	int status;             /*分区块的状态，0：空闲，1：以被分配*/ 
}MMB; 
 
/*定义全局变量*/ 
MMB *idleHead=NULL; /*空闲分区链表的头指针*/ 
MMB *usedHead=NULL; /*分配分区链表的头指针*/ 
MMB *usedRear=NULL; /*分配分区链表的链尾指针*/ 
MMB *np;             /*循环首次适应算法中指向即将被查询的空闲块*/ 
 
 
int idleNum=1;/*当前空闲分区的数目*/ 
int usedNum=0;/*当前已分配分区的数目*/ 
 
MMB *memIdle=NULL; /*指向将要插入分配分区链表的空闲分区*/ 
MMB *memUsed=NULL; /*指向将要插入空闲分区链表的已分配分区*/ 
 
int flag=1;/*标志分配是否成功，1：成功*/ 
  
/*函数声明*/ 
void textcolor (int color);/*输出着色*/ 
void InitMem();/*初始化函数*/ 
int GetUseSize(float miu,float sigma); /*获得请求尺寸*/ 
 
MMB *SelectUsedMem(int n);/*选择待释放的块*/ 
 
void AddToUsed();/*将申请到的空闲分区加到分配分区链表中*/ 
int RequestMemff(int usize); /*请求分配指定大小的内存,首次适应算法*/ 
int RequestMemnf(int usize); /*请求分配指定大小的内存,循环首次适应算法*/  
 
void AddToIdle();/*将被释放的分配分区加到空闲分区链表中(按地址大小）*/ 
void ReleaseMem(); /*释放指定的分配内存块*/ 
 
 
/*主函数*/ 
void main() 
{ 
	int sim_step; 
	float miu,sigma; /*使随机生成的请求尺寸符合正态分布的参数*/ 
	int i; 
	int a; 
	char c; 
	MMB *p; 
/*	double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0; 
	double aveStep=0,aveSize=0,aveRatio=0; 
	int step=0,usesize=0; */ 
	textcolor(11); 
	printf("\n\t\t内存管理模拟程序\n\n"); 
/*	InitMem();*/ 
	while(true) 
	{ 
		double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0; 
	    double aveStep=0,aveSize=0,aveRatio=0; 
	    int step=0,usesize=0; 
		InitMem(); 
		textcolor(12); 
		printf("\n\n首次适应算法：     0"); 
	    printf("\n循环首次适应算法： 1\n"); 
        textcolor(11); 
	    printf("\n请选择一种算法："); 
    	scanf("%d",&a); 
		textcolor(15); 
	    printf("\n输入一定数量的步数：(sim_step)"); 
	    scanf("%d",&sim_step); 
	    printf("\n 输入使随机生成的请求尺寸符合正态分布的参数：miu,sigma "); 
	    scanf("%f,%f",&miu,&sigma); 
	    for(i=1;i<=sim_step;i++) 
		{ 
			textcolor(10); 
			printf("\n\n#[%d]\n",i); 
			do{ 
				usesize=GetUseSize(miu,sigma); 
				while((usesize<0)||(usesize>TotalMemSize)) 
				{ 
					usesize=GetUseSize(miu,sigma); 
				} 
				textcolor(13); 
				printf("\n\n申请的内存尺寸为：%d",usesize); 
			    printf("\n此时可用的空闲分区有 %d 块情况如下：",idleNum); 
			    p=idleHead; 
				textcolor(15); 
				while(p!=NULL) 
				{ 
					printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize); 
				    p=p->next; 
				} 
				TotalSize+=usesize; 
				if(a==0) 
					step=RequestMemff(usesize); 
				else 
					step=RequestMemnf(usesize); 
				TotalStep+=step; 
				n++; 
			}while(flag==1); 
			p=usedHead; 
			while(p!=NULL) 
			{ 
				TotalUSize+=p->memSize; 
			    printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize); 
			    p=p->next; 
			} 
			textcolor(11); 
			if(TotalUSize!=0) 
			{ 
				Ratio=TotalUSize/TotalMemSize; 
                TotalUSize=0; 
			    printf("\n内存利用率NO.%d :%f%c",i,100*Ratio,'%'); 
			} 
			else 
			{ 
				Ratio=0; 
			    printf("\n内存利用率NO.%d :%c%c",i,'0','%'); 
			} 
			TotalRatio+=Ratio; 
		    ReleaseMem(); 
		} 
		if(n!=0) 
		{ 
			textcolor(10); 
			aveStep=TotalStep/n; 
		    aveSize=TotalSize/n; 
            aveRatio=TotalRatio/sim_step; 
		    printf("\n平均搜索步骤：%f",aveStep); 
		    printf("\n平均请求尺寸：%f",aveSize); 
		    printf("\n平均内存利用率：%f",aveRatio); 
		} 
	} 
} 
// 输出着色 ///////////////////////////////////////// 
void textcolor (int color) 
{ 
    SetConsoleTextAttribute (GetStdHandle (STD_OUTPUT_HANDLE), color ); 
} 
 
/****************************** 
函数名：InitMem() 
用途：把内存初始化为一整块空闲块 
****************************************/ 
void InitMem() 
{ 
	MMB *p; 
	p=getpch(MMB); 
	p->memSize=TotalMemSize; 
	p->stAddr=0; 
	p->status=0; 
	p->next=NULL; 
	idleHead=p; 
	np=idleHead; 
	usedHead=NULL; 
	usedRear=NULL; 
	idleNum=1; 
    usedNum=0; 
	flag=1; 
	memIdle=NULL;  
    memUsed=NULL; 
	 
	 
} 
 
/****************************** 
函数名：GetUseSize(float miu,float sigma) 
用途：获得请求尺寸； 
参数说明：float miu,float sigma ：正态分布的参数 
返回值:申请尺寸的大小； 
****************************************************/ 
int GetUseSize(float miu,float sigma) 
{ 
	float r1,r2; 
	float u,v,w; 
	float x,y; 
	do 
	{ 
		r1=rand()/32767.0; 
		r2=rand()/32767.0; 
 
		u=2*r1-1; 
		v=2*r2-1; 
		 
		w=u*u+v*v; 
	}while(w>1); 
	x=u*sqrt(((-log(w))/w)); 
	y=v*sqrt(((-log(w))/w)); 
	return miu+sigma*x; 
} 
 
/****************************** 
函数名：*SelectUsedMem(int n) 
用途：选择待释放的块(0~n-1) 
返回值：指向待释放的块的指针； 
****************************************************/ 
MMB *SelectUsedMem(int n) 
{ 
	MMB *p; 
	int i,j; 
	if(n>0) 
	{ 
	    i = rand()%n ; 
		textcolor(5); 
	    printf("\n\n当前已分配分区总数为：%d",n); 
	    printf("\n待释放块的序号为：%d\n",i ); 
		p=usedHead; 
		if(p!=NULL) 
		{ 
			for(j=i;j>0;j--) 
				p=p->next; 
			return(p); 
		} 
		else 
			return(NULL); 
	} 
	else 
	{ 
		printf("\n当前没有可释放的资源！\n"); 
	} 
} 
/****************************** 
函数名：AddToUsed() 
用途：将申请到的空闲分区加到分配分区链表中 
***************************************************************/ 
void AddToUsed() 
{ 
	MMB *p; 
	memIdle->status=1; 
	if(usedHead==NULL) 
	{ 
		usedHead=memIdle; 
		usedRear=usedHead; 
		 
	} 
	else 
	{ 
		usedRear->next=memIdle; 
		usedRear=memIdle; 
	} 
	usedNum++; 
	printf("\n当前分配分区共有%d块！",usedNum); 
	p=usedHead; 
	while(p!=NULL) 
	{ 
		printf("\n始址:%d     \t 尺寸：%d",p->stAddr,p->memSize); 
		p=p->next; 
	} 
} 
/****************************** 
函数名：RequestMemff(int usize) 
参数说明：usize：请求尺寸的大小； 
用途：请求分配指定大小的内存,首次适应算法 
返回值：搜索步骤 
***************************************************************/ 
int RequestMemff(int usize) 
{ 
	MMB *p1,*p2,*s; 
	int step; 
	int suc=0; 
	int size1,size2; 
	 
	if(idleHead==NULL) 
	{ 
		flag=0; 
		textcolor(12); 
		printf("\n分配失败！"); 
		return 0; 
	} 
	else 
	{ 
		if((idleHead->memSize)>usize) 
		{ 
			size1=(idleHead->memSize)-usize; 
			if(size1<=MinSize) 
			{ 
				memIdle=idleHead; 
				 
				idleHead=idleHead->next; 
				memIdle->next=NULL; 
				idleNum--; 
			} 
			else 
			{ 
				s=getpch(MMB); 
				s->memSize=usize; 
				s->stAddr=idleHead->stAddr; 
				s->status=1; 
				s->next=NULL; 
				memIdle=s; 
 
				idleHead->memSize=idleHead->memSize-usize; 
				idleHead->stAddr=idleHead->stAddr+usize;				 
			} 
			step=1; 
			flag=1; 
			textcolor(12); 
			printf("\n分配成功！"); 
			AddToUsed(); 
 
		} 
		else 
		{ 
			p1=idleHead; 
			step=1; 
			p2=p1->next; 
			while(p2!=NULL) 
			{ 
				if((p2->memSize)>usize) 
				{ 
					size2=(p2->memSize)-usize; 
					if(size2<=MinSize) 
					{ 
						p1->next=p2->next; 
						memIdle=p2; 
						memIdle->next=NULL; 
						idleNum--; 
						 
					} 
					else 
					{ 
						s=getpch(MMB); 
						s->memSize=usize; 
				        s->stAddr=p2->stAddr; 
				        s->status=1; 
						s->next=NULL; 
			        	memIdle=s; 
				        p2->memSize=p2->memSize-usize; 
				        p2->stAddr=p2->stAddr+usize; 
						 
					} 
					flag=1; 
					suc=1; 
					textcolor(12); 
					printf("\n分配成功！"); 
					AddToUsed(); 
					p2=NULL; 
				} 
				else 
				{ 
					p1=p1->next; 
					p2=p2->next; 
					step++; 
				} 
			} 
			if(suc==0) 
			{ 
				flag=0; 
				textcolor(12); 
				printf("\n分配失败！"); 
			} 
		} 
	} 
	return step; 
} 
 
/****************************** 
函数名：AddToIdle() 
用途：将被释放的分配分区加到空闲分区链表中(按地址递增顺序排列） 
***************************************************************/ 
void AddToIdle() 
{ 
	MMB *p1,*p2; 
    int insert=0; 
	if((idleHead==NULL)) 
	{ 
		idleHead=memUsed; 
		idleNum++; 
		np=idleHead; 
	} 
	else 
	{ 
		int Add=(memUsed->stAddr)+(memUsed->memSize); 
		if((memUsed->stAddrstAddr)&&(Add!=idleHead->stAddr)) 
		{ 
			memUsed->next=idleHead; 
			idleHead=memUsed; 
			idleNum++; 
		} 
		else 
		{ 
			 
			if((memUsed->stAddrstAddr)&&(Add==idleHead->stAddr)) 
			{ 
				idleHead->stAddr=memUsed->stAddr; 
				idleHead->memSize+=memUsed->memSize; 
				 
			} 
			else 
			{ 
				p1=idleHead; 
				p2=p1->next; 
				while(p2!=NULL) 
				{ 
					if(memUsed->stAddr>p2->stAddr) 
					{ 
						p1=p1->next; 
						p2=p2->next; 
					} 
					else 
					{ 
						int Add1=p1->stAddr+p1->memSize; 
						int Add2=p2->stAddr-memUsed->memSize; 
						if((Add1==memUsed->stAddr)&&(memUsed->stAddr!=Add2)) 
						{ 
							p1->memSize=p1->memSize+memUsed->memSize; 
						} 
						if((Add1!=memUsed->stAddr)&&(memUsed->stAddr==Add2)) 
						{ 
							p2->memSize=p2->memSize+memUsed->memSize; 
							p2->stAddr=memUsed->stAddr; 
						} 
						if((Add1!=memUsed->stAddr)&&(memUsed->stAddr!=Add2)) 
						{ 
							memUsed->next=p2; 
							p1->next=memUsed; 
							if(np->stAddr==p2->stAddr) 
								np=p1->next; 
							idleNum++; 
						} 
						if((Add1==memUsed->stAddr)&&(memUsed->stAddr==Add2)) 
						{ 
							p1->memSize=p1->memSize+memUsed->memSize+p2->memSize; 
							p1->next=p2->next; 
							if((np->stAddr)==(p2->stAddr)) 
								np=p1; 
							idleNum--; 
						} 
						p2=NULL; 
						insert=1; 
					} 
				} 
				if(insert==0) 
				{ 
					p1->next=memUsed; 
					idleNum++; 
				} 
			} 
		} 
	} 
} 
 
/****************************** 
函数名：ReleaseMem() 
用途：释放指定的分配内存块 
***************************************************************/ 
void ReleaseMem() 
{ 
	MMB *q1,*q2; 
	MMB *s; 
	if(usedNum==0) 
	{ 
		printf("\n当前没有分配分区!"); 
		return; 
	} 
	else 
	{ 
		s=SelectUsedMem(usedNum); 
		if(s!=NULL) 
		{ 
 
			if(s->stAddr==usedHead->stAddr) 
			{ 
				memUsed=usedHead; 
				usedHead=usedHead->next; 
				memUsed->next=NULL; 
				AddToIdle(); 
				usedNum--; 
			} 
			else 
			{ 
				q1=usedHead; 
			    q2=q1->next; 
				while(q2!=NULL) 
				{ 
					if(q2->stAddr!=s->stAddr) 
					{ 
						q1=q1->next; 
						q2=q2->next; 
					} 
					else 
					{ 
						q1->next=q2->next; 
						memUsed=q2; 
						memUsed->next=NULL; 
						if(q1->next==NULL) 
							usedRear=q1; 
						AddToIdle(); 
						usedNum--; 
						q2=NULL; 
					} 
				} 
			} 
		} 
	} 
} 
 
/****************************** 
函数名：RequestMemnf(int usize) 
参数说明：usize：请求尺寸的大小； 
用途：请求分配指定大小的内存,循环首次适应算法 
返回值：搜索步骤 
***************************************************************/ 
int RequestMemnf(int usize) 
{ 
	MMB *p2,*p,*s; 
	int step; 
	int iNum=0; 
	int suc=0; 
	int size1,size2,size3; 
	 
	if(idleHead==NULL) 
	{ 
		flag=0; 
		printf("\n分配失败！"); 
		return 0; 
	} 
	else 
	{ 
		iNum=idleNum; 
		while(iNum>0) 
		{ 
			iNum--; 
			if((np->memSize)>usize) 
			{ 
				/*指针指向的空闲块满足条件,且正好为头指针*/ 
				if(np->stAddr==idleHead->stAddr) 
				{ 
					size1=(idleHead->memSize)-usize; 
					if(size1<=MinSize) 
					{ 
						memIdle=idleHead; 
						idleHead=idleHead->next; 
						memIdle->next=NULL; 
						idleNum--; 
					} 
					else 
					{ 
						s=getpch(MMB); 
				        s->memSize=usize; 
				        s->stAddr=idleHead->stAddr; 
				        s->status=1; 
				        s->next=NULL; 
				        memIdle=s; 
						idleHead->memSize=idleHead->memSize-usize; 
				        idleHead->stAddr=idleHead->stAddr+usize; 
					} 
					if((idleHead==NULL)||(idleHead->next==NULL)) 
						np=idleHead; 
					else 
						np=idleHead->next; 
					 
				} 
				else/*指针指向的空闲块满足条件,不为头指针*/ 
				{ 
					size2=(np->memSize)-usize; 
					if(size2<=MinSize) /*从空闲链表中删除*/ 
					{ 
						p=idleHead; 
						while(p->next->stAddr!=np->stAddr) 
							p=p->next; 
						p->next=np->next; 
					    memIdle=np; 
						memIdle->next=NULL; 
					    np=p; 
				        idleNum--; 
					} 
					else 
					{ 
						s=getpch(MMB); 
				        s->memSize=usize; 
				        s->stAddr=np->stAddr; 
				        s->status=1; 
				        s->next=NULL; 
				        memIdle=s; 
 
				        np->memSize=np->memSize-usize; 
				        np->stAddr=np->stAddr+usize; 
					} 
					if(np->next==NULL) 
						np=idleHead; 
					else 
						np=np->next; 
				} 
				step=1; 
				flag=1; 
				suc=1; 
				textcolor(12); 
    		    printf("\n分配成功！"); 
			    AddToUsed(); 
			    iNum=0; 
			} 
			else /*当前指针指向的空闲区不满足条件*/ 
			{ 
			    step=1; 
			    p2=np->next; 
				if(p2==NULL) 
				{ 
					np=idleHead; 
					iNum--; 
				} 
				else 
				{ 
					if((p2->memSize)>usize) 
					{ 
						size3=(p2->memSize)-usize; 
						if(size3<=MinSize) 
						{ 
							np->next=p2->next; 
						    memIdle=p2; 
						    memIdle->next=NULL; 
						    idleNum--; 
						} 
						else 
						{ 
							s=getpch(MMB); 
						    s->memSize=usize; 
				            s->stAddr=p2->stAddr; 
				            s->status=1; 
						    s->next=NULL; 
			        	    memIdle=s; 
				            p2->memSize=p2->memSize-usize; 
				            p2->stAddr=p2->stAddr+usize; 
						} 
						flag=1; 
					    suc=1; 
					    printf("\n分配成功！"); 
				  	    AddToUsed(); 
						if(p2->next==NULL) 
							np=idleHead; 
					    else 
							np=p2->next; 
					    p2=NULL; 
					    iNum=0; 
					} 
					else 
					{ 
						np=np->next; 
						p2=p2->next; 
						iNum--; 
						step++; 
					} 
				} 
			} 
//			iNum--; 
		} 
		if(suc==0) 
		{ 
			flag=0; 
			textcolor(12); 
			printf("\n分配失败！"); 
		} 
	} 
	return step; 
}