操作系统内存buddy算法和页置换算法实验报告.doc

操作系统内存buddy算法和页置换算法实验报告 实验目的 通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 实验内容 实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。 设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1) 最佳置换算法（Optimal） 2) 先进先出法（Fisrt In First Out） 3) 最近最久未使用（Least Recently Used） 4) 最不经常使用法（Least Frequently Used） 其中，命中率＝１－页面失效次数／页地址流长度 试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。 项目要求及分析 要求：用随机函数仿真程序进行内存申请，并且以较为随机的次序进行释放。对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。 分析：总的内存大小固定（默认为2048），申请内存的时候用到随机函数，为了使分配效果更加突出，每次申请内存大小为1——600。每次申请完并成功分配后，得到剩余内存大小availMemory和碎片大小fragment[]，来得到分配失败的原因。分配成功的内存集记录为haveAllo[]，在haveAllo[]中随机抽取内存进行释放。 要求：首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 分析：可以直接忽略指令的内容，按照地址来进行分析，这样是执行更加方便。各个算法总体相同，主要区别就是置换的条件不同，掌握好条件是本实验的关键。 具体实现 4.1 流程图： 分配内存： 释放内存： 2、（1）最佳置换算法（Optimal） （2）先进先出法（Fisrt In First Out） （3）最近最久未使用（Least Recently Used） 4) 最不经常使用法（Least Frequently Used） 4.2数据结构定义： 1、 typedef struct MemoryTree{ struct MemoryTree *left; struct MemoryTree *right; struct MemoryTree *father; int tab; int thisMemory; int used; }TreeNode, *Mtree; 内存节点定义： tab为可用标记，1为可用，0为已用 thisMemory表示此节点共有内存量 used表示已用内存量 int AlloMemory(int toBeAllo, Mtree root) 分配内存 void ReleaseMemory(int toBeRele, Mtree root) 释放内存 void Delete(int a[], int num) 从数组a中删除元素num，该函数用于内存释放。 void ScanMemory(Mtree root) 浏览分配树，以得到可用内存和碎片 2、 void init_addr(void) 初始化指令序列，并按照一定规则执行 void init_page(void) 初始化页表 int isIn(int a) 判断地址为a的指令是否在页中 int find_max(int num, int data[]) 找出data序列中第一个最大值的序号 int find_min(int num, int data[]) 找出data序列中第一个最小值的序号 float optimal(void) optimal算法，返回命中率 float FIFO(void) FIFO算法，返回命中率 float LRU(void) LRU算法，返回命中率 float LFU(void) LFU算法，返回命中率 调试运行结果 假设有3次分配，然后释放。结果如下： 若分配次数增加，假设变为7次，结果如下： 我们发现，出现两次碎片过多引起的分配失败。释放过程只释放5次就结束了，不会释放非配失败的内存： 我们进行对页表大小为1、5、10、15、20、25、32来进行模拟，结果如下： （1）页表大小为1 （2）页表大小为5 （3）页表大小为10 （4）页表大小为15