河南城建学院《操作系统》课程设计说明书设计题目：存储管理专业：计算机科学与技术指导教师：邵国金班级：0814121学号：081412112姓名：同组人：计算机科学与工程学院2015 年1 月9日前言本课程设计是编制页面置换算法FIFO、LRU、LFU、NUR和OPT的模拟程序,并模拟其在内存的分配过程。

同时根据页面走向，分别采用FIFO、LRU、LFU、NUR和OPT算法进行页面置换，统计命中率；同时系统可以随意设置当前分配给作业的物理块数。

系统运行时，任意输入一个页面访问序列，可以设定不同的页面置换算法和物理块数，输出其页面淘汰的情况，计算其缺页次数和缺页率。

系统结束后，比较同一个页面访问序列，可以得出在不同的页面置换算法和物理块数的情况下，其产生的缺页次数和缺页率。

使用FIFO算法，由于测试数据相同的页面比较少，所以采用FIFO算法时，需要置换的页面多，比较繁琐，没有优化效果，所以FIFO算法性能不好。

使用LRU的算法，此组数据显示LRU的算法使用比较繁琐，总的来说，NUR、LFU、LRU 算法介于FIFO和OPT之间。

通过系统模拟得出，OPT算法的性能高，LRU、NUR、LRU算法的性能次之，FIFO的算法性能最差，较少应用；由于OPT算法在实际上难于实现，所以实际应用一般用LRU算法。

本程序实现了操作系统中页式虚拟存储管理中缺页中断理想型淘汰算法，该算法在访问串中将来再也不出现的或是在离当前最远的位置上出现的页淘汰掉。

这样，淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。

该程序能按要求随机确定内存大小，随机产生页面数，进程数，每个进程的页数，给进程分配的页数等，然后运用理想型淘汰算法对每个进程进行计算缺页数，缺页率，被淘汰的序列等功能。

目录一．系统环境 (1)1.1硬件环境 (1)1.2软件环境 (1)二．设计目的 (2)三．总体设计 (3)3.1程序设计组成框图 (3)3.2流程图 (4)四．详细设计 (7)4.1模块功能说明 (7)4.11数据结构 (7)4.12函数定义 (8)4.13变量定义 (8)4.2算法分析 (8)五．调试与测试 (10)5.1调试方法 (10)5.11使用Vi编译程序 (10)5.12运行程序 (12)5.2结果分析与讨论 (13)5.3测试问题及采取措施 (13)六．源程序 (14)七．心得体会 (23)八．参考文献 (24)一．系统环境1.1硬件环境PC机一台，0.99G内存，2.0GHZ主频1.2软件环境设计和实验将Windows环境下，gcc和虚拟机软件VMWare存储管理的主要功能之一是合理地分配空间。

请求页式管理是一种常用的虚拟存储管理技术。

本设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

要求：(1)通过随机数产生一个指令序列，共320条指令。

指令的地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分。

具体的实施方法是：①在[0，319]的指令地址之间随机选取一起点m；②顺序执行一条指令，即执行地址为m+l的指令；③在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；④顺序执行一条指令，其地址为m’+1；⑤在后地址[m’+2，319]中随机选取一条指令并执行；⑥重复上述步骤①~⑤，直到执行320次指令。

(2)将指令序列变换成为页地址流。

设:①页面大小为1K；②用户内存容量为4页到32页；③用户虚存容量为32K。

在用户虚存中，按每页存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条~第9条指令为第0页(对应虚存地址为[0，9])；第10条~第19条指令为第1页(对应虚存地址为[10，19])；………第310条~第319条指令为第31页(对应虚存地址为[310，319])。

按以上方式，用户指令可组成32页。

(3)计算并输出下述各种算法在不同内存容量下的命中率（要为以下各种算法定义数据结构）。

①先进先出的算法(FIFO)；②最近最少使用算法(LRU)；③最近最不经常使用算法(NUR/NRU/CLOCK)。

命中率=1-页面失效次数/页地址流长度在本设计中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。

(4)关于随机数产生办法，Linux/UNIX系统提供函数srand（）和rand（），分别进行初始化和产生随机数。

例如:srand()语句可初始化一个随机数：a[0]=10*rand()/32767*319+1，a[1]=10*rand()/32767*a[0]；………语句可用来产生a[0]、a[1]、…中的随机数。

3.1程序设计组成框图系统分为4个子模块：初始化模块，FIFO、LRU、LFU、NUR和OPT的五个算法模块。

初始化模块：initialize( )初始化函数，给每个相关的页面赋值。

FIFO算法模块：计算使用FIFO算法时的命中率。

LRU算法模块：计算使用LRU算法时的命中率。

LFU算法模块：计算使用OPT算法时的命中率。

NUR算法模块：计算使用LFU算法时的命中率。

OPT算法模块：计算使用NUR算法时的命中率。

