內(nèi)存管理模型的設(shè)計與實現(xiàn)(共15頁)

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

2、利用可用的內(nèi)存進行分配，如果空間不夠時，進行內(nèi)存緊縮或其他方案進行處理）對進程給予指定的內(nèi)存分配；3.從系統(tǒng)開始啟動到多個進程參與申請和運行時，進程最少要有3個以上，每個執(zhí)行申請的時候都要能夠?qū)ο到y(tǒng)當前的內(nèi)存情況進行查看的接口；4.對內(nèi)存的申請進行內(nèi)存分配，對使用過的空間進行回收，對給定的某種頁面調(diào)度進行合理的頁面分配。5.利用不同的顏色代表不同的進程對內(nèi)存的占用情況，動態(tài)更新這些信息。【算法設(shè)計】（1）設(shè)計思想：通過建立一個鏈表，來描述已分配和空閑的內(nèi)存分區(qū)。對于每一個分區(qū)，它可能存放了某個進程，也可能是兩個進程間的空閑區(qū)。鏈表中的每一個結(jié)點，分別描述了一個內(nèi)存分區(qū)，包括它的起始地址、長度、

3、指向下一個結(jié)點的指針以及分區(qū)的當前狀態(tài)。在基于鏈表的存儲管理中,當一個新的進程到來時,需要為它分配內(nèi)存空間,即為它尋找某個空閑分區(qū),該分區(qū)的大小必須大于或等于進程的大小.最先匹配法:假設(shè)新進程的大小為M,那么從鏈表的首節(jié)點開始,將每一個空閑節(jié)點的大小與M相比較,直到找到合適的節(jié)點.這種算法查找的節(jié)點很少,因而速度很快.最佳匹配算法:搜索整個鏈表,將能夠裝得下該進程的最小空閑區(qū)分配出去.最壞匹配法：在每次分配的時候,總是將最大的那個空閑區(qū)切去一部分,分配給請求者.它的依據(jù)是當一個很大的空閑區(qū)被切割成一部分后,可能仍然是一個比較大的空閑區(qū),從而避免了空閑區(qū)越分越小的問題.（2）設(shè)計表示： 分區(qū)結(jié)點

4、設(shè)計： template class ChainNode friend Chain; public: char pro; /內(nèi)存塊存放的程序名o 代表(dibio)操作系統(tǒng)代表(dibio)空閑區(qū) T size; /內(nèi)存(ni cn)塊的大小 T begin; /內(nèi)存塊起始地址 ChainNode *link; /下一個內(nèi)存塊 ; template分區(qū)鏈表設(shè)計： class Chain public: Chain() first=NULL; Chain(); int ff(int manage,char pro,int size); void assign(ChainNode *q,char

5、pro,int size);/動態(tài)分配內(nèi)存 int bf(int manage,char pro,int size);/最佳適應法 int wf(int manage,char pro,int size);/最壞適應法 int delpro(int manage,char pro);/撤銷進程，可能要進行內(nèi)存塊的合并 void del_pro(int manage); void init(int manage);/內(nèi)存的初始化void assign_pro(int manage); /public:ChainNode *first; ChainNode *p; ;（3）詳細設(shè)計表示：Main(

6、) childmenu(int manage)/子菜單蹋?show()/顯示內(nèi)存使用情況 assign_pro(manage) /給進程pro根據(jù)選擇(xunz)情況分配內(nèi)存wf(manage,pro,size)bf(manage,pro,size)ff(manage,pro,size)/最先適應(shyng)法 /最佳適應法 /最壞適應法【調(diào)試(dio sh)報告】【附錄(fl)】#include #include #include template class ChainNode friend Chain; public: char pro; /內(nèi)存塊存放的程序名o 代表(dibio)操作

7、系統(tǒng)代表(dibio)空閑區(qū) T size; /內(nèi)存(ni cn)塊的大小 T begin; /內(nèi)存塊起始地址 ChainNode *link; /下一個內(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);/動態(tài)分配內(nèi)存 int bf(int manage,char pro,int size);/最佳適應法 int wf(int manage,char pr

8、o,int size);/最壞適應法 int delpro(int manage,char pro);/撤銷進程，可能要進行內(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)存，一個頭指針,內(nèi)存總大小為256k/int snum=20,50,30,45,54,52; /void assign(memory *q,char pro,int size);

9、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)，大小(dxio)5k,起始地址是0kbase-begin=0;base-pro=o;base-size=5;if(manage=0)/靜態(tài)(jngti)內(nèi)存，初始化7個內(nèi)存塊，第一個內(nèi)存塊是操作系統(tǒng)p=base;q=new memory;/空閑塊1，大小20，起始(q sh)地址5kq-begin=5;q-pro=0;q-size=20;p-next

