操作系統(tǒng)之內(nèi)存分配與回收

1、操作系統(tǒng)實(shí)驗(yàn)內(nèi)存的分配與回收 實(shí)驗(yàn)報(bào)告1、 實(shí)驗(yàn)題目：內(nèi)存的分配與回收2、 實(shí)驗(yàn)內(nèi)容：利用可變分區(qū)的首次適應(yīng)算法，模擬內(nèi)存的分配與回收。3、 實(shí)驗(yàn)?zāi)康模赫莆湛勺兎謪^(qū)首次適應(yīng)算法的原理以及其編程實(shí)現(xiàn)。4、 實(shí)驗(yàn)過程：1、基本思想：可變分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需求，動態(tài)地為之分配內(nèi)存空間。首次適應(yīng)算法要求空閑空間鏈以地址遞增的次序鏈接。進(jìn)行內(nèi)存分配時(shí)，從鏈表頭部開始依次檢索，找到第一個(gè)不小于請求空間大小的空閑空間進(jìn)行分配。分配時(shí)需考慮碎片問題，若分配會導(dǎo)致碎片產(chǎn)生則將整塊分區(qū)分配。內(nèi)存的回收需要考慮四種情況：回收分區(qū)前后兩個(gè)分區(qū)都空閑，則需要和前后兩個(gè)分區(qū)合并；（2）回收分區(qū)只有前一分區(qū)空閑，則與

2、前一分區(qū)合并；（3）回收分區(qū)只有后一分區(qū)空閑，則和后一分區(qū)合并；（4）回收分區(qū)獨(dú)立，不考慮合并。2、主要數(shù)據(jù)結(jié)構(gòu)：struct FreeArea 鏈結(jié)點(diǎn)包含的數(shù)據(jù)：分區(qū)號、大小、起址、標(biāo)記 int ID;int size;long address;int sign;struct Node 雙鏈表結(jié)點(diǎn)結(jié)構(gòu)體：數(shù)據(jù)區(qū)、前向指針、后繼指針FreeArea data;struct Node *prior; struct Node *next; *DLinkList;3、輸入、輸出： 輸入： I.內(nèi)存分配時(shí)由鍵盤輸入分區(qū)ID和大?。?II.內(nèi)存回收時(shí)由鍵盤輸入需要回收的分區(qū)ID；輸出： 輸出內(nèi)存的分配情

3、況（按照地址從低到高）4、 程序流程圖：結(jié)束合并后回收合并后回收該分區(qū)后一個(gè)分區(qū)空閑該分區(qū)前一個(gè)分區(qū)空閑合并后回收該分區(qū)前后都空閑回收分區(qū)獨(dú)立輸入分區(qū)號顯示分區(qū)情況結(jié)束開始退出Choice=0Choice=3Choice=2將分區(qū)從空閑鏈移出，并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)整塊分配判斷是否會有碎片內(nèi)存不足判斷剩余空間是否足夠輸入分區(qū)大小輸入分區(qū)號輸入有誤驗(yàn)證該分區(qū)是否已經(jīng)被占用Choice=1Choice>3或choice<0選擇操作choice輸出可選操作5、 實(shí)驗(yàn)結(jié)果截屏：6、 源程序代碼：#include<iostream>using namespace std;#defin

4、e Free 0 /空閑狀態(tài)#define Busy 1 /已用狀態(tài)#define PBusy 2 /碎片已用狀態(tài)#define FINISH 1 /完成#define FINISH2 1 /完成#define ERROR 0 /出錯(cuò)#define memory 512 /最大內(nèi)存空間為(單位：KB）#define min 10 /碎片最小值(單位：KB)typedef struct FreeArea/空閑鏈數(shù)據(jù)int ID;int size;long address;int sign;typedef struct Node /空閑連結(jié)構(gòu) FreeArea data;struct Node *

5、prior; struct Node *next; *DLinkList;DLinkList head; /頭結(jié)點(diǎn)DLinkList tail; /尾結(jié)點(diǎn)int Create()/初始化head=(DLinkList)malloc(sizeof(Node);/分配內(nèi)存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;ta

6、il->data.ID=0;tail->data.sign=Free;return FINISH;int FirstFit(int ID,int request)/首次適應(yīng)算法DLinkList temp=(DLinkList)malloc(sizeof(Node);/新建作業(yè)的結(jié)點(diǎn)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=re

7、quest)/剩余大小恰好滿足p->data.sign=Busy;p->data.ID=ID;return FINISH;break;else if(p->data.sign=Free && p->data.size>request && (p->data.size-request>min)/滿足需求且有剩余且不產(chǎn)生碎片temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->ne

8、xt=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.size>request && p->data.size-request<=min)/產(chǎn)生碎片時(shí)p->data.sign=PBusy;p->data.ID=ID;

9、return FINISH;break;p=p->next;/若前面的分區(qū)都已分配，P指針后移return ERROR;int Allocate()/主存分配int ID,request;cout<<"請輸入作業(yè)所在分區(qū)號："cin>>ID;cout<<"請輸入分配的主存(單位:KB)："cin>>request;if(request<0 |request=0)cout<<"分配的主存必須是正整數(shù)！"<<endl;return ERROR;if(Fir

10、stFit(ID,request)=FINISH)cout<<"分配成功！"<<endl;elsecout<<"內(nèi)存不足，分配失??！"<<endl;int Recycle(int ID)/回收Node *p=head;while(p)if(p->data.ID=ID)p->data.sign=Free;/p->data.ID=Free;if(p->prior->data.sign=Free)&&(p->next->data.sign=Free)/與前

11、后的空閑塊相連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是最后一個(gè)結(jié)點(diǎn)p->prior->data.ID=Free;p->next=NULL;elsep->next->next->prior=p->prior;break; if(p->prior

12、->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是最后一個(gè)結(jié)點(diǎn)p->next=NULL;elsep-&g

13、t;next->next->prior=p;p->next=p->next->next;break;break;p=p->next;cout<<"分區(qū)："<<ID<<"回收成功"<<endl;return FINISH;void show()/顯示cout<<" 主存分配情況 n"Node *p=head->next;while(p)cout<<"分區(qū)號："if(p->data.ID=Free)c

14、out<<"Free"<<endl;elsecout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address;cout<<" 分區(qū)大?。?quot;<<p->data.size<<" KB"cout<<" 狀 態(tài)："if(p->data.sign=Free)cout<<"空 閑"<&l

15、t;endl;else if(p->data.sign=PBusy)cout<<"碎片已分配"<<endl;elsecout<<"已分配"<<endl;p=p->next;cout<<endl;void main()Create();int choice;int i;for(i=0;i+) cout<<"請輸入操作："cout<<"1.分配內(nèi)存 2.回收內(nèi)存 3.顯示主存 0.退出"cout<<endl;cin>>choice;