实验八 页面置换模拟程序设计

一、实验目的

1、通过软件模拟页面置换过程，加深对请求页式存储管理实现原理的理解

2、理解和掌握OPT、FIFO和LRU三种页面置换算法，深入分析三者之间的优缺点。

二、实验环境

硬件环境：计算机一台，局域网环境；

软件环境： Windows或Linux操作系统， C语言编程环境。

三、实验内容和步骤

参考设计思路

（1）重要数据结构

① 页表数据结构

typedef struct

{

 int vmn;

 int pmn;

 int exist;

 int time;

 }vpage_item;

 vpage_item page_table[VM_PAGE];

页表是虚地址向物理地址转换的依据，包含虚页号所对应的实页号，是否在物理内存中。

页表中增加了一个time项，用于替换算法选择淘汰页面，在不同的替换算法中，time含义不一样。

在LRU算法中，time为最近访问的时间。该虚页每访问一次，time置为当前访问时刻，淘汰页面时，淘汰time值最小的，即最久没有被使用的。

在FIFO算法中，time为该虚页进入内存的时间。只有当该虚页从外存进入内存时，才置该标志。淘汰页面时，淘汰time值最小的，即最早进入内存的虚页。

在OPT算法中，time没有任何意义。

② 物理页位图数据结构

vpage_item * ppage_bitmap[PM_PAGE];

物理页位图是用于记录物理页是否被使用，用于物理页内存的分配。正常情况下是一个数组，元素值为0时，代表相应物理页没有装入任何虚页，值为1时，代表该物理页装入虚页。但为方便替换算法检索要替换出去的虚页，数组的每个元素值为当前放在该物理页的页表项的指针。若值为NULL，则表示该物理页没有被占用，当值不为NULL时，表示正在占用该物理页的虚页。

③指令相关数据结构

//每条指令信息

typedef struct{

int  num;

int  vpage;

int  offset;

int  inflow;

}instr_item;

//指令数组

instr_item instr_array[TOTAL_INSTR];

//指令流数据结构

struct instr_flow{

instr_item *instr;

struct instr_flow *next;

};

//指令流头数据结构

struct instr_flow_head{

int num;

struct instr_flow *next;

};

struct instr_flow_head iflow_head;

每条指令包括指令号、该指令所属虚页及页内偏移（这两项可以根据指令号计算出来，增加这两项是为了方便编程）。inflow是一个辅助项，用于构建指令流。

本题要求，按照规则生成的指令流中，应包含所有的共320条指令。但每次随机生成的指令号，可能已在指令流中，因此最终指令流中的指令数可能远远超过320条指令。

设置inflow的目的是为了便于统计是否320条指令均已加入到指令流中。在该条指令加入到指令流中时，如果inflow为0，表示该指令尚未在指令流中，则统计数加1；如果inflow为1，表示该指令已经加入过指令流，该指令虽然再次加入指令流，但统计数不增加。这样，当统计计数为320时，表示所有的指令均已加入到指令流中。

struct instr_flow为指令流数据结构，struct instr_flow_head始终指向指令流的头，其中num用于指令流中指令数量计数，用于计算缺页率。

（2）主程序，如下图所示。

（3）指令流生成流程

指令流的生成按照实验要求生成，其算法流程如下图所示。

（4）物理内存分配流程

物理内存分配时，需要根据当前置换算法选择淘汰页面。其算法流程下图所示。

（5）运行流程图，如下图所示。

（6）三种置换算法

①OPT算法：在当前指令的后续指令流中，寻找已在内存中的虚页，哪个最远才被使用，反过来，如果先找到最近三个（物理页面总数为4）也在内存中的虚页，则剩下的那个虚页肯定就是最远才被使用的虚页，该虚页被淘汰，其物理内存分配给当前指令所在的虚页。

②FIFO算法：在已在物理内存中的虚页中，寻找time最小的虚页（最早进入物理内存的虚页），该虚页即是被淘汰的虚页。

③LRU算法：思想同FIFO算法，但time最小的虚页含义是最久没有被使用的虚页。

在这三种置换算法中，OPT的算法稍微复杂一些，下图给了该算法的程序流程图。

程序代码