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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 操作系統(tǒng)課程設(shè)計(jì)報(bào)告 題 目：動態(tài)分區(qū)內(nèi)存管理班 級：計(jì)算機(jī)1303班 學(xué) 號： 姓 名： 徐葉指導(dǎo)教師：代仕芳 日 期： 2015.11.5專心-專注-專業(yè)一、 實(shí)驗(yàn)?zāi)康募耙?本實(shí)驗(yàn)要求用高級語言編寫模擬內(nèi)存的動態(tài)分區(qū)分配和回收算法（不考慮緊湊），以便加深理解并實(shí)現(xiàn)首次適應(yīng)算法（FF）、循環(huán)首次適應(yīng)算法(NF)、最佳適應(yīng)算法（BF），最壞適應(yīng)算法(WF)的具體實(shí)現(xiàn)。2、 實(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ū)鏈），模擬管

2、理 64M 的內(nèi)存塊；2） 設(shè)計(jì)內(nèi)存分配函數(shù)；3） 設(shè)計(jì)內(nèi)存回收函數(shù)；4） 實(shí)現(xiàn)動態(tài)分配和回收操作；5） 可動態(tài)顯示每個(gè)內(nèi)存塊信息 動態(tài)分區(qū)分配是要根據(jù)進(jìn)程的實(shí)際需求，動態(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

3、) 該算法是由首次適應(yīng)算法演變而成，在為進(jìn)程分配內(nèi)存空間時(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ù)組，總是把能滿足條件的，又

4、是最大的空閑分區(qū)分配給作業(yè)。 系統(tǒng)從空閑分區(qū)鏈表中找到所需大小的分區(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ū)的起始地

5、址，大小為上空閑區(qū)與釋放區(qū)之和。合并后修改上空閑區(qū)對應(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?，F(xiàn)有五個(gè)作業(yè)J1,J2,J3,J4,J5。他們各需要主存1k,10k,128k,28k,25k。作業(yè)的完成順序

6、為：J5, J1,J3,J2,J4，每完成一個(gè)作業(yè)系統(tǒng)回收為其分配的內(nèi)存空間，使用回收算法，回收內(nèi)存。初始界面（輸入）主存分配情況(1)首次適應(yīng)算法(2)循環(huán)首次適應(yīng)算法(3)最佳適應(yīng)算法(4)最壞適應(yīng)算法(首次適應(yīng)算法下)分配內(nèi)存(首次適應(yīng)算法下)回收內(nèi)存四、總結(jié)老師布置這次的實(shí)驗(yàn)題目的一開始，自己根本不知道要干什么，因?yàn)樵谏险n時(shí)對動態(tài)分區(qū)分配這節(jié)內(nèi)容學(xué)得沒有很深刻，對許多東西一知半解，所以在上機(jī)時(shí)根本不知道如何下手，后來，將本章內(nèi)容反復(fù)的看了幾遍之后，終于有了自己的思路。通過此次的學(xué)習(xí)，理解了內(nèi)存管理的相關(guān)理論，掌握了連續(xù)動態(tài)分區(qū)管理的理論，通過對實(shí)際問題的編程實(shí)現(xiàn)，獲得實(shí)際應(yīng)用和編程能力

7、；充分了解了內(nèi)存管理的機(jī)制實(shí)現(xiàn)，從而對計(jì)算機(jī)的內(nèi)部有了更深的認(rèn)識，對于以后對操作系統(tǒng)的深入有很大的作用。在做課程設(shè)計(jì)的過程中我遇到了不少問題，比如鏈表指針部分就很容易搞混，而且很多地方不容易考慮全面，比如內(nèi)存回收時(shí)空閑區(qū)的合并部分，要考慮釋放的內(nèi)存空間前后是否為空閑區(qū)，若是，如何來合并，另外若用的是最佳適應(yīng)算法，進(jìn)行內(nèi)存回收時(shí)還有考慮前后空閑塊地址是否相接，因?yàn)樗前凑諌K的大小排序的，若不相接，即使兩個(gè)塊在鏈表中的位置相鄰，也不能合并，而且要注意每次分配或釋放空間后都要對鏈表進(jìn)行排序，這是由算法思想決定的，這些條件都是在做的過程中逐步完善的，所遇到的這些問題通過詢問同學(xué)和查閱資料得以解決。 整

