內(nèi)存打點(diǎn)模型的設(shè)計(jì)與實(shí)現(xiàn)

1、操作系統(tǒng)課程實(shí)驗(yàn)報(bào)告學(xué)生姓名：班學(xué)號(hào)：指導(dǎo)教師：袁國斌中國地質(zhì)大學(xué)信息工程學(xué)院2012年 12月 15日實(shí)習(xí)題目：內(nèi)存管理模型的設(shè)計(jì)與實(shí)現(xiàn)【需求規(guī)格說明】（1）對(duì)于給定的一個(gè)存儲(chǔ)空間自己設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行管理，可以使用單個(gè)鏈表，也可以使用多個(gè)鏈表，自己負(fù)責(zé)存儲(chǔ)空間的所有管理組織，要求采用分頁方式（指定單元大小為頁，如 4K, 2K,進(jìn)程申請以頁為單位）來組織基本內(nèi)容；（2）當(dāng)進(jìn)程對(duì)內(nèi)存進(jìn)行空間申請操作時(shí)，模型采用一定的策略（如：首先利用可用的內(nèi)存進(jìn)行分配，如果空間不夠時(shí)，進(jìn)行內(nèi)存緊縮或其他方案進(jìn)行處理）對(duì)進(jìn)程給予指定的內(nèi)存分配；（3）從系統(tǒng)開始啟動(dòng)到多個(gè)進(jìn)程參與申請和運(yùn)行時(shí)，進(jìn)程最少要有3個(gè)以上

2、，每個(gè)執(zhí)行申請的時(shí)候都要能夠?qū)ο到y(tǒng)當(dāng)前的內(nèi)存情況進(jìn)行查看的接口；（4）對(duì)內(nèi)存的申請進(jìn)行內(nèi)存分配，對(duì)使用過的空間進(jìn)行回收，對(duì)給定的某種頁面調(diào) 度進(jìn)行合理的頁面分配。（5）利用不同的顏色代表不同的進(jìn)程對(duì)內(nèi)存的占用情況，動(dòng)態(tài)更新這些信息。【算法設(shè)計(jì)】（1）設(shè)計(jì)思想：通過建立一個(gè)鏈表， 來描述已分配和空閑的內(nèi)存分區(qū)。 對(duì)于每一個(gè)分區(qū)，它可能存 放了某個(gè)進(jìn)程，也可能是兩個(gè)進(jìn)程間的空閑區(qū)。 鏈表中的每一個(gè)結(jié)點(diǎn)， 分別描述了一個(gè) 內(nèi)存分區(qū)，包括它的起始地址、長度、指向下一個(gè)結(jié)點(diǎn)的指針以及分區(qū)的當(dāng)前狀態(tài)。在基于鏈表的存儲(chǔ)管理中，當(dāng)一個(gè)新的進(jìn)程到來時(shí)，需要為它分配內(nèi)存空間，即為它尋找 某個(gè)空閑分區(qū)，該分區(qū)的大小

3、必須大于或等于進(jìn)程的大小通常的分配算法有最先匹配法最佳匹配法，最快匹配法最先匹配法是一種簡單的算法 ，它的基本思路是：假設(shè)新進(jìn)程的大小為 M，那么從鏈 表的首節(jié)點(diǎn)開始，將每一個(gè)空閑節(jié)點(diǎn)的大小與 M相比較，直到找到合適的節(jié)點(diǎn)這種算法 查找的節(jié)點(diǎn)很少，因而速度很快最佳匹配算法的基本思路是：搜索整個(gè)鏈表，將能夠裝得下該進(jìn)程的最小空閑區(qū)分 配出去為了克服最佳匹配算法把空閑區(qū)切割的太小的缺點(diǎn)，人們又提出了一種最壞匹配法也就是說，在每次分配的時(shí)候，總是將最大的那個(gè)空閑區(qū)切去一部分，分配給請求者.它的依據(jù)是當(dāng)一個(gè)很大的空閑區(qū)被切割成一部分后，可能仍然是一個(gè)比較大的空閑區(qū)，從而避免了空閑區(qū)越分越小的問題 （2

