内存打点模型的设计与实现

1、操作系统课程实验报告学生姓名：班学号：指导教师：袁国斌中国地质大学信息工程学院2012年 12月 15日实习题目：内存管理模型的设计与实现【需求规格说明】（1）对于给定的一个存储空间自己设计数据结构进行管理，可以使用单个链表，也可以使用多个链表，自己负责存储空间的所有管理组织，要求采用分页方式（指定单元大小为页，如 4K, 2K,进程申请以页为单位）来组织基本内容；（2）当进程对内存进行空间申请操作时，模型采用一定的策略（如：首先利用可用的内存进行分配，如果空间不够时，进行内存紧缩或其他方案进行处理）对进程给予指定的内存分配；（3）从系统开始启动到多个进程参与申请和运行时，进程最少要有3个以上

2、，每个执行申请的时候都要能够对系统当前的内存情况进行查看的接口；（4）对内存的申请进行内存分配，对使用过的空间进行回收，对给定的某种页面调 度进行合理的页面分配。（5）利用不同的颜色代表不同的进程对内存的占用情况，动态更新这些信息。【算法设计】（1）设计思想：通过建立一个链表， 来描述已分配和空闲的内存分区。 对于每一个分区，它可能存 放了某个进程，也可能是两个进程间的空闲区。 链表中的每一个结点， 分别描述了一个 内存分区，包括它的起始地址、长度、指向下一个结点的指针以及分区的当前状态。在基于链表的存储管理中，当一个新的进程到来时，需要为它分配内存空间，即为它寻找 某个空闲分区，该分区的大小

3、必须大于或等于进程的大小通常的分配算法有最先匹配法最佳匹配法，最快匹配法最先匹配法是一种简单的算法 ，它的基本思路是：假设新进程的大小为 M，那么从链 表的首节点开始，将每一个空闲节点的大小与 M相比较，直到找到合适的节点这种算法 查找的节点很少，因而速度很快最佳匹配算法的基本思路是：搜索整个链表，将能够装得下该进程的最小空闲区分 配出去为了克服最佳匹配算法把空闲区切割的太小的缺点，人们又提出了一种最坏匹配法也就是说，在每次分配的时候，总是将最大的那个空闲区切去一部分，分配给请求者.它的依据是当一个很大的空闲区被切割成一部分后，可能仍然是一个比较大的空闲区，从而避免了空闲区越分越小的问题 （2

4、）设计表示：分区结点设计：templatevclass T>class ChainN ode代表操作系统代表动态分配内存/最佳适应法/最坏适应法/撤销进程，可能要进frie nd Chain<T>public:char pro; /内存块存放的程序名"o"空闲区T size; /内存块的大小T begi n; /内存块起始地址Chai nN ode<T> *li nk; /下一个内存块;templatevclass T>分区链表设计：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);行内存块的合并void del_pro(i nt man age);void init(int manage);/ 内存的初始化void assig n_pro(i nt man age) ;

6、 /public:Chai nN ode<T> *first;Chai nN ode<T> *p;(3)详细设计表示/最先适应法/最佳适应法/最坏适应法【调试报告】回静态分配勰现喙况是起始-结束地址 0k 4k 5k 24k25k 74k7510414 105k149k lsejcaak 2042551(0«F-技返回上一目录（内存将被初始化陵进暮讓舀岛存大小計青选择分配算袪：1,最先适应法。2,最佳适应法。3,最坏适S3)C:Wmd0w55y5tem 32cmd.e5feSB C:Wmdow5sy5tem 32 cmd,exe回S3薛现在的储存情况是:1内睿

7、 険统区 程2闲区大小20 k30k砖k54hS2kJiS論分配、返回上一目录<内存将被初始化起始-结束地址0k 4k5k 24K25k 74k7510414 105k149k lSQkak 204k255k黠蠶麟獭小嗣卄,最先昭2，甌三适应法。3,取坏适SB C:Windowssyste m 3 2crnd. exe动态分配厂千现在的储 < 二篙况是：带操線2 空由区.建立脇呈并分配、播销进槿 亠丄返回上一目录<内存将被初皓化统区大小5k2511<起始结束地址4k5k*255k'0 1嘉弓存 汚内 的请 程程 进进 AA4处聖一 青主冃-吐最先适应法®

