北方工业大学计算机操作系统实验2 杨 先 宇.docVIP

操作系统实验报告 学 生 姓 名 杨 先 宇 学 号 班 级 计13-4 实验名称 储存管理 实验序号 实验2 实验日期 2015.12.13 实验人 杨先宇 一、实验目的和要求 请求页式存储管理是一种常用的虚拟存储管理技术。本实验目的是通过请求页式存储管理中页面置换算法的模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。 二、相关背景知识 1. 先进先出页面淘汰算法（FIFO） 地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出（FIFO）法。 优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。[ 2. 最近最久未使用页面淘汰法（LRU） 关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。而内存的虚拟存储管理，是现在最通用，最成功的方式—— 在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。 然而，有利就有弊，虚拟页式存储管理减少了进程所需的内存空间，却也带来了运行时间变长这一缺点：进程运行过程中，不可避免地要把在外存中存放的一些信息和内存中已有的进行交换，由于外存的低速，这一步骤所花费的时间不可忽略。因而，采取尽量好的算法以减少读取外存的次数，也是相当有意义的事情。 三、实验内容 1. 通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 1. 50%的指令是顺序执行的； 2. 25%的指令是均匀分布在前地址部分； 3. 25%的指令是均匀分布在后地址部分； 具体的实施方法是： 1. 在[0，319]的指令地址之间随机选取一起点m； 2. 顺序执行一条指令，即执行地址为m+1的指令； 3. 在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’； 4. 顺序执行一条指令，其地址为m’+1； 5. 在后地址[m’+2, 319]中随机选取一条指令并执行； 6. 重复上述步骤1~5，直到执行320次指令。 2. 将指令序列变换成页地址流，设 1. 页面大小为1K； 2. 用户内存容量为4页到32页； 3. 用户虚存容量为32K。 在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中存放的方式为： 第0条至第9条指令为第0页（对应虚存地址为[0，9]）； 第10条至第19条指令为第1页（对应虚存地址为[10，19]）； …… 第310条至第319条指令为第31页（对应虚存地址为[310，319]）； 按以上方式，用户指令可以组成32页。 3. 计算并输出下述各种算法在不同内存容量下的命中率。 1. 先进先出页面淘汰算法（FIFO） 2. 最近最久未使用页面淘汰法（LRU） 命中率=1 - 页面失效次数/页地址流长度 在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令对应的页不在内存的次数。 4. 随机数产生办法 关于随机数产生办法，Linux或UNIX系统提供函数srand()和rand()，分别进行初始化和产生随机数。 四、关键数据结构与函数的说明 全局变量 const int maxn = 320; //序列个数 const int max = maxn +20;//数组大小 const int maxp = max/10; //最大页数 int inst[max];//指令序列 int page[max];//页地址流 int size; //内存能容纳的页数 bool in[maxp]; //该页是否在内存里，提高效率 int pin[maxp]; //现在在内存里的页 其中in[]数组是为了方便直接判断该页是否在内存里，而不用遍历内存里所有页来判断。fault_n用来记录缺页次数。 2. 随机指令序列的产生 void produce_inst() { int m, n; int num = 0; while(num m