基于可重定位分區(qū)分配算法的內(nèi)存管理的設(shè)計實現(xiàn)分析

1、-. z.組號成績計算機操作系統(tǒng)課程設(shè)計報告題目基于可重定位分區(qū)分配算法的存管理的設(shè)計與實現(xiàn)專業(yè)：計算機科學(xué)與技術(shù)班級：*+：指導(dǎo)教師：2016年12月 23 日設(shè)計目的掌握存的連續(xù)分配方式的各種分配算法設(shè)計容基于可重定位分區(qū)分配算法的存管理的設(shè)計與實現(xiàn)。本系統(tǒng)模擬操作系統(tǒng)存分配算法的實現(xiàn)，實現(xiàn)可重定位分區(qū)分配算法，采用PCB定義構(gòu)造體來表示一個進程，定義了進程的名稱和大小，進程存起始地址和進程狀態(tài)。存分區(qū)表采用空閑分區(qū)表的形式來模擬實現(xiàn)。要求定義與算法相關(guān)的數(shù)據(jù)構(gòu)造，如PCB、空閑分區(qū)；在使用可重定位分區(qū)分配算法時必須實現(xiàn)緊湊。設(shè)計原理可重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法根本上一樣，差異僅

2、在于：在這種分配算法中，增加了緊湊功能。通常，該算法不能找到一個足夠大的空閑分區(qū)以滿足用戶需求時，如果所有的小的空閑分區(qū)的容量總和大于用戶的要求，這是便須對存進展緊湊，將經(jīng)過緊湊后所得到的大空閑分區(qū)分配給用戶。如果所有的小空閑分區(qū)的容量總和仍小于用戶的要求，則返回分配失敗信息詳細(xì)設(shè)計及編碼模塊分析分配模塊這里采用首次適應(yīng)(FF)算法。設(shè)用戶請求的分區(qū)大小為u.size,存中空閑分區(qū)大小為m.size,規(guī)定的不再切割的剩余空間大小為size。空閑分區(qū)按地址遞增的順序排列；在分配存時，從空閑分區(qū)表第一個表目開場順序查找，如果m.sizeu.size且size，說明多余局部太小，不再分割，將整個分區(qū)

3、分配給請求者；如果m.sizeu.size且m.size-u.sizesize，就從該空閑分區(qū)中按請求的大小劃分出一塊存空間分配給用戶，剩余的局部仍留在空閑分區(qū)表中；如果m.sizeu.size的空閑區(qū)？按動態(tài)分區(qū)方式分配空閑分區(qū)總和u.size進展緊湊修改有關(guān)數(shù)據(jù)構(gòu)造分配失敗返回返回分區(qū)號及首址否否是是代碼實現(xiàn)#include#include#include#include#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define SIZE 15

4、 /進程表/int ppNo=1; /用于遞增生成進程號int pLength=0;struct PCBint pNo; /進程號(名)int pSize; / 進程大小int pOccupy; / 實際占用的存int pStartAddr; / 進程起始地址int pState; /進程狀態(tài);struct PCB pList200;/空閑分區(qū)表局部/typedef int Status;typedef struct emptyNode /空閑分區(qū)構(gòu)造體int areaSize; /空閑分區(qū)大小int aStartAddr; /空閑分區(qū)始址struct emptyNode *ne*t;empt

5、yNode,*LinkList;int ListDelete(struct PCB *pList,int i);/AAA/刪除下標(biāo)為i的進程void pSort(struct PCB *pList); /AAA/存中的進程按始址遞增排序void pact(LinkList &L,struct PCB *pList);/AAA/緊湊 ,存中進程移動，修改良程數(shù)據(jù)構(gòu)造；空閑分區(qū)合并，修改空閑分區(qū)表數(shù)據(jù)構(gòu)造void amalgamate(LinkList &L); /AAA/回收后進展合并空閑分區(qū)void recycle(LinkList &L,struct PCB *pList); /AAA/回收

