使用最近未使用页淘汰(nru)算法模拟实现页淘汰进程

《使用最近未使用页淘汰(nru)算法模拟实现页淘汰进程》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、使用最近未使用页淘汰（NRU）算法模拟实现页淘汰进程摘要：最近未使用页淘汰（NRU）算法或者时钟算法是实际使用的诸多页淘汰算法中的一种。本课程设计是使用C程序设计语言，在windows平台下对页淘汰（NRU）算法模拟，通过页淘汰（NRU）算法的模拟来进一步的加深对使用NRU算法的了解，及对C程序设计语言的使用。关键词：页淘汰NRU时钟算法一．设计的背景介绍1.1介绍相关概念，相关算法页淘汰工作通常是由一个系统进程或线程完成的，该进程称为页淘汰进程。页淘汰的时机：当内存空闲页面数低于系统所配置的最小阈值时启动（唤醒）页淘汰的进程，页淘汰进程被启动后就开始不停地选择和淘

2、汰释放页，直到内存的空闲页面数达到系统所配置的最大阈值为止。此后，页淘汰进程进入睡眠（等待）状态，直到下次因内存空闲页面数少于最小阈值而被再次唤醒（启动）。最近未使用页淘汰（NRU）算法的原理：①该算法为每个页面设置两个硬件位—访问位和修改位访问位=0:该页尚未被访问过;访问位=1:该页已经被访问过修改位=0:该页尚未被修改过;访问位=1:该页已经被修改过②开始时所有页的访问位,修改位都设为0,访问/修改时再置1。③当页淘汰进程工作时,首先淘汰那些访问位为0的页。然后，如果还需要继续淘汰（即空闲页面尚未达到最大阈值），则淘汰那些访问位为1但修改位为0的页。最后如果空

3、闲页面还不够，则淘汰那些修改位为1的页。④由于大多数页迟早要被访问，故页淘汰进程定期遍历内存页—将每页的访问位都置为0（周期性地对访问位清零）。这种清除过程类似于时针在时钟面上的运行故NRU算法又称为时钟（clock）算法。1.2简要介绍设计环境、设计工具利用VC++6.0/TC3.0在Dos/Windows平台使用最近未使用页淘汰（NRU）算法模拟实现页淘汰进程二．设计思路和总体流程图2.1基本思路以命令行方式运行程序，调用read()函数读入页面请求队列，按照页面请求队列的先后顺序逐个处理请求页面。调用nru()函数通过nru算法选择要淘汰的页面，将其淘汰，调入

4、申请页面，输出相关结果的信息。2.2数据文件格式说明第一行为工作集大小（wnum）第二行为申请页面的总数(pnum)；第三行为页号(pagenum),修改位(mbit)中间用＂

5、＂符号隔开；其余为一个页面请求队列，各行两数分别表示页面申请页号和修改位，程序按请求的先后顺序处理申请页。用户可根据需要任意修改工作集大小，申请页面的总数，页面请求队列。文件样例如下：wnum:3pnum:10pagenum

6、mbit112031513061402130712.3数据结构定义⑴定义页面请求队列Pagetypedefstruct{intpagenum;//页面号intmbit;

7、//修改位}Page;⑵定义工作集Wspacetypedefstruct{intpageno;//页面号intrbit;//访问位intmbit;//修改位intstatus;//该页的标志位，表示是否被占用}Wspace;⑶其他intpnum;//申请页面的总数intwnum;//工作集大小intb[4];//标志位数组，四个数组元素分别表示工作集内是否存在访问位、修改位分别为00，01，10，11的页面，初始值为0，当存在时置12.4总体流程图图1.程序总体流程图2.5根据总体流程图进行模块分割、模块功能说明本程序共分成2个模块：⑴文件读入模块：主要用于读入文件

8、信息，并将文件的内容全部输出，检验读入是否正确。此模块通过调用read()函数实现。⑵主体函数模块：实现nru算法，这是本课程设计的主体模块，通过调用nru()函数实现。调入每个申请页，当工作集满时运用nru算法选择要淘汰的页面，将其淘汰。nru()函数中包括两个子函数print(),callin()●print()函数：信息输出，主要用于输出相关的结果信息，包括申请页面的页面号、修改位，工作集中的各页页面号、访问位、修改位。在程序处理完一页后调用此函数，使用户能清楚的了解处理完一个申请页面后工作集的内容。●callin()函数：调入申请页，主要完成四个操作：申请页

9、面调入；访问位置1，表示被访问；根据请求页面的修改位修改工作集页面的修改位；状态位置1，表示该页已经被占用。该函数在三种情形下可调用①工作集存在空闲页，调入申请页时；②申请页已在工作集中，修改访问位和修改位时；③工作集满时，需淘汰工作集内的页面，调入申请页时。三．算法的实现3.1模块流程图及算法实现1．文件读入模块主要用于读入文件信息，并将文件的内容全部输出，检验读入是否正确。通过read()函数实现。read()函数流程图如下：图2.read()函数流程图具体的程序代码如下：voidread(intargc,char*argv[],Page**page,int