请求页式存储管理的模拟
实验目的：熟悉虚拟存储管理的各种页面置换算法，并编写模拟程序实现请求页式存储管理的页面置换算法----最近最久未使用算法（LRU），要求在每次产生置换时显示页面分配状态和缺页率。
实验内容：1、运行给出的实验程序，查看执行情况，进而分析算法的执行过程，在理解FIFO页面置换算法后，给出最近最久未使用算法（LRU）置换算法的模拟程序实现，并集成到参考程序中。
2、执行2个页面置换模拟程序，分析缺页率的情况。最好页框数和访问序列长度可调节，在使用同一组访问序列数据的情况下，改变页框数并执行2个页面置换模拟程序，查看缺页率的变化。
3、在每次产生置换时要求显示分配状态和缺页率。程序的地址访问序列通过随机数产生，要求具有足够的长度。最好页框数和访问序列长度可调节。
编写程序
#include "windows.h"
#include <conio.h>
#include <stdlib.h>
#include <fstream.h>
#include <io.h>
#include <string.h>
#include <stdio.h>
void initialize(); //初始化相关数据结构
void createps(); //随机生成访问序列
void displayinfo(); //显示当前状态及缺页情况
void fifo(); //先进先出算法
int findpage(); //查找页面是否在内存
void lru(); //最近最久未使用算法
int invalidcount = 0; // 缺页次数
int vpoint; //页面访问指针
int pageframe[10]; // 分配的页框
int pagehistory[10]; //记录页框中数据的访问历史
int rpoint; //页面替换指针
int inpflag; //缺页标志，0为不缺页，1为缺页
struct PageInfo //页面信息结构
{
int serial[100]; // 模拟的最大访问页面数，实际控制在20以上
int flag; // 标志位，0表示无页面访问数据
int diseffect; // 缺页次数
int total_pf; // 分配的页框数
int total_pn; // 访问页面序列长度
} pf_info;
////////////////////////////////////////////////////////////////////////
//初始化相关数据结构
void initialize()
{
int i,pf;
inpflag=0; //缺页标志，0为不缺页，1为缺页
pf_info.diseffect =0; // 缺页次数
pf_info.flag =0; // 标志位，0表示无页面访问数据
printf("\n请输入要分配的页框数："); // 自定义分配的页框数
scanf("%d",&pf);
pf_info.total_pf =pf;
for(i=0;i<100;i++) // 清空页面序列
{
pf_info.serial[i]=-1;
}
}
///////////////////////////////////////////////////////////////////
// 随机生成访问序列
void createps(void )
{
int s,i,pn;
initialize(); //初始化相关数据结构
printf("\n请输入要随机生成访问序列的长度："); //自定义随机生成访问序列的长度
scanf("%d",&pn);
srand(rand()); //初始化随机数队列的"种子"
s=((float) rand() / 32767) * 50 + pn; // 随机产生页面序列长度
pf_info.total_pn = s;
for(i=0;i<s;i++) //产生随机访问序列
{
pf_info.serial[i]=((float) rand() / 32767) * 16 ; //随机数的大小在0-15之间
}
}
////////////////////////////////////////////////////////////////////////
// 显示当前状态及缺页情况
void displayinfo(void)
{
int i,n;
if(vpoint==0)
{
printf("\n=============页面访问序列=============\n");
for(i=0; i<pf_info.total_pn; i++)
{
printf("%4d",pf_info.serial[i]);
if ((i+1) % 10 ==0) printf("\n"); //每行显示10个
}
printf("\n======================================\n");
}
printf("访问%3d : 内存<",pf_info.serial[vpoint]);
for(n=0;n<pf_info.total_pf;n++) // 页框信息
{
if (pageframe[n] >=0)
printf("%3d",pageframe[n]);
else
printf(" ");
}
printf(" >");
if(inpflag==1) //缺页标志，0为不缺页，1为缺页
{
printf(" ==>缺页 ");
printf("缺页率%3.1f",(float)(pf_info.diseffect)*100.00/vpoint);
}
printf("\n");
}
////////////////////////////////////////////////////////////////////////
// 查找页面是否在内存，1为在内存，0为不在即缺页
int findpage(int page)
{
int n;
for(n=0;n<pf_info.total_pf;n++)
{
pagehistory[n] ++; // 访问历史加1
}
for(n=0;n<pf_info.total_pf;n++)
{
if (pageframe[n]==page )
{
inpflag=0 ; //inpflag缺页标志，0为不缺页，1为缺页
pagehistory[n]=0; //置访问历史为0
return 1;
}
}
inpflag=1; //页面不存在，缺页
return 0;
}
////////////////////////////////////////////////////////////////////////
// FIFO页面置换算法
void fifo(void)
{
int n,count,pstate;
rpoint=0; // 页面替换指针初始化为0
invalidcount = 0; // 缺页数初始化为0
createps(); // 随机生成访问序列
count=0; // 是否装满是所有的页框
for(n=0;n<pf_info.total_pf;n++) // 清除页框信息
{
pageframe[n]=-1;
}
inpflag=0; //缺页标志，0为不缺页，1为缺页
for(vpoint=0;vpoint<pf_info.total_pn;vpoint++) // 执行算法
{
pstate=findpage(pf_info.serial[vpoint]); //查找页面是否在内存
if(count<pf_info.total_pf) // 开始时不计算缺页
{
if(pstate==0) // 页不存在则装入页面
{
pageframe[rpoint]=pf_info.serial[vpoint];
rpoint=(rpoint+1) % pf_info.total_pf;
count++;
}
}
else // 正常缺页置换
{
if(pstate==0) // 页不存在则置换页面
{
pageframe[rpoint]=pf_info.serial[vpoint];
rpoint=(rpoint+1) % pf_info.total_pf;
pf_info.diseffect++; // 缺页次数加1
}
}
Sleep(10);
displayinfo(); // 显示当前状态
} // 置换算法循环结束
_getch();
return;
}
///////////////////////////////////////////////////////////////////
// LRU页面置换算法
void lru(void)
{
int n,count,pstate,max;
rpoint=0; // 页面替换指针
invalidcount = 0; // 缺页次数初始化为0
createps(); // 随机生成访问序列
count=0; // 是否装满所有的页框
for(n=0;n<pf_info.total_pf;n++)
{
pageframe[n]=-1; // 清除页框信息
pagehistory[n]=0; // 清除页框历史
}
inpflag=0; //缺页标志，0为不缺页，1为缺页
for(vpoint=0;vpoint<pf_info.total_pn;vpoint++) // 执行算法
{
pstate=findpage(pf_info.serial[vpoint]); //查找页面是否在内存
if(count<pf_info.total_pf) // 开始时不计算缺页
{
if(pstate==0) // 页不存在则装入页面
{
pageframe[rpoint]=pf_info.serial[vpoint]; //把要调入的页面放入一个空的页框里
rpoint=(rpoint+1) % pf_info.total_pf;
count++;
}
}
else // 正常缺页置换
{
if(pstate==0)// 页不存在则置换页面
{
max=0;
for(n=1;n<pf_info.total_pf;n++)
{
if(pagehistory[n]>pagehistory[max])
{
max=n;
}
}
rpoint=max;
pageframe[rpoint]=pf_info.serial[vpoint];
pagehistory[rpoint]=0;
pf_info.diseffect++; // 缺页次数加1
}
}
Sleep(10);
displayinfo(); // 显示当前状态
} // 置换算法循环结束
_getch();
return;
}
///////////////////////////////////////////////////////////////////
// 主函数
int main()
{
char ch;
system("cls") ;
while ( true )
{
printf("*******************************************\n");
printf(" 若要执行FIFO页面置算法请按“1”\n");
printf(" 若要执行LRU 页面置算法请按“2” \n");
printf(" 若要退出请按“3”\n") ;
printf("*******************************************\n");
printf( "Enter your choice (1 or 2 or 3): ");
do
{ //如果输入信息不正确，继续输入
ch = (char)_getch() ;
}while(ch != '1' && ch != '2'&& ch != '3');
printf("\n\n你按的是：%c ,现在为你执行对应操作。",ch);
if(ch == '3') //选择3，退出
{
return 0;
}
else
{
if(ch == '1') //选择1，FIFO
{
printf("\n\n----------*****执行FIFO算法*****-----------\n");
fifo();
}
else
{
printf("\n\n----------*****执行LRU算法*****----------\n");
lru();
}
}
system("cls") ;
}
printf("\n\nPress Any Key To Continue:");
_getch() ;
return 0;
}
实验总结：
通过本次实验，我对操作系统有了更深层次的认识和了解，通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，通过对页面、页表、地址转换和页面置换过程的模拟，我对请求调页系统的原理和实现过程的理解大大加深。
第二篇：实验3 页面置换算法模拟实验
淮海工学院计算机工程学院
实验报告书
课程名：《 操 作 系 统 》
题 目： 虚拟存储器管理
班 级：
学 号： 姓 名：
《 操作系统 》实验报告 - 1 -
一、实验目的与要求
1. 目的：
请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换
算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。
2. 要求：
本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、
并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。
二、实验说明
1．设计中虚页和实页的表示
本设计利用C语言的结构体来描述虚页和实页的结构。
虚页结构 实页结构
在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。
在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。
2．关于缺页次数的统计
为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。
3．LRU算法中“最近最久未用”页面的确定
为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前
《 操作系统 》实验报告 - 2 - countime值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出time值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。
4．算法中实页的组织
因为能分配的实页数n是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free和busy两个链表：free链表用于组织未分配出去的实页，首指针为free_head，初始时n个实页都处于free链表中；busy链表用于组织已分配出去的实页，首指针为busy_head，尾指针为busy_tail，初始值都为null。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明n个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将busy_head 所指的实页从busy链表中取下，分配给该虚页，然后再将该实页插入到busy链表尾部；对于LRU算法则要从所有已分配实页的虚页中找出time值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。
《 操作系统 》实验报告 - 3 -
四、主要程序清单
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "conio.h"
#include "time.h"
#define TRUE 1
#define FALSE 0
#define NULL 0
#define total_instruction 20
#define total_vp 10
typedef struct
{ int pn,pfn;
}pv_type;
pv_type pv[10];
typedef struct pf_struct
{ int pn,pfn;
struct pf_struct *next;
}pf_type;
pf_type pf[20],*free_head,*busy_head,*busy_tail,*q;
int page[total_instruction];
int total_pf;
int count;
void initialiaze()
{ int i;
count=0;
for(i=0;i<total_vp;i++)
{ pv[i].pn=i;
pv[i].pfn=-1;
}
printf("请输入实页数目:");
scanf("%d",&total_pf);
for(i=0;i<=total_pf-1;i++)
{ pf[i].next=&pf[i+1];
pf[i].pfn=i+1;
pf[i].pn=-1;
}
pf[total_pf-1].next=NULL;
free_head=&pf[0];
printf("随机产生的页地址流为：\n");
for(i=0;i<total_instruction;i++)
{ page[i]=rand()%10;
printf("%2d",page[i]);
}
}
void FIFO()
《 操作系统 》实验报告 - 4 - { int i,j;
pf_type *p;
q=busy_head=busy_tail=NULL;
for(i=0;i<=total_instruction-1;i++)
{ printf("\n第%d次执行:",i+1);
if(pv[page[i]].pfn==-1)
{ count+=1;
printf("缺页，缺页次数count=%d,",count);
if(free_head==NULL)
{
printf("实页%d中的页面%d将被置换出去",busy_head->pfn,busy_head->pn);
p=busy_head->next;
pv[busy_head->pn].pfn=-1;
free_head=busy_head;
free_head->next=NULL;
busy_head=p;
}
p=free_head->next;
free_head->next=NULL;
free_head->pn=page[i];
pv[page[i]].pfn=free_head->pn;
if(busy_tail==NULL)
busy_head=busy_tail=free_head;
else
{ busy_tail->next=free_head;
busy_tail=free_head;
}
free_head=p;
}
else printf("命中，缺页次数不变，仍为count=%d",count);
printf("\npfn pn");
for(j=0;j<=total_pf-1;j++)
{if(pf[j].pn!=-1)
printf("\n%d%8d",pf[j].pfn,pf[j].pn);
}
}
printf("\n先进先出算法的命中率为:%6.4f\n缺页总次数为%d\n",1-(float)count/20,count);
}
void main()
{
srand((unsigned)time(NULL));
initialiaze();
FIFO();
《 操作系统 》实验报告 - 5 - }五、程序运行结果
《 操作系统 》实验报告 - 6 -
六、实验体会
这次实验的目的是模拟虚拟存储的页面置换算法，请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。
这次实验我采用的是先进先出算法。在程序中主要是设计了如下几个数据结构：pv_type——用来表示虚页的有关信息，pf_type——用来表示内存中实页的有关信息。同时还用到了两个链表——free和busy，分别用来表示空闲实页面和已经存有虚页的忙页面。在进行页面置换时，要同时更改free和busy链表中的虚页号和实页号，free链表中的虚页号应该改到默认状态。当内存中不存在下一个要调入内存的虚页且内存中已经没有空闲页面时，那么将发生页面置换。
通过这次实验使我对页面置换算法有了进一步的了解，加强了自己的动手能力和编程的能力，巩固了课堂上所学的知识。