10、=q;p=q;q=new memory;/空閑塊2，大小50，起始地址25kq-begin=25;q-pro=0;q-size=50;p-next=q;p=q;q=new memory;/空閑塊3，大小30，起始地址75kq-begin=75;q-pro=0;q-size=30;p-next=q;p=q;q=new memory;/空閑塊4，大小45，起始地址105kq-begin=105;q-pro=0;q-size=45;p-next=q;p=q;q=new memory;/空閑塊5，大小54，起始(q sh)地址150kq-begin=150;q-pro=0;q-size=54;p-ne

11、xt=q;p=q;q=new memory;/空閑(kngxin)塊6，大小52，起始地址204kq-begin=204;q-pro=0;q-size=52;p-next=q;q-next=NULL;else/動態(tài)內(nèi)存，只有(zhyu)一個大的內(nèi)存塊p=new memory;/空閑塊251k,起始地址是5kp-begin=5;p-pro=0;p-size=251;p-next=NULL;base-next=p;void assign(memory *q,char pro,int size)/動態(tài)，給進程pro在內(nèi)存塊q-next上分配size大小，q不為空且q-next不為空/因為要進行插入操

12、作，所以傳的是要分配內(nèi)存塊的前指針memory *p=q-next;memory *temp=new memory;temp=new memory;/代表進程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=p-size-size;p-begin=temp-begin+temp-size;temp-next=p;else/插入(ch r)的內(nèi)存塊等于空閑區(qū)塊temp-next=p-next;delete p;int ff(int manage

13、,char pro,int size)/最先適應(shyng)法memory *p=base;memory *q=p;while(p)/遍歷內(nèi)存找到第一個適合(shh)進程pro的內(nèi)存塊，保存它的前指針if(p-sizepro!=0)q=p;p=p-next;else break;if(p=NULL)return 0;/沒找到,返回0else/找到了,返回1if(manage=0)p-pro=pro;/靜態(tài)，直接讓進程進駐內(nèi)存else assign(q,pro,size);/動態(tài)，調(diào)用assign來給進程pro分配return 1;int bf(int manage,char pro,int

14、size)/最佳適應法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=p;q=p;p=p-next;if(temp=NULL)return 0;/沒找到,返回(fnhu)0else if(manage=0)temp-pro=pro;/靜態(tài)，直接(zhji)讓進程進駐內(nèi)存else assign(front,pro,size);/動態(tài)，調(diào)用assign來給進程(jnchng)pro

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

16、;/動態(tài)，調(diào)用assign來給進程pro分配return 1;int delpro(int manage,char pro)/撤銷進程，可能要進行內(nèi)存塊的合并memory *p=base,*q;while(p)/遍歷內(nèi)存，尋找進程proif(p-pro!=pro)q=p;p=p-next;else break;if(p=NULL)return 0;/沒找到,返回(fnhu)0else/找到了,返回(fnhu)1if(manage=0)p-pro=0;/靜態(tài)內(nèi)存，直接撤銷進程(jnchng)，不用內(nèi)存塊合并else/動態(tài)內(nèi)存，可能要進行內(nèi)存合并，分4種情況if(q-pro!=0)if(p-nex

17、t=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-next-size=p-size+p-next-size;delete p;elseif(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-siz

18、e;delete p-next;delete p;return 1;void print(char ch,int begin,int size)/根據(jù)內(nèi)存塊內(nèi)容(nirng)，格式化輸入一塊內(nèi)存塊switch(ch)case o:printf(操作系統(tǒng)(co zu x tn)區(qū)t%3dkt%3dk%3dkn,size,begin,begin+size-1);break;case 0 :printf(空閑(kngxin)區(qū) t%3dkt%3dk%3dkn,size,begin,begin+size-1);break;default :printf(進程%c t%3dkt%3dk%3dkn,ch,

19、size,begin,begin+size-1);break;void show()/格式化顯示內(nèi)存的儲存情況memory *p=base;int count=1;cout內(nèi)存現(xiàn)在的儲存情況是：pro,p-begin,p-size);p=p-next;void del_pro(int manage)/撤銷進程pro，調(diào)用delpromemory *p=base;char pro,result;coutpro;if(pro=o)cout操作系統(tǒng)不可撤銷endl;elseresult=delpro(manage,pro);if(result=0)cout沒有找到進程(jnchng)pro,撤銷失敗

20、endl;else cout進程(jnchng)pro撤銷成功endl;void assign_pro(int manage)/給進程pro根據(jù)選擇(xunz)情況分配內(nèi)存int size,result=-1;char choose ,pro;coutpro;coutsize;cout請選擇分配算法：1，最先適應法。2，最佳適應法。3，最壞適應法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(result=0)cout進程pro分配失敗endl;else if(result=1)cout進程pro分配成功endl;else cout輸入錯誤endl;void childmenu(int manage)/子菜單char choice