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

第1页共14页实验报告学院（系）名称：计算机与通信工程学院姓名张君卓学号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.当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。4.当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。5.运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。实验要求：1．详细描述实验设计思想、程序结构及各模块设计思路；2．详细描述程序所用数据结构及算法；3．明确给出测试用例和实验结果；4．为增加程序可读性，在程序中进行适当注释说明；5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等；6．实验报告撰写要求结构清晰、描述准确逻辑性强；7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。第2页共14页【实验过程记录（源程序、测试用例、测试结果及心得体会等）】#includeiostream#includemalloc.h#includestdlib.husingnamespacestd;typedefstructFreeLink{//定义自由链structFreeLink*prior;charname;intstart;intsize;boolflag;structFreeLink*next;}*ptr,*head;headtop;ptrp;voidprint(){//将内存分配情况打印到屏幕上p=top;cout************************内存分配情况表************************endl;cout区号\t\t起始位置\t区间长度\t区间状态\tendl;do{coutp-name\t\tp-start\t\tp-size\t\t;if(p-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);}voidasc(ptr&p){//最佳适应法的内存分配函数intmin;ptrop;FreeLink*fl=(FreeLink*)malloc(sizeof(FreeLink));cout请输入要分配内存的进程名endl;cinfl-name;cout请输入要分配内存的大小endl;cinfl-size;min=256;第3页共14页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(op-sizefl-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(fl);gotoflag1;}cout内存过小，分配失败！endl;gotoflag2;flag1:cout分配成功！endl;flag2:;}voiddec(ptr&p){//最坏适应法的内存分配函数intmax;ptrop;FreeLink*fl=(FreeLink*)malloc(sizeof(FreeLink));cout请输入要分配内存的进程名endl;cinfl-name;cout请输入要分配内存的大小endl;cinfl-size;max=fl-size;fl-flag=true;do{if(p-flag==false&&p-size=max){max=p-size;op=p;}p=p-next;第4页共14页}while(p!=NULL);if(op-sizefl-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;gotoflag3;}if(op-size==fl-size){op-flag=fl-flag;op-name=fl-name;free(fl);gotoflag3;}cout内存过小，分配失败！endl;gotoflag4;flag3:cout分配成功！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-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-prior-next=p-next;}else{p-next-prior=p-prior;p-prior-next=p-next;}p-prior-size=p-prior-size+p-size;第5页共14页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;}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请输入要分配内存的进程名endl;cinfl-name;cout请输入要分配内存的大小endl;cinfl-size;fl-flag=true;do{if(p-flag==false&&p-sizefl-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;第6页共14页}while(p!=NULL);cout内存过小，分配失败！endl;gotob;a:cout分配成功！endl;b:;}voidrecover(ptr&p){//内存回收函数charn='';cout请输入要回收的内存对应的进程名;cinn;do{if(p-flag==true&&p-name==n){splice(p);gotoc;}p=p-next;}while(p!=NULL);cout内存并未分配给对应进程，回收失败！endl;gotod;c:cout内存回收成功！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;cinpcb-name;cout请输入要分配内存的大小endl;gotof;e:cout超过内存最大容量请重新输入要分配内存的大小endl;f:cinpcb-size;if(pcb-size256)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;第7页共14页cout1.分配内存endl;cout2.回收内存endl;cout3.结束操作endl;cout请输入你的选择;cinchoice;}while(choice!='1'&&choice!='2'&&choice!='3');switch(choice){case'1':allocate(p);print();break;case'2':recover(p);print();break;case'3':clear();return0;break;}}}intbfa(){//最佳适应法charchoice='';print();ptrpcb=(FreeLink*)