基于可重定位分区分配算法的内存管理的设计与实现之欧阳治创编.docx
- 文档编号:9315663
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:18
- 大小:19.67KB
基于可重定位分区分配算法的内存管理的设计与实现之欧阳治创编.docx
《基于可重定位分区分配算法的内存管理的设计与实现之欧阳治创编.docx》由会员分享,可在线阅读,更多相关《基于可重定位分区分配算法的内存管理的设计与实现之欧阳治创编.docx(18页珍藏版)》请在冰点文库上搜索。
基于可重定位分区分配算法的内存管理的设计与实现之欧阳治创编
组号成果
时间2021.03.10
创作:
欧阳治
计算机操纵系统
课程设计陈述
题目基于可重定位分区分派算法的内存管理的设计与实现
专业:
计算机科学与技术
班级:
学号+姓名:
指导教师:
12月23日
一.设计目的
掌握内存的连续分派方法的各种分派算法
二.设计内容
基于可重定位分区分派算法的内存管理的设计与实现。
本系统模拟操纵系统内存分派算法的实现,实现可重定位分区分派算法,采取PCB界说结构体来暗示一个进程,界说了进程的名称和年夜小,进程内存起始地址和进程状态。
内存分区表采取空闲分区表的形式来模拟实现。
要求界说与算法相关的数据结构,如PCB、空闲分区;在使用可重定位分区分派算法时必须实现紧凑。
三.设计原理
可重定位分区分派算法与静态分区分派算法基本上相同,不同仅在于:
在这种分派算法中,增加了紧凑功能。
通常,该算法不克不及找到一个足够年夜的空闲分区以满足用户需求时,如果所有的小的空闲分区的容量总和年夜于用户的要求,这是便须对内存进行“紧凑”,将经过“紧凑”后所获得的年夜空闲分区分派给用户。
如果所有的小空闲分区的容量总和仍小于用户的要求,则前往分派失败信息
四.详细设计及编码
1.模块阐发
(1)分派模块
这里采取首次适应(FF)算法。
设用户请求的分区年夜小为u.size,内存中空闲分区年夜小为m.size,规定的不再切割的剩余空间年夜小为size。
空闲分区按地址递增的顺序排列;在分派内存时,从空闲分区表第一个表目开始顺序查找,如果m.size≥u.size且m.sizeu.size≤size,说明过剩部分太小,不再联系,将整个分区分派给请求者;如果m.size≥u.size且m.sizeu.size>size,就从该空闲分区中按请求的年夜小划分出一块内存空间分派给用户,剩余的部分仍留在空闲分区表中;如果m.size (2)内存回收模块 进行内存回收操纵时,先随机产生一个要回收的进程的进程号,把该进程从进程表中中删除,它所释放的空闲内存空间拔出到空闲分区表;如果回收区与拔出点的前一个空闲分区相邻,应将回收区与拔出点的前一分区合并,修改前一个分区的年夜小;如果回收区与拔出点的后一个空闲分区相邻,应将回收区与拔出点的后一分区合并,回收区的首址作为新空闲分区的首址,年夜小为两者之和;如果回收区同时与拔出点的前、后空闲分区相邻,应将三个分区合并,使用前一个分区的首址,取消后一个分区,年夜小为三者之和。 (3)紧凑模块 将内存中所有作业进行移动,使他们全都相邻接,把原来分离的多个空闲小分区拼接成一个年夜分区。 2.流程图 否 否 是是 3.代码实现 #include #include #include #include #defineTURE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineINFEASIBLE1 #defineOVERFLOW2 #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/构造一个新的有头节点的空链表L StatusClearList(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 pList[i]=pList[i+1]; } pLength; }//ListDelete voidpSort(structPCB*pList){//AAA/内存中的进程按始址递增排序 inti,j; structPCBtemp; for(i=0;i for(j=0;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 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[pLength1].pStartAddr+pList[pLength1].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; }//InitList StatusClearList(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 aStartAddr){ s>next=r>next; r>next=s; break; } r=p; p=p>next;//后移 } if(p==NULL){ r>next=s; s>next=NULL; } } returnOK; }//ListInsert2 voidDeleteElem(LinkList&L,intaStartAddr)//*****删除线性表中始址值为aStartAddr的结点 { LinkListp=L,q; while(p>next! =NULL) { q=p>next; if(q>aStartAddr==aStartAddr) { p>next=q>next; free(q); } else p=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; } return1;//没有足够年夜的 } 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 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>areaSizeprocess>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>areaSizeprocess>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>areaSizeprocess>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("待装入作业: %dSize=%dKB\n",p.pNo,p.pSize); //1、请求分派size //2、检索空闲分区表(首次适应FF) PrintList(L); stAddr=search(L,p.pSize);//获得足够年夜的分区的始址,没有则前往1 if(stAddr==1){//没有足够年夜的分区 if(add(L)>=p.pSize){//空闲区总和足够年夜 printf("没有足够年夜的空闲分区但空闲总和足够年夜\n"); //紧凑 compact(L,pList); //按静态分区方法分派 distribute(L,&p); //compact(L,pList);//紧凑 }else{//空闲区总和缺乏 printf("分派失败\n\n"); } }else{//有足够年夜的 distribute(L,&p); PrintList(L); //compact(L,pList);//紧凑 } }else{//回收 if(pLength>0){ recycle(L,pList); //compact(L,pList);//紧凑 }else{ printf("无可回收内存! "); } } system("pause"); }//while return0; } 4.结果及其相关阐发 图4.1 阐发: 作业1年夜小为20KB。 找到足够年夜空闲分区,进行划分分派。 图4.2 阐发: 作业2年夜小为70KB。 找到足够年夜空闲分区,进行划分分派。 图4.3 阐发: 先回收进程1年夜小为20KB,删除进程,并把释放的空闲分区拔出空闲分区表;再回收进程2年夜小为70KB,删除进程,并把释放的空闲分区拔出空闲分区表; 图4.4 阐发: 法度运行一段时间后的进程分派情况和空闲分区情况。 图4.5 阐发: 法度运行一段时间后的进程分派情况和空闲分区情况。 图4.6 阐发: 内存中已没有进程,所以不克不及进行回收。 图4.7 阐发: 没有足够年夜的空闲分区且所有分区之和也不满足要求,分派失败。 图4.8 图4.9 阐发: 进行紧凑,图4.8状态装换为图4.9状态。 五.课程设计小结 这次课程设计让我受益匪浅。 通过这次课程设计,我不单深刻理解
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 定位 分区 分配 算法 内存 管理 设计 实现 欧阳 创编