8、個(gè)實(shí)驗(yàn)做完后，我對內(nèi)存動態(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 /完成 #define ERROR 0 /出錯 #define MAX_length 65536 /最大內(nèi)存空間為64M typedef int Status; int flag; typedef

9、struct freearea/定義一個(gè)空閑區(qū)說明表結(jié)構(gòu) long size; /分區(qū)大小 long address; /分區(qū)地址 int state; /狀態(tài) ElemType; / 線性表的雙向鏈表存儲結(jié)構(gòu) typedef struct DuLNode ElemType data; struct DuLNode *prior; /前趨指針 struct DuLNode *next; /后繼指針 DuLNode,*DuLinkList; DuLinkList block_first; /頭結(jié)點(diǎn) DuLinkList block_last; /尾結(jié)點(diǎn) Status alloc(int);/內(nèi)存

10、分配 Status free(int); /內(nèi)存回收 Status FF(int);/首次適應(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)malloc(sizeof(DuLNode); block_last=(DuLinkList)malloc(sizeof(DuLNode); block_

11、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; Status NotFree(int i,int j)DuLinkList temp=(DuLinkList)malloc(sizeof(Du

12、LNode); 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->data.address+temp->data.size; p->data.size-=i; temp->

13、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; if(ch=2) /選擇首次循環(huán)適應(yīng)算法 if(NF(request)=OK) cout<

14、;<"分配成功！"<<endl; else cout<<"內(nèi)存不足，分配失敗！"<<endl; return OK; if(ch=3) /選擇最佳適應(yīng)算法 if(BF(request)=OK) cout<<"分配成功！"<<endl; else cout<<"內(nèi)存不足，分配失?。?quot;<<endl; return OK; if(ch=4) /選擇最差適應(yīng)算法 if(WF(request)=OK) cout<<"

15、;分配成功！"<<endl; else cout<<"內(nèi)存不足，分配失??！"<<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è)開辟新空間且初始化 DuLinkList temp=(DuLin

16、kList)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.size>requ

17、est) /有空閑塊能滿足需求且有剩余 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

18、 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->

19、data.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->da

20、ta.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

21、; /記錄最佳插入位置 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=req

22、uest) q->data.state=Busy; return OK; else temp->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; /記錄最大剩余空間 DuL

23、inkList temp=(DuLinkList)malloc(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; el

24、se 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.state=Busy; return OK; else temp->prior=q->prior; temp->next=q; temp->data.address=q->data.address; q->prior->n

25、ext=temp; q->prior=temp; q->data.address+=request; 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; else return ERROR; p->data.state=Free; if(p->prior!=block_first && p->prio

26、r->data.state=Free&&p->data.address=p->prior->data.address+p->prior->data.size)/與前面的空閑塊相連 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.s

27、tate=Free&&p->next->data.address=p->data.address+p->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-&g

28、t;next->data.size; p->next=NULL; return OK; /顯示主存分配情況 void show() int flag = 0; cout<<"n主存分配情況:n" cout<<"*nn" DuLNode *p=block_first->next; cout<<"分區(qū)號t起始地址t分區(qū)大小t狀態(tài)nn" while(p) if(p->data.state=Notfree) p=p->next;elseif(p->data.state=B

29、usy) cout<<" "<<flag+<<"t" else cout<<"t"flag+;cout<<" "<<p->data.address<<"tt" cout<<" "<<p->data.size<<"KBtt" if(p->data.state=Free) cout<<"空閑nn" else cout<<"已分配nn" p=p->next; cout<<"*nn" /主函數(shù) vo