根据可重定位分区分配算法的内存管理组织的设计与实现

**组号 成绩计算机操作系统课程设计报告题目 基于可重定位分区分配算法的内存管理的设计与实现谢谢阅读专业： 计算机科学与技术班级：学号+姓名：指导教师：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.size>size，就从该空闲分区中按请求的大小划分出一块内存空间分配给用户，剩余的部分仍留在空闲分区表中；如果m.size<u.size则查找下一个空闲分区表项，直到找到一个足够大的空闲分区；如果没有找到一个足够大的内存空闲分区，但所有的小的空闲分区的容量总和大于用户的要求，就进行紧凑，将紧凑后得到的大的空闲分区按上述的方式分配给用户；但如果所有的小的空闲分区的容量总和仍不能满足用户需要，则分配失败。谢谢阅读（2）内存回收模块进行内存回收操作时，先随机产生一个要回收的进程的进程号，把该进程从进程表中中删除，它所释放的空闲内存空间插入到空闲分区表；如果回收区与插入点的前一个空闲分区相邻，应将回收区与插入点的前一分区合并，修改前一个分区的大小；如果回收区与插入点的后一个空闲分区相邻，应将回收区与插入点的后一分区合并，回收区的首址作为新空闲分区的首址，大小为二者之和；如果回收区同时与插入点的前、后空闲分区相邻，应将三个分区合并，使用前一个分区的首址，取消后一个分区，大小为三者之和。谢谢阅读（3）紧凑模块将内存中所有作业进行移动，使他们全都相邻接，把原来分散的多个空闲小分区拼接成一个大分区。感谢阅读2.流程图开始分配失败返回 请求分配u.size分区否否空闲分区总和≥u.size?找到>u.size的空闲区？是是进行紧凑 按动态分区方式分配修改有关数据结构 返回分区号及首址**3.代码实现#include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#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(;i<pLength-1;i++){pList[i]=pList[i+1];}pLength--;}//ListDelete**voidpSort(structPCB*pList){//AAA/内存中的进程按始址递增排序谢谢阅读inti,j;structPCBtemp;for(i=0;i<pLength-1;i++){for(j=0;j<pLength-i-1;j++){感谢阅读if(pList[j].pStartAddr>pList[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;i<pLength-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 占用：%d感谢阅读KB\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->areaSize=s1->areaSize;s->aStartAddr=s1->aStartAddr;谢谢阅读if(p==NULL){L->next=s;s->next=NULL;}else{while(p!=NULL){if(s1->aStartAddr<p->aStartAddr){精品文档放心下载s->next=r->next;**r->next=s;break;}r=p;p=p->next;//后移}if(p==NULL){r->next=s;s->next=NULL;}}returnOK;}//ListInsert2voidDeleteElem(LinkList&L,intaStartAddr)//*****删除线性表中始址值为谢谢阅读aStartAddr的结点{LinkListp=L,q;while(p->next!=NULL){q=p->next;if(q->aStartAddr==aStartAddr)感谢阅读**{p->next=q->next;free(q);}elsep=p->next;}}//DeleteElem////////////////////////////////////////////////精品文档放心下载voidPrintList(LinkListL)//AAA/*****输出各结点的值感谢阅读{printf("\n空闲分区情况: 始址\t大小\n");谢谢阅读LinkListp=L->next;while(p!=NULL){printf(" %dK\t%dKB\n",p->aStartAddr,p->areaSize);感谢阅读p=p->next;}printf("\n");}//PrintList**voidcreatP(structPCB*p){//AAA/初始化进程精品文档放心下载intsize;srand(time(NULL));size=rand()%7+1;size*=10;p->pNo=ppNo++;p->pSize=size;p->pOccupy=0;p->pStartAddr=0;p->pState=0;}intsearch(LinkList&L,intpSize){//检索分区表,返回合适分区的首址感谢阅读LinkListp=L->next;while(p!=NULL){if(p->areaSize>=pSize){returnp->aStartAddr;}p=p->next;}return-1;//没有足够大的**}intadd(LinkList&L){//返回空闲分区总和精品文档放心下载LinkListp=L->next;intsum=0;while(p!=NULL){sum+=p->areaSize;p=p->next;}returnsum;}voidpListPrint(structPCB*pList){//AAA/输出内存中空间占用情况感谢阅读printf("\n进程分配情况: 进程\t始址\t占用\n");感谢阅读for(inti=0;i<pLength;i++){感谢阅读printf(" P%d\t%dK\t%dKB\n",精品文档放心下载pList[i].pNo,pList[i].pStartAddr,pList[i].pOccupy);谢谢阅读}}**voiddistribute(LinkList&L,structPCB*process){精品文档放心下载LinkListp=L->next;while(p!=NULL){if(p->areaSize>=process->pSize)谢谢阅读break;p=p->next;}printf("%dKB<%dKB",process->pSize,p->areaSize);谢谢阅读if(p->areaSize-process->pSize<=SIZE){谢谢阅读//不用分割全部分配（直接删除此空闲分区结点）process->pStartAddr=p->aStartAddr;//进程始址变化谢谢阅读process->pState=1;//进程状态process->pOccupy=p->areaSize;//进程实际占用内存为改空闲分区的大小感谢阅读pList[pLength++]=*process;//把进程加入进程列表谢谢阅读printf(" 且 %dKB-%dKB=%dKB<%dKB 则 整区分配\n",谢谢阅读p->areaSize,process->pSize,p->areaSize-process->pSize,SIZE);谢谢阅读pSort(pList);printf("\n分配后>>>>\n");pListPrint(pList);//输出内存中空间占用情况感谢阅读**DeleteElem(L,p->aStartAddr);感谢阅读}else{//分割分配process->pStartAddr=p->aStartAddr;//进程始址变化感谢阅读process->pState=1;//进程状态process->pOccupy=process->pSize;//进程实际占用内存为该进程的大小精品文档放心下载pList[pLength++]=*process;//把进程加入进程列表精品文档放心下载printf(" 且 %dKB-%dKB=%dKB>%dKB 则 划分分配\n",精品文档放心下载p->areaSize,process->pSize,p->areaSize-process->pSize,SIZE);感谢阅读pSort(pList); //进程排序printf("\n分配后>>>>\n");pListPrint(pList);//输出内存中空间占用情况感谢阅读//compact(L,pList);p->aStartAddr+=process->pSize;//空闲分区始址变化感谢阅读p->areaSize-=process->pOccupy;//空闲分区大小变化精品文档放心下载}}intmain(){//0、创建一个进程，参数随机数方式产生structPCBp;inti,num,dele,k,stAddr,flag;精品文档放心下载**LinkLists,L;printf("********************************可重定位分区分配精品文档放心下载********************************");精品文档放心下载if(!InitList(L))//初始化空闲分区表谢谢阅读printf("创建表失败\n");while(1){srand(time(0));flag=rand()%100+1;if(flag%2==0){creatP(&p);//初始化进程printf("____________________________________________________________________________谢谢阅读____");printf("待装入作业:%d Size=%dKB\n",p.pNo,p.pSize);感谢阅读//1、请求分配size//2、检索空闲分区表(首次适应FF)PrintList(L);stAddr=search(L,p.pSize);//得到足够大的分区的始址，没有则返回-1谢谢阅读if(stA