根據(jù)可重定位分區(qū)分配算法的內(nèi)存管理組織的設(shè)計(jì)與實(shí)現(xiàn)

**組號(hào) 成績(jī)計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目 基于可重定位分區(qū)分配算法的內(nèi)存管理的設(shè)計(jì)與實(shí)現(xiàn)謝謝閱讀專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：學(xué)號(hào)+姓名：指導(dǎo)教師：2016年12月23日**一．設(shè)計(jì)目的掌握內(nèi)存的連續(xù)分配方式的各種分配算法二．設(shè)計(jì)內(nèi)容基于可重定位分區(qū)分配算法的內(nèi)存管理的設(shè)計(jì)與實(shí)現(xiàn)。本系統(tǒng)模擬操作系統(tǒng)內(nèi)存分感謝閱讀配算法的實(shí)現(xiàn)，實(shí)現(xiàn)可重定位分區(qū)分配算法，采用PCB定義結(jié)構(gòu)體來(lái)表示一個(gè)進(jìn)程，謝謝閱讀定義了進(jìn)程的名稱和大小，進(jìn)程內(nèi)存起始地址和進(jìn)程狀態(tài)。內(nèi)存分區(qū)表采用空閑分區(qū)表謝謝閱讀的形式來(lái)模擬實(shí)現(xiàn)。要求定義與算法相關(guān)的數(shù)據(jù)結(jié)構(gòu)，如PCB、空閑分區(qū)；在使用可謝謝閱讀重定位分區(qū)分配算法時(shí)必須實(shí)現(xiàn)緊湊。三．設(shè)計(jì)原理可重定位分區(qū)分配算法與動(dòng)態(tài)分區(qū)分配算法基本上相同，差別僅在于：在這種分配謝謝閱讀算法中，增加了緊湊功能。通常，該算法不能找到一個(gè)足夠大的空閑分區(qū)以滿足用戶需謝謝閱讀求時(shí)，如果所有的小的空閑分區(qū)的容量總和大于用戶的要求，這是便須對(duì)內(nèi)存進(jìn)行“緊謝謝閱讀湊”，將經(jīng)過(guò)“緊湊”后所得到的大空閑分區(qū)分配給用戶。如果所有的小空閑分區(qū)的容感謝閱讀量總和仍小于用戶的要求，則返回分配失敗信息四．詳細(xì)設(shè)計(jì)及編碼1.模塊分析（1）分配模塊**這里采用首次適應(yīng)(FF)算法。設(shè)用戶請(qǐng)求的分區(qū)大小為u.size,內(nèi)存中空閑分區(qū)大小為m.size,規(guī)定的不再切割的剩余空間大小為size?？臻e分區(qū)按地址遞增的順序排列；在分配內(nèi)存時(shí)，從空閑分區(qū)表第一個(gè)表目開(kāi)始順序查找，如果m.size≥u.size且m.size-u.size≤size，說(shuō)明多余部分太小，不再分割，將整個(gè)分區(qū)分配給請(qǐng)求者；如果m.size≥u.size且m.size-u.size>size，就從該空閑分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi)存空間分配給用戶，剩余的部分仍留在空閑分區(qū)表中；如果m.size<u.size則查找下一個(gè)空閑分區(qū)表項(xiàng)，直到找到一個(gè)足夠大的空閑分區(qū)；如果沒(méi)有找到一個(gè)足夠大的內(nèi)存空閑分區(qū)，但所有的小的空閑分區(qū)的容量總和大于用戶的要求，就進(jìn)行緊湊，將緊湊后得到的大的空閑分區(qū)按上述的方式分配給用戶；但如果所有的小的空閑分區(qū)的容量總和仍不能滿足用戶需要，則分配失敗。謝謝閱讀（2）內(nèi)存回收模塊進(jìn)行內(nèi)存回收操作時(shí)，先隨機(jī)產(chǎn)生一個(gè)要回收的進(jìn)程的進(jìn)程號(hào)，把該進(jìn)程從進(jìn)程表中中刪除，它所釋放的空閑內(nèi)存空間插入到空閑分區(qū)表；如果回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)相鄰，應(yīng)將回收區(qū)與插入點(diǎn)的前一分區(qū)合并，修改前一個(gè)分區(qū)的大?。蝗绻厥諈^(qū)與插入點(diǎn)的后一個(gè)空閑分區(qū)相鄰，應(yīng)將回收區(qū)與插入點(diǎn)的后一分區(qū)合并，回收區(qū)的首址作為新空閑分區(qū)的首址，大小為二者之和；如果回收區(qū)同時(shí)與插入點(diǎn)的前、后空閑分區(qū)相鄰，應(yīng)將三個(gè)分區(qū)合并，使用前一個(gè)分區(qū)的首址，取消后一個(gè)分區(qū)，大小為三者之和。謝謝閱讀（3）緊湊模塊將內(nèi)存中所有作業(yè)進(jìn)行移動(dòng)，使他們?nèi)枷噜徑?，把原?lái)分散的多個(gè)空閑小分區(qū)拼接成一個(gè)大分區(qū)。感謝閱讀2.流程圖開(kāi)始分配失敗返回 請(qǐng)求分配u.size分區(qū)否否空閑分區(qū)總和≥u.size?找到>u.size的空閑區(qū)？是是進(jìn)行緊湊 按動(dòng)態(tài)分區(qū)方式分配修改有關(guān)數(shù)據(jù)結(jié)構(gòu) 返回分區(qū)號(hào)及首址**3.代碼實(shí)現(xiàn)#include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineSIZE15////////////////////////////進(jìn)程表//////////////感謝閱讀intppNo=1;//用于遞增生成進(jìn)程號(hào)intpLength=0;structPCB{**intpNo;//進(jìn)程號(hào)(名)intpSize;//進(jìn)程大小intpOccupy;//實(shí)際占用的內(nèi)存intpStartAddr;//進(jìn)程起始地址intpState;//進(jìn)程狀態(tài)};structPCBpList[200];//////////////////空閑分區(qū)表部分///////////////謝謝閱讀typedefintStatus;typedefstructemptyNode{//空閑分區(qū)結(jié)構(gòu)體intareaSize;//空閑分區(qū)大小intaStartAddr;//空閑分區(qū)始址structemptyNode*next;}emptyNode,*LinkList;intListDelete(structPCB*pList,inti);//AAA/刪除下標(biāo)為i的進(jìn)程精品文檔放心下載voidpSort(structPCB*pList); //AAA/內(nèi)存中的進(jìn)程按始址遞增排序精品文檔放心下載voidcompact(LinkList&L,structPCB*pList);//AAA/緊湊,內(nèi)存中進(jìn)程移動(dòng)，修改進(jìn)精品文檔放心下載程數(shù)據(jù)結(jié)構(gòu)；空閑分區(qū)合并，修改空閑分區(qū)表數(shù)據(jù)結(jié)構(gòu)voidamalgamate(LinkList&L); //AAA/回收后進(jìn)行合并空閑分區(qū)感謝閱讀**voidrecycle(LinkList&L,structPCB*pList);//AAA/回收，從進(jìn)程表中刪除進(jìn)程，謝謝閱讀把釋放出的空間插入到空閑分區(qū)鏈表中StatusInitList(LinkList&L);//1AAA/構(gòu)造一個(gè)新的有頭節(jié)點(diǎn)的空鏈表LStatusClearList(LinkList&L);//2AAA/將鏈表L重置為空表StatusListInsert(LinkList&L,LinkLists1);//AAA/*****根據(jù)始址進(jìn)行插入voidDeleteElem(LinkList&L,intaStartAddr);//*****刪除線性表中始址值為aStartAddr的結(jié)點(diǎn)voidPrintList(LinkListL);//AAA/*****輸出各結(jié)點(diǎn)的值voidcreatP(structPCB*p);//AAA/初始化進(jìn)程intsearch(LinkList&L,intpSize);//AAA/檢索分區(qū)表,返回合適分區(qū)的首址intadd(LinkList&L);//AAA/返回空閑分區(qū)總和voidpListPrint(structPCB*pList);//AAA/輸出內(nèi)存中空間占用情況voiddistribute(LinkList&L,structPCB*process);精品文檔放心下載intListDelete(structPCB*pList,inti)//AAA/刪除下標(biāo)為i的進(jìn)程感謝閱讀{for(;i<pLength-1;i++){pList[i]=pList[i+1];}pLength--;}//ListDelete**voidpSort(structPCB*pList){//AAA/內(nèi)存中的進(jìn)程按始址遞增排序謝謝閱讀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/緊湊,內(nèi)存中進(jìn)程移動(dòng)，修改進(jìn)程數(shù)據(jù)結(jié)構(gòu)；空閑分區(qū)合并，修改空閑分區(qū)表數(shù)感謝閱讀據(jù)結(jié)構(gòu)voidcompact(LinkList&L,structPCB*pList){精品文檔放心下載printf("進(jìn)行緊湊\n");//1、進(jìn)程移動(dòng),修改進(jìn)程數(shù)據(jù)結(jié)構(gòu)inti;pList[0].pStartAddr=0;//第一個(gè)進(jìn)程移到最上面精品文檔放心下載for(i=0;i<pLength-1;i++){**pList[i+1].pStartAddr=pList[i].pStartAddr+pList[i].pOccupy;感謝閱讀}//2、空閑分區(qū)合并，修改空閑分區(qū)表數(shù)據(jù)結(jié)構(gòu)LinkListp=L->next,s;intsumEmpty=0;while(p!=NULL)//求空閑區(qū)總和{sumEmpty+=p->areaSize;p=p->next;}ClearList(L);//清空空閑分區(qū)表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/回收后進(jìn)行合并空閑分區(qū)謝謝閱讀LinkListp=L->next,q=p->next;精品文檔放心下載**while(q!=NULL){if(p->aStartAddr+p->areaSize==q->aStartAddr){謝謝閱讀p->areaSize+=q->areaSize;DeleteElem(L,q->aStartAddr);//刪除被合并的結(jié)點(diǎn)感謝閱讀q=p->next;}else{p=q;q=q->next;}}}//AAA/回收，從進(jìn)程表中刪除進(jìn)程，把釋放出的空間插入到空閑分區(qū)鏈表中謝謝閱讀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("回收內(nèi)存 進(jìn)程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);//輸出內(nèi)存中空間占用情況感謝閱讀PrintList(L);}///////////////////////////////////////////謝謝閱讀StatusInitList(LinkList&L)//1AAA/構(gòu)造一個(gè)新的有頭節(jié)點(diǎn)的空鏈表L感謝閱讀{LinkLists;**L=(LinkList)malloc(sizeof(emptyNode)); //生成新節(jié)點(diǎn)(頭結(jié)點(diǎn))感謝閱讀if(!L)returnERROR;//申請(qǐng)內(nèi)存失敗精品文檔放心下載s=(LinkList)malloc(sizeof(emptyNode));謝謝閱讀s->areaSize=900;s->aStartAddr=0;L->next=s; //頭節(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)感謝閱讀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/*****根據(jù)始址進(jìn)行插入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的結(jié)點(diǎn){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/*****輸出各結(jié)點(diǎn)的值感謝閱讀{printf("\n空閑分區(qū)情況: 始址\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/初始化進(jìn)程精品文檔放心下載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){//檢索分區(qū)表,返回合適分區(qū)的首址感謝閱讀LinkListp=L->next;while(p!=NULL){if(p->areaSize>=pSize){returnp->aStartAddr;}p=p->next;}return-1;//沒(méi)有足夠大的**}intadd(LinkList&L){//返回空閑分區(qū)總和精品文檔放心下載LinkListp=L->next;intsum=0;while(p!=NULL){sum+=p->areaSize;p=p->next;}returnsum;}voidpListPrint(structPCB*pList){//AAA/輸出內(nèi)存中空間占用情況感謝閱讀printf("\n進(jìn)程分配情況: 進(jì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){謝謝閱讀//不用分割全部分配（直接刪除此空閑分區(qū)結(jié)點(diǎn)）process->pStartAddr=p->aStartAddr;//進(jìn)程始址變化謝謝閱讀process->pState=1;//進(jìn)程狀態(tài)process->pOccupy=p->areaSize;//進(jìn)程實(shí)際占用內(nèi)存為改空閑分區(qū)的大小感謝閱讀pList[pLength++]=*process;//把進(jìn)程加入進(jìn)程列表謝謝閱讀printf(" 且 %dKB-%dKB=%dKB<%dKB 則 整區(qū)分配\n",謝謝閱讀p->areaSize,process->pSize,p->areaSize-process->pSize,SIZE);謝謝閱讀pSort(pList);printf("\n分配后>>>>\n");pListPrint(pList);//輸出內(nèi)存中空間占用情況感謝閱讀**DeleteElem(L,p->aStartAddr);感謝閱讀}else{//分割分配process->pStartAddr=p->aStartAddr;//進(jìn)程始址變化感謝閱讀process->pState=1;//進(jìn)程狀態(tài)process->pOccupy=process->pSize;//進(jìn)程實(shí)際占用內(nèi)存為該進(jìn)程的大小精品文檔放心下載pList[pLength++]=*process;//把進(jìn)程加入進(jìn)程列表精品文檔放心下載printf(" 且 %dKB-%dKB=%dKB>%dKB 則 劃分分配\n",精品文檔放心下載p->areaSize,process->pSize,p->areaSize-process->pSize,SIZE);感謝閱讀pSort(pList); //進(jìn)程排序printf("\n分配后>>>>\n");pListPrint(pList);//輸出內(nèi)存中空間占用情況感謝閱讀//compact(L,pList);p->aStartAddr+=process->pSize;//空閑分區(qū)始址變化感謝閱讀p->areaSize-=process->pOccupy;//空閑分區(qū)大小變化精品文檔放心下載}}intmain(){//0、創(chuàng)建一個(gè)進(jìn)程，參數(shù)隨機(jī)數(shù)方式產(chǎn)生structPCBp;inti,num,dele,k,stAddr,flag;精品文檔放心下載**LinkLists,L;printf("********************************可重定位分區(qū)分配精品文檔放心下載********************************");精品文檔放心下載if(!InitList(L))//初始化空閑分區(qū)表謝謝閱讀printf("創(chuàng)建表失敗\n");while(1){srand(time(0));flag=rand()%100+1;if(flag%2==0){creatP(&p);//初始化進(jìn)程printf("____________________________________________________________________________謝謝閱讀____");printf("待裝入作業(yè):%d Size=%dKB\n",p.pNo,p.pSize);感謝閱讀//1、請(qǐng)求分配size//2、檢索空閑分區(qū)表(首次適應(yīng)FF)PrintList(L);stAddr=search(L,p.pSize);//得到足夠大的分區(qū)的始址，沒(méi)有則返回-1謝謝閱讀if(stA