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

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

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

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

4、 odefriend ChainvT>p ublic:char pro; /内存块存放的程序名"o"代表操作系统代表T size; /内存块的大小空闲区T begi n; /内存块起始地址下一个内存块/动态分配内存最佳适应法 最坏适应法 撤销进程，可能要进Chai nN odevT> *li nk; / ;tempi ate<class T>分区链表设计：class Chai np ublic:Chai n()first=NULL;Chai n();int ff(int man age,char p ro,i nt size);void assig

5、n(Chai nN ode<T> *q,char p ro,i nt size);/ int bf(i nt man age,char p ro,i nt size); int wf(int man age,char p ro,i nt size); int delp ro(i nt man age,char p ro);行内存块的合并void del_ pro(i nt man age);void init(int manage);/ 内存的初始化void assig n_p ro(i nt man age) ; /p ublic:Chai nN ode<T> *fi

6、rst;Chai nN ode<T> *p;(3 )详细设计表示：选择情况分配内存#incl#in clude <>/给进程pro根据mana/bf(man age,pro,size)wf(man age,pro,size)chilnage)show()/最先适应法ff(ma nagger 报pro,size)附录】<>include <>最佳适应法旁坏适应temp late<class T>class Cha inN odefriend Chain<T>public:char pro; /内存块存放的程序名 "

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

8、nage,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> *p;memory *base; / 代表内存，一个头指针 /int snum=20,50,30,45,54,52;/void assign(memory *q,char pro,int size);v

9、oid init(int manage)memory *p,*q; if(base!=NULL) p=base;while(p)q=p->next; delete p; p=q;/ 内存的初始化/ 这一块是释放链表/ 动态分配内存 最佳适应法 最坏适应法 撤销进程，可能要进行内存块的, 内存总大小为 256k6，base=new memory; / base->begin=0; base->pro='o' base->size=5;if(manage=0) / p=base;q=new memory; q->begin=5; q->pro=0

10、; 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;操作系统，大小 5k, 起始地址是 0k静态内存，初始化 7 个内存块，第一个内存块是操作系统/空闲块空闲块空闲块1，2，3，大小 20，大小 50，大小 30，起始地址起始地址起始地址5k25k75kp=q;q=new memory; q

11、->begin=105; q->pro=0; q->size=45; p->next=q;p=q;/空闲块4，大小 45，起始地址105kq=new memory; q->begin=150; q->pro=0; q->size=54; p->next=q;/空闲块5，大小 54，起始地址150kp=q; q=new memory; q->begin=204; q->pro=0; q->size=52; p->next=q;/空闲块大小 52，起始地址204kq->next=NULL; else/ 动态内存，只有一个

12、大的内存块/ 空闲块 251k, 起始地址是 5kp=new memory; p->begin=5; p->pro=0; p->size=251; p->next=NULL; base->next=p; void assign(memory *q,char pro,int size) 上分配 size 大小， q 不为空且 q->next 不为空 是要分配内存块的前指针 memory *p=q->next; memory *temp=new memory; temp=new memory; temp->begin=p->begin; tem

13、p->size=size; temp->pro=pro; q->next=temp; if(p->size!=size) / 代表进程动态，给进程 pro 在内存块 q->next/ 因为要进行插入操作，所以传的pro 的内存块/ 插入的内存块小于空闲区块p->size=p->size-size; p->begin=temp->begin+temp->size; temp->next=p; else/ 插入的内存块等于空闲区块/ 最先适应法/ 遍历内存找到第一个适合进程 pro 的内存块，保存temp->next=p-&g

14、t;next;delete p;int ff(int manage,char pro,int size)memory *p=base;memory *q=p;while(p)它的前指针 if(p->size<size|p->pro!=0) q=p; p=p->next;else break; if(p=NULL)return 0; else if(manage=0)p->pro=pro; else assign(q,pro,size); return 1;int bf(int manage,char pro,int size)memory *p=base,*tem

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

16、=pro; / else assign(front,pro,size); return 1;int wf(int manage,char pro,int size)/ 没找到 , 返回 0静态，直接让进程进驻内存/ 动态，调用 assign 来给进程 pro 分配/ 最坏适应法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; fr

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

18、o)q=p; p=p->next;else break;if(p=NULL)return 0;elseif(manage=0)p->pro=0; else/没找到 , 返回 0找到了 , 返回 1静态内存，直接撤销进程，不用内存块合并动态内存，可能要进行内存合并，分 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->

19、;begin;p->next->size=p->size+p->next->size;delete p; else/ 前内存块是空闲块，后内存if(p->next=NULL|p->next->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

20、; delete p->next;delete p; return 1;/ 根据内存块内容，格式化输入一块内void print(char ch,int begin,int size) 存块 switch(ch) case '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("进

21、程 %ct%3dkt%3dk%3dkn",ch,size,begin,begin+size-1);break;/ 格式化显示内存的储存情况void show()memory *p=base;int count=1;cout<<" 内存现在的储存情况是： "<<endl;printf(”块号t 内容tt 大小t起始-结束地址n");while(p)printf(" %2d ",count+); print(p->pro,p->begin,p->size); p=p->next;/ 撤销进程

22、 pro ，调用 delprovoid del_pro(int manage)memory *p=base; char pro,result;H.cout<<" 请输入你要撤销的进程的名字： cin>>pro;if(pro='o')cout<<" 操作系统不可撤销 "<<endl; elseresult=delpro(manage,pro);"<<endl;if(result=0)cout<<" 没有找到进程 "<<pro<<

23、;", 撤销失败 "<<endl; else cout<<" 进程 "<<pro<<" 撤销成功/ 给进程 pro 根据选择情况分配内存 void assign_pro(int manage) int size,result=-1; char choose ,pro;cout<<" 请输入进程的名字 :" cin>>pro;cout<<" 请输入进程请求的内存大小 :" cin>>size;2，最佳适应法。 3

24、，最坏适应法 "<<endl;cout<<" 请选择分配算法： 1，最先适应法。 cin>>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;/ 子菜单静态分配 "<<endl;void childmenu(int manage)char