基于可重定位分区分配算法的内存管理的设计与实现

组号成绩计算机操作系统课程设计报告题目基于可重定位分区分配算法的内存管理的设计与实现专业：计算机科学与技术班级：学号+姓名：指导教师：2016年12月23日一．设计目的掌握内存的连续分配方式的各种分配算法二．设计内容基于可重定位分区分配算法的内存管理的设计与实现。本系统模拟操作系统内存分配算法的实现，实现可重定位分区分配算法，采用PCB定义结构体来表示一个进程，定义了进程的名称和大小，进程内存起始地址和进程状态。内存分区表采用空闲分区表的形式来模拟实现。要求定义与算法相关的数据结构，如PCB、空闲分区；在使用可重定位分区分配算法时必须实现紧凑。三．设计原理可重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑功能。通常，该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这是便须对内存进行“紧凑”，将经过“紧凑”后所得到的大空闲分区分配给用户。如果所有的小空闲分区的容量总和仍小于用户的要求，则返回分配失败信息四．详细设计及编码1.模块分析（1）分配模块这里采用首次适应(FF)算法。设用户请求的分区大小为u.size,内存中空闲分区大小为m.size,规定的不再切割的剩余空间大小为size。空闲分区按地址递增的顺序排列；在分配内存时，从空闲分区表第一个表目开始顺序查找，如果m.size≥u.size且m.size-u.size≤size，说明多余部分太小，不再分割，将整个分区分配给请求者；如果m.size≥u.size且m.size-u.sizesize，就从该空闲分区中按请求的大小划分出一块内存空间分配给用户，剩余的部分仍留在空闲分区表中；如果m.sizeu.size则查找下一个空闲分区表项，直到找到一个足够大的空闲分区；如果没有找到一个足够大的内存空闲分区，但所有的小的空闲分区的容量总和大于用户的要求，就进行紧凑，将紧凑后得到的大的空闲分区按上述的方式分配给用户；但如果所有的小的空闲分区的容量总和仍不能满足用户需要，则分配失败。（2）内存回收模块进行内存回收操作时，先随机产生一个要回收的进程的进程号，把该进程从进程表中中删除，它所释放的空闲内存空间插入到空闲分区表；如果回收区与插入点的前一个空闲分区相邻，应将回收区与插入点的前一分区合并，修改前一个分区的大小；如果回收区与插入点的后一个空闲分区相邻，应将回收区与插入点的后一分区合并，回收区的首址作为新空闲分区的首址，大小为二者之和；如果回收区同时与插入点的前、后空闲分区相邻，应将三个分区合并，使用前一个分区的首址，取消后一个分区，大小为三者之和。（3）紧凑模块将内存中所有作业进行移动，使他们全都相邻接，把原来分散的多个空闲小分区拼接成一个大分区。2.流程图否否是是3.代码实现#includestdio.h#includestdlib.h#includetime.h#includewindows.h开始请求分配u.size分区找到u.size的空闲区？按动态分区方式分配空闲分区总和≥u.size?进行紧凑修改有关数据结构分配失败返回返回分区号及首址#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineSIZE15////////////////////////////进程表//////////////intppNo=1;//用于递增生成进程号intpLength=0;structPCB{intpNo;//进程号(名)intpSize;//进程大小intpOccupy;//实际占用的内存intpStartAddr;//进程起始地址intpState;//进程状态};structPCBpList[200];//////////////////空闲分区表部分///////////////typedefintStatus;typedefstructemptyNode{//空闲分区结构体intareaSize;//空闲分区大小intaStartAddr;//空闲分区始址structemptyNode*next;}emptyNode,*LinkList;intListDelete(structPCB*pList,inti);//AAA/删除下标为i的进程voidpSort(structPCB*pList);//AAA/内存中的进程按始址递增排序voidcompact(LinkList&L,structPCB*pList);//AAA/紧凑,内存中进程移动，修改进程数据结构；空闲分区合并，修改空闲分区表数据结构voidamalgamate(LinkList&L);//AAA/回收后进行合并空闲分区voidrecycle(LinkList&L,structPCB*pList);//AAA/回收，从进程表中删除进程，把释放出的空间插入到空闲分区链表中StatusInitList(LinkList&L);//1AAA/构造一个新的有头节点的空链表LStatusClearList(LinkList&L);//2AAA/将链表L重置为空表StatusListInsert(LinkList&L,LinkLists1);//AAA/*****根据始址进行插入voidDeleteElem(LinkList&L,intaStartAddr);//*****删除线性表中始址值为aStartAddr的结点voidPrintList(LinkListL);//AAA/*****输出各结点的值voidcreatP(structPCB*p);//AAA/初始化进程intsearch(LinkList&L,intpSize);//AAA/检索分区表,返回合适分区的首址intadd(LinkList&L);//AAA/返回空闲分区总和voidpListPrint(structPCB*pList);//AAA/输出内存中空间占用情况voiddistribute(LinkList&L,structPCB*process);intListDelete(structPCB*pList,inti)//AAA/删除下标为i的进程{for(;ipLength-1;i++){pList[i]=pList[i+1];}pLength--;}//ListDeletevoidpSort(structPCB*pList){//AAA/内存中的进程按始址递增排序inti,j;structPCBtemp;for(i=0;ipLength-1;i++){for(j=0;jpLength-i-1;j++){if(pList[j].pStartAddrpList[j+1].pStartAddr){temp=pList[j];pList[j]=pList[j+1];pList[j+1]=temp;}}}}//AAA/紧凑,内存中进程移动，修改进程数据结构；空闲分区合并，修改空闲分区表数据结构voidcompact(LinkList&L,structPCB*pList){printf(进行紧凑\n);//1、进程移动,修改进程数据结构inti;pList[0].pStartAddr=0;//第一个进程移到最上面for(i=0;ipLength-1;i++){pList[i+1].pStartAddr=pList[i].pStartAddr+pList[i].pOccupy;}//2、空闲分区合并，修改空闲分区表数据结构LinkListp=L-next,s;intsumEmpty=0;while(p!=NULL)//求空闲区总和{sumEmpty+=p-areaSize;p=p-next;}ClearList(L);//清空空闲分区表s=(LinkList)malloc(sizeof(emptyNode));s-aStartAddr=pList[pLength-1].pStartAddr+pList[pLength-1].pOccupy;s-areaSize=sumEmpty;ListInsert(L,s);printf(\n紧凑后的\n);pListPrint(pList);PrintList(L);}voidamalgamate(LinkList&L){//AAA/回收后进行合并空闲分区LinkListp=L-next,q=p-next;while(q!=NULL){if(p-aStartAddr+p-areaSize==q-aStartAddr){p-areaSize+=q-areaSize;DeleteElem(L,q-aStartAddr);//删除被合并的结点q=p-next;}else{p=q;q=q-next;}}}//AAA/回收，从进程表中删除进程，把释放出的空间插入到空闲分区链表中voidrecycle(LinkList&L,structPCB*pList){intindex,delPNo,delPSize,delPOccupy,delPStartAddr;LinkLists;srand(time(0));index=rand()%pLength;delPNo=pList[index].pNo;delPSize=pList[index].pSize;delPOccupy=pList[index].pOccupy;delPStartAddr=pList[index].pStartAddr;printf(________________________________________________________________________________);printf(回收内存进程P%d:始址：%dK占用：%dKB\n,delPNo,delPStartAddr,delPOccupy);printf(\n回收后\n);ListDelete(pList,index);//pListPrint(pList);s=(LinkList)malloc(sizeof(emptyNode));s-areaSize=delPOccupy;s-aStartAddr=delPStartAddr;ListInsert(L,s);amalgamate(L);pListPrint(pList);//输出内存中空间占用情况PrintList(L);}///////////////////////////////////////////StatusInitList(LinkList&L)//1AAA/构造一个新的有头节点的空链表L{LinkLists;L=(LinkList)malloc(sizeof(emptyNode));//生成新节点(头结点)if(!L)returnERROR;//申请内存失败s=(LinkList)malloc(sizeof(emptyNode));s-areaSize=900;s-aStartAddr=0;L-next=s;//头节点的指针域指向第一个结点s-next=NULL;returnOK;}//InitListStatusClearList(LinkList&L)//2AAA/将链表L重置为空表{LinkListp,r;p=L-next;r=p-next;while(p!=NULL){free(p);if(r==NULL){p=NULL;}else{p=r;r=p-next;}}L-next=NULL;returnOK;}//ClearList//AAA/*****根据始址进行插入StatusListInsert(LinkList&L,LinkLists1){LinkListr=L,p=L-next,s;//指针s=(LinkList)malloc(sizeof(emptyNode));s-areaSiz