20102100062黄耿星页面置换算法实验报告.doc

计算机学院 操作系统实验报告 项目名称：模拟操作系统的页面置换 指导老师：陈红英 成 员： 黄耿星（20102100062） 一、综设计实验题目：模拟操作系统的页面置换 二、中文摘要：在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。本实验通过模拟操作系统中的页面置换，比较FIFO、LRU、OPT三种页面置换算法的缺页率。 关键词： 缺页中断 页面置换算法 FIFO LRU OPT 三、前言 实验目的 1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。 2、掌握用随机数生成满足一定条件的指令地址流的方法。 3、掌握页面置换的模拟方法。 实验要求与内容 1、采用一种熟悉的语言，如C、PASCAL或C++等，编制程序，最好关键代码采用C/C++，界面设计可采用其它自己喜欢的语言。 2、模拟操作系统采用OPT、FIFO和LRU算法进行页面置换的过程。 3、设程序中地址范围为0到32767，采用随机数生成256个指令地址，满足50%的地址是顺序执行，25%向前跳，25%向后跳。为满足上述条件，可采取下列方法：设d0=10000，第n个指令地址为dn，第n+1个指令地址为dn+1，n的取值范围为0到255。每次生成一个1到1024范围内的随机数a，如果a落在1到512范围内，则dn+1=dn+1。如果a落在513到768范围内，则设置dn+1为1到dn范围内一个随机数。如果a落在769到1024范围内，则设置dn+1为dn到32767范围内一个随机数。例如：srand();初始化一个随机函数。 a[0]＝10*rand()/32767*255+1;a[1]=10*rand()/32767*a[0]…语句可用来产生a[0]与a[1]中的随机数。 或采用以下方式：（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，319]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m' D：顺序执行一条指令，其地址为m'+1 E：在后地址[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页。 4、页面大小的取值范围为1K，2K，4K，8K，16K。按照页面大小将指令地址转化为页号。对于相邻相同的页号，合并为一个。 5、分配给程序的内存块数取值范围为1块，2块，直到程序的页面数。 6、分别采用OPT、FIFO和LRU算法对页号序列进行调度，计算出对应的缺页中断率。 7、打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。 8、分析页面大小和分配给程序的内存块数对缺页中断率的影响。分析不同的页面置换算法的调度性能。 9、在上机实现该程序之后，要求写出实验报告，其中包括实验名称、实验目的、实验内容、程序的主要流程图、实验心得和主要源程序清单等。 四、需求分析： 置换算法内存中没有空闲页面时候被调用。它的目的是选出一个被淘汰的页面。如果内存中有足够的空闲页面存放所调入的页，则不必使用置换算法。把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。因此，置换算法应该置换那些被访问概率最低的页，将它们移出内存。所以，我们有必要通过一系列客观数据，通过三种常用