內(nèi)存管理模型的設(shè)計(jì)與實(shí)現(xiàn)

1、無 操作系統(tǒng)課程實(shí)驗(yàn)報(bào)告操作系統(tǒng)課程實(shí)驗(yàn)報(bào)告 學(xué)生姓名： 尹朋 班 學(xué) 號(hào)： 111131 指導(dǎo)教師： 袁國(guó)斌 中國(guó)地質(zhì)大學(xué)信息工程學(xué)院中國(guó)地質(zhì)大學(xué)信息工程學(xué)院 2015 年年 1 月月 4 日日 無 實(shí)習(xí)題目：內(nèi)存管理模型的設(shè)計(jì)與實(shí)現(xiàn)實(shí)習(xí)題目：內(nèi)存管理模型的設(shè)計(jì)與實(shí)現(xiàn) 【需求規(guī)格說明】【需求規(guī)格說明】 對(duì)內(nèi)存的可變分區(qū)申請(qǐng)采用鏈表法管理進(jìn)行模擬實(shí)現(xiàn)。要求： 1.對(duì)于給定的一個(gè)存儲(chǔ)空間自己設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行管理，可以使用單個(gè)鏈表，也可以使用多個(gè)鏈表，自己負(fù)責(zé)存儲(chǔ)空間的所有管理組織，要求采用分頁(yè)方式 （指定單元大小為頁(yè)，如 4K，2K，進(jìn)程申請(qǐng)以頁(yè)為單位） 來組織基本內(nèi)容； 2.當(dāng)進(jìn)程對(duì)內(nèi)存進(jìn)行空

2、間申請(qǐng)操作時(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)程參與申請(qǐng)和運(yùn)行時(shí)，進(jìn)程最少要有 3 個(gè)以上，每個(gè)執(zhí)行申請(qǐng)的時(shí)候都要能夠?qū)ο到y(tǒng)當(dāng)前的內(nèi)存情況進(jìn)行查看的接口； 4.對(duì)內(nèi)存的申請(qǐng)進(jìn)行內(nèi)存分配，對(duì)使用過的空間進(jìn)行回收，對(duì)給定的某種頁(yè)面調(diào)度進(jìn)行合理的頁(yè)面分配。 5.利用不同的顏色代表不同的進(jìn)程對(duì)內(nèi)存的占用情況，動(dòng)態(tài)更新這些信息。 【算法設(shè)計(jì)】【算法設(shè)計(jì)】 （1 1）設(shè)計(jì)思想設(shè)計(jì)思想： 通過建立一個(gè)鏈表，來描述已分配和空閑的內(nèi)存分區(qū)。對(duì)于每一個(gè)分區(qū)，它可能存放了某個(gè)進(jìn)程，也可能是兩個(gè)進(jìn)

3、程間的空閑區(qū)。鏈表中的每一個(gè)結(jié)點(diǎn)， 分別描述了一個(gè)內(nèi)存分區(qū)，包括它的起始地址、長(zhǎng)度、指向下一個(gè)結(jié)點(diǎn)的指針以及分區(qū)的當(dāng)前狀態(tài)。在基于鏈表的存儲(chǔ)管理中,當(dāng)一個(gè)新的進(jìn)程到來時(shí),需要為它分配內(nèi)存空間,即為它尋找某個(gè)空閑分區(qū),該分區(qū)的大小必須大于或等于進(jìn)程的大小. 最先匹配法:假設(shè)新進(jìn)程的大小為 M,那么從鏈表的首節(jié)點(diǎn)開始,將每一個(gè)空閑節(jié)點(diǎn)的大小與 M 相比較,直到找到合適的節(jié)點(diǎn).這種算法查找的節(jié)點(diǎn)很少,因而速度很快. 最佳匹配算法:搜索整個(gè)鏈表,將能夠裝得下該進(jìn)程的最小空閑區(qū)分配出去. 最壞匹配法：在每次分配的時(shí)候,總是將最大的那個(gè)空閑區(qū)切去一部分,分配給請(qǐng)求者.它的依據(jù)是當(dāng)一個(gè)很大的空閑區(qū)被切割成一

