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

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

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

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

4、nnode friend chain; public: char pro; /内存块存放的程序名 o 代表操作系统代表空闲区 t size; /内存块的大小 t begin; /内存块起始地址 chainnode *link; /下一个内存块 ; template 分区链表设计： class chain public: chain() first=null; chain(); int ff(int manage,char pro,int size); void assign(chainnode *q,char pro,int size);/动态分配内存 int bf(int manage,ch

5、ar 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 *first; chainnode *p; ; （3）详细设计表示：main() childmenu( intmanage) / 子菜sho

6、w()/显示内存使用情况/ 给进程 pro 根据选择情况分配内存/ 最先适应法 /最佳适应法 /最坏适应法【调试报告】assign_pro(manage) wf(manage,pro,size) ff(manage,pro,size) bf(manage,pro,size) 【附录】#include #include #include template class chainnode friend chain; public: char pro; /内存块存放的程序名o 代表操作系统代表空闲区 t size; /内存块的大小 t begin; /内存块起始地址 chainnode *link;

7、 /下一个内存块 ; template class chain public: chain() first=null; chain(); int ff(int manage,char pro,int size); void assign(chainnode *q,char 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); / 撤销进程，可能要进行内存

8、块的合并void del_pro(int manage); void init(int manage); / 内存的初始化void assign_pro(int manage) ; / public: chainnode *first; chainnode *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!=

9、null) / 这一块是释放链表 p=base; while(p) q=p-next; delete p; p=q; base=new memory; /操作系统，大小5k, 起始地址是0k base-begin=0; base-pro=o; base-size=5; if(manage=0) / 静态内存，初始化7 个内存块，第一个内存块是操作系统 p=base; q=new memory; / 空闲块 1，大小 20，起始地址5k q-begin=5; q-pro=0; q-size=20; p-next=q; p=q; q=new memory; / 空闲块 2，大小 50，起始地址25

10、k q-begin=25; q-pro=0; q-size=50; p-next=q; p=q; q=new memory; / 空闲块 3，大小 30，起始地址75k q-begin=75; q-pro=0; q-size=30; p-next=q; p=q; q=new memory; / 空闲块 4，大小 45，起始地址105k q-begin=105; q-pro=0; q-size=45; p-next=q; p=q; q=new memory; / 空闲块 5，大小 54，起始地址150k q-begin=150; q-pro=0; q-size=54; p-next=q; p=q

11、; q=new memory; / 空闲块 6，大小 52，起始地址204k q-begin=204; q-pro=0; q-size=52; p-next=q; q-next=null; else / 动态内存，只有一个大的内存块 p=new memory; / 空闲块 251k, 起始地址是5k p-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

12、不为空 / 因为要进行插入操作，所以传的是要分配内存块的前指针memory *p=q-next; memory *temp=new memory; temp=new memory; / 代表进程 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

13、; delete p; int ff(int manage,char pro,int size) / 最先适应法 memory *p=base; memory *q=p; while(p) / 遍历内存找到第一个适合进程pro 的内存块，保存它的前指针 if(p-sizepro!=0) q=p; p=p-next; else break; if(p=null)return 0; / 没找到 , 返回 0 else / 找到了 , 返回 1 if(manage=0)p-pro=pro; / 静态，直接让进程进驻内存else assign(q,pro,size); / 动态，调用 assign 来

14、给进程 pro 分配 return 1; int bf(int manage,char pro,int size) / 最佳适应法 memory *p=base,*temp=null,*q,*front; int min=256; while(p) / 遍历内存找到最佳的内存块，保存它的前指针 if(p-pro=0&p-size=size&minp-size) min=p-size; front=q; temp=p; q=p; p=p-next; if(temp=null)return 0; / 没找到 , 返回 0 else if(manage=0)temp-pro=pro;

15、 / 静态，直接让进程进驻内存else assign(front,pro,size); / 动态，调用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&maxsize) max=p-size; front=q; temp=p; q=p; p=p-next; if(temp=null)retu

16、rn 0; / 没找到 , 返回 0 else / 找到了 , 返回 1 if(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) / 遍历内存，寻找进程pro if(p-pro!=pro) q=p; p=p-next; else break; if(p=null)return 0; /

17、没找到 , 返回 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; delete p; else if(p-next=null|p-next-pro!

18、=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 o:printf(操作系统区t%3dkt%3dk%3dkn,size,begin,begi

19、n+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 内存现在的储存情况是：pro,p-begin,p-size); p=p-next; void del_pro(int manage) / 撤销进程 pro ，调用 de

20、lpro memory *p=base; char pro,result; coutpro; if(pro=o)cout操作系统不可撤销endl; else result=delpro(manage,pro); if(result=0)cout没有找到进程 pro, 撤销失败 endl; else cout进程 pro 撤销成功 endl; void assign_pro(int manage) / 给进程 pro 根据选择情况分配内存 int size,result=-1; char choose ,pro; coutpro; coutsize; cout 请选择分配算法：1，最先适应法。 2，最佳适应法。 3，最坏适应法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)cou