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

1、操作系統(tǒng)課程實(shí)驗(yàn)報(bào)告學(xué)生姓名:尹朋班學(xué)號(hào)：111131指導(dǎo)教師：袁國斌中國地質(zhì)大學(xué)信息工程學(xué)院2015年1月4日實(shí)習(xí)題目：內(nèi)存管理模型的設(shè)計(jì)與實(shí)現(xiàn)【需求規(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ǔ)空間的所有管理組織，要求采用分頁方式（指定單元大小為頁，如 4K, 2K,進(jìn)程申請(qǐng)以頁為單位）來組織基本內(nèi)容;2. 當(dāng)進(jìn)程對(duì)內(nèi)存進(jìn)行空間申請(qǐng)操作時(shí)，模型采用一定的策略（如:首先利用可用的內(nèi)存進(jìn)行分配，如果空間不夠時(shí)，進(jìn)行內(nèi)存緊縮或其他方案進(jìn)行處理）對(duì)進(jìn)程給予指定的內(nèi)存分配;3.

2、從系統(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ì)給定的某種頁面調(diào)度進(jìn)行合理的頁面分配。5.利用不同的顏色代表不同的進(jìn)程對(duì)內(nèi)存的占用情況，動(dòng)態(tài)更新這些信息?！舅惴ㄔO(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)存

3、空間，即為它尋找某個(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ū)被切割成一部分后,可能仍然是一個(gè)比較大的空閑區(qū) , 從而避免了空閑區(qū)越分越小的問題 .2）設(shè)計(jì)表示：分區(qū)結(jié)點(diǎn)設(shè)計(jì)：template<class T>class ChainNod

4、efriend Chain<T>public:char pro; /內(nèi)存塊存放的程序名 "o"代表操作系統(tǒng)'代表空閑區(qū)T size; /內(nèi)存塊的大小T begin; /內(nèi)存塊起始地址ChainNode<T> *link; /下一個(gè)內(nèi)存塊;template<class T>分區(qū)鏈表設(shè)計(jì)：class Chainpublic:Chain()first=NULL;Chain();動(dòng)態(tài)分配內(nèi)存最佳適應(yīng)法最壞適應(yīng)法 撤銷進(jìn)程，可能要進(jìn)行內(nèi)存int ff(int manage,char pro,int size);/void assign(Ch

5、ainNode<T> *q,char pro,int size);/ int bf(int manage,char pro,int size); int wf(int manage,char pro,int size);int delpro(int manage,char pro);塊的合并void del_pro(int manage);void init(int manage); / 內(nèi)存的初始化 void assign_pro(int manage) ; / public:ChainNode<T> *first;ChainNode<T> *p;/給進(jìn)程

