操作系统存储管理实验报告

《操作系统存储管理实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京邮电大学操作系统实验实验报告实验日期：2010-12-20实验名称：存储管理一、实验目的2二、实验内容2三、实验分析2◆对于伙伴算法2◆对于虚拟存储区和内存工作区的不同算法3四、编程实现3◆伙伴算法3◇原理3◇伙伴的概念3◇内存的释放4◇位图法4◇伪代码4◇运行结果演示5◆最佳置换算法5◇基本思想5◇伪代码实现5◇运行结果演示6◆先进先出法（FisrtInFirstOut）6◇基本思想6◇伪代码实现6◇运行结果演示7◆最近最久未使用（LeastRecentlyUsed）7◇基本思想7◇伪代码实现7◇运行结果演示7◆最不经常使用法（LeastFrequentlyUsed）

2、8◇基本思想8◇伪代码实现8◇运行结果演示8◆最近未使用法（NoUsedRecently）8◇基本思想8◇伪代码实现9◇运行结果演示9五、各种算法运行综合比较9六、实验心得10七、程序源代码11◆伙伴算法11◆最佳置换算法19◆先进先出法22◆最近最久未使用24◆最不经常使用法27◆最近未使用法30一、实验目的通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、实验内容◆实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。◆设计

3、一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1)最佳置换算法（Optimal）2)先进先出法（FisrtInFirstOut）3)最近最久未使用（LeastRecentlyUsed）4)最不经常使用法（LeastFrequentlyUsed）5)最近未使用法（NoUsedRecently）其中，命中率＝１－页面失效次数／页地址流长度。试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。三、实验分析◆对于伙伴算法，用随机函数仿真进程进行内存申请，并且以较为随机的次序进行释放。对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎

4、片而不能满足。◆对于虚拟存储区和内存工作区的不同算法，其中主要的流程：首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。实验可先从一个具体的例子出发。（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的B：25%的指令是均匀分布在前地址部分C：25%的指令是均匀分布在后地址部分具体的实施方法是：A：在[0，319]的指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1的指令C：在前地址[0,m+1]中随机选取一条指令并执行，该指

5、令的地址为m’D：顺序执行一条指令，其地址为m’+1E：在后地址[m’+2，319]中随机选取一条指令并执行F：重复步骤A-E，直到320次指令（2）将指令序列变换为页地址流设：页面大小为1K；用户内存容量4页到32页；用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条-第9条指令为第0页（对应虚存地址为[0，9]）第10条-第19条指令为第1页（对应虚存地址为[10，19]）………………………………第310条-第319条指令为第31页（对应虚存地址为[310，319]）按以上方式，用户指令可组成32页。四、编程

6、实现◆伙伴算法◇原理：伙伴算法把所有的空闲页面分为10个块组，每组中块的大小是2的幂次方个页面，例如，第0组中块的大小都为2 0（1个页面），第1组中块的大小为都为21（2个页面），第9组中块的大小都为29（512个页面）。也就是说，每一组中块的大小是相同的，且这同样大小的块形成一个链表。◇伙伴的概念，满足以下三个条件的称为伙伴：(1)两个块大小相同(2)两个块地址连续(3)两个块必须是从同一个大块中分离出来的。◇内存的释放，是分配的逆过程，也可以看作是伙伴的合并过程。当释放一个块时，先在其对应的链表中考查是否有伙伴存在，如果没有伙伴块，就直接把要释放的块挂入链表头；如果有

7、，则从链表中摘下伙伴，合并成一个大块，然后继续考查合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块(2个页面)。◇位图法，通常我们用位图来实现整个过程中，位图的某一位对应两个互为伙伴的块，为l表示其中一块分配出去了，为0表示两块都空闲。伙伴算法中无论是分配还是释放内存块都只对相应的位图位进行异或操作。分配内存时对位图的操作是为释放过程服务，释放过程根据位图判断伙伴是否存在，如果对相应位的异或操作得1，则没有伙伴可以合并，如果异或操作得0，就进行合并，并且继续按这种方式合并伙伴，直到不能