內(nèi)存管理實(shí)驗(yàn)報(bào)告

1、操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目：動(dòng)態(tài)分區(qū)內(nèi)存管理班級：計(jì)算機(jī)1303班學(xué)號(hào)：2120131138姓名：徐葉指導(dǎo)教師：代仕芳日 期：2015.11.5實(shí)驗(yàn)?zāi)康募耙蟊緦?shí)驗(yàn)要求用高級語言編寫模擬內(nèi)存的動(dòng)態(tài)分區(qū)分配和回收算法（不考慮緊湊），以便加深理解并實(shí)現(xiàn)首次適應(yīng)算法（FF）、循環(huán)首次適應(yīng)算法（NF）、最佳適應(yīng)算法（BF）, 最壞適應(yīng)算法（WF）的具體實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容本實(shí)驗(yàn)主要針對操作系統(tǒng)中內(nèi)存管理相關(guān)理論進(jìn)行實(shí)驗(yàn)，要求實(shí)驗(yàn)者編寫一個(gè)程序，該程序管理一塊虛擬內(nèi)存，實(shí)現(xiàn)內(nèi)存分配和回收功能。1 ）設(shè)計(jì)內(nèi)存分配的數(shù)據(jù)結(jié)構(gòu)（空閑分區(qū)表 / 空閑分區(qū)鏈），模擬管理 64M的內(nèi)存塊；2 ）設(shè)計(jì)內(nèi)存分配函數(shù)；3 ）

2、設(shè)計(jì)內(nèi)存回收函數(shù)；4 ）實(shí)現(xiàn)動(dòng)態(tài)分配和回收操作；5 ）可動(dòng)態(tài)顯示每個(gè)內(nèi)存塊信息動(dòng)態(tài)分區(qū)分配是要根據(jù)進(jìn)程的實(shí)際需求，動(dòng)態(tài)地分配內(nèi)存空間，涉及到分區(qū)分配所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配回收。程序主要分為四個(gè)模塊：（ 1）首次適應(yīng)算法（FF）在首次適應(yīng)算法中，是從已建立好的數(shù)組中順序查找，直至找到第一個(gè)大小能滿足要求的空閑分區(qū)為止，然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空間令開辟一塊新的地址，大小為原來的大小減去作業(yè)大小，若查找結(jié)束都不能找到一個(gè)滿足要求的分區(qū)，則此次內(nèi)存分配失敗。（ 2）循環(huán)首次適應(yīng)算法（NF）該算法是由首次適應(yīng)算法演變而成，在為進(jìn)程分配內(nèi)存空間

3、時(shí)，不再是每次都從第一個(gè)空間開始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直至找到第一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)，為實(shí)現(xiàn)本算法，設(shè)置一個(gè)全局變量f ,來控制循環(huán)查找，當(dāng)f%N=0時(shí)，f=0 ;若查找結(jié)束都不能找到一個(gè)滿足要求的分區(qū)，則此次內(nèi)存分配失敗。（ 3）最佳適應(yīng)算法（BF）最壞適應(yīng)分配算法是每次為作業(yè)分配內(nèi)存時(shí)，掃描整個(gè)數(shù)組，總是把能滿足條件的，又是最小的空閑分區(qū)分配給作業(yè)。（ 4）最壞適應(yīng)算法（WF）最壞適應(yīng)分配算法是每次為作業(yè)分配內(nèi)存時(shí)，掃描整個(gè)數(shù)組，總是把能滿足條件的，又是最大的空閑分區(qū)分配給作業(yè)。系統(tǒng)從空閑分區(qū)鏈表中找到所

4、需大小的分區(qū)，如果空閑分區(qū)大小大于分區(qū)大小，則從分 區(qū)中根據(jù)請求的大小劃分出一塊內(nèi)存分配出去，余下的部分則留在空閑鏈表中。然后，將分配區(qū)的首址返回給調(diào)用者。當(dāng)進(jìn)程運(yùn)行完回收內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)四種情況：1 、當(dāng)空閑區(qū)的上下兩相鄰分區(qū)都是空閑區(qū)：將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)。新空閑 區(qū)的起始地址為上空閑區(qū)的始址，大小為三個(gè)空閑區(qū)之和。空閑區(qū)合并后，取消可用表中下空閑區(qū)的表目項(xiàng)，修改上空閑區(qū)的對應(yīng)項(xiàng)。2、當(dāng)空閑區(qū)的上相鄰區(qū)是空閑區(qū)：將釋放區(qū)與上空閑區(qū)合并為一個(gè)空閑區(qū)，具起始地 址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后修改上空閑區(qū)對

