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

年4月19日内存管理模型的设计与实现文档仅供参考操作系统课程实验报告学生姓名：尹朋班学号：111131指导教师：袁国斌中国地质大学信息工程学院1月4日

实习题目：内存管理模型的设计与实现【需求规格说明】对内存的可变分区申请采用链表法管理进行模拟实现。要求：1.对于给定的一个存储空间自己设计数据结构进行管理，能够使用单个链表，也能够使用多个链表，自己负责存储空间的所有管理组织，要求采用分页方式（指定单元大小为页，如4K，2K，进程申请以页为单位）来组织基本内容；2.当进程对内存进行空间申请操作时，模型采用一定的策略（如：首先利用可用的内存进行分配，如果空间不够时，进行内存紧缩或其它方案进行处理）对进程给予指定的内存分配；3.从系统开始启动到多个进程参与申请和运行时，进程最少要有3个以上，每个执行申请的时候都要能够对系统当前的内存情况进行查看的接口；4.对内存的申请进行内存分配，对使用过的空间进行回收，对给定的某种页面调度进行合理的页面分配。5.利用不同的颜色代表不同的进程对内存的占用情况，动态更新这些信息。【算法设计】（1）设计思想：经过建立一个链表，来描述已分配和空闲的内存分区。对于每一个分区，它可能存放了某个进程，也可能是两个进程间的空闲区。链表中的每一个结点，分别描述了一个内存分区，包括它的起始地址、长度、指向下一个结点的指针以及分区的当前状态。在基于链表的存储管理中,当一个新的进程到来时,需要为它分配内存空间,即为它寻找某个空闲分区,该分区的大小必须大于或等于进程的大小.最先匹配法:假设新进程的大小为M,那么从链表的首节点开始,将每一个空闲节点的大小与M相比较,直到找到合适的节点.这种算法查找的节点很少,因而速度很快.最佳匹配算法:搜索整个链表,将能够装得下该进程的最小空闲区分配出去.最坏匹配法：在每次分配的时候,总是将最大的那个空闲区切去一部分,分配给请求者.它的依据是当一个很大的空闲区被切割成一部分后,可能依然是一个比较大的空闲区,从而避免了空闲区越分越小的问题.

