实验二报告-杨先宇

1、北方工业大学操作系统实验报告学 生 姓 名 杨 先宇 学 号班 级 计13-4 实验名称储存管理实验序号2实验日期2015.12.14实验人杨先宇一、实验目的和要求请求页式存储管理是一种常用的虚拟存储管理技术。本实验目的是通过请求页式存储管理中页面置换算法的模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。二、相关背景知识1.先进先出页面淘汰算法（FIFO）地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页

2、面置换算法。最简单的页面置换算法是先入先出（FIFO）法。优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。2.最近最久未使用页面淘汰法（LRU）关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。而内存的虚拟存储管理，是现在最通用，最成功的方式 在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的

3、并发度。虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。然而，有利就有弊，虚拟页式存储管理减少了进程所需的内存空间，却也带来了运行时间变长这一缺点：进程运行过程中，不可避免地要把在外存中存放的一些信息和内存中已有的进行交换，由于外存的低速，这一步骤所花费的时间不可忽略。因而，采取尽量好的算法以减少读取外存的次数，也是相当有意义的事情。三、实验内容1.通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：1.50%的指令是顺序执行的；2.25%的指令是均匀分布在前地址部分；3.25%的指令是均匀分布在后地址部分；具体的实施

4、方法是：1.在0，319的指令地址之间随机选取一起点m；2.顺序执行一条指令，即执行地址为m+1的指令；3.在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m；4.顺序执行一条指令，其地址为m+1；5.在后地址m+2, 319中随机选取一条指令并执行；6.重复上述步骤15，直到执行320次指令。2.将指令序列变换成页地址流，设1.页面大小为1K；2.用户内存容量为4页到32页；3.用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中存放的方式为：第0条至第9条指令为第0页（对应虚存地址为0，9）；第10条至第19条指令为第1页（对应虚存地址为1

5、0，19）；第310条至第319条指令为第31页（对应虚存地址为310，319）；按以上方式，用户指令可以组成32页。3.计算并输出下述各种算法在不同内存容量下的命中率。1.先进先出页面淘汰算法（FIFO）2.最近最久未使用页面淘汰法（LRU）命中率=1 - 页面失效次数/页地址流长度在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令对应的页不在内存的次数。4.随机数产生办法关于随机数产生办法，Linux或UNIX系统提供函数srand()和rand()，分别进行初始化和产生随机数。四、关键数据结构与函数的说明1. 全局变量const int maxn = 320; /

6、序列个数const int max = maxn +20;/数组大小const int maxp = max/10; /最大页数int instmax;/指令序列int pagemax;/页地址流int size; /内存能容纳的页数bool inmaxp; /该页是否在内存里，提高效率int pinmaxp; /现在在内存里的页其中in数组是为了方便直接判断该页是否在内存里，而不用遍历内存里所有页来判断。fault_n用来记录缺页次数。2.随机指令序列的产生void produce_inst() int m, n; int num = 0; while(num maxn) m = rand(

7、) % maxn; instnum+ = (m+1)%maxn; if(num = maxn) break; m = (m+2) % maxn; if(m = 0) m = 160; n = rand() % m; instnum+ = (n+1)%maxn; if(num = maxn) break; n = (n+2) % maxn; m = maxn - n; if(m = 0) m = 160; m = rand() % m + n; instnum+ = m; 五、编译与执行过程截图1先进先出页面淘汰算法（FIFO）2最近最久未使用页面淘汰法（LRU）六、实验结果与分析1先进先出页面

8、淘汰算法（FIFO）FIFO最简单的页置换算法，FIFO的页置换的算法为每个页记录着该页调入内存的时间。当必须置换一页时，将选择最旧的页。注意并不需要记录调入一页的确切时间，可以创建一个FIFO队列来管理内存中的所有页。队列中的首页将被置换。当需要调入页时，将它加入到队列的尾部。FIFO的页置换算法很好理解和实现，但是，其性能并不是很好。所替代的页可能是很久以前使用的、现已不再使用的初始化模块，另一方面，所替代的页可能包含一个以前初始化的并且不断使用的常用变量。2最近最久未使用页面淘汰法（LRU）LRU置换为每个页关联该页上次使用的时间。当必须置换一次的时候，LRU选择最长时间没有使用的页，这

