logo资料库

北邮操作系统第二次实验报告.doc

发布时间：2022-06-23 发布人：admin 分类：说明书 资料大小：0.83M 资料格式：doc 举报 版权申诉
第1页 / 共38页
第2页 / 共38页
第3页 / 共38页
第4页 / 共38页
第5页 / 共38页
第6页 / 共38页
第7页 / 共38页
第8页 / 共38页
资料共38页，剩余部分请下载后查看
    实验二 存储管理 2011211319 班 2011211651 张建恒 一．实验目的 通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置 换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面 置换算法的基本思想和实现过程，并比较它们的效率。 二．实验内容 1.实现一个内存管理的伙伴算法，实现内存块申请时的分配和释 放后的回收。 实验准备： 用随机函数仿真进程进行内存申请，并且以较为随机的次序进行 释放。对其碎片进行统计，当申请分配内存失败时区分实际空间不足 和由于碎片而不能满足。 2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1) 最佳置换算法（Optimal） 2) 先进先出法（Fisrt In First Out） 3) 最近最久未使用（Least Recently Used） 4) 最不经常使用法（Least Frequently Used） 其中，命中率＝１－页面失效次数／页地址流长度。 试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的 命中率比较。 实验准备： 本实验中主要的流程：首先用 srand( )和 rand( )函数定义和产生指令序列， 然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中 率。 实验可先从一个具体的例子出发。 （1）通过随机数产生一个指令序列，共 2048 条指令。指令的地址按下述原 则生成： A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，1023]的指令地址之间随机选取一起点 m B：顺序执行一条指令，即执行地址为 m+1 的指令 C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为 m’ D：顺序执行一条指令，其地址为 m’+1 E：在后地址[m’+2，2047]中随机选取一条指令并执行
    F：重复步骤 A-E，直到 2048 次指令 （2）将指令序列变换为页地址流 设：页面大小为 4K； 用户内存容量 4 页到 32 页； 用户虚存容量为 32K。 在用户虚存中，按每 K 存放 64 条指令排列虚存地址，即 2048 条指令在虚 存中的存放方式为： 第 0 条-第 63 条指令为第 0 页（对应虚存地址为[0，63]） 第 64 条-第 127 条指令为第 1 页（对应虚存地址为[64，127]） ……………………………… 第 1984 条-第 2047 条指令为第 31 页（对应虚存地址为[1984，2047]） 按以上方式，用户指令可组成 32 页。 （以此为基础，给出较为一般的情形：仿真内存容量和虚存容量参数变化时 的情形。） 3. 实现内存的 slab 分配器： 其基本思想是：一次向内核获取整数页，slab 根据数据结构的大小进行 划分为一个个小的数据结构，当需要时直接从该链表上摘取一个返回应用程 序，当应用程序释放时，而非真正释放，只需要该空间放回到链表中，当分 散的一页多块又聚集一页时，又会拼成一页，同时判断 slab 空闲的页数，如 果空闲页超过一定的页数，就会向系统释放一定的页数。一个 slab 分配器只 能管理一个指定大小的数据结构分配。 三．实验环境及实验人员 本程序的实验环境为 windows xp 上的 VC6.0，本组成员为张建恒一人。 四．程序设计 1.数据结构： （伙伴系统） (1)节点结构 struct memory_node{ int remain_max; int use; int total; int pid; int flag; struct memory_node *left; struct memory_node *right; }； // 还能分配的最大空间 // 已用掉的大小 // 标记进程号 //是否分裂，是否有孩子,0 为未分配
    typedef struct memory_node *NODE; int pn,;// 页号 int pn;// 面好 int counter;// 一周期内访问该页面次数 int time;// time 为访问时间 (置换算法) (2)页面类型 typedef struct { }pl-type; (3)页面控制结构 Pfc_struct { int pn,pfn; struct pfc_struct *next; }; typedef struct pfc_struct pfc_type; // 初始时的总内存 2.模块结构 （伙伴系统） # define Inital 1024 NODE root=(memory_node *)malloc(1*sizeof(memory_node));// 根节点 int chip=0; int chip_num=0; void inital(NODE node,int num); int memory_alloc(int item,NODE node,int pid); void Lprintf(void); void preoder_print(NODE node); int memory_merge(int pid,NODE node); // 中序遍历打印所有叶结点 // 记录总的碎片大小 // 记录总的碎片数量 // 输出格式控制 // 初始化节点 // 伙伴算法分配 // 伙伴算法合并 pfc_struct[total_vp];// pfc[total_vp] 定义用户进程虚页控制结构 *freepf_head;// 空页面的头指针 *busypf_head;//忙页面的头指针 *freepf_tail;//. 空页面的尾指针 *busypf_tail;//. 忙页面的尾指针 （置换算法） pfc_type pfc_type pfc_type pfc_type pfc_type int a[total_instruction];//指令流数据组 int page[total_instruction];// 每条指令所属页号 int offset[total_instruction]; //每页装入 10 指令后取模运算页号偏移值 int total_pf; int disaffect ; // 失效页面数 void Lprintf(void); void initialize(int total_pf) // 用户进程内存页面数 // 初始化相关数据结构 // 格式控制
    void FIFO(int total_pf) void LRU (int total_pf) void OPT(int total_pf) void LFU(int total_pf) void NUR(int total_pf ) //Fisrt In First Out //Least Recently Used //Optimal //Least Frequently Used //No Used Recently 3.算法流程
    五．实验理论分析 （伙伴算法） Buddy System 是一种经典的内存管理算法。在 Unix 和 Linux 操作系统中 都有用到，起作用是减少存储空间中的空洞，减少碎片，增加利用率。 避免外碎片的方法有两种： A.在某些情况下，连续的页框确实必要； B.即使连续页框的分配不是很必要，它在保持内核页表不变方面所起的 作用也是不容忽视的。假如修改页表，则导致平均访存次数增加，从而 频发刷新 TLB； C.通过 4M 的页可以访问大块连续的物理内存，但相对于 4K 的页使用， TLB 未命中率降低，加快平均访存速度。 Buddy 算法将所有空闲页框分组为 10 个块链表，每个块链表分别包含 1,2,4,8,16,32,64,128,256,512 个连续的页框，每个块的第一个页框的物理 地址使该块大小的整数倍。 回收的过程相反，内核试图把大小为 b 的空闲伙伴合并为一个大小为 2B 的单独块，满足以下两个条件块成为伙伴： A.两个块具有相同的大小，记作 b; B.它们的物理地址连续； C.第一个块的第一个页框的物理地址是 2*b*2^12 的倍数； 为了模拟 Buddy System 算法，我采用了数组的数据结构，并使用了结构 体，用来记录各项数据与标记，虽然不是真正的操作系统所使用的方法， 但成功模拟了插入和回收的过程。在回收时我采用物理上的合并——即 删除实际物理节点，释放空间。然而实际中可能根据需要仅仅是删除标 记项，使之标记成没用过的，从而避免了合并，会提高下一次的插入操 作的效率。 碎片百分比=碎片总大小/总内存大小。 （置换算法） 页式虚拟存储器实现的一个难点是设计页面调度算法，即将新页面调入 内存时，如果内存中所有的物理页都已经分配出去，就要按照某种策略 来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。 页面替换算法主要用于如下几个地方： （1）虚拟存储器，主存页面（或程序段）的替换； （2）Cache 中的块替换； （3）虚拟存储器的快慢表中，快表的替换； （4）虚拟存储器中，用户基地址寄存器的替换。 在虚拟存储器中常用的页面替换算法有如下几种： （1）最优替换算法。上面介绍的几种页面替换算法主要是以主存储器中页 面调度情况的历史信息为依据，它假设将来主存储器中的页面调度情况与过去一
    段时间以内主存储器中的页面调度情况相同。显然，这种假设不总是对的。最好 的算法应该是选择将来最久不被访问的页面作为替换的页面，这种替换算法的命 中率一定是最高的，它就是最优替换算法。 要实现 OPT 算法，唯一的办法是让程序先执行一遍，记录下实际的页地址 流情况。根据这个页地址流才能找到当前要被替换的页面。显然，这样做不现实。 因此，OPT 算法只是一种理想化的算法，然而，它也是一种很有用的算法。实 际上，经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其他条件 一定时，哪一种页面替换算法的命中率与 OPT 算法最为接近，那么，它就是一 种比较好的页面替换算法。 （2）先进先出算法。这种算法选择最优调入主存储器的页面作为被替换的 页面，它的优点是比较容易实现，能够利用主存储器中调度情况的历史信息，但 是，没有反应程序的局部性。因为最先调入主存的页面，很可能也是经常要使用 的页面。 （3）最久没有使用算法。这种算法把近期最久没有被访问的页面作为被替 换的页面。它把 LFU 算法中要记录数量上的“多”与“少”简化成判断“有” 或“无”，因此，实现起来比较简单。 （4）近期最少使用算法。这种算法选择近期最少访问的页面作为被替换的 页面。显然，这是一种非常合理的办法，因为到目前为止最少使用的页面，很可 能将来也最少被访问。该算法既充分利用了主存中页面调度情况的历史信息，又 正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面 设置一个很长的计数器，并且要选择一个固定的始终为它们定时计数。在选择被 替换的页面时，要从所有计数器中找出一个计数值最大的计数器。因此，通常采 用下一种相对比较简单的方法。 六．实验结果：
    分享到：
    赞 收藏

    相关推荐

    资料库

    操作系统

    共收录1433份资料，累计11个分类，关注成员有19位，主要包括：CentOS,MacOS,DOS,Solaris,Ubuntu,Unix,OS,桌面系统,其它,Windows Server,Linux

    热门标签

    CentOS MacOS DOS Solaris Ubuntu Unix OS 桌面系统 其它 Windows Server Linux

    最新资料