计算机操作系统内存分配实验报告

1一、实验目的熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、实验内容和要求主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。三、实验主要仪器设备和材料实验环境硬件环境：PC或兼容机软件环境：VC++6.0四、实验原理及设计分析某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。（作业1申请130KB、作业2申请60KB、作业3申请100KB、作业2释放60KB、作业4申请200KB、作业3释放100KB、作业1释放130KB、作业5申请140KB、作业6申请60KB、作业7申请50KB）当作业1进入内存后，分给作业1（130KB），随着作业1、2、3的进入，分别分配60KB、100KB，经过一段时间的运行后，作业2运行完毕，释放所占内存。此时，作业4进入系统，要求分配200KB内存。作业3、1运行完毕，释放所占内存。此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。为它们进行主存分配和回收。1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明2链的变化情况以及各作业的申请、释放情况显示打印出来。2.采用可变分区存储管理，分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。3、主存空间分配（1）首次适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。（2）最佳适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中（3）最坏适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。4、主存空间回收当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况：（1）释放区下邻空闲区（低地址邻接）（2）释放区上邻空闲区（高地址邻接）（3）释放区上下都与空闲区邻接（4）释放区上下邻都与空闲区不邻接五、程序流程图main函数里的流程图3分配空间里的流程图初始化first和end整理分区序号显示空闲分区链选择算法aa=1，首次适应算法a=2，最佳适应算法a=3，最坏适应算法选择操作ii=1，分配空间函数ai=0，退出程序i=2，回收空间函数结束4回收空间里的流程图p-data.length=request分配不成功分配空间函数a=1a=2a=3输入申请内存大小按顺序找空闲块初始化q，使它指向空闲块中长度小的一块输入申请内存大小初始化q，使它指向空闲块中长度大的一块p-data.lengthrequestp的状态为已分配剩下p-data.length-=request输入申请内存大小YYNN返回到整理分区序号5六、相关数据结构及关键函数说明本程序采用了一个structfree_table数据结构，里面包含分区序号（num）、起始地址（address）、分区长度（length）和分区状态（state）。还用了线性表的双性链表存储结构（structNode），里面包含前区指针（prior）和后继指针（next）。一开始定义一条（含有first和end）的链，用开始指针和尾指针开创空间链表。然后分别按三种算法进行分配和回收。p的状态改为空闲回收p，p的前一个为firstp的后一个是endp的后一个状态空与后面空闲块相连将p的状态改为空闲将p的状态改为空闲回收空间函数p的后一个是endYNYNYNp的前一个状态空p的前一个状态空p的后一个状态空p的后一个状态空p的后一个状态空p的后一个状态空YYYNNN与前面空闲块相连p的状态改为空闲与前面空闲块相连与后面空闲块相连YN返回到整理分区序号6在该程序中关键函数有，sort（）、allocation（）、recovery（）、和First_fit（）、Best_fit（）、Worst_fit（）；其中sort（）函数是用来整理分区序号的，如在删序号3时，她与前面序号2相连在一起了，然后序号2中的长度总满足申请的内存大小，就会在序号2中分配，然后序号在2的基础上加1，一直加，加到与原本序号3的下一个序号也就是4相等，这时sort（）就开始有明显的工作了；allocation（）是分配空间的，也是过渡到三个算法中的，当三个算法中满足或者不满足分配请求，都会又返回值给allocation（）；recovery（）是用来回收内存的，里面包含了四种情况相连结果，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接这四种情况的结果。七、源代码#includestdio.h#includestdlib.h#defineOK1//完成#defineERROR0//出错typedefintStatus;typedefstructfree_table//定义一个空闲区说明表结构{intnum;//分区序号longaddress;//起始地址longlength;//分区大小intstate;//分区状态}ElemType;typedefstructNode//线性表的双向链表存储结构{ElemTypedata;structNode*prior;//前趋指针structNode*next;//后继指针}Node,*LinkList;LinkListfirst;//头结点LinkListend;//尾结点intflag;//记录要删除的分区序号StatusInitblock()//开创带头结点的内存空间链表{first=(LinkList)malloc(sizeof(Node));end=(LinkList)malloc(sizeof(Node));first-prior=NULL;first-next=end;end-prior=first;end-next=NULL;7end-data.num=1;end-data.address=40;end-data.length=600;end-data.state=0;returnOK;}voidsort()//分区序号重新排序{Node*p=first-next,*q;q=p-next;for(;p!=NULL;p=p-next){for(q=p-next;q;q=q-next){if(p-data.num=q-data.num){q-data.num+=1;}}}}//显示主存分配情况voidshow(){intflag=0;//用来记录分区序号Node*p=first;p-data.num=0;p-data.address=0;p-data.length=40;p-data.state=1;sort();printf(\n\t\t》主存空间分配情况《\n);printf(**********************************************************\n\n);printf(分区序号\t起始地址\t分区大小\t分区状态\n\n);while(p){printf(%d\t\t%d\t\t%d,p-data.num,p-data.address,p-data.length);if(p-data.state==0)printf(\t\t空闲\n\n);elseprintf(\t\t已分配\n\n);p=p-next;}printf(**********************************************************\n\n);}8//首次适应算法StatusFirst_fit(intrequest){//为申请作业开辟新空间且初始化Node*p=first-next;LinkListtemp=(LinkList)malloc(sizeof(Node));temp-data.length=request;temp-data.state=1;p-data.num=1;while(p){if((p-data.state==0)&&(p-data.length==request)){//有大小恰好合适的空闲块p-data.state=1;returnOK;break;}elseif((p-data.state==0)&&(p-data.lengthrequest)){//有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;temp-data.num=p-data.num;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.length;p-data.length-=request;p-data.num+=1;returnOK;break;}p=p-next;}returnERROR;}//最佳适应算法StatusBest_fit(intrequest){intch;//记录最小剩余空间Node*p=first;Node*q=NULL;//记录最佳插入位置LinkListtemp=(LinkList)malloc(