内存分配,首次适应算法

./实实验报告实验名称：存分配与回收二、实验容：用首次适应算法实现存储空间的分配,回收作业所占用的存储空间。三、实验目的：一个好的计算机系统不仅要有足够的存储容量,较高的存取速度和稳定可靠的存储器,而且能够合理的分配和使用这些主存空间。当用户提出申请主存空间的要求时,存储管理能够按照一定的策略分析主存的使用情况,找出足够的空间分配给申请者；当作业运行完毕,存储管理要回收作业占用的主存空间。本实验实现在可变分区存储管理方式下,采用最先适应算法对主存空间进行分配和回收,以加深了解操作系统的存储管理功能。实验过程：基本思想空闲分区链以地址递增的次序连接。在分配存时,从链首开始顺序查找,直至找到一个大小能够满足要求的空闲分区为止；然后再按照作业大小,从该分区中划出一块存空间分配给请求者,余下的空闲分区仍然留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区,则此次存分配失败。b>主要数据结构typedefstructFreeLink{//空闲链 structFreeLink*prior; charname; intstart; intsize; boolflag; structFreeLink*next;}*ptr,*head;headtop;ptrp;c>存分配算法当有进程要求分配主存时,依据首次适应算法从链头开始,延链查找一个足以容纳该进程的空闲区。若这个分区比较大,则一分为二,一部分分配给进程,另一部分作为空闲区仍留在链中的当前位置,修改它的上一个空闲区的前向指针值为再加上分配给进程的分区大小,下一个空闲区的后向指针值为再加上分配给进程的分区大小,使链保持完整。若这个分区的大小正好等于进程的大小,该分区全部分配给进程,并将该空闲区从链中摘除〔即修改下一个空闲区的后向指针=该空闲区后向指针,上一个空闲区的前向指针=该空闲区的前向指针。再在已分配区表中找一个空表目,登记刚刚分配的存始址、长度和进程号。d>存的回收当进程运行完成,释放存时,通过输入进程号,来回收进程占用的分区。在回收时,释放区与空闲区相邻接的情况要考虑4种情况：⊙释放区下邻空闲区⊙释放区上邻空闲区⊙释放区与上下空闲区均相邻⊙释放区与上下空闲区均不相邻e>程序流程图※空闲链的首次适应算法分配流程图开始申请xkb内存开始申请xkb内存由链头找到第一个空闲区分区大小≥xkb？大于分区大小=分区大小-xkb,修改下一个空闲区的后向指针内容为〔后向指针+xkb;修改上一个空闲区的前向指针为〔前向指针+xkb将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址,修改上一个空闲区的前向指针为该空闲区的前向指针等于小于延链查找下一个空闲区到链尾了？作业等待返回是否登记已分配表返回分配给进程的内存首地址※空闲链的首次适应算法回收流程图开始开始输入完成进程的标号在分配区表中查找释放区p下邻分区空闲区前一个空闲区的后向指针指向p的后一个分区,p的后一个分区的前向指针指向p的前一个分区,且p的前一个分区大小更改为加上p的大小,释放p释放区p上邻分区空前一个分区的后向指针指向p的后一个空闲分区,p的后一个空闲分区的前向指针指向p的前一个分区,且p的后一个分区大小更改为加上p的大小释放区p上下均邻空闲区前一个空闲区的后向指针指向p的后一个空闲分区,p的后一个空闲分区的前向指针指向p的前一个空闲分区,且p的前一个空闲分区大小更改为加上p的大小再加上p的后一个空闲分区的大小,合并后的这个空闲区的后向指针指向p的下下个分区,如果p的下下个分区不为空,则其前向指针指向合并后的这个空闲区,释放p和p的下一个分区释放区p上下均不邻空闲区将p放在链首,并修改其状态位为空闲f截屏五、源代码#include<iostream.>#include<malloc.h>#include<stdlib.h>usingnamespacestd;typedefstructFreeLink{//定义空闲链 structFreeLink*prior; charname; intstart; intsize; boolflag; structFreeLink*next;}*ptr,*head;headtop;ptrp;voidprint<>{//将存分配情况打印到屏幕上 p=top; cout<<"************************存分配情况表************************"<<endl; cout<<"区号\t\t"<<"起始位置\t"<<"区间长度\t"<<"区间状态\t"<<endl;do{ cout<<p->name<<"\t\t"<<p->start<<"\t\t"<<p->size<<"\t\t"; if<p->flag==false>//flag为false,表明该分区空闲 { cout<<"空闲"<<endl; } else { cout<<"已占用"<<endl;} p=p->next; } while<p!=NULL>;}voidclear<>{//结束操作时清空"存"以备其他操作 do{ p=top; top=top->next; free<p>; } while<top!=NULL>; cout<<"存已清空！";}voidhebing<ptr&p>{//若被操作的存有相邻空闲区则将空闲区拼接合并 intx; if<p->prior->flag==false&&p->next->flag==false>x=1;//释放区与上下空闲区均相邻 if<<p->prior->flag==false&&p->next->flag==true>||<p->prior->flag==false&&p->next==NULL>>x=2;//释放区下邻空闲区 if<<p->prior->flag==true&&p->next->flag==false>||<p->prior==NULL&&p->next->flag==false>>x=3;//释放区上邻空闲区 if<<p->prior->flag==true&&p->next->flag==true>||<p->prior==NULL&&p->next->flag==true>||<p->prior->flag==true&&p->next==NULL>>x=4;//释放区与上下空闲区均不相邻switch<x>{ case1:p->next->prior=p->prior; p->prior->next=p->next; p->prior->size=p->prior->size+p->size+p->next->size; p->prior->next=p->next->next; if<p->next->next!=NULL> p->next->next->prior=p->next->prior; free<p->next>;//释放 free<p>; break;case2:if<p->next==NULL>//p为最后一个分区 { p->prior->next=p->next; } else{ p->next->prior=p->prior; p->prior->next=p->next; } p->prior->size=p->prior->size+p->size; free<p>; break; case3:if<p->prior==NULL>//p为第一个分区 { top=p->next; p->next->prior=NULL; p->next->start=p->start; p->next->size=p->next->size+p->size; } else{ p->next->prior=p->prior; p->prior->next=p->next; p->next->start=p->start; p->next->size=p->next->size+p->size; } free<p>; break; case4:p->name='*';//将释放区移至链首并标记为未被占用 p->flag=false; break; }}voidallocate<ptr&p>{//最先适应法的存分配函数 FreeLink*fl=<FreeLink*>malloc<sizeof<FreeLink>>; cout<<"请输入要分配存的进程号："; cin>>fl->name; cout<<"请输入要分配存的大小："; cin>>fl->size; fl->flag=true; do{ if<p->flag==false&&p->size>fl->size>{ fl->start=p->start; p->start=fl->start+fl->size; p->size=p->size-fl->size; fl->next=p; fl->prior=p->prior; p->prior->next=fl;p->prior=fl;gotoa; } if<p->flag==false&&p->size==fl->size>{p->flag=fl->flag; p->name=fl->name; free<fl>;gotoa; } p=p->next; }while<p!=NULL>; cout<<"存过小,分配失败！"<<endl; gotob;a:cout<<"分配成功！"<<endl;b:;//啥也不做}voidhuishou<ptr&p>{//存回收函数 charn=''; cout<<"请输入要回收的存对应的进程号："; cin>>n; do{ if<p->flag==true&&p->name==n> { hebing<p>;gotoc; } p=p->next; }while<p!=NULL>; cout<<"存未能分配给该进程,回收失败！"<<endl; gotod;c:cout<<"存回收成功！"<<endl;d:;}intfirstfit<>{//最先适应法 charchoice=''; print<>; ptrpcb=<FreeLink*>malloc<sizeof<FreeLink>>; pcb->next=top; pcb->prior=top->prior;top->prior=pcb; pcb->start=top->start; cout<<"请输入要为系统分配的存块号："; cin>>pcb->name; cout<<"请输入要分配存的大小："; gotof;e: cout<<"超过存最大容量,请重新输入要分配存的大小：";f: cin>>pcb->size; if<pcb->size>256> gotoe; top->size=top->size-pcb->size; top=pcb; top->flag=true; top->next->start+=top->size; print<>; while<true>{ do{ p=top->next; cout<<"请从下列选项中进行选择："<<endl; cout<<"1.分配存"<<endl; cout<<"2.回收存"<<endl; cout<<"3.结束操作"<<endl; cout<<"请输入你的选择："; cin>>choice; }while<choice!='1'&&choice!='2'&&choice!='3'>; switch<choice>{ case'1':allocate<p>;print<>;break; case'2':huishou<p>;print<>;break; case'3':clear<>;return0;break; } }}intmain<>{//主函数ptrfree=<FreeLink*>malloc<sizeof<FreeLink>>;top=free;top->name='*';top->start=0;top->size=256; top->flag=false;top->prior=NULL;top->next=NU