操作系统课程设计连续存储空间管理仿真实现

1、 操作系统原理课程设计实践报告题 目: 连续存储空间管理仿真实现 姓 名: 学 院: 专 业: 班 级: 学 号: 指导教师: 职称: 教授 2014年3月 10 日连续存储空间管理仿真实现摘要：连续分配方式，是指为一个用户程序分配一个连续的内存空间。模拟连续存储空间固定分区、可变分区、伙伴系统三种分配方法，其中可变分区采用四种适应算法。整个系统中包括以下功能：查询、分配、回收、退出，并能通过良好的用户界面体现出来，为了深刻理解操作系统中的内存分配技术，动态地为进程分配内存空间，本系统可按照用户分配的作业自动完成内存管理的模拟演示。这对深入理解操作系统内存分配原理，透析作业执行的各种情况，发现

2、和探究新的更加高效的内存管理方式有重大意义。关键字：存储空间管理；固定分区；可变分区；伙伴系统；仿真1 目的及意义存储器是计算机系统的重要组成部分，而如何有效地管理存储器对系统地性能有很大的影响，存储器管理的主要对象是内存。连续分配方式，是指为一个用户程序分配一个连续的内存空间。这种分配方式曾被广泛应用于20世纪6070 年代的os中，它至今仍在内存分配方式中占有一席之地；又可把连续分配方式进一步分为单一连续分配、固定分区分配、动态分区分配以及动态重定位分区分配四种方式。由于在一台计算机中的内存分配过程的不可视性、算法的复杂性、内存情况的多样性和不确定性，使得算法分析与其它算法间的比较相当困难

3、。用模拟系统的方法将整个内存的分配使用的过程可视化，这对深入理解操作系统的存储器管理，透析算法原理，创新算法具有重要意义。2 理论基础 2.1 固定分区理论基础固定分区式分配是最简单的一种可运行多道程序的存储管理方式。这是将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样，把用户空间划分为几个分区，便允许有几道作业并发运行。当有一空闲分区时，便可以再从外存的后备作业队列中选择一个适当大小的作业装入该分区，当该作业结束时，又可再从后备作业队列中找出另一作业调入该分区。1划分分区的方法分区大小不等。为了克服分区大小相等而缺乏灵活性的这个缺点，可把内存区划分成含有多个较小的分

4、区、适量的中等分区及少量的大分区。这样，便可根据程序的大小为之分配适当的分区。2内存分配为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，见图1所示。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。1图1：固定分区分区示意及内存分配图2.2 可变分区理论基础动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、

5、分区分配算法和分区的分配与回收操作这样三个问题。1分区分配中的数据结构 空闲分区链：为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。 2分区分配算法（1） 首次适应算法(first fit)在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。 1（2）

6、 循环首次适应算法(next fit)该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。1 3（3） 最佳适应算法(best fit)所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。1 （4） 最坏适应算法(worst fit)最坏适应分配算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲

7、区分割给作业使用。1 32.3 伙伴系统理论基础12伙伴系统规定，无论已分配分区或空闲分区，其大小均为2 的k 次幂，k 为整数，lkm，其中：21 表示分配的最小分区的大小，2m 表示分配的最大分区的大小，通常2m是整个可分配内存的大小。假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0km)个空闲分区链表。当需要为进程分配一个长度为n 的存储

8、空间时，首先计算一个i 值，使2i1n2i，然后在空闲分区大小为2i 的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i1的空闲分区链表中寻找。若存在2i1 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i 的空闲分区链表中。若大小为2i1的空闲分区也不存在，则需要查找大小为2i2的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为2i1 的两个分区，一个用于分配，一个加入到大小为2i1的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为2

9、i 的两个分区，一个用于分配，一个加入到大小为2i的空闲分区链表中。若仍然找不到，则继续查找大小为2i3的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2k的空闲分区进行k 次分割才能得到所需分区。一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为2i的空闲分区时，若事先已存在2i的空闲分区时，则应将其与伙伴分区合并为大小为2i1的空闲分区，若事先已存在2i1的空闲分区时，又应继续与其伙伴分区合并为大小为2i2的空闲分区，依此类推。33 设计思想及设计功能说明 3.1 固定分区设计思想一开始对于固定分区的连续内存分配我的想法是利用二维数组设计内存分配表，将内存

