內存管理模擬程序
*******************************/
#include<iostream.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include <time.h>
#include <windows.h>
/*定義宏*/
#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;
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->stAddr<idleHead->stAddr)&&(Add!=idleHead->stAddr))
{
memUsed->next=idleHead;
idleHead=memUsed;
idleNum++;
}
else
{
if((memUsed->stAddr<idleHead->stAddr)&&(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;
}