（2）设计表示：分区结点设计：template<classT>classChainNode{ friendChain<T>;public: charpro;//内存块存放的程序名"o"代表操作系统‘’代表空闲区 Tsize;//内存块的大小 Tbegin;//内存块起始地址 ChainNode<T>*link;//下一个内存块};template<classT>分区链表设计：classChain{public: Chain() {first=NULL;}~Chain();intff(intmanage,charpro,intsize); voidassign(ChainNode<T>*q,charpro,intsize);//动态分配内存 intbf(intmanage,charpro,intsize); //最佳适应法 intwf(intmanage,charpro,intsize); //最坏适应法 intdelpro(intmanage,charpro); //撤销进程，可能要进行内存块的合并 voiddel_pro(intmanage);voidinit(intmanage); //内存的初始化 voidassign_pro(intmanage) ;//public: ChainNode<T>*first; ChainNode<T>*p;};（3）详细设计表示：Main()Main()childmenu(childmenu(intmanage) //子菜单蹋?show()//显示内存使用情况show()//显示内存使用情况assign_pro(manage)assign_pro(manage)//给进程pro根据选择情况分配内存wf(manage,pro,size)bf(manage,pro,size)ff(manage,pro,size)wf(manage,pro,size)bf(manage,pro,size)ff(manage,pro,size)//最先适应法//最佳适应法//最坏适应法【调试报告】 【附录】#include<iostream.h>#include<stdio.h>#include<process.h>template<classT>classChainNode{ friendChain<T>;public: charpro;//内存块存放的程序名"o"代表操作系统‘’代表空闲区 Tsize;//内存块的大小 Tbegin;//内存块起始地址 ChainNode<T>*link;//下一个内存块};template<classT>classChain{public: Chain() {first=NULL;}~Chain();intff(intmanage,charpro,intsize); voidassign(ChainNode<T>*q,charpro,intsize); //动态分配内存 intbf(intmanage,charpro,intsize); //最佳适应法 intwf(intmanage,charpro,intsize); //最坏适应法 intdelpro(intmanage,charpro); //撤销进程，可能要进行内存块的合并 voiddel_pro(intmanage);voidinit(intmanage); //内存的初始化 voidassign_pro(intmanage) ;//public: ChainNode<T>*first; ChainNode<T>*p;};memory*base; //代表内存，一个头指针,内存总大小为256k//intsnum[]={20,50,30,45,54,52};//voidassign(memory*q,charpro,intsize);voidinit(intmanage) //内存的初始化{ memory*p,*q; if(base!=NULL) //这一块是释放链表 { p=base; while(p) { q=p->next; deletep; p=q; } } base=newmemory;//操作系统，大小5k,起始地址是0k base->begin=0; base->pro='o'; base->size=5; if(manage==0) //静态内存，初始化7个内存块，第一个内存块是操作系统 { p=base; q=newmemory; //空闲块1，大小20，起始地址5k q->begin=5; q->pro=0; q->size=20; p->next=q; p=q; q=newmemory; //空闲块2，大小50，起始地址25k q->begin=25; q->pro=0; q->size=50; p->next=q; p=q; q=newmemory; //空闲块3，大小30，起始地址75k q->begin=75; q->pro=0; q->size=30; p->next=q; p=q; q=newmemory; //空闲块4，大小45，起始地址105k q->begin=105; q->pro=0; q->size=45; p->next=q; p=q; q=newmemory; //空闲块5，大小54，起始地址150k q->begin=150; q->pro=0; q->size=54; p->next=q; p=q; q=newmemory; //空闲块6，大小52，起始地址204k q->begin=204; q->pro=0; q->size=52; p->next=q; q->next=NULL; } else //动态内存，只有一个大的内存块 { p=newmemory; //空闲块251k,起始地址是5k p->begin=5; p->pro=0; p->size=251; p->next=NULL; base->next=p; }}voidassign(memory*q,charpro,intsize) //动态，给进程pro在内存块q->next上分配size大小，q不为空且q->next不为空{ //因为要进行插入操作，因此传的是要分配内存块的前指针 memory*p=q->next; memory*temp=newmemory; temp=newmemory; //代表进程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; deletep; }}intff(intmanage,charpro,intsize) //最先适应法{ memory*p=base; memory*q=p; while(p) //遍历内存找到第一个适合进程pro的内存块，保存它的前指针 { if(p->size<size||p->pro!=0) { q=p; p=p->next; } elsebreak; } if(p==NULL)return0; //没找到,返回0 else //找到了,返回1 { if(manage==0)p->pro=pro; //静态，直接让进程进驻内存 elseassign(q,pro,size); //动态，调用assign来给进程pro分配 } return1; }intbf(intmanage,charpro,intsize) //最佳适应法{ memory*p=base,*temp=NULL,*q,*front; intmin=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)return0; //没找到,返回0 else { if(manage==0)temp->pro=pro; //静态，直接让进程进驻内存 elseassign(front,pro,size); //动态，调用assign来给进程pro分配 } return1;}intwf(intmanage,charpro,intsize) //最坏适应法{ memory*p=base,*temp=NULL,*q,*front; intmax=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)return0; //没找到,返回0 else //找到了,返回1 { if(manage==0)temp->pro=pro; //静态，直接让进程进驻内存 elseassign(front,pro,size); //动态，调用assign来给进程pro分配 } return1;}intdelpro(intmanage,charpro) //撤销进程，可能要进行内存块的合并{ memory*p=base,*q; while(p) //遍历内存，寻找进程pro { if(p->pro!=pro) { q=p; p=p->next; } elsebreak; } if(p==NULL)return0; //没找到,返回0 else //找到了,返回1 { if(manage==0)p->pro=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; deletep; } } else { if(p->next==NULL||p->next->pro!=0) //前内存块是空闲块，后内存块不是空闲块 { q->next=p->next; q->size=q->size+p->size; deletep; } else //前后内存块都是空闲块 { q->next=p->next->next; q->size=q->size+p->size+p->next->size; deletep->next; deletep; } } } } return1;}voidprint(charch,intbegin,intsize) //根据内存块内容，格式化输入一块内存块{ switch(ch) { case'o':printf("操作系统区\t%3dk\t%3dk~%3dk\n",size,begin,begin+size-1);break; case0:printf("空闲区 \t%3dk\t%3dk~%3dk\n",size,begin,begin+size-1);break; default:printf("进程%c\t%3dk\t%3dk~%3dk\n",ch,size,begin,begin+size-1);break; }}voidshow() //格式化显示内存的储存情况{ memory*p=base; intcount=1; cout<<"内存现在的储存情况是："<<endl; printf("块号\t内容\t\t大小\t起始-结束地址\n"); while(p) { printf("%2d",count++); print(p->pro,p->begin,p->size); p=p->next; }}voiddel_pro(intmanage) //撤销进程pro，调用delpro{ memory*p=base; charpro,result; cout<<"请输入你要撤销的进程的名字："; cin>>pro; if(pro=='o')cout<<"操作系统不可撤销"<<endl; else { result=delpro(manage,pro); if(result==0)cout<<"没有找到进程"<<pro<<",撤销失败"<<endl; elsecout<<"进程"<<pro<<"撤销成功"<<endl; }}voidassign_pro(intmanage) //给进程pro根据选择情况分配内存{ intsize,result=-1; charchoose,pro; cout<<"请输入进程的名字:"; cin>>pro; cout<<"请输入进程请求的内存大小:"; cin>>size; cout<<"请选择分配算法：1，最先适应法。2，最佳适应法。3，最坏适应法"<<endl; 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(r