根據可重定位分區(qū)分配算法的內存管理組織的設計與實現

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