10、块的起始地址、占用长度、占用标志等信息用数组的一项进行表示，然后我用了40分钟写了100行左右的代码，并且有比较简介清晰的显示界面。但是之后跟其他同学交流，与组员的沟通使我明白，连续内存分配的固定分区方式不是简单地用数组进行标识模拟，这只是理论上的分配，并没有真正的实现内存的分配。借鉴了可变分区的实现，我决定采用链表去做，建立了相应的数据结构，建了一个空闲区链表，一个已分配链表，将手动输入的信息动态建立结点，插入到相对应的链表中，以此来模拟分配内存，由于固定分区是固定大小的内存块，所以要查找比输入所需内存容量大的内存块，有就放置，没有就给出提示。再之后跟老师交流之后，尤其是助教的讲解，使得我们

11、明白，在操作系统中的连续内存分配的过程中是与cpu紧密联系的，动态的建立进程，不确定的生成进程信息，可以被cpu执行的进程才会进入就绪队列，其余的进程则是在后备等待队列中等待系统资源的满足。对此我们小组经过几次激烈的讨论，最终确定代码的各项规范以及数据结构的最终版本，并紧赶时间完成代码，并且将之前的手动输入进程信息改成随机数生成，将之前的文本形式的输出改成图形化可控制输出显示，很好的提高了用户交互的友好性。3.2 可变分区设计思想对于首次适应算法：从空闲分区中从头遍历，低地址开始直到找到一个大于等于申请内存大小的分区，直接在已分区中按照地址递增顺序增加该进程。同时判断该分区长度是否等于零。若等

12、于零，则删除该分区，分配完毕。回收某区时，首先在已分配区中找到该进程，释放该进程所占的分区，并将该分区插入到空闲分区中。插入到空闲分区中时要从头遍历空闲分区判断该分区是否能与相邻分区拼接。拼接有三种情况：与左分区、与右分区、与左右分区拼接，拼接后相应的改变分区的地址和长度。若不能进行拼接，则按照地址递增顺序作为独立分区加入到空闲分区当中，回收完毕。6对于下次适应算法：与首次适应算法类似，不同的是，总是从空闲区的上次扫描结束处顺序查找空闲区表，直到找到第一个能满足长度要求的空闲区为止。图2：首次适应算法及下次适应算法分配内存流程图判断后备等待队列是否有进程n拼接与左结点相邻与右结点相邻y与左右结

13、点相邻n新分区空闲结点n回收内存地址空闲区最大地址拼接可与左结点拼接yy图3：首次适应算法及下次适应算法回收内存流程图对于最优适应算法：分配内存时，先把空闲区按长度递增顺序排列，通过扫描整个空闲区从空闲区中挑选一个能满足进程要求的最小分区进行分配。具体分配过程与最先适应算法相同，分配完毕。回收分去时，现在已分配区中找到该进程，并释放进程节点，首先把该回收的分区插在空闲区的链尾，从头遍历空闲分区，判断左拼接和右拼接，若可以拼接，则直接修改链尾分区的地址和长度，同时删除与之拼接的分区，回收完毕。将空闲区大小排序nyy分区长度-=size进程加入已分配链表在空闲区遍历查找最佳分区分区长度=0分区长度

14、=sizefree分区pcb进入后备waitlistn对于最差适应算法：与最优适应算法类似，不同的是再分配内存时，首先把空闲区按长度递减顺序排列，使分配内存时总是挑选一个最大的空闲区分割给作业使用。3图4：最优适应算法及最差适应算法分配内存流程图nynny回收内存无空闲区链在链尾并遍历空闲区加入空闲区按分区大小排序合并分区合并分区y与右分区相邻 y与左分区相邻 与右分区相邻 n图5：最优适应算法及最差适应算法回收内存流程图3.3 伙伴系统设计思想24假设系统的可利用内存空间容量为2m个字（地址从0到2m-1），则在开始运行时，整个内存区是一个大小为2m的块。空闲将所有的大小相同的空闲块建于一张

15、子表中。每个子表是一个双重链表，这样的链表可能有m+1个，将这m+1个表头指针用向量结构组织成一个表，称为可利用空间表。3程序模拟把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续页框的页框块。最大可以申请1024个连续页框，对应4mb大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。 2要申请一个256个页框的块，先从256个页框的链表中查找空闲块，如果没有，就去512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框