5、應(yīng)的可用 表的表目項(xiàng)。3、當(dāng)空閑區(qū)的下相鄰區(qū)是空閑區(qū)：將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的始址作為 合并區(qū)的始址。合并區(qū)的長度為釋放區(qū)與下空閑區(qū)之和。 合并后修改可用表中相應(yīng)的表目項(xiàng)4、兩相鄰區(qū)都不是空閑區(qū)：釋放區(qū)作為一個(gè)新空閑可用區(qū)插入可用表。三、調(diào)試及運(yùn)行測試案例：假定主存中按地址順序依次有五個(gè)空閑區(qū)。始址地址分別為：3K, 40K, 60K, 100K, 500K,空閑區(qū)大小依次為：32k,10k,15k,228k,100k 。現(xiàn)有五個(gè)作業(yè)J1,J2,J3,J4,J5 。他們各需要 主存1k,10k,128k,28k,25k 。作業(yè)的完成順序?yàn)椋篔5, J1,J3,J2,J4 ,每完成一

6、個(gè)作業(yè)系統(tǒng)回 收為其分配的內(nèi)存空間，使用回收算法，回收內(nèi)存。初始界面(輸入)主存分配情況(1)首次適應(yīng)算法18-百福日¥取音適適存應(yīng)次應(yīng)應(yīng)導(dǎo)算配法應(yīng)能 八算適法法主存分配情況:分區(qū)號(hào)起始地址分區(qū)大小332KB4010KB6010050015KB228KB100KB輸人要進(jìn)行的操作；選擇目立輸入：*(2)循環(huán)首次適應(yīng)算法二' *C:BocuMent s and SettingsAdMinistrat orDebug1_ exe,一口法法 算算 配法應(yīng)速主存分配情況，分區(qū)號(hào)起始地址分區(qū)大小狀態(tài)332KB空閑4010KB空鬧6015KB空閑100228KB空閑500100KB空閑(

7、3)最佳適應(yīng)算法分區(qū)號(hào)起始地址分區(qū)大小狀態(tài)332KH空閑4010KB空閑6015KB空閑100228 KB空閑500100KB空閑主存分配情況:(4)最壞適應(yīng)算法算青L配法應(yīng)改 存應(yīng)次應(yīng)應(yīng) 修首適適 搭次選苜曾¥柬a* VI % VI胡擇L4輸？分區(qū)號(hào)起始地址分區(qū)大小狀態(tài)332KB空閑4M10KB空鬧6015KB空閑100228KB空閑500100KB空閑（首次適應(yīng)算法下）分配內(nèi)存匕、 L； vyocusent s and z>ettmgsAdBinist rat orXUebugX I a ese請輸入要筋的操作工選擇0-2輸入1:分配內(nèi)存2：回收內(nèi)存0：退出請輸入要分配的內(nèi)

8、存?zhèn)€數(shù)二曾依次頊入其大小.2511281028請輸入鬻要分配的主存大小單位：kb;請輸入需要分配的主存大小單位= KB： 分配成功I請輸入需要分配的主存大小 單位-kb； 分蛇成蜀!請輸入需要分配的主存大小單位,： 分品成功！請輸入需要分配的主存大小單位:kb； 分配成班主存分配情況二分區(qū)號(hào)起始地址分區(qū)大小狀態(tài)032SMB已分配1281KE己分配2?6 KB空閑34010KB已分配6015KB空閑5100128KB已分配622828KB已分配2H672KB空閑500100KB空閑rt *C:Docu»ents and Set±ingEAd»inist ratorD

9、ebug1. eze*請輸入要分配的內(nèi)存?zhèn)€數(shù)：量依次量入其大小.請輸入黑要分配的主存大小單位:阿；1分配成功I請輸入需要分配的主存大?。▎挝?MRM 2分配成功I,輸入需要分配的主存大小單位:N5 3務(wù)配成珈請輸入需要分配的主存大小單位:KB3 4於配成功！請輸入需要分配的主存大?。▎挝欢﨣R：5分配成功I請輸入需要分配的主存大小單位;KB3 6分配成多！分配成功！主存分配情況工分區(qū)號(hào)起始地址分區(qū)大小狀態(tài)031KB已分配142KB己分配263KB已分配394KB己分配4135KB已分配5186KB已分配2411 KB空閑4010KB空閑6015KB空閑100228 KB空閑500100KB空閑

