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

使用最近未使用页淘汰（NRU）算法模拟实现页淘汰进程 摘要：最近未使用页淘汰（NRU）算法或者时钟算法是实际使用的诸多页淘汰算法中的一种。本课程设计是使用C程序设计语言，在windows平台下对页淘汰（NRU）算法模拟，通过页淘汰（NRU）算法的模拟来进一步的加深对使用NRU算法的了解，及对C程序设计语言的使用。 关键词：页淘汰 NRU 时钟算法 一．设计的背景介绍 1.1 介绍相关概念，相关算法 页淘汰工作通常是由一个系统进程或线程完成的，该进程称为页淘汰进程。 页淘汰的时机：当内存空闲页面数低于系统所配置的最小阈值时启动（唤醒）页淘汰的进程，页淘汰进程被启动后就开始不停地选择和淘汰释放页，直到内存的空闲页面数达到系统所配置的最大阈值为止。此后，页淘汰进程进入睡眠（等待）状态，直到下次因内存空闲页面数少于最小阈值而被再次唤醒（启动）。 最近未使用页淘汰（NRU）算法的原理： ①该算法为每个页面设置两个硬件位—访问位和修改位 访问位= 0:该页尚未被访问过; 访问位= 1:该页已经被访问过 修改位= 0:该页尚未被修改过; 访问位= 1:该页已经被修改过开始时所有页的访问位,修改位都设为0, 访问/修改时再置1。 ③当页淘汰进程工作时,首先淘汰那些访问位为0的页。然后，如果还需要继续淘汰（即空闲页面尚未达到最大阈值），则淘汰那些访问位为1但修改位为0的页。最后如果空闲页面还不够，则淘汰那些修改位为1的页。 ④由于大多数页迟早要被访问，故页淘汰进程定期遍历内存页—将每页的访问位都置为0（周期性地对访问位清零）。这种清除过程类似于时针在时钟面上的运行故NRU算法又称为时钟（clock）算法。 1.2 简要介绍设计环境、设计工具 利用VC++6.0/TC3.0在Dos/Windows平台使用最近未使用页淘汰（NRU）算法模拟实现页淘汰进程 二．设计思路和总体流程图 2.1 基本思路 以命令行方式运行程序，调用read()函数读入页面请求队列，按照页面请求队列的先后顺序逐个处理请求页面。调用nru()函数通过nru算法选择要淘汰的页面，将其淘汰，调入申请页面，输出相关结果的信息。 2.2数据文件格式说明 第一行为工作集大小（wnum）typedef struct { int pagenum; //页面号 int mbit; //修改位 }Page; ⑵定义工作集Wspace typedef struct { int pageno; //页面号 int rbit; //访问位 int mbit; //修改位 int status; //该页的标志位，表示是否被占用 }Wspace; ⑶其他 int pnum; //申请页面的总数 int wnum; //工作集大小 int b[4]; //标志位数组，四个数组元素分别表示工作集内是否存在访问位、修改位分别为00，01，10，11的页面，初始值为0，当存在时置1 2.4总体流程图 图1.程序总体流程图 2.5根据总体流程图进行模块分割、模块功能说明 本程序共分成2个模块： ⑴文件读入模块： 主要用于读入文件信息，并将文件的内容全部输出，检验读入是否正确。此模块通过调用read()函数实现。 ⑵主体函数模块： 实现nru算法，这是本课程设计的主体模块，通过调用nru() 函数实现。 调入每个申请页，当工作集满时运用nru算法选择要淘汰的页面，将其淘汰。nru()函数中包括两个子函数print(),callin() ●print()函数： 信息输出，主要用于输出相关的结果信息，包括申请页面的页面号、修改位，工作集中的各页页面号、访问位、修改位。在程序处理完一页后调用此函数，使用户能清楚的了解处理完一个申请页面后工作集的内容。 ●callin()函数： 调入申请页，主要完成四个操作：申请页面调入；访问位置1，表示被访问；根据请求页面的修改位修改工作集页面的修改位；状态位置1，表示该页已经被占用。该函数在三种情形下可调用①工作集存在空闲页，调入申请页时；②申请页已在工作集中，修改访问位和修改位时；③工作集满时，需淘汰工作集内的页面，调入申请页时。 三．算法的实现 3.1 模块流程图及算法实现 1．文件读入模块 主要用于读入文件信息，并将文件的内容全部输出，检验读入是否正确。通过read()函数实现。 read() 函数流程图如下： 图2.read( )函数流程图 具体的程序代码如下： void read(int argc,char * argv[],Page **page,int *pnum,int *wnum