16、的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。分配内存是否空闲？add_full_memory()下一级大小sizestartynn后备wait有进程内存回收pcb进入后备waitlistclk+=sizepcb进入readylist5.2 可变分区算法流程图10：可变分区算法流程图算法开始时，先模拟进程并发环境，将产生的进程送入到pcb表中，选择最先适应算法、最优适应算法、下次适应算法、最差适应算法四个算法中的一个进行开始。这是判断有没有到达进入时间的进程，如果有就开始申请内存，一旦内存足够就对其分配内存，与此同时判断该进程是否已经结束，即持续时间为零如果已

17、经结束就从pcb表中删除该进程，同时系统时间加1。如果内存不足够分配则将该进程加入到后备等待队列中，每次内存回收结束后下一次分配开始前都要检查后备等待队列中是否有进程一旦有就采取先来先服务策略为第一个进程分配空间，对内存的判断还与之前相同。一旦后备等待队列里有，就不再为信赖的进程分配空间而是将其直接加入到等待队列中，重复以上过程直到pcb表中没有进程为止，程序结束。结束systime=pcb-start初始化pcb表pcb进入full_memoryynn后备wait有进程内存回收pcb进入后备waitlistsystime+=size5.3 伙伴系统算法流程图11：伙伴系统算法流程图伙伴系统整

18、体流程与可变分区类似，区别在于分配存储空间的方式和回收存储空间的方式，即具体区别于算法。6 开发调试及运行环境 6.1 开发及运行环境vc+6.06.2 用户手册1. 安装使用（1）在vc+6.0安装路径中找到lib文件夹加入提供的lib文件夹中的项目；（2）在vc+6.0安装路径中找到include文件夹加入提供的include文件夹中的项目；（3）将19211209_李艳伟文件夹拷贝到e盘根目录下；（4） 双击连续存储空间管理仿真系统.exe。2. 操作（1）根据提示输入数据；（2）每一次循环轻敲一下回车，输出数据；（3）按任意键结束。3. 注意事项（1）内存长度设定为1024；（2）伙伴

19、系统建议输入较小的起始时间以及持续时间以免长时间不出现变化。7 功能说明及测试数据分析 7.1 功能说明1. 固定分区图12：随机产生进程显示图图13：固定分区分区图图14：固定分区内存分配图 由随机数产生随机进程，进行分配，每一种颜色代表一个新的进程，在进程占用内存时会将黑色置为内存的颜色这样便于查看。左上角显示的是系统时间，每检索一次时间增加1，与进程的持续时间与开始时间相匹配。2. 可变分区图15：随机产生进程显示图图16：可变分区分区图17：可变分区内存分配图可变分区与固定分区相类似，只不过内存开始不再划分为固定的块，而是根据产生的进程对其按照四种可选的不同算法进行分配，依旧使用颜色表

20、示不同进程，左上角显示系统时间。 3. 伙伴系统图18：伙伴系统内存分配图由于时间不足，所以伙伴系统缺少图形化界面而是采用文字输出，不过为了清晰也按顺序输出内存块占用情况，以及地址及占用其的进程，方便查看。7.2 测试数据及分析设置的内存大小为1024，所以我们选择了许多有代表性的数据：（1）进程1:32；进程2:64；进程3:128；进程4:256（2）进程1:512；进程2:664；进程3:128；进程4:256（3）进程1:256；进程2:256；进程3:256；进程4:256这三组数据可分别测试普通情况不存在内存不足情况下、存在内存占用需进入后备等待队列情况下、以及是否能正确合并伙伴的

21、三种情况，这三组数据都返回了良好的结果。8 存在问题及改进设想8.1 存在问题（1）后备等待队列采取先来先服务的策略，可能会使某些申请小内存的进程长时间滞留。（2）对于同类别的分配算法，没有找到合适的比较优劣的指标。（3）没有实现搬家问题。（4）对于同时到来的进程没有优先级处理，实际变为不同时间的进程处理。8.2改进 （1）采用更优质的算法比如多级反馈队列处理。（2）多查找阅读相关文献找到合适的比较可变分区不同算法优劣的指标。（3）实现搬家问题。（4）更加人性化的界面。9实践体会及心得9.1 工作分配（1）组长：李艳伟 固定分区存储管理、固定分区并发环境模拟 可变分区并发环境模拟（2）组员：李

