操作系統(tǒng)之內存分配與回收.doc

_操作系統(tǒng)實驗內存的分配與回收 實驗報告1、 實驗題目：內存的分配與回收2、 實驗內容：利用可變分區(qū)的首次適應算法，模擬內存的分配與回收。3、 實驗目的：掌握可變分區(qū)首次適應算法的原理以及其編程實現。4、 實驗過程：1、基本思想：可變分區(qū)分配是根據進程的實際需求，動態(tài)地為之分配內存空間。首次適應算法要求空閑空間鏈以地址遞增的次序鏈接。進行內存分配時，從鏈表頭部開始依次檢索，找到第一個不小于請求空間大小的空閑空間進行分配。分配時需考慮碎片問題，若分配會導致碎片產生則將整塊分區(qū)分配。內存的回收需要考慮四種情況：回收分區(qū)前后兩個分區(qū)都空閑，則需要和前后兩個分區(qū)合并；（2）回收分區(qū)只有前一分區(qū)空閑，則與前一分區(qū)合并；（3）回收分區(qū)只有后一分區(qū)空閑，則和后一分區(qū)合并；（4）回收分區(qū)獨立，不考慮合并。2、主要數據結構：struct FreeArea 鏈結點包含的數據：分區(qū)號、大小、起址、標記 int ID;int size;long address;int sign;struct Node 雙鏈表結點結構體：數據區(qū)、前向指針、后繼指針FreeArea data;struct Node *prior; struct Node *next; *DLinkList;3、輸入、輸出： 輸入： I.內存分配時由鍵盤輸入分區(qū)ID和大小； II.內存回收時由鍵盤輸入需要回收的分區(qū)ID；輸出： 輸出內存的分配情況（按照地址從低到高）4、 程序流程圖：結束合并后回收合并后回收該分區(qū)后一個分區(qū)空閑該分區(qū)前一個分區(qū)空閑合并后回收該分區(qū)前后都空閑回收分區(qū)獨立輸入分區(qū)號顯示分區(qū)情況結束開始退出Choice=0Choice=3Choice=2將分區(qū)從空閑鏈移出，并修改相應數據結構整塊分配判斷是否會有碎片內存不足判斷剩余空間是否足夠輸入分區(qū)大小輸入分區(qū)號輸入有誤驗證該分區(qū)是否已經被占用Choice=1Choice3或choice0選擇操作choice輸出可選操作5、 實驗結果截屏：6、 源程序代碼：#includeusing namespace std;#define Free 0 /空閑狀態(tài)#define Busy 1 /已用狀態(tài)#define PBusy 2 /碎片已用狀態(tài)#define FINISH 1 /完成#define FINISH2 1 /完成#define ERROR 0 /出錯#define memory 512 /最大內存空間為(單位：KB）#define min 10 /碎片最小值(單位：KB)typedef struct FreeArea/空閑鏈數據int ID;int size;long address;int sign;typedef struct Node /空閑連結構 FreeArea data;struct Node *prior; struct Node *next; *DLinkList;DLinkList head; /頭結點DLinkList tail; /尾結點int Create()/初始化head=(DLinkList)malloc(sizeof(Node);/分配內存tail=(DLinkList)malloc(sizeof(Node);head-prior=NULL;head-next=tail;tail-prior=head;tail-next=NULL;tail-data.address=0;tail-data.size=memory;tail-data.ID=0;tail-data.sign=Free;return FINISH;int FirstFit(int ID,int request)/首次適應算法DLinkList temp=(DLinkList)malloc(sizeof(Node);/新建作業(yè)的結點temp-data.ID=ID;temp-data.size=request;temp-data.sign=Busy;Node *p=head;/插入指針P while(p)if(p-data.sign=Free & p-data.size=request)/剩余大小恰好滿足p-data.sign=Busy;p-data.ID=ID;return FINISH;break;else if(p-data.sign=Free & p-data.sizerequest & (p-data.size-requestmin)/滿足需求且有剩余且不產生碎片temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size=p-data.size-request;return FINISH;break;else if(p-data.sign=Free & p-data.sizerequest & p-data.size-requestdata.sign=PBusy;p-data.ID=ID;return FINISH;break;p=p-next;/若前面的分區(qū)都已分配，P指針后移return ERROR;int Allocate()/主存分配int ID,request;coutID;coutrequest;if(request0 |request=0)cout分配的主存必須是正整數！endl;return ERROR;if(FirstFit(ID,request)=FINISH)cout分配成功！endl;elsecout內存不足，分配失??！data.ID=ID)p-data.sign=Free;/p-data.ID=Free;if(p-prior-data.sign=Free)&(p-next-data.sign=Free)/與前后的空閑塊相連p-prior-data.size=p-prior-data.size+p-data.size+p-next-data.size;p-prior-next=p-next-next;if(p-next-next=NULL)/若p-next是最后一個結點p-prior-data.ID=Free;p-next=NULL;elsep-next-next-prior=p-prior;break; if(p-prior-data.sign=Free)/與前面的空閑塊相連p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;break;if(p-next-data.sign=Free)/與后面的空閑塊相連p-data.size+=p-next-data.size;if(p-next-next=NULL)/若p-next是最后一個結點p-next=NULL;elsep-next-next-prior=p;p-next=p-next-next;break;break;p=p-next;cout分區(qū)：ID回收成功endl;return FINISH;void show()/顯示coutnext;while(p)coutdata.ID=Free)coutFreeendl;elsecoutdata.IDendl;cout起始地址：data.address;cout 分區(qū)大?。篸ata.size KB;coutdata.sign=Free)cout空 閑data.sign=PBusy)cout碎片已分配endl;elsecout已分配next;coutendl;void main()Create();int choice;int i;for(i=0;i+) cout請輸入操作：;cout1.分配內存 2.回收內存 3.顯示主存 0.退出;coutchoice;if(choice=1)/ 分配內存Allocate();