4、）設(shè)計(jì)表示：分區(qū)結(jié)點(diǎn)設(shè)計(jì)：templatevclass T>class ChainN ode代表操作系統(tǒng)代表動(dòng)態(tài)分配內(nèi)存/最佳適應(yīng)法/最壞適應(yīng)法/撤銷進(jìn)程，可能要進(jìn)frie nd Chain<T>public:char pro; /內(nèi)存塊存放的程序名"o"空閑區(qū)T size; /內(nèi)存塊的大小T begi n; /內(nèi)存塊起始地址Chai nN ode<T> *li nk; /下一個(gè)內(nèi)存塊;templatevclass T>分區(qū)鏈表設(shè)計(jì)：class Chai npublic:Chai n()first=NULL;Chai n();int ff

5、(int man age,char pro,i nt size);void assig n(Chai nN ode<T> *q,char pro,i nt size);/int bf(i nt man age,char pro,i nt size);int wf(int man age,char pro,i nt size);int delpro(i nt man age,char pro);行內(nèi)存塊的合并void del_pro(i nt man age);void init(int manage);/ 內(nèi)存的初始化void assig n_pro(i nt man age) ;

6、 /public:Chai nN ode<T> *first;Chai nN ode<T> *p;(3)詳細(xì)設(shè)計(jì)表示/最先適應(yīng)法/最佳適應(yīng)法/最壞適應(yīng)法【調(diào)試報(bào)告】回靜態(tài)分配勰現(xiàn)喙況是起始-結(jié)束地址 0k 4k 5k 24k25k 74k7510414 105k149k lsejcaak 2042551(0«F-技返回上一目錄（內(nèi)存將被初始化陵進(jìn)暮讓舀島存大小計(jì)青選擇分配算袪：1,最先適應(yīng)法。2,最佳適應(yīng)法。3,最壞適S3)C:Wmd0w55y5tem 32cmd.e5feSB C:Wmdow5sy5tem 32 cmd,exe回S3薛現(xiàn)在的儲(chǔ)存情況是:1內(nèi)睿

7、 険統(tǒng)區(qū) 程2閑區(qū)大小20 k30k磚k54hS2kJiS論分配、返回上一目錄<內(nèi)存將被初始化起始-結(jié)束地址0k 4k5k 24K25k 74k7510414 105k149k lSQkak 204k255k黠蠶麟獺小嗣卄,最先昭2，甌三適應(yīng)法。3,取壞適SB C:Windowssyste m 3 2crnd. exe動(dòng)態(tài)分配廠千現(xiàn)在的儲(chǔ) < 二篙況是：帶操線2 空由區(qū).建立脇呈并分配、播銷進(jìn)槿 亠丄返回上一目錄<內(nèi)存將被初皓化統(tǒng)區(qū)大小5k2511<起始結(jié)束地址4k5k*255k'0 1嘉弓存 汚內(nèi) 的請 程程 進(jìn)進(jìn) AA4處聖一 青主冃-吐最先適應(yīng)法®

8、;取最佳適應(yīng)法* 3.最壞適【用戶手冊】用戶按照顯示屏要求輸入程序所需要的即可【附錄】#in elude <iostream.h>#i nclude <stdio.h>#i nclude <process.h>template<class T>class Cha inN odefriend Chain<T>public:char pro; /內(nèi)存塊存放的程序名"o"代表操作系統(tǒng)代表空閑區(qū)T size; /內(nèi)存塊的大小T begi n; /內(nèi)存塊起始地址Chai nN ode<T> *li nk; /下一

9、個(gè)內(nèi)存塊;template<class T>class Chai npublic:Chai n()first=NULL;Chai n();int ff(int man age,char pro,i nt size);/動(dòng)態(tài)分配內(nèi)存/最佳適應(yīng)法/最壞適應(yīng)法/撤銷進(jìn)程，可能要進(jìn)行內(nèi)存塊的合void assig n( Cha inN ode<T> *q,char pro,i nt size);int bf(int man age,char pro,i nt size);int wf(int man age,char pro,i nt size);int delpro(i nt

10、 man age,char pro);并void del_pro(i nt man age);void init(int manage);/ 內(nèi)存的初始化void assig n_pro(i nt man age) ; /public:Chai nN ode<T> *first;Chai nN ode<T> *p;,內(nèi)存總大小為256kmemory *base;/代表內(nèi)存，一個(gè)頭指針/int sn um=20,50,30,45,54,52;/void assig n( memory *q,char pro,i nt size);void in it(i nt man a

11、ge)/ 內(nèi)存的初始化memory *p,*q;if(base!=NULL)/這一塊是釋放鏈表p=base;while(p)q=p->n ext;delete p;p=q;base=new memory; / 操作系統(tǒng)，大小 5k,起始地址是 Okbase->begi n=0;base_>pro='o：base->size=5;if(manage=0) /靜態(tài)內(nèi)存，初始化 7個(gè)內(nèi)存塊，第一個(gè)內(nèi)存塊是操作系統(tǒng)p=base;q=new memory; q->begi n=5; q->pro=0; q->size=20; p_>n ext=q;

