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

1、操作系統(tǒng)課程實(shí)驗(yàn)報(bào)告學(xué)生姓名：尹朋班學(xué)號(hào)：111131指導(dǎo)教師：袁國(guó)斌中國(guó)地質(zhì)大學(xué)信息工程學(xué)院2015年1月4日實(shí)習(xí)題目：內(nèi)存管理模型的設(shè)計(jì)與實(shí)現(xiàn)【需求規(guī)格說(shuō)明】對(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è)為單位)來(lái)組織基本內(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)存分配

2、；3 .從系統(tǒng)開(kāi)始啟動(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ì)使用過(guò)的空間進(jìn)行回收，對(duì)給定的某種頁(yè)面 調(diào)度進(jìn)行合理的頁(yè)面分配。5 .利用不同的顏色代表不同的進(jìn)程對(duì)內(nèi)存的占用情況，動(dòng)態(tài)更新這些信息?！舅惴ㄔO(shè)計(jì)】(1)設(shè)計(jì)思想：通過(guò)建立一個(gè)鏈表，來(lái)描述已分配和空閑的內(nèi)存分區(qū)。對(duì)于每一個(gè)分區(qū)，它可能存放了某個(gè)進(jìn)程，也可能是兩個(gè)進(jìn)程間的空閑區(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)程到來(lái)時(shí)，需

3、要為它分配內(nèi)存空間，即為它尋找 某個(gè)空閑分區(qū)，該分區(qū)的大小必須大于或等于進(jìn)程的大小.最先匹配法：假設(shè)新進(jìn)程白大小為 M,那么從鏈表的首節(jié)點(diǎn)開(kāi)始，將每一個(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ū)越分越小的問(wèn)題 .(2)設(shè)計(jì)表示：分區(qū)結(jié)點(diǎn)設(shè)計(jì)：template<class T> class ChainNo

4、defriend 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();int ff(int manage,char pro,int size);void assign(ChainNode<T> *q,char pro,int size);/

5、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<T> *first;ChainNode<T> *p;(3)詳細(xì)設(shè)計(jì)表示：.childmenM(呼)Vmanashowo/ 制/菜、< 選擇

6、情況分配內(nèi)存二晶愀(咚密11/ff(ma na|M報(bào)口】bf(manage,pro,size)【附錄】 . pro,size)#include'<iostream.h>#include <stdio.h>#include <process.h>template<class T>class ChainNode動(dòng)態(tài)分配內(nèi)存/最佳適應(yīng)法/最壞適應(yīng)法/撤銷進(jìn)程，可能要進(jìn)>/給進(jìn)程pro根據(jù)/wf(manage, 一)friend Chain<T>public:char pro; 內(nèi)存塊存放的程序名"o"代表操

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

8、nage,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<T> *first;ChainNode<T> *p;memory *base;代表內(nèi)存，一個(gè)頭指針，內(nèi)存總大小為256k/int snum尸20,50,30,45,54,52;/void assign(memor

9、y *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,起始地址是 Okbase->begin=O;base->pro='o'base->size=5;if(manage=O) /靜態(tài)內(nèi)存，初始化 7個(gè)內(nèi)存塊，第一個(gè)內(nèi)存塊是操作系統(tǒng)p=base;q=new memory;q->begin

10、=5;q->pro=0;q->size=20; p->next=q;P=q；q=new memory; q->begin=25;q->pro=0;q->size=50; p->next=q;P=q；q=new memory; q->begin=75;q->pro=0;q->size=30; p->next=q;P=q；q=new memory; q->begin=105;q->pro=0;q->size=45; p->next=q;P=q；q=new memory; q->begin=150;q-&

11、gt;pro=0;q->size=54; p->next=q;P=q；q=new memory;/空閑塊1,大小/空閑塊2,大小/空閑塊3,大小/空閑塊4,大小/空閑塊5,大小/空閑塊6,大小20,起始地址5k50,起始地址25k30,起始地址75k45,起始地址105k54,起始地址150k52,起始地址204kq->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,起始地址是 5kp->begin=5; p-

12、>pro=0; p->size=251; p->next=NULL; base->next=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

13、=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/插入的內(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)/遍

14、歷內(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; else/沒(méi)找到，返回0找到了，返回1if(manage=0)p->pro=pro;else assign(q,pro,size);return 1;int bf(int manage,char pro,int size)memory *p=base,*temp=NULL,*q,*front;int min=256;/靜態(tài)，直接讓進(jìn)程進(jìn)駐內(nèi)存/動(dòng)態(tài)，調(diào)用assign來(lái)

15、給進(jìn)程pro分配/最佳適應(yīng)法while(p) /遍歷內(nèi)存找到最佳的內(nèi)存塊，保存它的前指針if(p->pro=0&&p->size>=size&&min>p->size)min=p->size;front=q;temp=p;q=p;p=p->next;if(temp=NULL)return 0; else/沒(méi)找到，返回0if(manage=0)temp->pro=pro; else assign(front,pro,size);return 1;int wf(int manage,char pro,int size)

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

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

18、內(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->next->size=p->size+p->next->size; delete p; else if(p->next=NULL|p->next->pro!=0)/ 前內(nèi)存塊是空閑塊，后內(nèi)存塊不是空閑塊q

19、->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)容，格式化輸入一塊內(nèi)存塊 switch(ch) case 'o':printf(&

20、quot;操作系統(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)程 %ct%3dkt%3dk%3dkn",ch,size,begin,begin+size-1);break; void show()/格式化顯示內(nèi)存的儲(chǔ)存情況 memory *p=base; int count=1; cout<<"內(nèi)存

21、現(xiàn)在的儲(chǔ)存情況是："<<endl;printf("塊號(hào)t內(nèi)容tt 大小t起始-結(jié)束地址n");while(p) printf(" %2d ",count+);print(p->pro,p->beginp>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=

22、9;o')cout<<" 操作系統(tǒng)不可撤銷"<<endl; else result=delpro(manage,pro);if(result=0)cout<<"沒(méi)有找到進(jìn)程"<<pro<<",撤銷失敗"<<endl;else cout<<" 進(jìn)程"<<pro<<"撤銷成功"<<endl;void assign_pro(int manage)/給進(jìn)程pro根據(jù)選擇情況分配

23、內(nèi)存int size,result=-1;char 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)法"<<endl; cin>>choose;switch(choose) case '1':result=ff(manage,pro,size); break;case '

24、;2': result=bf(manage,pro,size); break;case '3':result=wf(manage,pro,size); break;if(result=0)cout<<" 進(jìn)程"<<pro<<"分配失敗"<<endl;else if(result=1)cout<<"進(jìn)程"<<pro<<"分配成功"<<endl;else cout<<"輸入錯(cuò)誤"<<endl;void childmenu(int manage)/ 子菜單char choice;init(manage