实验2：存储器的分配与回收

1、大津谖I学实验报告学院（系）名称：计算机与通信工程学院姓名张君卓学号20135612专业计算机科学与技术班级2013级1班实验项目实验二：存储器的分配与回收算法实现课程名称操作系统课程代码0668036实验时间2015年11月13日第5、6节2011年12月1日第3、4节2011年12月5日第7、8节实验地点软件实验室7-216软件实验室7-219软件实验室7-215批改意见成绩教师签字：实验内容:1. 模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。2. 采用最先适应法、最佳适应法、最坏适应法分配主存空间。3. 当一个新作业要求装入主存时，必须

2、查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。4. 当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。5. 运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。实验要求：1 .详细描述实验设计思想、程序结构及各模块设计思路；2 .详细描述程序所用数据结构及算法；3. 明确给出测试用例和实验结果；4. 为增加程序可读性，在程序中进行适当注释说明；5. 认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等；6. 实验报告撰写要求结构清晰、描述准确逻辑性

3、强；7. 实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。【实验过程记录(源程序、测试用例、测试结果及心得体会等)】#include<iostream>#include<malloc.h>#include<stdlib.h>usingnamespacestd;typedefstructFreeLink/定义自由链structFreeLink*prior;charname;intstart;intsize;boolflag;structFreeLink*next;*ptr,*head;headtop;ptrp;voidprint()/将内存分配情况打

4、印到屏幕上p=top;cout<<"*内存分配情况表*"<<endl;cout<<"区号tt"<<”起始位置t"<<”区间长度t"<<”区间状态t"<<endl;docout<<p->name<<"tt"<<p->start<<"tt"<<p->size<<"tt"if(p->flag=f