12、p=q;/空閑塊1,大小20,起始地址5kq=new memory; q->begi n=25; q->pro=0; q->size=50; p_>n ext=q;p=q;/空閑塊2,大小50,起始地址25kq=new memory; q->begi n=75; q->pro=0; q->size=30; p_>n ext=q;p=q;/空閑塊3,大小30,起始地址75kq=new memory;/空閑塊4,大小45,起始地址105kq->begi n=105; q_>pro=0; q->size=45; p_>n ext

13、=q; p=q;q=new memory; /空閑塊 5,大小 54,起始地址 150k q->begi n=150;q_>pro=0;q->size=54;p_>n ext=q;p=q;q=new memory;/空閑塊6,大小52，起始地址 204kq->begi n=204;q->pro=0;q->size=52;p_>n ext=q;q-> next=NULL;else/動(dòng)態(tài)內(nèi)存，只有一個(gè)大的內(nèi)存塊p=new memory;/空閑塊251k,起始地址是 5kp->begi n=5;p->pro=0;p->size=

14、251;p-> next=NULL;base->n ext=p;void assig n( memory *q,char pro,i nt size)上分配size 大小，q不為空且 q->next不為空配內(nèi)存塊的前指針I(yè)I動(dòng)態(tài)，給進(jìn)程 pro在內(nèi)存塊/因?yàn)橐M(jìn)行插入操作，所以傳的->next乏要分memory *p=q _>n ext;memory *temp=new memory; temp=new memory;temp->begi n=p_>begi n; temp->size=size;temp->pro=pro;q->n

15、ext=temp; if(p->size!=size)II代表進(jìn)程pro的內(nèi)存塊II插入的內(nèi)存塊小于空閑區(qū)塊p->size=p->size-size; p->begi n=temp->beg in+temp->size; temp->n ext=p; elseII插入的內(nèi)存塊等于空閑區(qū)塊temp->n ext=p->n ext;delete p;int ff(int man age,char pro,i nt size)memory *p=base;memory *q=p;while(p)的前指針if(p_>size<size|

16、p_>pro!=0) q=p;p=p->n ext;else break;if(p=NULL)return 0;elseif(ma nage=0)p_>pro=pro; else assig n( q,pro,size);return 1;int bf(int man age,char pro,i nt size)/最先適應(yīng)法/遍歷內(nèi)存找到第一個(gè)適合進(jìn)程pro的內(nèi)存塊，保存它/沒找到，返回0/找到了，返回1/靜態(tài)，直接讓進(jìn)程進(jìn)駐內(nèi)存/動(dòng)態(tài)，調(diào)用assign來給進(jìn)程pro分配/最佳適應(yīng)法memory *p=base,*temp=NULL,*q,*fr ont;int min=2

17、56;while(p)/遍歷內(nèi)存找到最佳的內(nèi)存塊，保存它的前指針if(p->pro=0&&p->size>=size&&min >p->size)min=p->size;fron t=q;temp=p;q=p;p=p->n ext;if(temp=NULL)return 0;/ 沒找到，返回 0elseelse assig n(fron t,pro,size);II動(dòng)態(tài)，調(diào)用assign來給進(jìn)程pro分配return 1;int wf(int man age,char pro,i nt size)memory *p=ba