22、小敏 可变分区存储管理，四个算法分配与回收 最终汇报ppt制作（3）组员：毛新玥 伙伴系统、伙伴系统并发环境模拟 最终汇报ppt制作、撰写实验报告9.2 时间分配2014.2.9-2.15 小组成员复习操作系统知识选择三个题目2014.2.16-2.17 组员线上讨论，确定数据结构、所用语言最终题目及分工2014.2.18-2.22 组员自己寻找资料掌握自己分工部分知识并开始写算法2014.2.23-3.2 继续完善自己算法2014.3.3 与老师交流加入并行2014.3.5 与老师交流增加后续等待队列以及pcb表2014.3.6-3.7 收尾工作以及测试汇报2014.3.7-3.12 撰写实

23、验报告9.3实践体会参考文献：1 汤子丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统（第三版）m.西安：西安电子科技大学出版社.2007 p1212 严蔚敏，吴伟民.数据结构（c语言版）m.北京：清华大学出版社.2007 p2033 孙钟秀，费翔林，骆斌.操作系统教程（第4版）m.北京：高等教育出版社.2008.4 p2374 温秀梅，丁学钧.visual c+面向对象程序设计教程与实验（第二版）m.北京：清华大学出版社.2009.4 p2075 郑晓曦，张虎.一种改进的伙伴系统内存管理方法.j.计算机与数字工程.20086 谭耀铭.操作系统导论.m.光明日报出版社.2008.6核心部分源码： #

24、include #include #include #include typedef struct pnodeint data;int sign;int address;struct pnode *pre;struct pnode *next;pnode,*queueptr;typedef structqueueptr front;queueptr rear;linkqueue;linkqueue ff,ff_fenpei; /空闲区链与已分配区链queueptr ff_ff;queueptr ff_next_ff; /针对下次适应算法，保存每次扫描完未分配区的位置int ff_count=0

25、; /已分配的进程数int ff_total=0; /已分配的分区容量void banjia(linkqueue &ff,linkqueue &ff_fenpei) /搬家queueptr p,q,r;p=ff_fenpei.front;p-address=0;q=p-next;while(q) /修改已分配链表中进程的地址q-address=p-address+p-data;p=q;q=q-next;/q能否=nullr=ff.front; /修改空闲区q=r-next;r-address=p-address+p-data;r-data=10000-ff_total;r-next=null;

26、r-pre=null;ff.rear=r;while(q) /释放原空闲区中其它结点p=q-next;free(q);q=p;void sort(linkqueue &ff) /按分区从小到大排序(针对最佳适应算法)int num=0,t1,t2;queueptr ff_ff;ff_ff=ff.front;while(ff_ff!=null) /确定空闲区中分区的数目num+;ff_ff=ff_ff-next;ff_ff=ff.front;for(int i=0;inum-1;i+) /冒泡排序for(int j=0;jdataff_ff-next-data)t1=ff_ff-data;ff_

27、ff-data=ff_ff-next-data;ff_ff-next-data=t1;t2=ff_ff-address;ff_ff-address=ff_ff-next-address;ff_ff-next-address=t2;ff_ff=ff_ff-next;ff_ff=ff.front;void sort1(linkqueue &ff) /按分区从大到小排序(针对最差适应算法)int num=0,t1,t2;queueptr ff_ff;ff_ff=ff.front;while(ff_ff!=null) /确定空闲区中分区的数目num+;ff_ff=ff_ff-next;ff_ff=ff

28、.front;for(int i=0;inum-1;i+) /冒泡排序for(int j=0;jdatanext-data)t1=ff_ff-data;ff_ff-data=ff_ff-next-data;ff_ff-next-data=t1;t2=ff_ff-address;ff_ff-address=ff_ff-next-address;ff_ff-next-address=t2;ff_ff=ff_ff-next;ff_ff=ff.front;void add_ff(linkqueue &ff_fenpei,queueptr process) /按照地址递增顺序添加进程控制块于已分配链表中

29、if(ff_fenpei.front=null)/已分配链表中空，该进程成为头结点ff_fenpei.front=ff_fenpei.rear=process;elsequeueptr ff_fenpei_ff,ff_fenpei_ff1;ff_fenpei_ff=ff_fenpei.front;while(ff_fenpei_ff!=null)if(process-addressaddress)if(process-addressaddress) /如果小于已分配的最低地址，则成为已分配链表的头结点 process-next=ff_fenpei_ff;process-pre=null;ff_

