内存的分配与回收实验报告(最先适应法)

#define n 64 //定义内存的大小

int a[n],count=0;//数组a用来保存内存使用状况1为已分配0为未分配，count用来记name数组中元素个数

char name[n];//已分配内存的名称（字符类型） typedef struct linknode{ char pid; int start; int length;

struct linknode *left,*right; }de_node; //进程节点结构体定义

//head1表示未分配内存队列头指针，head2便是已分配进程队列头指针 de_node *head1,*head2=NULL;

struct linknode* creat()//创建一个进程节点 {

int len,flag1=1;//用于表示进程是否可以创建 char id;

struct linknode* p;

p = (de_node *)malloc(sizeof(de_node));//试图在系统内存中开辟空间创建一个进程 if (p==NULL) //p为空，说明系统没有可用内存用于创建此模拟进程 { printf(\"系统没有足够的内存可供使用！\\n\");//输出 }

printf(\"请输入进程id(字符类型)和长度:\");//为进程输入id和分配的长度 scanf(\"%c %d\ fflush(stdin);//清除输入缓存

if((id>='a'&&id<='z'||id>='A'&&id<='Z')&&(len>0)){

for(int i=0;iprintf(\"此名称进程已存在！！\");

flag1=0;//标志位为0，表示下面对p指向内容不做修改 free(p);

return(NULL);//返回空指针

return NULL; }

if(len==0) {//如果输入要分配的进程长度为0，释放p,返回空指针 printf(\"输入长度为0！\\n\"); free(p); return(NULL);

}

if(flag1){//标志位1，可以对p指向内容进行修改 p->pid=id; //id

p->start=0; //初始开始内存位置，在以后会修改 p->length=len;//长度 p->left=NULL;//左指针 p->right=NULL;//右指针

name[count++]=id;//将id存入数组，count自加 return(p); }

else {printf(\"输入进程格式有误\\n\"); free(p); } }

//分配内存空间

void distribute(de_node *p) { de_node *q=head1,*temp; int flag=0; do{//do_while循法

//判断当前指向的内存空间的长度是否满足p所申请的长度,大于就分配 if(q->length>=p->length)

{

return (NULL); }//返回创建的进程的地址

p->start=q->start;//把进程的内存开始地址指向内存的可用开始地址处 q->start+=p->length;//可用地址起始改变 q->length-=p->length;//可用内存长度修改

for(int i=p->start;istart+p->length;i++)//将已分配的内存空间全部置1 a[i]=1;

flag=1;//表示内存可分配

//队列不止一个进程，第一个满足条件，并且刚好分配完，修改指针指向 if(q->length==0&&q->right!=q) head1=q->right; q->left->right=q->right; q->right->left=q->left;

free(q);//把这个已分配完的空间指针释放

} }

{ if(q==head1)//如果第一个满足，修改头指针指向

if(flag==1)//已做完处理直接跳出循环 break;

if(flag==0)//当前指向的内存不满足，指向下一个，继续判断是否满足 q=q->right;

}while(q!=head1);//搜索一遍可用内存序列 if(flag==0){//没有可用的内存 printf(\"没有满足的内存！\\n\");

count--;//由于创建时加1，但在分配内存时失败，把1又减掉 free(p);//把这个未分配到内存的进程释放 }

if(flag==1){//表示上面已分配好内存，并已修改内存链表，下面修改已分配内存的进程队列 temp=head2;//把已分配内存的进程队列赋值给临时指针

if(temp==NULL)//如果还还没有存在的任何的进程，说明当前是第一个 { head2=p;//让头指针指向第一个进程

p->left=p;//双向队列第一个左右指针都指向自己 p->right=p;//双向队列第一个左右指针都指向自己 }

else if(temp!=NULL){//已存在队列，把当前直接链到第一个，与上面的区别是指针指向 head2=p;//让头指针指向p指向的进程

p->left=temp->left;//p进程左边为原来第一个的左边 p->right=temp;//p进程右边指向第一个 temp->left->right=p;//原来第一个的左边为p temp->left=p;//原来第一个的左边的进程为p } } }

//对进程的回收 void reclaim() { char id; int flag=0;

de_node *q=head2,*p=head1; if(head2==NULL)//表示当前没有进程 { printf(\"已没有进程！\\n\"); }

else {//已分配内存队列如果不为空

printf(\"输入要回收的进程id：\");//输入要回收进程的id scanf(\"%c\ fflush(stdin);

for(int i=0;i{//判断当前的进程是否满足要求

for(int j=i;jname[j]=name[j+1];//向前覆盖 name[j+1]=NULL;//置空 count--;//减一 }

//判断是否总共只有一个进程且是够刚好也满足条件

if(q->pid==id&&q->right==q&&head2==q) { head2=NULL;//把已分配队列直接置空 flag=1;//表示找到满足条件的进程 }

if(flag==0){//上面的都没找到 do{

if(q->pid==id){//如果找到

if(q==head2) head2=q->right;

q->left->right=q->right;//修改指针指向 q->right->left=q->left; flag=1;

break;

}

else q=q->right;

}while(q!=head2);

}//如果找到或是遍历一遍结束

if(flag==0) printf(\"没有此进程号！！！\\n\");//没有找到满足的进程 if(flag==1){//表示找到了

for(int i=q->start;istart+q->length;i++)//释放占有的内存

a[i]=0;

//接下来修改可用内存的队列，

while(q->start>p->start&&p->right!=head1){

//从第一个开始找到回收回来的内存开始地址大的那个队列

p=p->right;

}

if(p==head1)//表示比第一个的开始还小，那么就要修改头地址

head1=q;//其他情况不用修改头地址，只需找到应该的位置，把此进程插进去 q->left=p->left;//修改指针的指向 q->right=p; p->left->right=q; p->left=q;

if(q->start+q->length==p->start)//可以与后面合并的情况

{ q->length+=p->length;//修改指针的指向

p->right->left=q; q->right=p->right; free(p);

}

if(q->left->start+q->left->length==q->start)//可以与前面合并的情况

{ q->left->length+=q->length;//修改指针的指向

q->left->right=q->right; q->right->left=q->left; free(q);

}

}

} }

//打印输出

void print()

{ de_node *q=head2,*p=head1;

if(count==0)

printf(\"没有进程占有内存。\\n\"); else

{ printf(\"输出进程id号：\\n\"); for(int i=0;iprintf(\"\\n\");

printf(\"输出内存当前使用情况：\\n\"); for(int j=0;jprintf(\"内存初始名称为 i,回收后可能会变，可以查看回收来自那个进程\\n\");

do //输出可用内存序列

{ if(p!=NULL)

{ printf(\"进程id:%c 开始地址:%d 长度%d\\n\

p=p->right; } //主函数 void main() { int x;

}

}while(p!=head1); printf(\"\\n\");

printf(\"已分配进程队列：\\n\"); do //已分配进程队列 {

if(q!=NULL)

{

printf(\"进程id:%c 开始地址:%d 长度%d\\n\ q=q->right;

}

}while(q!=head2);

de_node *point,*p1; //创建内存的初始状态

point=(struct linknode*)malloc(sizeof(struct linknode)); head1=point; point->pid='i'; point->start=0; point->length=n; head1->left=point; head1->right=point; print(); while(1) {

printf(\" ------MENU-------\\n\"); printf(\"1----distribute(分配)\\n\"); printf(\"2----reclaim(回收)\\n\"); printf(\"3----view (浏览)\\n\"); printf(\"4----exit(退出)\\n\");

printf(\"请输入上面的选项(1--4):\\n\"); scanf(\"%d\ fflush(stdin); switch(x)

{ case 1:

{ p1=creat();

if(p1==NULL) printf(\"创建进程失败。\\n\");

else distribute(p1); x=0; break;

}

case 2:

{ reclaim(); x=0; }

break;

case 3:

{ print(); x=0;

break;}

case 4: } } 测试用例 运行时屏幕显示:

{ printf(\"Thanks;Bye-bye!\");exit(0); x=0;

break;}

default: }

{ printf(\"输入有误，请重新输入。\\n\");}

实验结果： 1.成功实现了内存的分配与回收，实现了最先适应算法。 2.更好的掌握了双向链表与指针的应用。 3.代码具有比较好的健壮性，能处理非法输入。 4.回收时可以将可用的相邻内存区合并起来，减少碎片。