18、se,*temp=NULL,*q,*fr ont;/最壞適應(yīng)法int max=0;while(p)/遍歷內(nèi)存，找到最大的一塊內(nèi)存if(p->pro=0&&p->size>=size&&max<p->size)max=p->size; fron t=q; temp=p;q=p; p=p->n ext; if(temp=NULL)return 0; else/沒找到，返回0/找到了，返回1if(ma nage=0)temp_>pro=pro; /靜態(tài)，直接讓進(jìn)程進(jìn)駐內(nèi)存else assig n(fron t,pro,s

19、ize); return 1;int delpro(i nt man age,char pro)memory *p=base,*q; while(p)if(p->pro!=pro)q=p;p=p->n ext;else break;if(p=NULL)return 0;elseII動(dòng)態(tài)，調(diào)用assign來給進(jìn)程pro分配/撤銷進(jìn)程，可能要進(jìn)行內(nèi)存塊的合并II遍歷內(nèi)存，尋找進(jìn)程proif(ma nage=0)p_>pro=0;elseII沒找到，返回0II找到了，返回1II靜態(tài)內(nèi)存，直接撤銷進(jìn)程，不用內(nèi)存塊合并II動(dòng)態(tài)內(nèi)存，可能要進(jìn)行內(nèi)存合并，分4種情況塊是空閑塊/前后內(nèi)存塊都

20、不是空閑塊/前內(nèi)存塊不是空閑塊，后內(nèi)存if(q->pro!=0)if(p_>n ext=NULL|p->n ext->pro!=0) p->pro=0;else不是空閑塊 elseif(p->n ext=NULL|p->n ext_>pro!=0)/前內(nèi)存塊是空閑塊，后內(nèi)存塊q_>n ext=p->n ext; q->size=q->size+p->size; delete p; else/前后內(nèi)存塊都是空閑塊q_>n ext=p->n ext;p_>n ext->begi n=p_>b

21、egi n;p->n ext->size=p->size+p->n ext->size; delete p;q->n ext=p->n ext- >n ext; q->size=q->size+p->size+p->n ext->size; delete p->n ext;delete p; return 1;void prin t(char ch,i nt beg in ,i nt size) switch(ch)case/根據(jù)內(nèi)存塊內(nèi)容,格式化輸入一塊內(nèi)存塊'o':pri ntf("

22、;t%3dkt%3dk%3dkn",size,begi n, begi n+size-1);break; case 0 :pri ntf("空閑區(qū)t%3dkt%3dk%3dkn",size,begi n, begi n+size-1);break; default:pri ntf("%ct%3dkt%3dk%3dkn",ch,size,begi n,begi n+size-1);break;void show()/格式化顯示內(nèi)存的儲(chǔ)存情況memory *p=base;int coun t=1;cout<<"內(nèi)存現(xiàn)在的儲(chǔ)存情

23、況是："<<endl;printf("塊號(hào)t 內(nèi)容tt 大小t起始-結(jié)束地址n");while(p)printf(” %2d",cou nt+);prin t(p->pro,p->begi n,p_>size);p=p->n ext;void del_pro(i nt man age)/ 撤銷進(jìn)程 pro，調(diào)用 delpromemory *p=base;char pro,result;cout<<"請輸入你要撤銷的進(jìn)程的名字："cin> >pro;if(pro='o&

24、#39;)cout<<"操作系統(tǒng)不可撤銷"<<e ndl;elseresult=delpro(ma nage,pro);if(result=0)cout<<"沒有找到進(jìn)程"<<pro<<",撤銷失敗"<<endl;else cout<<" 進(jìn)程"<<pro<<"撤銷成功"<<endl;void assign_pro(int manage)/給進(jìn)程pro根據(jù)選擇情況分配內(nèi)存int

25、 size,result=-1;char choose ,pro;cout<<"請輸入進(jìn)程的名字:"cin> >pro;cout<<"請輸入進(jìn)程請求的內(nèi)存大小:"cin> >size;cout<<"請選擇分配算法：1,最先適應(yīng)法。2，最佳適應(yīng)法。3,最壞適應(yīng)法"<<endl;cin> >choose;switch(choose)case '1':result=ff(ma nage,pro,size);break;case 2:result=bf(ma nage,pro,size);break;case 3:result=wf(ma nage,pro,size);break;if(result=0)cout<<" 進(jìn)程"<<pro<<"分配失敗"<<endl;else if(result=1)cout<<" 進(jìn)程"<<pro<<