9、种策略为向后看最优页置换算法。LRU置换算法被认为相当不错，其主要问题是如何实现LRU置换，页帧的排序序列按页帧上次使用时间来定，有两种可行方法：计算器 为每个页表项关联一个使用时间域，并为CPU增加一个逻辑时钟或者计数器。对每次内存引用，计算器都会增加，每次内存引用的时候时钟寄存器的内容会被复制到相应页所对应的页表项的使用时间域内。用这种方式就得到每页的最近使用时间。置换具有最小时间的页。这种方案需要搜索页表已经查找LRU也，且每次内存访问都要写入内存。在改变页表时，因CPU调度，也必须保持时间。必须考虑时钟溢出。栈 每当引用一个页，该页就从栈中删除并放在顶部。这样，栈顶部总是最近使用的页，

10、栈底部总是LRU页。由于必须是从栈中删除项，所以，该栈可实现为具有头部指针和尾指针的双向链表。虽然每个更新有点费事，但是置换不需要搜索；尾部指针指向栈底部，就是LRU页。七、调试时遇到的问题及解决方法1.随机指令序列的产生出现问题：发现有时按步骤操作可能会出错。要及时排错。八、调试后的程序源代码1.先进先出页面淘汰算法（FIFO）#include#include#include#includeint str320;/320条指令 int page32;/物理内存页int page_lock32;int count_num32;int error=0;int already_given=0; i

11、nt find_page(int i) return (i/10);int page_schelduing_opt(int num) int i,j,m,n,count,find; for(i=0;inum;i+) pagei=-1;page_locki=0; for(i=0;i320;i+) find=0; count=0; for(j=0;jalready_given;j+) if(pagej=stri) find=1; break; if(!find) error+; for(n=0;nnum;n+) page_lockn=0; if(already_givennum) pagealre

12、ady_given=stri; already_given+; else for(m=i;m320&(countnum);m+) for(n=0;nnum;n+) if(strm=pagen) page_lockn=1; count+; for(n=0;nnum;n+) if(page_lockn=0) pagen=stri; break; main() int i,j,m,n,upper,least,x=0; for(i=0;i320;i+) stri=i; i=0; upper=319; least=0; srand (time(NULL); while(i80) /every time

13、4 orders m=least+rand()%(upper+1); /m /执行m+1 strx+=find_page(m+1); n=least+rand()%(m+2);/ m /执行n 和 n+1 strx+=find_page(n); strx+=find_page(n+1); n=n+2+rand()%(320-n-2); /执行 n strx+=find_page(n); upper=n; least=0; i+; printf(当前运行的算法是OPT算法n); for(j=4;j33;j+) printf(%d:t,j); error=0; for(i=0;i32;i+) pa

14、gei=0; page_locki=0; i=0; error=0;already_given=0; page_schelduing_opt(j); printf(%.2f,%dt,1-(float)error/320,error); if(j-3)%3=0&j!=4) printf(n); printf(n); system(pause);2最近最久未使用页面淘汰法（LRU）#include#include#include#includeint str320;/320条指令 int page32;/物理内存页int page_lock32;int count_num32;int error=

15、0;int already_given=0; int find_page(int i) return (i/10);int page_schelduing_fifo(int num) int i,j,m,n,count=0,find; for(i=0;inum;i+) pagei=-1; for(i=0;i320;i+) find=0; count=0; for(j=0;jalready_given;j+) if(pagej=stri) find=1;break; if(find=0) if(already_givennum) pagealready_given=stri; already_g

16、iven+; else if(already_given=num) for(j=0;jalready_given-1;j+) pagej=pagej+1; pagej=stri; error+; main() int i,j,m,n,upper,least,x=0; for(i=0;i320;i+) stri=i; i=0; upper=319; least=0; srand (time(NULL); while(i80) /every time 4 orders m=least+rand()%(upper+1); /m /执行m+1 strx+=find_page(m+1); n=least

17、+rand()%(m+2);/ m /执行n 和 n+1 strx+=find_page(n); strx+=find_page(n+1); n=n+2+rand()%(320-n-2); /执行 n strx+=find_page(n); upper=n; least=0; i+; printf(当前运行的算法是FIFO算法n); for(j=4;j33;j+) printf(%d:t,j); error=0; for(i=0;i32;i+) pagei=0; page_locki=0; i=0; error=0;already_given=0; page_schelduing_fifo(j); printf(%.2f,%dt,1-(float)error/320,error); if(j-3)%3=0&j!=4) print