30、fenpei_ff-pre=process;ff_fenpei.front=process;else /不小于已分配的最低地址 if(ff_fenpei_ff-pre!=null) ff_fenpei_ff-pre-next=process; process-next=ff_fenpei_ff; process-pre=ff_fenpei_ff-pre; break;ff_fenpei_ff1=ff_fenpei_ff; /记录每次比较的结点ff_fenpei_ff=ff_fenpei_ff-next;if(ff_fenpei_ff=null) /大于已分配的最大地址ff_fenpei_ff1

31、-next=process; /进程链在最后process-pre=ff_fenpei_ff1;ff_fenpei.rear=process;void first_fit(linkqueue &ff,queueptr &ff_ff,linkqueue &ff_fenpei) / 最先适应算法int name,size; bool find;while(1)coutname;coutsize;l1:ff_ff=ff.front;find=false;while(ff_ff!=null) /从低地址开始遍历查找if(ff_ff-data=size)queueptr process=(queuept

32、r)malloc(sizeof(pnode);process-address=ff_ff-address;process-data=size;process-sign=name;process-next=null;process-pre=null;add_ff(ff_fenpei,process); / 将进程加入已分配链表ff_ff-data-=size; /分区长度减小ff_ff-address+=size; /分区地址增加find=true; ff_count+; ff_total+=size; if(ff_ff-data=0) /如果该分区已经分配完 则删除结点if(ff_ff-pre

33、=null) /如果该分区是首分区ff.front=ff_ff-next;if(ff.front!=null) /还存在可用分区ff.front-pre=null;else if(ff_ff-next=null) /尾分区ff_ff-pre-next=null; else /在中间ff_ff-pre-next=ff_ff-next; ff_ff-next-pre=ff_ff-pre;free(ff_ff); /删除节点break;ff_ff=ff_ff-next;if(!find) /如果没有合适大小的分区可供使用，则判断是否可以进行移动搬家int rest=10000-ff_total;/剩

34、余的分区长度 if(rest=size) /搬家banjia(ff,ff_fenpei);goto l1; /搬家后继续分配elsecout已无足够空间，请等待!n;break;void next_fit(linkqueue &ff,queueptr &ff_ff,linkqueue &ff_fenpei) /下次适应算法int name,size; bool find;while(1)coutname;coutsize;if(ff_next_ff=null) /循环，又从头结点开始l2:ff_next_ff=ff.front;find=false;while(ff_next_ff!=null

35、) /从低地址开始遍历查找if(ff_next_ff-data=size)queueptr process=(queueptr)malloc(sizeof(pnode);process-address=ff_next_ff-address;process-data=size;process-sign=name;process-next=null;process-pre=null;add_ff(ff_fenpei,process); / 将进程加入相应进程队列ff_next_ff-data-=size; /分区长度减小ff_next_ff-address+=size; /分区地址增加find=t

36、rue; ff_count+; ff_total+=size; if(ff_next_ff-data=0) /如果该分区已经分配完 则删除结点if(ff_next_ff-pre=null) /如果该分区是首分区ff_next_ff=ff_next_ff-next;if(ff_next_ff!=null) /还存在可用分区ff_next_ff-pre=null;else /非首分区if(ff_next_ff-next=null) /尾分区ff_next_ff-pre-next=null; /ff_next_ff=ff.front;else /在中间ff_next_ff-pre-next=ff_n

37、ext_ff-next; ff_next_ff-next-pre=ff_next_ff-pre; free(ff_next_ff);break;ff_next_ff=ff_next_ff-next;if(!find) /如果没有合适大小的分区可供使用，则判断是否可以进行移动搬家int rest=10000-ff_total; if(rest=size) /经移动搬家可以凑出所需空间banjia(ff,ff_fenpei);goto l2; /搬家后继续分配elsecout已无足够空间，请等待!n; break;void best_fit(linkqueue &ff,queueptr &ff_ff,linkqueue &ff_fenpei) / 最佳适应算法sort(ff); /按分区长度大小排序int name,size; bool find;while(1)coutname;coutsize;/ff_ff=ff.front=ff.rear;l3:ff_ff=ff.front;find=false;while(ff