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

1、 組號(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ū)

2、分配算法與動(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。空閑分區(qū)按地址遞增的順序排列；在分配內(nèi)存時(shí)，從空閑分區(qū)表第一個(gè)表目開(kāi)始順序查找，如

3、果m.sizeu.size且m.size-u.sizesize，說(shuō)明多余部分太小，不再分割，將整個(gè)分區(qū)分配給請(qǐng)求者；如果m.sizeu.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)存回收模

4、塊進(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

5、分區(qū)找到>u.size的空閑區(qū)？按動(dòng)態(tài)分區(qū)方式分配空閑分區(qū)總和u.size?進(jìn)行緊湊修改有關(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>#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define SIZE 15 /進(jìn)程表/int pp

6、No=1; /用于遞增生成進(jìn)程號(hào) int pLength=0;struct PCBint pNo; /進(jìn)程號(hào)(名)int pSize; / 進(jìn)程大小 int pOccupy; / 實(shí)際占用的內(nèi)存 int pStartAddr; / 進(jìn)程起始地址 int pState; /進(jìn)程狀態(tài) ;struct PCB pList200;/空閑分區(qū)表部分/typedef int Status;typedef struct emptyNode /空閑分區(qū)結(jié)構(gòu)體 int areaSize; /空閑分區(qū)大小 int aStartAddr; /空閑分區(qū)始址 struct emptyNode *next;emptyNo

7、de,*LinkList;int ListDelete(struct PCB *pList,int i);/AAA/刪除下標(biāo)為i的進(jìn)程 void pSort(struct PCB *pList); /AAA/內(nèi)存中的進(jìn)程按始址遞增排序 void compact(LinkList &L,struct PCB *pList);/AAA/緊湊 ,內(nèi)存中進(jìn)程移動(dòng)，修改進(jìn)程數(shù)據(jù)結(jié)構(gòu)；空閑分區(qū)合并，修改空閑分區(qū)表數(shù)據(jù)結(jié)構(gòu) void amalgamate(LinkList &L); /AAA/回收后進(jìn)行合并空閑分區(qū) void recycle(LinkList &L,struct PC

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

9、List(LinkList L); /AAA/*輸出各結(jié)點(diǎn)的值void creatP(struct PCB *p); /AAA/初始化進(jìn)程int search(LinkList &L,int pSize); /AAA/檢索分區(qū)表 ,返回合適分區(qū)的首址 int add(LinkList &L); /AAA/返回空閑分區(qū)總和 void pListPrint(struct PCB *pList); /AAA/輸出內(nèi)存中空間占用情況 void distribute(LinkList &L,struct PCB *process);int ListDelete(struct PC

10、B *pList,int i)/AAA/刪除下標(biāo)為i的進(jìn)程 for(;i<pLength-1;i+)pListi=pListi+1;pLength-;/ListDeletevoid pSort(struct PCB *pList) /AAA/內(nèi)存中的進(jìn)程按始址遞增排序 int i,j;struct PCB temp;for(i=0;i<pLength-1;i+)for(j=0;j<pLength-i-1;j+)if(pListj.pStartAddr>pListj+1.pStartAddr)temp=pListj;pListj=pListj+1;pListj+1=tem

11、p;/AAA/緊湊 ,內(nèi)存中進(jìn)程移動(dòng)，修改進(jìn)程數(shù)據(jù)結(jié)構(gòu)；空閑分區(qū)合并，修改空閑分區(qū)表數(shù)據(jù)結(jié)構(gòu) void compact(LinkList &L,struct PCB *pList) printf("進(jìn)行緊湊n"); /1、進(jìn)程移動(dòng),修改進(jìn)程數(shù)據(jù)結(jié)構(gòu)int i;pList0.pStartAddr=0; /第一個(gè)進(jìn)程移到最上面 for(i=0;i<pLength-1;i+)pListi+1.pStartAddr=pListi.pStartAddr+pListi.pOccupy;/2、 空閑分區(qū)合并，修改空閑分區(qū)表數(shù)據(jù)結(jié)構(gòu) LinkList p=L->next

12、,s;int sumEmpty=0;while(p!=NULL)/求空閑區(qū)總和 sumEmpty+=p->areaSize;p=p->next;ClearList(L); /清空空閑分區(qū)表s=(LinkList)malloc(sizeof(emptyNode);s->aStartAddr=pListpLength-1.pStartAddr+pListpLength-1.pOccupy; s->areaSize=sumEmpty;ListInsert(L,s); printf("n緊湊后的>>>>n"); pListPrint(

13、pList);PrintList(L);void amalgamate(LinkList &L)/AAA/回收后進(jìn)行合并空閑分區(qū) LinkList p=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; elsep=q;q=q->next;/AAA/回收 ，從進(jìn)程表中刪除進(jìn)程 ，把釋放出

14、的空間插入到空閑分區(qū)鏈表中 void recycle(LinkList &L,struct PCB *pList) int index,delPNo,delPSize,delPOccupy,delPStartAddr; LinkList s; srand(time(0); index=rand()%pLength; delPNo=pListindex.pNo; delPSize=pListindex.pSize; delPOccupy=pListindex.pOccupy; delPStartAddr=pListindex.pStartAddr; printf("_"

15、;); printf("回收內(nèi)存 進(jìn)程 P%d: 始址：%d K 占用：%d KBn",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(

16、L); pListPrint(pList);/輸出內(nèi)存中空間占用情況 PrintList(L); /Status InitList(LinkList &L) /1AAA/構(gòu)造一個(gè)新的有頭節(jié)點(diǎn)的空鏈表LLinkList s;L=(LinkList)malloc(sizeof(emptyNode); /生成新節(jié)點(diǎn)(頭結(jié)點(diǎn))if(!L) return ERROR; /申請(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-

17、>next=NULL;return OK;/InitListStatus ClearList(LinkList &L) /2AAA/將鏈表L重置為空表LinkList p,r;p=L->next; r=p->next;while(p!=NULL)free(p);if(r=NULL)p=NULL;elsep=r; r=p->next;L->next=NULL;return OK;/ClearList /AAA/*根據(jù)始址進(jìn)行插入 Status ListInsert(LinkList &L,LinkList s1)LinkList r=L,p=L-&g

18、t;next,s;/指針 s=(LinkList)malloc(sizeof(emptyNode);s->areaSize=s1->areaSize;s->aStartAddr=s1->aStartAddr;if(p=NULL)L->next=s;s->next=NULL;elsewhile(p!=NULL) if(s1->aStartAddr < p->aStartAddr) s->next=r->next; r->next=s; break; r=p; p=p->next; /后移 if(p=NULL) r-&g

19、t;next=s; s->next=NULL; return OK;/ListInsert2void DeleteElem(LinkList &L,int aStartAddr)/*刪除線性表中始址值為aStartAddr的結(jié)點(diǎn)LinkList p=L,q;while(p->next!=NULL)q=p->next;if(q->aStartAddr=aStartAddr)p->next=q->next;free(q);elsep=p->next;/DeleteElem/void PrintList(LinkList L)/AAA/*輸出各結(jié)點(diǎn)的

20、值 printf("n空閑分區(qū)情況: 始址t 大小n");LinkList p=L->next;while(p!=NULL) printf(" %d Kt%d KBn",p->aStartAddr,p->areaSize);p=p->next;printf("n");/PrintList void creatP(struct PCB *p) /AAA/初始化進(jìn)程int size;srand(time(NULL); size=rand()%7+1; size*=10;p->pNo=ppNo+;p->p

21、Size=size;p->pOccupy=0;p->pStartAddr=0;p->pState=0;int search(LinkList &L,int pSize) /檢索分區(qū)表 ,返回合適分區(qū)的首址 LinkList p=L->next;while(p!=NULL)if(p->areaSize>=pSize)return p->aStartAddr;p=p->next;return -1;/沒(méi)有足夠大的 int add(LinkList &L) /返回空閑分區(qū)總和 LinkList p=L->next;int sum=

22、0; while(p!=NULL)sum+=p->areaSize;p=p->next;return sum;void pListPrint(struct PCB *pList)/AAA/輸出內(nèi)存中空間占用情況 printf("n進(jìn)程分配情況: 進(jìn)程t 始址t占用n");for(int i=0;i<pLength;i+) printf(" P%dt %d Kt%d KBn", pListi.pNo,pListi.pStartAddr,pListi.pOccupy);void distribute(LinkList &L,stru

23、ct PCB *process)LinkList p=L->next;while(p!=NULL)if(p->areaSize>=process->pSize) break; p=p->next;printf("%d KB < %d KB",process->pSize,p->areaSize);if(p->areaSize-process->pSize<=SIZE)/不用分割全部分配 （直接刪除此空閑分區(qū)結(jié)點(diǎn)）process->pStartAddr=p->aStartAddr; /進(jìn)程始址變化

24、process->pState=1; /進(jìn)程狀態(tài) process->pOccupy=p->areaSize; /進(jìn)程實(shí)際占用內(nèi)存 為改空閑分區(qū)的大小 pListpLength+= *process; /把進(jìn)程加入進(jìn)程列表 printf(" 且 %d KB - %d KB = %d KB < %d KB 則 整區(qū)分配n", p->areaSize,process->pSize,p->areaSize-process->pSize,SIZE);pSort(pList); printf("n分配后>>>&

25、gt;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)程的大小 pListpLength+= *process; /把進(jìn)程加入進(jìn)程列表 printf(" 且 %d KB - %d KB = %d KB > %d

26、KB 則 劃分分配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ū)大小 變化 int

27、main()/0、創(chuàng)建一個(gè)進(jìn)程，參數(shù)隨機(jī)數(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);/初始化進(jìn)程 printf("_"); printf("待裝入作業(yè):%d Size = %d KBn",p.pNo,p.pSize); /1、請(qǐng)求分配 size /2、檢索空閑分區(qū)表(首次適應(yīng)FF) PrintList(L); stAddr=search(L,p.pSize);/得到足夠大的分區(qū)的始址 ，沒(méi)