10、（首次適應(yīng)算法下）回收內(nèi)存1輸入要進(jìn)行的操作：k=分配內(nèi)存0=回收內(nèi)存退出，輸入要回收的分區(qū)號(hào)臺(tái)存勺配情況選擇0-2輸入；8今區(qū)號(hào)起始地址分區(qū)大小狀態(tài)325KB空閑128LKB己分配2?6 KB空閑34610KB已分配6D15KB空閑S100128KB已分配622828KB己分配2S672KB空閑500100KB空閑cv ,C：Docu»ents and SettingsAd*inistratorDebug1.exe-口四、總結(jié)老師布置這次的實(shí)驗(yàn)題目的一開始，自己根本不知道要干什么，因?yàn)樵谏险n時(shí)對動(dòng)態(tài)分 區(qū)分配這節(jié)內(nèi)容學(xué)得沒有很深刻，對許多東西一知半解，所以在上機(jī)時(shí)根本不知道如何下手

11、, 后來，將本章內(nèi)容反復(fù)的看了幾遍之后，終于有了自己的思路。通過此次的學(xué)習(xí)，理解了內(nèi)存管理的相關(guān)理論，掌握了連續(xù)動(dòng)態(tài)分區(qū)管理的理論，通過 對實(shí)際問題的編程實(shí)現(xiàn)，獲得實(shí)際應(yīng)用和編程能力；充分了解了內(nèi)存管理的機(jī)制實(shí)現(xiàn)，從而 對計(jì)算機(jī)的內(nèi)部有了更深的認(rèn)識(shí)，對于以后對操作系統(tǒng)的深入有很大的作用。在做課程設(shè)計(jì)的過程中我遇到了不少問題，比如鏈表指針部分就很容易搞混，而且很多 地方不容易考慮全面，比如內(nèi)存回收時(shí)空閑區(qū)的合并部分，要考慮釋放的內(nèi)存空間前后是否 為空閑區(qū)，若是，如何來合并，另外若用的是最佳適應(yīng)算法，進(jìn)行內(nèi)存回收時(shí)還有考慮前后 空閑塊地址是否相接，因?yàn)樗前凑諌K的大小排序的，若不相接，即使兩個(gè)塊在

12、鏈表中的位 置相鄰，也不能合并，而且要注意每次分配或釋放空間后都要對鏈表進(jìn)行排序，這是由算法 思想決定的，這些條件都是在做的過程中逐步完善的，所遇到的這些問題通過詢問同學(xué)和查 閱資料得以解決。整個(gè)實(shí)驗(yàn)做完后，我對內(nèi)存動(dòng)態(tài)分區(qū)內(nèi)存管理有了更加深刻的理解，我個(gè)人的編程能力 也得到了一定程度的提高。附錄(附錄源代碼)#include<iostream>#include<stdlib.h>using namespace std;# define Free 0 /空閑狀態(tài)# define Busy 1 /已用狀態(tài)# define Notfree 2# define OK 1/完成

13、# define ERROR 0 /出錯(cuò)#define MAX_length 65536 / 最大內(nèi)存空間為 64Mtypedef int Status;int flag;typedef struct freearea/Zt義一個(gè)空閑區(qū)說明表結(jié)構(gòu)long size; /分區(qū)大小long address; /分區(qū)地址/int state; /狀態(tài)ElemType;/ 線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)typedef struct DuLNodeElemType data;struct DuLNode *prior; / 前趨指針struct DuLNode *next; /后繼指針DuLNode,*DuL

14、inkList;DuLinkList block_first; / 頭結(jié)點(diǎn)DuLinkList block_last;/尾結(jié)點(diǎn)Status alloc(int);內(nèi)存分配Status free(int); /內(nèi)存回收Status FF(int);/Zt 次適應(yīng)算法Status NF(int);/循環(huán)首次適應(yīng)算法Status BF(int); /最佳適應(yīng)算法Status WF(int); /最差適應(yīng)算法void show();/查看分配Status Initblock();/開創(chuàng)空間表Status Initblock()/開創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表block_first=(DuLinkList)