4、部分后,可能仍然是一個(gè)比較大的空閑區(qū),從而避免了空閑區(qū)越分越小的問題. （2 2）設(shè)計(jì)表示設(shè)計(jì)表示： 分區(qū)結(jié)點(diǎn)設(shè)計(jì)： template class ChainNode friend Chain; public: char pro; /內(nèi)存塊存放的程序名o 代表操作系統(tǒng)代表空閑區(qū) 無 T size; /內(nèi)存塊的大小 T begin; /內(nèi)存塊起始地址 ChainNode *link; /下一個(gè)內(nèi)存塊 ; template 分區(qū)鏈表設(shè)計(jì)： class Chain public: Chain() first=NULL; Chain(); int ff(int manage,char pro,int

5、size); void assign(ChainNode *q,char pro,int size);/動(dòng)態(tài)分配內(nèi)存 int bf(int manage,char pro,int size); /最佳適應(yīng)法 int wf(int manage,char pro,int size); /最壞適應(yīng)法 int delpro(int manage,char pro); /撤銷進(jìn)程，可能要進(jìn)行內(nèi)存塊的合并 void del_pro(int manage); void init(int manage); /內(nèi)存的初始化 void assign_pro(int manage) ; / public: Cha

6、inNode *first; ChainNode *p; ; （3 3）詳細(xì)設(shè)計(jì)表示詳細(xì)設(shè)計(jì)表示： Main() childmenu(int manage) /子菜show()/顯示內(nèi)存使用情況 無 /給進(jìn)程pro根據(jù)選擇情況分配內(nèi)存 /最先適應(yīng)法 /最佳適應(yīng)法 /最壞適應(yīng)法 【調(diào)試報(bào)告】 assign_pro(manage) wf(manage,pro,size) ff(manage,pro,size) bf(manage,pro,size) 無 無 【附錄】【附錄】 #include #include #include template class ChainNode friend Cha

7、in; public: char pro; /內(nèi)存塊存放的程序名o 代表操作系統(tǒng)代表空閑區(qū) T size; /內(nèi)存塊的大小 T begin; /內(nèi)存塊起始地址 ChainNode *link; /下一個(gè)內(nèi)存塊 ; template class Chain public: Chain() first=NULL; Chain(); 無 int ff(int manage,char pro,int size); void assign(ChainNode *q,char pro,int size); /動(dòng)態(tài)分配內(nèi)存 int bf(int manage,char pro,int size); /最佳適

8、應(yīng)法 int wf(int manage,char pro,int size); /最壞適應(yīng)法 int delpro(int manage,char pro); /撤銷進(jìn)程，可能要進(jìn)行內(nèi)存塊的合并 void del_pro(int manage); void init(int manage); /內(nèi)存的初始化 void assign_pro(int manage) ; / public: ChainNode *first; ChainNode *p; ; memory *base; /代表內(nèi)存，一個(gè)頭指針,內(nèi)存總大小為 256k /int snum=20,50,30,45,54,52; /vo

9、id assign(memory *q,char pro,int size); void init(int manage) /內(nèi)存的初始化 memory *p,*q; if(base!=NULL) /這一塊是釋放鏈表 p=base; while(p) q=p-next; delete p; p=q; base=new memory; /操作系統(tǒng)，大小 5k,起始地址是 0k base-begin=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; /空閑塊 1，大

10、小 20，起始地址 5k q-begin=5; q-pro=0; 無 q-size=20; p-next=q; p=q; q=new memory; /空閑塊 2，大小 50，起始地址 25k q-begin=25; q-pro=0; q-size=50; p-next=q; p=q; q=new memory; /空閑塊 3，大小 30，起始地址 75k q-begin=75; q-pro=0; q-size=30; p-next=q; p=q; q=new memory; /空閑塊 4，大小 45，起始地址 105k q-begin=105; q-pro=0; q-size=45; p-n

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

12、=p; void assign(memory *q,char pro,int size) /動(dòng)態(tài)，給進(jìn)程 pro 在內(nèi)存塊q-next 上分配 size 大小，q 不為空且 q-next 不為空 /因?yàn)橐M(jìn)行插入操作，所以傳的是要分配內(nèi)存塊的前指針 memory *p=q-next; memory *temp=new memory; temp=new memory; /代表進(jìn)程 pro 的內(nèi)存塊 temp-begin=p-begin; temp-size=size; temp-pro=pro; q-next=temp; if(p-size!=size) /插入的內(nèi)存塊小于空閑區(qū)塊 p-size

13、=p-size-size; p-begin=temp-begin+temp-size; temp-next=p; else /插入的內(nèi)存塊等于空閑區(qū)塊 temp-next=p-next; delete p; int ff(int manage,char pro,int size) /最先適應(yīng)法 memory *p=base; memory *q=p; while(p) /遍歷內(nèi)存找到第一個(gè)適合進(jìn)程 pro 的內(nèi)存塊，保存它的前指針 if(p-sizepro!=0) q=p; p=p-next; else break; if(p=NULL)return 0; /沒找到,返回 0 else /找到

