内存管理模型的设计与实现

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

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

3、为它分配内存空间,即为它寻找某个空闲分区,该分区的大小必须大于或等于进程的大小.最先匹配法:假设新进程的大小为M,那么从链表的首节点开始,将每一个空闲节点的大小与M相比较,直到找到合适的节点.这种算法查找的节点很少,因而速度很快.最佳匹配算法:搜索整个链表,将能够装得下该进程的最小空闲区分配出去.最坏匹配法：在每次分配的时候,总是将最大的那个空闲区切去一部分,分配给请求者.它的依据是当一个很大的空闲区被切割成一部分后,可能仍然是一个比较大的空闲区,从而避免了空闲区越分越小的问题.（2）设计表示： 分区结点设计： template<class T> class ChainNode f

4、riend Chain<T> public: char pro; /内存块存放的程序名"o" 代表操作系统代表空闲区 T size; /内存块的大小 T begin; /内存块起始地址 ChainNode<T> *link; /下一个内存块 ; template<class T>分区链表设计： class Chain public: Chain() first=NULL; Chain(); int ff(int manage,char pro,int size); void assign(ChainNode<T> *q,cha

5、r 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);/内存的初始化void assign_pro(int manage); /public:ChainNode<T> *first; ChainNode<T>

6、*p; ;（3）详细设计表示：Main() childmenu(int manage)/子菜单蹋?show()/显示内存使用情况 assign_pro(manage) /给进程pro根据选择情况分配内存wf(manage,pro,size)bf(manage,pro,size)ff(manage,pro,size)/最先适应法 /最佳适应法 /最坏适应法【调试报告】【附录】#include <iostream.h>#include <stdio.h>#include <process.h>template<class T> class Chain

7、Node friend Chain<T> public: char pro; /内存块存放的程序名"o" 代表操作系统代表空闲区 T size; /内存块的大小 T begin; /内存块起始地址 ChainNode<T> *link; /下一个内存块 ; template<class T> class Chain public: Chain() first=NULL; Chain(); int ff(int manage,char pro,int size); void assign(ChainNode<T> *q,char

8、 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);/内存的初始化void assign_pro(int manage); /public:ChainNode<T> *first; ChainNode<T> *

9、p; ;memory *base;/代表内存，一个头指针,内存总大小为256k/int snum=20,50,30,45,54,52; /void assign(memory *q,char pro,int size);void init(int manage)/内存的初始化memory *p,*q;if(base!=NULL)/这一块是释放链表p=base;while(p)q=p->next;delete p;p=q;base=new memory; /操作系统，大小5k,起始地址是0kbase->begin=0;base->pro='o'base->

10、size=5;if(manage=0)/静态内存，初始化7个内存块，第一个内存块是操作系统p=base;q=new memory;/空闲块1，大小20，起始地址5kq->begin=5;q->pro=0;q->size=20;p->next=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;

11、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，起始地址150kq->begin=150;q->pro=0;q->size=54;p->next=q;p=q;q=new memory;/空闲块6，大小52，起始地址204kq->begin=204;q->pro=0;q->size=52;p->next=q;q->next=NUL

12、L;else/动态内存，只有一个大的内存块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)/动态，给进程pro在内存块q->next上分配size大小，q不为空且q->next不为空/因为要进行插入操作，所以传的是要分配内存块的前指针memory *p=q->next;memory *temp=new memory;temp=new memor

13、y;/代表进程pro的内存块temp->begin=p->begin;temp->size=size;temp->pro=pro;q->next=temp;if(p->size!=size)/插入的内存块小于空闲区块p->size=p->size-size;p->begin=temp->begin+temp->size;temp->next=p;else/插入的内存块等于空闲区块temp->next=p->next;delete p;int ff(int manage,char pro,int size)/最先

14、适应法memory *p=base;memory *q=p;while(p)/遍历内存找到第一个适合进程pro的内存块，保存它的前指针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;/静态，直接让进程进驻内存else assign(q,pro,size);/动态，调用assign来给进程pro分配return 1;int bf(int manage,char pro,int size)/最

15、佳适应法memory *p=base,*temp=NULL,*q,*front;int min=256;while(p)/遍历内存找到最佳的内存块，保存它的前指针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;/没找到,返回0else if(manage=0)temp->pro=pro;/静态，直接让进程进驻内存else assign(front,pro,si

16、ze);/动态，调用assign来给进程pro分配return 1;int wf(int manage,char pro,int size)/最坏适应法memory *p=base,*temp=NULL,*q,*front;int max=0;while(p)/遍历内存，找到最大的一块内存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;/没找到,返回0else /找

17、到了,返回1if(manage=0)temp->pro=pro;/静态，直接让进程进驻内存else assign(front,pro,size);/动态，调用assign来给进程pro分配return 1;int delpro(int manage,char pro)/撤销进程，可能要进行内存块的合并memory *p=base,*q;while(p)/遍历内存，寻找进程proif(p->pro!=pro)q=p;p=p->next;else break;if(p=NULL)return 0;/没找到,返回0else/找到了,返回1if(manage=0)p->pro=

18、0;/静态内存，直接撤销进程，不用内存块合并else/动态内存，可能要进行内存合并，分4种情况if(q->pro!=0)if(p->next=NULL|p->next->pro!=0)/前后内存块都不是空闲块p->pro=0;else/前内存块不是空闲块，后内存块是空闲块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-

19、>pro!=0)/前内存块是空闲块，后内存块不是空闲块q->next=p->next;q->size=q->size+p->size;delete p;else/前后内存块都是空闲块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)/根据内存块内容，格式化输入一块内存块switch(ch)case

20、 'o':printf("操作系统区t%3dkt%3dk%3dkn",size,begin,begin+size-1);break;case 0 :printf("空闲区 t%3dkt%3dk%3dkn",size,begin,begin+size-1);break;default :printf("进程%c t%3dkt%3dk%3dkn",ch,size,begin,begin+size-1);break;void show()/格式化显示内存的储存情况memory *p=base;int count=1;cout

21、<<"内存现在的储存情况是："<<endl;printf("块号t 内容tt大小t起始-结束地址n");while(p)printf(" %2d ",count+);print(p->pro,p->begin,p->size);p=p->next;void del_pro(int manage)/撤销进程pro，调用delpromemory *p=base;char pro,result;cout<<"请输入你要撤销的进程的名字："cin>>p

22、ro;if(pro='o')cout<<"操作系统不可撤销"<<endl;elseresult=delpro(manage,pro);if(result=0)cout<<"没有找到进程"<<pro<<",撤销失败"<<endl;else cout<<"进程"<<pro<<"撤销成功"<<endl;void assign_pro(int manage)/给进程pr

23、o根据选择情况分配内存int 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(manage,pro,size);break;ca

24、se '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;