6、pro根據(jù)選調(diào)試報(bào)告】 【附錄】ff(ma na/最壞適應(yīng)/最先適應(yīng)法#in elude <>#in elude <>#in elude <>temp late<class T>class Cha inN odefriend Chain<T>p ublic:char pro; /內(nèi)存塊存放的程序名"o"代表操作系統(tǒng)代表空閑區(qū)T size; /內(nèi)存塊的大小T beg in; /內(nèi)存塊起始地址下一個(gè)內(nèi)存塊Chai nN ode<T> *li nk; /;template<class T>clas

7、s Chainpublic:Chain() first=NULL;Chain();/ 動(dòng)態(tài)分配int ff(int manage,char pro,int size);void assign(ChainNode<T> *q,char pro,int size);內(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

8、);void init(int manage);/內(nèi)存的初始化; /void assign_pro(int manage)public:ChainNode<T> *first;ChainNode<T> *p;memory *base;/ 代表內(nèi)存，一個(gè)頭指針 , 內(nèi)存總大小為 256k/int snum=20,50,30,45,54,52;/void assign(memory *q,char pro,int size);void init(int manage) / 內(nèi)存的初始化memory *p,*q;if(base!=NULL)/ 這一塊是釋放鏈表p=base;w

9、hile(p)q=p->next;delete p;p=q;base=new memory; / 操作系統(tǒng)，大小 5k, 起始地址是 0kbase->begin=0;base->pro='o'base->size=5;if(manage=0) / 靜態(tài)內(nèi)存，初始化 7 個(gè)內(nèi)存塊，第一個(gè)內(nèi)存塊是操作 系統(tǒng)z 一 SAb6H0dAb-bHdP4X UAdz一 SAb6H0dAb&h£6 qAb- seqHd6H0dAb&OLHU 一 6 qAbMSOL 9寸 wy寸 = moeEMUHb-bHdP4X UAd-oeH z 一 SAb

10、6H0dAb-bHdP4X UAdq->size=45;p->next=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, 起

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

12、存塊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;else/ 插入的內(nèi)存塊等于空閑區(qū)塊temp->next=p->next;/ 最先適應(yīng)法delete p;int ff(int manage,char pro,int size)memory *p=base;memory

13、*q=p;while(p)/ 遍歷內(nèi)存找到第一個(gè)適合進(jìn)程 pro 的內(nèi)存塊，保存它的前指針if(p->size<size|p->pro!=0)q=p;p=p->next;else break;if(p=NULL)return 0;/ 沒找到,返回 0else/ 找到了,返回 1if(manage=0)p->pro=pro;直接讓進(jìn)程進(jìn)駐內(nèi)存else assign(q,pro,size);/ 動(dòng)態(tài)，調(diào)用 assign 來給進(jìn)程 pro 分temp=p;/ 最佳適應(yīng)法return 1;int bf(int manage,char pro,int size)memory

14、 *p=base,*temp=NULL,*q,*front;int min=256;while(p)/ 遍歷內(nèi)存找到最佳的內(nèi)存塊，保存它的前指if(p->pro=0&&p->size>=size&&min>p->size)min=p->size;front=q;temp=p;if(temp=NULL)return 0;/沒找到,返回 0elseif(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

15、 分配/ 最壞適應(yīng)法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&&max<p->size)max=p->size;front=q;q=p;p=p->next;if(temp=NULL)return 0;/ 沒找到 , 返回else直接讓進(jìn)程進(jìn)駐內(nèi)存/ 找到了 , 返回 1if(mana

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

17、 動(dòng)態(tài)內(nèi)存，可能要進(jìn)行內(nèi)存合并，分 4 種情況/ 前后內(nèi)存塊都不if(q->pro!=0)if(p->next=NULL|p->next->pro!=0)是空閑塊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;if(p->next=NULL|p->next->pro!=0)/ 前內(nèi)存塊是空閑else塊，

18、后內(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;/ 根據(jù)內(nèi)存塊內(nèi)容，格式void print(char ch,int begin,int size)化輸入一塊內(nèi)存塊switch(ch)case 'o':printf

19、(" 操作系統(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<<"

20、內(nèi)存現(xiàn)在的儲(chǔ)存情況是： "<<endl;printf（”塊號(hào)t 內(nèi)容tt 大小t起始-結(jié)束地址n"）;while(p)print(p->pro,p->begin,p->size);p=p->next;void del_pro(int manage)/ 撤銷進(jìn)程 pro ，調(diào)用delpromemory *p=base;char pro,result;cout<<" 請(qǐng)輸入你要撤銷的進(jìn)程的名字： "cin>>pro;if(pro='o')cout<<" 操作系統(tǒng)

21、不可撤銷 "<<endl;elseresult=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;ch

22、ar choose ,pro;cout<<" 請(qǐng)輸入進(jìn)程的名字 :"cin>>pro;cout<<" 請(qǐng)輸入進(jìn)程請(qǐng)求的內(nèi)存大小 :"cin>>size;cout<<" 請(qǐng)選擇分配算法： 1，最先適應(yīng)法。 2，最佳適應(yīng)法。 3，最壞適應(yīng)法"<<e ndl;cin>>choose;switch(choose)case '1':result=ff(manage,pro,size);break;case '2':result=b

23、f(manage,pro,size);break;case '3':result=wf(manage,pro,size);break;else if(result=1)cout<<" 進(jìn)程 "<<pro<<" 分配成功 "<<endl;else cout<<" 輸入錯(cuò)誤 "<<endl;void childmenu(int manage)char choice;init(manage);while(1)system("cls");/ 子菜單靜態(tài)分配 "