8、;取最佳适应法* 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; /内存块存放的程序名"o"代表操作系统代表空闲区T size; /内存块的大小T begi n; /内存块起始地址Chai nN ode<T> *li nk; /下一

9、个内存块;template<class T>class Chai npublic:Chai n()first=NULL;Chai n();int ff(int man age,char pro,i nt size);/动态分配内存/最佳适应法/最坏适应法/撤销进程，可能要进行内存块的合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);/ 内存的初始化void assig n_pro(i nt man age) ; /public:Chai nN ode<T> *first;Chai nN ode<T> *p;,内存总大小为256kmemory *base;/代表内存，一个头指针/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)/ 内存的初始化memory *p,*q;if(base!=NULL)/这一块是释放链表p=base;while(p)q=p->n ext;delete p;p=q;base=new memory; / 操作系统，大小 5k,起始地址是 Okbase->begi n=0;base_>pro='o：base->size=5;if(manage=0) /静态内存，初始化 7个内存块，第一个内存块是操作系统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/动态内存，只有一个大的内存块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不为空配内存块的前指针II动态，给进程 pro在内存块/因为要进行插入操作，所以传的->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代表进程pro的内存块II插入的内存块小于空闲区块p->size=p->size-size; p->begi n=temp->beg in+temp->size; temp->n ext=p; elseII插入的内存块等于空闲区块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)/最先适应法/遍历内存找到第一个适合进程pro的内存块，保存它/没找到，返回0/找到了，返回1/静态，直接让进程进驻内存/动态，调用assign来给进程pro分配/最佳适应法memory *p=base,*temp=NULL,*q,*fr ont;int min=2

17、56;while(p)/遍历内存找到最佳的内存块，保存它的前指针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动态，调用assign来给进程pro分配return 1;int wf(int man age,char pro,i nt size)memory *p=ba

18、se,*temp=NULL,*q,*fr ont;/最坏适应法int max=0;while(p)/遍历内存，找到最大的一块内存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; /静态，直接让进程进驻内存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动态，调用assign来给进程pro分配/撤销进程，可能要进行内存块的合并II遍历内存，寻找进程proif(ma nage=0)p_>pro=0;elseII没找到，返回0II找到了，返回1II静态内存，直接撤销进程，不用内存块合并II动态内存，可能要进行内存合并，分4种情况块是空闲块/前后内存块都

20、不是空闲块/前内存块不是空闲块，后内存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)/前内存块是空闲块，后内存块q_>n ext=p->n ext; q->size=q->size+p->size; delete p; else/前后内存块都是空闲块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/根据内存块内容,格式化输入一块内存块'o':pri ntf("

22、;t%3dkt%3dk%3dkn",size,begi n, begi n+size-1);break; case 0 :pri ntf("空闲区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()/格式化显示内存的储存情况memory *p=base;int coun t=1;cout<<"内存现在的储存情

23、况是："<<endl;printf("块号t 内容tt 大小t起始-结束地址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)/ 撤销进程 pro，调用 delpromemory *p=base;char pro,result;cout<<"请输入你要撤销的进程的名字："cin> >pro;if(pro='o&

24、#39;)cout<<"操作系统不可撤销"<<e ndl;elseresult=delpro(ma nage,pro);if(result=0)cout<<"没有找到进程"<<pro<<",撤销失败"<<endl;else cout<<" 进程"<<pro<<"撤销成功"<<endl;void assign_pro(int manage)/给进程pro根据选择情况分配内存int

25、 size,result=-1;char choose ,pro;cout<<"请输入进程的名字:"cin> >pro;cout<<"请输入进程请求的内存大小:"cin> >size;cout<<"请选择分配算法：1,最先适应法。2，最佳适应法。3,最坏适应法"<<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<<" 进程"<<pro<<"分配失败"<<endl;else if(result=1)cout<<" 进程"<<pro<<