6、，從進程表中刪除進程，把釋放出的空間插入到空閑分區(qū)鏈表中Status InitList(LinkList &L); /1AAA/構(gòu)造一個新的有頭節(jié)點的空鏈表LStatus ClearList(LinkList &L); /2AAA/將鏈表L重置為空表Status ListInsert(LinkList &L,LinkList s1); /AAA/*根據(jù)始址進展插入void DeleteElem(LinkList &L,int aStartAddr);/*刪除線性表中始址值為aStartAddr的結(jié)點void PrintList(LinkList L); /AAA/*輸出各結(jié)點的值void cr

7、eatP(struct PCB *p); /AAA/初始化進程int search(LinkList &L,int pSize); /AAA/檢索分區(qū)表 ,返回適宜分區(qū)的首址int add(LinkList &L); /AAA/返回空閑分區(qū)總和void pListPrint(struct PCB *pList); /AAA/輸出存中空間占用情況void distribute(LinkList &L,struct PCB *process);int ListDelete(struct PCB *pList,int i)/AAA/刪除下標(biāo)為i的進程for(;ipLength-1;i+)pListi

8、=pListi+1;pLength-;/ListDeletevoid pSort(struct PCB *pList) /AAA/存中的進程按始址遞增排序int i,j;struct PCB temp;for(i=0;ipLength-1;i+)for(j=0;jpListj+1.pStartAddr)temp=pListj;pListj=pListj+1;pListj+1=temp;/AAA/緊湊 ,存中進程移動，修改良程數(shù)據(jù)構(gòu)造；空閑分區(qū)合并，修改空閑分區(qū)表數(shù)據(jù)構(gòu)造void pact(LinkList &L,struct PCB *pList) printf(進展緊湊n); /1、進程移動

9、,修改良程數(shù)據(jù)構(gòu)造int i;pList0.pStartAddr=0; /第一個進程移到最上面for(i=0;ine*t,s;int sumEmpty=0;while(p!=NULL)/求空閑區(qū)總和sumEmpty+=p-areaSize;p=p-ne*t;ClearList(L); /清空空閑分區(qū)表s=(LinkList)malloc(sizeof(emptyNode);s-aStartAddr=pListpLength-1.pStartAddr+pListpLength-1.pOccupy; s-areaSize=sumEmpty;ListInsert(L,s); printf(n緊湊后的

10、n); pListPrint(pList);PrintList(L);void amalgamate(LinkList &L)/AAA/回收后進展合并空閑分區(qū)LinkList p=L-ne*t,q=p-ne*t;while(q!=NULL)if(p-aStartAddr+p-areaSize=q-aStartAddr)p-areaSize+=q-areaSize;DeleteElem(L,q-aStartAddr);/刪除被合并的結(jié)點q=p-ne*t; elsep=q;q=q-ne*t;/AAA/回收，從進程表中刪除進程，把釋放出的空間插入到空閑分區(qū)鏈表中void recycle(LinkLi

11、st &L,struct PCB *pList) int inde*,delPNo,delPSize,delPOccupy,delPStartAddr; LinkList s; srand(time(0); inde*=rand()%pLength; delPNo=pListinde*.pNo; delPSize=pListinde*.pSize; delPOccupy=pListinde*.pOccupy; delPStartAddr=pListinde*.pStartAddr; printf(_); printf(回收存進程 P%d: 始址：%d K 占用：%d KBn,delPNo,de

12、lPStartAddr,delPOccupy); printf(n回收后n); ListDelete(pList,inde*); /pListPrint(pList); s=(LinkList)malloc(sizeof(emptyNode);s-areaSize=delPOccupy; s-aStartAddr=delPStartAddr; ListInsert(L,s); amalgamate(L); pListPrint(pList);/輸出存中空間占用情況 PrintList(L);/Status InitList(LinkList &L) /1AAA/構(gòu)造一個新的有頭節(jié)點的空鏈表LL

13、inkList s;L=(LinkList)malloc(sizeof(emptyNode); /生成新節(jié)點(頭結(jié)點)if(!L) return ERROR; /申請存失敗s=(LinkList)malloc(sizeof(emptyNode);s-areaSize=900;s-aStartAddr=0;L-ne*t=s; /頭節(jié)點的指針域指向第一個結(jié)點s-ne*t=NULL;return OK;/InitListStatus ClearList(LinkList &L) /2AAA/將鏈表L重置為空表LinkList p,r;p=L-ne*t; r=p-ne*t;while(p!=NULL)

14、free(p);if(r=NULL)p=NULL;elsep=r; r=p-ne*t;L-ne*t=NULL;return OK;/ClearList /AAA/*根據(jù)始址進展插入Status ListInsert(LinkList &L,LinkList s1)LinkList r=L,p=L-ne*t,s;/指針s=(LinkList)malloc(sizeof(emptyNode);s-areaSize=s1-areaSize;s-aStartAddr=s1-aStartAddr;if(p=NULL)L-ne*t=s;s-ne*t=NULL;elsewhile(p!=NULL) if(s

15、1-aStartAddr aStartAddr) s-ne*t=r-ne*t; r-ne*t=s; break; r=p; p=p-ne*t; /后移 if(p=NULL) r-ne*t=s; s-ne*t=NULL; return OK;/ListInsert2void DeleteElem(LinkList &L,int aStartAddr)/*刪除線性表中始址值為aStartAddr的結(jié)點LinkList p=L,q;while(p-ne*t!=NULL)q=p-ne*t;if(q-aStartAddr=aStartAddr)p-ne*t=q-ne*t;free(q);elsep=p-

16、ne*t;/DeleteElem/void PrintList(LinkList L)/AAA/*輸出各結(jié)點的值 printf(n空閑分區(qū)情況: 始址t 大小n);LinkList p=L-ne*t;while(p!=NULL) printf( %d Kt%d KBn,p-aStartAddr,p-areaSize);p=p-ne*t;printf(n);/PrintListvoid creatP(struct PCB *p) /AAA/初始化進程int size;srand(time(NULL); size=rand()%7+1; size*=10;p-pNo=ppNo+;p-pSize=s

17、ize;p-pOccupy=0;p-pStartAddr=0;p-pState=0;int search(LinkList &L,int pSize) /檢索分區(qū)表 ,返回適宜分區(qū)的首址LinkList p=L-ne*t;while(p!=NULL)if(p-areaSize=pSize)return p-aStartAddr;p=p-ne*t;return -1;/沒有足夠大的int add(LinkList &L) /返回空閑分區(qū)總和LinkList p=L-ne*t;int sum=0; while(p!=NULL)sum+=p-areaSize;p=p-ne*t;return sum;

18、void pListPrint(struct PCB *pList)/AAA/輸出存中空間占用情況printf(n進程分配情況: 進程t 始址t占用n);for(int i=0;ine*t;while(p!=NULL)if(p-areaSize=process-pSize) break; p=p-ne*t;printf(%d KB pSize,p-areaSize);if(p-areaSize-process-pSizepStartAddr=p-aStartAddr; /進程始址變化process-pState=1; /進程狀態(tài)process-pOccupy=p-areaSize; /進程實際

19、占用存為改空閑分區(qū)的大小pListpLength+= *process; /把進程參加進程列表printf( 且 %d KB - %d KB = %d KB 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-pOc

20、cupy=process-pSize; /進程實際占用存為該進程的大小pListpLength+= *process; /把進程參加進程列表printf( 且 %d KB - %d KB = %d KB %d KB 則劃分分配n, p-areaSize,process-pSize,p-areaSize-process-pSize,SIZE);pSort(pList); /進程排序printf(n分配后n);pListPrint(pList);/輸出存中空間占用情況/pact(L,pList);p-aStartAddr+=process-pSize; /空閑分區(qū)始址變化p-areaSize-=p

21、rocess-pOccupy; /空閑分區(qū)大小變化 int main()/0、創(chuàng)立一個進程，參數(shù)隨機數(shù)方式產(chǎn)生 struct PCB p; int i,num,dele,k,stAddr,flag; LinkList s,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 = %d KBn,p.pNo,p.pSize); /1、請求分配 size /2、檢索空閑分區(qū)表(首次適應(yīng)FF) PrintList(L); stAddr=search(L,p.pSize);/得到足夠大的分區(qū)的始址，沒有則返回-1 if(stAddr=-1)/沒有足夠大的分區(qū) if(add(L)=p.pSize)/空閑區(qū)總和足夠大 printf(沒有足夠大的空閑分區(qū)但空閑總和足夠大n); /緊湊 pact(L,pList)