15、malloc(sizeof(DuLNode); block_last=(DuLinkList)malloc(sizeof(DuLNode); block_first->prior=NULL;block_first->next=block_last;block_last->prior=block_first; block_last->next=NULL;block_last->data.address=0;block_last->data.size=MAX_length;block_last->data.state=Notfree;return OK;S

16、tatus NotFree(int i,int j)DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);static DuLNode *p=block_first->next;temp->data.size=i;temp->data.state=Free;temp->prior=p->prior;temp->next=p;temp->data.address=j;p->prior->next=temp;p->prior=temp;p->data.address=temp->

17、data.address+temp->data.size;p->data.size-=i;temp->next=block_last;block_last->prior=temp;return OK;/分配主存Status alloc(int ch) int request = 0;cout<<”請輸入需要分配的主存大小(單位:KB):"cin>>request;if(request<0 |request=0)cout<<"分配大小不合適，請重試！"<<endl;return ERROR

18、;if(ch=2) / 選擇首次循環(huán)適應(yīng)算法if(NF(request)=OK) cout<<" 分配成功！ "<<endl;else cout<<”內(nèi)存不足，分配失敗！"<<endl;return OK;if(ch=3) / 選擇最佳適應(yīng)算法if(BF(request)=OK) cout<<" 分配成功！ "<<endl;else cout<<”內(nèi)存不足，分配失敗！"<<endl;return OK;if(ch=4) / 選擇最差適應(yīng)算法

19、if(WF(request)=OK) cout<<" 分配成功！ "<<endl;else cout<<”內(nèi)存不足，分配失?。?quot;<<endl;return OK;else /默認(rèn)首次適應(yīng)算法if(FF(request)=OK) cout<<" 分配成功！ "<<endl;else cout<<”內(nèi)存不足，分配失敗！"<<endl;return OK;/首次適應(yīng)算法Status FF(int request)/為申請作業(yè)開辟新空間且初始化Du

20、LinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;while(p)if(p->data.state=Free && p->data.size=request)/ 有大小恰好合適的空閑塊p->data.state=Busy;return OK;break;if(p->data.state=Free && p->data.s

21、ize>request)/ 有空閑塊能滿足需求且有剩余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-=request;return OK;break;p=p->next;return ERROR;/循環(huán)首次適應(yīng)算法Status

22、NF(int request) /為申請作業(yè)開辟新空間且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp->data.size=request;temp->data.state=Busy;static DuLNode *p=block_first->next;/static 其值在下次調(diào)用時(shí)仍維持上次的值if(p->data.size<request)p=block_first->next;while(p)if(p->data.state=Free&&p->dat

23、a.size=request)/有大小恰好合適的空閑塊p->data.state=Busy;return OK;break;if(p->data.state=Free&&p->data.size>request)/ 有空閑塊能滿足需求且有剩余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

24、.address+temp->data.size;p->data.size-=request;return OK;break;p=p->next;return ERROR;/最佳適應(yīng)算法Status BF(int request) int ch; /記錄最小剩余空間DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; / 記錄最佳

25、插入位置while(p) / 初始化最小空間和最佳位置if(p->data.state=Free && (p->data.size>=request) ) if(q=NULL)q=p;ch=p->data.size-request;else if(q->data.size > p->data.size)q=p;ch=p->data.size-request;p=p->next;if(q=NULL) return ERROR;/ 沒有找到空閑塊else if(q->data.size=request)q->data

26、.state=Busy;return OK;elsetemp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.size=ch;return OK;return OK;/最壞適應(yīng)算法Status WF(int request)int ch; /記錄最大剩余空間DuLinkList temp=(DuLinkList)malloc

27、(sizeof(DuLNode);temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; / 記錄最佳插入位置while(p) / 初始化最大空間和最佳位置if(p->data.state=Free && (p->data.size>=request) ) if(q=NULL)q=p;ch=p->data.size-request;else if(q->data.size < p->data.

28、size)q=p;ch=p->data.size-request;p=p->next;if(q=NULL) return ERROR;/ 沒有找到空閑塊else if(q->data.size=request)q->data.state=Busy;return OK;elsetemp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prior=temp;q->data.address+=req

29、uest;q->data.size=ch;return OK;return OK;/主存回收Status free(int flag) DuLNode *p=block_first;for(int i= 0; i <= flag; i+) if(p!=NULL)p=p->next;elsereturn ERROR;p->data.state=Free;&&if(p->prior!=block_first p->prior->data.state=Free&&p->data.address=p->prior-&

30、gt;data.address+p->prior->data.size)/當(dāng) 前疝的空閑塊相連p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;p=p->prior;if(p->next!=block_last&&p->next->data.state=Free&&p->next->data.address=p->data.address+p-&

31、gt;data.size用后面的 空閑塊相連p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;if(p->next=block_last && p->next->data.state=Free)與最后的空閑塊相連p->data.size+=p->next->data.size;p->next=NULL; return OK;/顯示主存分配情況 void show()int fla

32、g = 0;cout<<"n主存分配情況：n"cout<<"*nn"DuLNode *p=block_first->next;cout<<"分區(qū)號(hào)t起始地址t分區(qū)大小t狀態(tài)nn"while(p)if(p->data.state=Notfree) p=p->next;elseif(p->data.state=Busy) cout<<" "<<flag+<<"t" else cout<<"t"flag+;cout<<" "<<p->data.address<<"tt"cout<<" "<<p->data.size&l