14、了,返回 1 無 if(manage=0)p-pro=pro; /靜態(tài)，直接讓進(jìn)程進(jìn)駐內(nèi)存 else assign(q,pro,size); /動(dòng)態(tài)，調(diào)用 assign 來給進(jìn)程 pro 分配 return 1; int bf(int manage,char pro,int size) /最佳適應(yīng)法 memory *p=base,*temp=NULL,*q,*front; int min=256; while(p) /遍歷內(nèi)存找到最佳的內(nèi)存塊，保存它的前指針 if(p-pro=0&p-size=size&minp-size) min=p-size; front=q; temp=

15、p; q=p; p=p-next; if(temp=NULL)return 0; /沒找到,返回 0 else if(manage=0)temp-pro=pro; /靜態(tài)，直接讓進(jìn)程進(jìn)駐內(nèi)存 else assign(front,pro,size); /動(dòng)態(tài)，調(diào)用 assign 來給進(jìn)程 pro 分配 return 1; int wf(int manage,char pro,int size) /最壞適應(yīng)法 memory *p=base,*temp=NULL,*q,*front; int max=0; while(p) /遍歷內(nèi)存，找到最大的一塊內(nèi)存 if(p-pro=0&p-size=

16、size&maxsize) max=p-size; front=q; temp=p; q=p; p=p-next; 無 if(temp=NULL)return 0; /沒找到,返回 0 else /找到了,返回 1 if(manage=0)temp-pro=pro; /靜態(tài)，直接讓進(jìn)程進(jìn)駐內(nèi)存 else assign(front,pro,size); /動(dòng)態(tài)，調(diào)用 assign 來給進(jìn)程 pro 分配 return 1; int delpro(int manage,char pro) /撤銷進(jìn)程，可能要進(jìn)行內(nèi)存塊的合并 memory *p=base,*q; while(p) /遍歷內(nèi)存

17、，尋找進(jìn)程 pro if(p-pro!=pro) q=p; p=p-next; else break; if(p=NULL)return 0; /沒找到,返回 0 else /找到了,返回 1 if(manage=0)p-pro=0; /靜態(tài)內(nèi)存，直接撤銷進(jìn)程，不用內(nèi)存塊合并 else /動(dòng)態(tài)內(nèi)存，可能要進(jìn)行內(nèi)存合并，分 4 種情況 if(q-pro!=0) if(p-next=NULL|p-next-pro!=0) /前后內(nèi)存塊都不是空閑塊 p-pro=0; else /前內(nèi)存塊不是空閑塊，后內(nèi)存塊是空閑塊 q-next=p-next; p-next-begin=p-begin; p-nex

18、t-size=p-size+p-next-size; delete p; else if(p-next=NULL|p-next-pro!=0) /前內(nèi)存塊是空閑塊，后內(nèi)存塊不是空閑塊 無 q-next=p-next; q-size=q-size+p-size; delete p; else /前后內(nèi)存塊都是空閑塊 q-next=p-next-next; q-size=q-size+p-size+p-next-size; delete p-next; delete p; return 1; void print(char ch,int begin,int size) /根據(jù)內(nèi)存塊內(nèi)容，格式化輸入

19、一塊內(nèi)存塊 switch(ch) case o:printf(操作系統(tǒng)區(qū)t%3dkt%3dk%3dkn,size,begin,begin+size-1);break; case 0 :printf(空閑區(qū) t%3dkt%3dk%3dkn,size,begin,begin+size-1);break; default :printf(進(jìn)程%c t%3dkt%3dk%3dkn,ch,size,begin,begin+size-1);break; void show() /格式化顯示內(nèi)存的儲(chǔ)存情況 memory *p=base; int count=1; cout內(nèi)存現(xiàn)在的儲(chǔ)存情況是：pro,p-b

20、egin,p-size); p=p-next; void del_pro(int manage) /撤銷進(jìn)程 pro，調(diào)用 delpro 無 memory *p=base; char pro,result; coutpro; if(pro=o)cout操作系統(tǒng)不可撤銷endl; else result=delpro(manage,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 size,result=-1; char choose ,pro; coutpro; coutsize; cout請(qǐng)選擇分配算法：1，最先適應(yīng)法。2，最佳適應(yīng)法。3，最壞適應(yīng)法choose; switch(choose) case 1: result=ff(manage,pro,size); break; case 2: result=bf(manage,pro,size); break; case 3: result=wf(manage,pro,size); break; if