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

计算机操作系统课程设计报告 基于可重定位分区分配算法得内存管理得设计与实现 班级: 指导教师: 掌握内存得连续分配方式得各种分配算法基于可重定位分区分配算法得内存管理得设计与实现。本系统模拟操作系统内存分配算法得实现,实现可重定位分区分配算法,采用PCB定义结构体来表示一个进程,定义了进程得名称与大小,进程内存起始地址与进程状态。内存分区表采用空闲分区表得形式来模拟实现。要求定义与算法相关得数据结构,如PCB、空闲分区;在使用可重定位分区分配算法时必须实现紧凑。可重定位分区分配算法与动态分区分配算法基本上相同,差别仅在于:在这种分配算法中,增加了紧凑功能。通常,该算法不能找到一个足够大得空闲分区以满足用户需求时,如果所有得小得空闲分区得容量总与大于用户得要求,这就是便须对内存进行“紧凑”,将经过“紧凑”后所得到得大空闲分区分配给用户。如果所有得小空闲分区得容量总与仍小于用户得要求,则返回分配失败信息(1)分配模块这里采用首次适应(FF)算法。设用户请求得分区大小为u、size,内存中空闲分区大小为m。size,规定得不再切割得剩余空间大小为size。空闲分区按地址递增得顺序排列;在izeize分配给用户,剩余得部分仍留在空闲分区表中;如果m、size〈u.size则查找下一个空闲分区表项,直到找到一个足够大得空闲分区;如果没有找到一个足够大得内存空闲分区,但所有得小得空闲分区得容量总与大于用户得要求,就进行紧凑,将紧凑后得到得大得空闲分区按上述得方式分配给用户;但如果所有得小得空闲分区得容量总与仍不能满足用户需要,则分配(2)内存回收模块进行内存回收操作时,先随机产生一个要回收得进程得进程号,把该进程从进程表中中删除,它所释放得空闲内存空间插入到空闲分区表;如果回收区与插入点得前一个空闲分区相邻,应将回收区与插入点得前一分区合并,修改前一个分区得大小;如果回收区与插入点得后一个空闲分区相邻,应将回收区与插入点得后一分区合并,回收区得首址作为新空闲分区得首址,大小为二者之与;如果回收区同时与插入点得前、后空闲分区相邻,应将三个分区合并,使用前一个分区得首址,取消后一个分区,大小为三者之与。(3)紧凑模块将内存中所有作业进行移动,使她们全都相邻接,把原来分散得多个空闲小分区拼接成程图否否etimeh#defineFALSE0#defineOK1#defineERROR0＃defineINFEASIBLE－1＃defineOVERFLOW-2////／///／／/／///／////／//////／进程表/／//／///////／/intppNo=1;//用于递增生成进程号intpLength＝0;structPCB{intpNo;/／进程号(名)intpStartAddr;//进程起始地址///////空闲分区表部分／/／//／/／／/／/／//体estructemptyNode＊next;}emptyNode,*LinkList;voidpSort(structPCB＊pList);/／AAA/内存中得进程按始址递增排序移动,修改进程数据结构;空闲分区合并,修改空闲分区表数据结构区voidrecycle(LinkList&L,structPCB*pList);／/AAA/回收,从进程表中删除进程,把释放出得空间插入到空闲分区链表中节点得空链表L插入性表中始址值为aStartAddr得结点voidPrintList(LinkListL);／/AAA/＊**＊＊输出各结点得值voidcreatP(structPCB*p);／／AAA/初始化进程合适分区得首址intadd(LinkList＆L);/／AAA／返回空闲分区总与AAA况voiddistributeLinkList&L,structPCB*process);intListDelete(structPCB＊pList,inti)／/AAA/删除下标为i得进程{ﻩfor(;i〈pLength—1;i+＋){}}／／ListDeletevoidpSort(structPCB*pList){//AAA/内存中得进程按始址递增排序ﻩinti,j;foriipLengthi+){ﻩfor(j=0;j<pLength-i-1;j＋+){ﻩﻩif(pList[j]。pStartAddr＞pList[j+1].pStartAddr){ﻩﻩﻩpList[j]＝pList[j+1];ﻩﻩﻩpList[j＋1]=temp;}ﻩﻩﻩ}ﻩﻩ}}/／AAA/紧凑,内存中进程移动,修改进程数据结构;空闲分区合并,修改空闲分区表数据结构//1、进程移动,修改进程数据结构ﻩinti;}构tywhile(p!=NULL)/／求空闲区总与{ﻩﻩﻩp=p->next;}ﻩstLﻩs－〉aStartAddr=pList[pLength-1].pStartAddr+pList[pLength-1]。}voidamalgamate(LinkList&L){//AAA/回收后进行合并空闲分区while(q！＝NULL){ﻩ}else{qﻩq=q－〉next;}}ﻩ}//AAA/回收,从进程表中删除进程,把释放出得空间插入到空闲分区链表中LinkLists;srand(time(0));delPSize=pList[index]、pSize;delPOccupy=pList[index]、pOccupy;delPStartAddr=pList[index]。pStartAddr;printf(”________________________________________________________________________________");printf("回收内存进程P％d:始址:%dK占用:％dKB\ListDelete(pList,index);//pListPrint(pList);s=(LinkList)malloc(sizeof(emptyNode));ListInsert(L,s);amalgamate(L);pListPrint(pList);/／输出内存中空间占用情况PrintList(L);}////／／//////////／///////／///////／/／////////StatusInitList(LinkList&L)//1AAA/构造一个新得有头节点得空链表L{LLinkListmallocsizeofemptyNode));//生成新节点(头结点)if(!L)returnERROR;//申请内存失败s=(LinkList)malloc(sizeof(emptyNode));s->areaSize＝900;s—〉aStartAddr=0;ﻩL->next=s;／／头节点得指针域指向第一个结点ﻩs－>next=NULL;L{ﻩwhile(p！=NULL){ﻩﻩﻩif(r==NULL){ﻩp=NULL;ﻩ}else{ﻩp＝r;}ﻩ}ﻩﻩL－>next=NULL;returnOK;}／/ClearList//AAA／＊＊*＊*根据始址进行插入{eﻩs—〉areaSize=s1-〉areaSize;ifpNULL{ﻩﻩs—〉next=NULL;ﻩﻩwhile(p！=NULL){ﻩﻩﻩs-＞next=r-〉next;ﻩr－＞next=s;ﻩﻩbreak;ﻩ}ﻩr＝p;ﻩp=p-＞next;/／后移}ﻩif(p==NULL){ﻩr—＞next=s;}}ﻩtAddr{while(p－〉next!＝NULL){ﻩﻩq=p->next;ﻩif(q－>aStartAddr＝=aStartAddr)ﻩ{}ﻩﻩﻩp＝p—>next;}////／///／/／///////////／／／/／///／//／///////／//////{printf("\n空闲分区情况:while(p！=NULL){printf(”Addr,p－＞areaSize);ﻩp＝p->next;}始址\t大小\n”);%dK\t%dKB\n",p—〉aStartvoidcreatP(structPCB＊p){//AAA/初始化进程srand(time(NULL));ﻩsize＊=10;ﻩp—〉pSize=size;p-〉pOccupy＝0;ﻩp—>pStartAddr=0;ﻩp－〉pState＝0;}ewhile(p!＝NULL){ﻩﻩﻩreturnp—>aStartAddr;}t}ﻩ}intadd(LinkList＆L){/／返回空闲分区总与while(p！=NULL){ﻩsum＋＝p-＞areaSize;}ﻩ}voidpListPrint(structPCB＊pList){//AAA/输出内存中空间占用情况printf(”\n进程分配情况:进程\t始址\t占用\n");ﻩprintf(”P％d\t％dK\t％dKB\n＂,y}}voiddistribute(LinkList＆L,structPCB*process){ﻩLinkListp=L-〉next;ﻩwhile(p!＝NULL){ﻩﻩﻩif(p-〉areaSize〉=process—＞pSize)break;}eif(p－>areaSize—process—>pSize〈=SIZE){ﻩ／/不用分割全部分配(直接删除此空闲分区结点)processpState1;//进程状态ﻩprocess-＞pOccupy=p－＞areaSize;／/进程实际占用内存为改空闲分区得大小ﻩprintf(”且%dKB－％dKB=%dKB<％dKB则整区分配\n",p-＞areaSize,process－＞pSize,p-〉areaSize－process－〉pSize,SIZE);ﻩﻩpSort(pList);pListPrint(pList);/／输出内存中空间占用情况eteElemLpaStartAddr}else{/／分割分配小pList[pLength＋+]＝*process;/／把进程加入进程列表ﻩprintf("且％dKB－％dKB=％dKB＞％dKB则划分分配\n”,Size,SIZE);//ﻩpact(L,pList);p—〉areaSize—=process—>pOccupy;//空闲分区大小变化}}//0、创建一个进程,参数随机数方式产生structPCBp;agLinkLists,L;f分区分配＊**＊****＊*＊＊＊＊*＊＊＊*＊*＊*＊**＊***＊＊");if(!InitList(L))／/初始化空闲分区表ﻩprintf(”创建表失败\n＂);while(1){ﻩﻩcreatP(&p);//初始化进程ﻩﻩprintf(”________________________________________________________________________________＂);printf(”待装入作业:%dSize=%dKB\n”,p.pNo,p、pSize);ﻩ//1、请求分配sizestAddr=search(L,p.pSize);//得到足够大得分区得始址,没有则返回—1ﻩﻩif(add(L)＞=p、pSize){//空闲区总与足够大ﻩﻩﻩﻩﻩ/／紧凑compact(L,pList);//ﻩ按动态分区方式分配／/pact(L,pL