5、alse)(cout<<"空闲"<<endl;else(cout<<"已占用"<<endl;p=p->next;while(p!=NULL);voidclear()/结束操作时清空"内存”以备其他操作do(p=top;top=top->next;free(p);while(top!=NULL);voidasc(ptr&p)/最佳适应法的内存分配函数intmin;ptrop;FreeLink*fl=(FreeLink*)malloc(sizeof(FreeLink);cout&l

6、t;<"请输入要分配内存的进程名"<<endl;cin>>fl->name;cout<<"请输入要分配内存的大小"<<endl;cin>>fl->size;min=256;fl->flag=true;do(if(p->flag=false&&p->size<=min&&p->size>=fl->size)min=p->size;op=p;p=p->next;while(p!=NULL);if(

7、op->size>fl->size)fl->start=op->start;op->start=fl->start+fl->size;op->size=op->size-fl->size;fl->next=op;fl->prior=op->prior;op->prior->next=fl;op->prior=fl;gotoflag1;if(op->size=fl->size)op->flag=fl->flag;op->name=fl->name;free(f

8、l);gotoflagl;cout<<"内存过小，分配失败！"<<endl;gotoflag2;flagl:cout<<"分配成功！"<<endl;flag2:;voiddec(ptr&p)/最坏适应法的内存分配函数intmax;ptrop;FreeLink*fl=(FreeLink*)malloc(sizeof(FreeLink);cout<<"请输入要分配内存的进程名"<<endl;cin>>fl->name;cout<<

9、"请输入要分配内存的大小"<<endl;cin>>fl->size;max=fl->size;fl->flag=true;doif(p->flag=false&&p->size>=max)max=p->size;op=p;p=p->next;while(p!=NULL);if(op->size>fl->size)(fl->start=op->start;op->start=fl->start+fl->size;op->size=op-

10、>size-fl->size;fl->next=op;fl->prior=op->prior;op->prior->next=fl;op->prior=fl;gotoflag3;if(op->size=fl->size)(op->flag=fl->flag;op->name=fl->name;free(fl);gotoflag3;cout<<”内存过小，分配失败！"<<endl;gotoflag4;flag3:cout<<"分配成功！"<&

11、lt;endl;flag4:voidsplice(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->ne

12、xt->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-

13、>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->prior->next

14、=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)top=p->next;p->next->prior=NULL;p->next->start=p->start;p->next->size=p->next->size+p->size;

15、elsep->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)

16、;cout<<"请输入要分配内存的进程名"<<endl;cin>>fl->name;cout<<"请输入要分配内存的大小"<<endl;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->s

17、ize-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:cou

18、t<<"分配成功！"<<endl;b:;voidrecover(ptr&p)/内存回收函数charn=''cout<<"请输入要回收的内存对应的进程名"cin>>n;doif(p->flag=true&&p->name=n)splice(p);gotoc;p=p->next;while(p!=NULL);cout<<"内存并未分配给对应进程，回收失败！"<<endl;gotod;c:cout<<

19、"内存回收成功！"<<endl;d:;intffa()/最先适应法charchoice=''print();ptrpcb=(FreeLink*)malloc(sizeof(FreeLink);pcb->next=top;pcb->prior=top->prior;top->prior=pcb;pcb->start=top->start;cout<<"请输入要为系统分配的内存块名"<<endl;cin>>pcb->name;cout<<&q

20、uot;请输入要分配内存的大小"<<endl;gotof;e:cout<<"超过内存最大容量请重新输入要分配内存的大小"<<endl;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&

21、lt;<”请从下列选项中进行选择”<<endl;cout<<”1.分配内存"<<endl;cout<<”2.回收内存"<<endl;cout<<”3.结束操作"<<endl;cout<<"请输入你的选择"cin>>choice;while(choice!='T&&choice!='2'&&choice!='3');switch(choice)(case'

22、1':allocate(p);print();break;case'2':recover(p);print();break;case'3':clear();return0;break;intbfa()(/最佳适应法charchoice=''print();ptrpcb=(FreeLink*)malloc(sizeof(FreeLink);pcb->next=top;pcb->prior=top->prior;top->prior=pcb;pcb->start=top->start;cout<<

23、;”请输入要为系统分配的内存块名”<<endl;cin>>pcb->name;cout<<"请输入要分配内存的大小"<<endl;gotoh;g:cout<<"超过内存最大容量请重新输入要分配内存的大小"<<endl;h:cin>>pcb->size;if(pcb->size>256)gotog;top->size=top->size-pcb->size;top=pcb;top->flag=true;top->next

24、->start+=top->size;print();while(true)dop=top->next;cout<<"请从下列选项中进行选择"<<endl;cout<<"1.分配内存"<<endl;cout<<"2.回收内存"<<endl;cout<<"3.结束操作"<<endl;cout<<"请输入你的选择"cin>>choice;while(choice!

25、='1'&&choice!='2'&&choice!='3');switch(choice)(case'1':asc(p);print();break;case'2':recover(p);print();break;case'3':clear();return0;break;intwfa()/最坏适应法charchoice=''print();ptrpcb=(FreeLink*)malloc(sizeof(FreeLink);pcb->next

26、=top;pcb->prior=top->prior;top->prior=pcb;pcb->start=top->start;cout<<"请输入要为系统分配的内存块名"<<endl;cin>>pcb->name;cout<<"请输入要分配内存的大小"<<endl;gotoj;i:cout<<"超过内存最大容量请重新输入要分配内存的大小"<<endl;j:cin>>pcb->size;if(pcb

27、->size>256)gotoi;top->size=top->size-pcb->size;top=pcb;top->flag=true;top->next->start+=top->size;print();while(true)dop=top->next;cout<<"请从下列选项中进行选择"<<endl;cout<<"1.分配内存"<<endl;cout<<"2.回收内存"<<endl;cout&

28、lt;<"3.结束操作"<<endl;cout<<"请输入你的选择"cin>>choice;while(choice!='T&&choice!='2'&&choice!='3');switch(choice)(case'1':dec(p);print();break;case'2':recover(p);print();break;case'3':clear();return0;break;in

29、tmain()/主函数charchoice=''ptrfree=(FreeLink*)malloc(sizeof(FreeLink);top=free;top->name=''top->start=0;top->size=256;top->flag=false;top->prior=NULL;top->next=NULL;cout<<"*Memoryallocationandrecoveryalgorithm*"<<endl;cout<<"*存储器的分配与回收算

30、法*"<<endl;while(true)docout<<"请从下列选项中进行选择"<<endl;cout<<"2.最优适应算法"<<endl;cout<<"3.最坏适应算法"<<endl;cout<<"4.退出"<<endl;cout<<"请输入你的选择"cin>>choice;while(choice!=T&&choice!='

31、2'&&choice!='3'&&choice!='4');switch(choice)(case'1':ffa();break;case'2':bfa();break;case'3':wfa();break;case'4':return0;break;截图：最先适应法匚"UsepnAdminirfltorDe5ktopUnfitled1.e>re*M*MlemoYyallocationandrecoueFyaIgorit3MM膏K陡W>

32、t膏XUJ<陡舞尊XN背普盹耘首登存fj春器£勺”j'日3与也'耳注WX菁K看M：琵XK着J(ME矢尊矢JK葺JC跤M：尊石膏亲Uli请输入你的选择1KXW*直NX3CM：WXMX昔JCXW*其XXNX1<伪有西F专-牝主区号起始位置度偷嶷|02Sb请输入要为系统分配的内存块名请输入要分配内存的大小_、4TX>C!MM：*J<J<<MXM：iiJ<JKO(JtM：BiJ<M!M：XJt|R情-兄表*区号起始位置度向*度1e&6僵的进程名着输入要分配内存的大小分配成功区号1起始位置&62&IZ选存分

33、列.内内件你要下配蕾入入从分回25H*置><就1<*>1算瓣>(瓣1<hex.me*:区间状态空闲二二二F“一等用=间普闲区EP5二二二二二M二FH4a虞6典23配分存内5起始位置0&2646下列选项中进行选择3»入要分配内存的进程名状用用用间占占占闲区已已已空'!_5iFJ-rprr-;区已已已已空忧用用ffl用间占占占占闲请从下列选项中送仃选择分配内存瀚sig分*就的进程名请输入要分配内存的大小30分配成功！区号起始位置I*264871101情1兄表区而矣贝620202530155区间状态已占用已闩用已占用已§用蕾用区

34、间状态空闲分配成功！M：K*KKJiM：KKKM：M#M：K*KXMKK1W内分再111胃区号起始位置区冏长度*020a20323233区间状态已占用请输入要分配内存的大1'内律分'W,'青衍MMK*>(*搔JlXiOCXiiHWJOMiHW区而k度20236度1起0羊4JJ选-T号输区胃请情区25gwg位g始ZXI迸中法法法1BW选应应应/适适茶一出入丛誓窖器输青-LLL主肩区间状态1.取佳适应法请输入要分配内存的大小20M：KMEXM：KitM：KlfrMK*KKXMKM*M区号也台位置厦020i青丛下列选项中迸行选择lilLx请瑞入要分配内存的进程名请新入要分配内存的进程名务输入要分配内存的大小40怜配成功！算携HMEMjCBHHJCNXXJ<>