3.2流程图LFU NUROPT四．详细设计本实验的程序设计基本上按照实验内容进行。

即首先用srand()和rand()函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,并针对不同的算法计算出相应的命中率。

相关定义如下:4.1模块功能说明4.11数据结构(l)页面类型typedef struct{int pn,pfn,count,time;} pl_type;其中pn为页号,pfn为面号,count为个周期内访问该页面次数time为访问时间。

(2)页面控制结构pfc_struct{int pn,pfn;struct pfc_struct *next;}typedef struct pfc_struct pfc_type;pfc_type pfc[xy],*free_head,*busy_head;pfc_type *busy_tail;其中：pfc[xy]定义用户进程虚页控制结构,*free_head为空页面头的指针,*busy_head为忙页面头的指针,*busy_tail为忙页面尾的指针。

4.12函数定义(1)void initialize():初始化函数,给每个相关的页面赋值。

(2)void FIFO():计算使用FIFO算法时的命中率。

(3)void LRU():计算使用LRU算法时的命中率。

(4)void OPT():计算使用OPT算法时的命中率。

(5)void LFU():计算使用LFU算法时的命中率。

(6)void NUR():计算使用NUR算法时的命中率。

4.13变量定义(1)int a[zllc];指令流数据组。

(2)int page[zllc];每条指令所属页号。

(3)int offset[zllc];每页装入10条指令后取模运算页号偏移值。

(4)int pf:用户进程的内存页面数。

(5)int zhihuan:页面失效次数。

4.2算法分析先进先出算法，即FIFO算法（First-In First-Out algorithm）。

这种算法选择最先调入主存储器的页面作为被替换的页面。

它的优点是比较容易实现，能够利用主储存器中页面调度情况的历史信息，但是没有反应程序的局部性。

因为最先调入主存的页面，很有可能是经常使用的页面。

最近最少使用算法，即LFU（Least Frequently used algorithm）。

这种算法选择近期最少访问的页面作为被替换的页面。

显然这是一种非常合理的算法，因为到目前为止最少使用的页面，和可能也是将来最少访问的页面。

该算法即充分利用了主存中吗调度的历史信息，又正确反映了程序的局部性。

但是这种算法实现起来非常的困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。

在选择被替换页面时，要从所有的计数器中选择一个计数值最大的计数器。

因此，通常使用如下一种简单的方法。

最久没有使用算法。

即LRU(Least Recently Used Algorithm)。

这种算法把近期最久没有被访问的页面作为被替换的页面。

它把LFU算法中要记录数量上的多与少简化成判断有于无，因此实现起来比较容易。

NUR算法在需要淘汰一页时，从哪些最近一个时期内未被访问的页面中任选一页淘汰。

只要在页面中增加一个访问位即可实现。

当某页被访问时，访问位置1.否则，访问位置0.系统周期性第对所有的引用位清零。

当须淘汰一页时从那些访问位为0 的页中选择一页进行淘汰。

如果引用位全为1或0，NRU算法退化为FIFO算法。

最优替换算法，即OPT(Optimal Replacement Algorithm).s上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。

当然这种假设不总是正确的。

最好的算法是选择将来醉酒不被访问的页面作为被替换的页面，这种算法的命中率是最高的，它就是最有替换算法。

要实现OPT算法，唯一的办法就是让程序先执行一遍，记录下实际的页地址流情况。

根据这个页地址流才能找到药被替换的页面。

显然这样做是不现实的。

因此OPT算法只是一种理想化的算法，然而它也是一种很用的算法。

实际上，经常把这种算法作为评价其他页面替换算法好坏的标准。

在其他条件相同的情况下，哪一种算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。

五．调试与测试5.1调试方法5.11使用Vi编译程序（1）打开VMware、选中Red Hat Enterprise Linux、查看属性、选项、共享文件夹添加（2）查看root的主目录→mnt→hgfs→zheng→zhengjingjing→使用vi打开5.12运行程序5.2结果分析与讨论从上述结果可知,在内存页面数较少(4~5页面)时,5种算法的命中率差别不大,都是50%左右。

在内存页面为7~25个页面之间时,5种算法的访内命中率大致在52%至87%之间变化。

但是,FIFO算法与0PT算法之间的差别一般在6~10个百分点左右。

在内存页面为25~32个页面时,由于用户进程的所有指令基本上都已装入内存,从而命中率已较大。

从而算法之间的差别不大。

比较上述5种算法,以OPT算法的命中率最高,NUR算法次之,再就是LFU算LRU算法,其次是FIF0算法。

5.3测试问题及采取措施本次课程设计中我们遇到的问题是，一开始没有弄清楚rand和sand函数的使用方法，以至于运行时的到的结果与实际算起来的不相符，后来查阅资料，上网浏览搜索相关信息后，终于弄明白了是怎么回事。