虚拟存储管理技术
一、实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。
二、实验要求与内容、过程与结果
1.用随机数产生一个指令序列，共320条指令。其地址按下述原则生成：
①50%的指令是顺序执行的；
②25%的指令是均匀分布在前地址部分；
③25%的指令是均匀分布在后地址部分；
具体的实施方法是：
A.在[0，319]的指令地址之间随机选区一起点M;
B.顺序执行一条指令，即执行地址为M+1的指令；
C.在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’；
D.顺序执行一条指令，其地址为M’+1；
E.在后地址[M’+2，319]中随机选取一条指令并执行；
F.重复A—E，直到执行320次指令。
2.指令序列变换成页地址流
设：（1）页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条—第9条指令为第0页（对应虚存地址为[0，9]）；
第10条—第19条指令为第1页（对应虚存地址为[10，19]）；
……………………………………
第310条—第319条指令为第31页（对应虚存地址为[310，319]）；
按以上方式，用户指令可组成32页。
3.计算并输出下述各种算法在不同内存容量下的命中率。
FIFO先进先出的算法
LRU最近最少使用算法
LFU最少访问页面算法
4.运行实例程序，内存块分别为4和5时，记录运行结果。缺页率有何变化？
内存块为4时 FIFO:
内存块为4时 LRU:
内存块为4时 LFU:
内存块为5时 FIFO:
内存块为5时 LRU:
内存块为5时 LFU:
答：随内存块数量的增加，缺页率降低。
5.参照示例程序，实现OPT算法。
提示：
A.缺页率=页面失效次数/页地址流长度=缺页次数/页面访问次数。
B.为了调试方便，可设置页地址流长度（页面访问次数）为100，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。
C.关于随机数产生方法，采用函数RAND()和RANDOMIZE()来产生。
D.OPT算法可修改示例程序，先生成页面访问序列，在需要淘汰页面时，从内存块中选择未来最久才被访问的页淘汰之。
程序代码：
#include <iostream>
#include<stdio.h>
#include <stdlib.h>
#include<time.h>
using namespace std;
#define Options 100 //共100条指令
struct MemBlock
{
int page;
int count;
MemBlock* next;
};
int main()
{
time_t t;
srand(unsigned(time(&t)));
int i,n,j,ii,m,answer,ffalse,count,fangfa,min;
double sum;
MemBlock *head,*tail,*temp,*table,*first,*ti,*Loadin;
cout<<"输入分配的内存块数目【2-6】："<<endl;
cin>>m;
cout<<endl;
cout<<"内存块初始化：\n";
table=new(MemBlock);
temp=table;
table->page=-1;
table->count=0;
head=table;
for(ii=2; ii<=m; ii++)
{
table=new(MemBlock);
table->page=-1;
table->count=0;
temp->next=table;
temp=table;
if (ii==m)
table->next=NULL;
}
for(ti=head; ti!=NULL; ti=ti->next)
cout<<ti->page<<"["<<ti->count<<"]"<<"\t\t";
cout<<endl;
cout<<"采用页面置换法:\n"<<"1-FIFO\n"<<"2-LRU\n"<<"3-LFU\n"<<"4-OPT"<<endl;
cout<<"请选择【1-4】:";
cin>>fangfa;
tail=table;
temp=head;
ffalse=0;
answer=0;
first=head;
count=0;
i=0;
int index=0;
int z;
int input[Options];
for(z=0;z<Options;z++)
{
input[z]=(rand()%Options+1)%Options/10;
}
for(z=0;z<Options;z++)
{
if(z%5==0)
printf("\n");
printf("%3d",input[z]);
}
printf("\n");
while(i<Options) //320条指令，指令访问地址为0-319
{
table=head;
temp=head;
answer=0;
min=400;
//随机生成指令的访问地址n，j为页号
if (count==0)
{
n=(rand()%Options+1)%Options;
j=n/10;
}
if(count==1)
{
n=rand()%(n+1);
j=n/10;
}
if(count==2)
{
j=((n+1)%Options)/10;
}
if(count==3)
{
j=((rand()%(Options-n-2))+n+2)/10;
}
if (fangfa==2||fangfa==3)
{
while(table!=NULL)
{
if (table->page==j) //访问的页已装入内存
{
answer=1;
++(table->count);
break;
}
table=table->next;
}
if(answer!=1) //访问的页不在内存
{
++ffalse; //页面缺页次数加1
cout<<j<<"页不在内存，请求装入！\n";
table=head;
while (table!=NULL) //查找最少访问的页temp
{
if(table->page==-1) //如果有空闲页，则不需要置换
{
temp=table;
break;
}
if (table->count<min)
{
temp=table;
min=table->count;
}
table=table->next;
}
if (temp->page!=-1) //淘汰temp页
cout<<temp->page<<"页被淘汰！\n";
temp->page=j; //装入j页到temp块中
temp->count=1;
if(count==3) //每过4次页面访问进行一次计数
{
table=head;
while(table)
{
if(table->page!=j && table->count>0)
table->count-=1;
table=table->next;
}
}
}
}
if (fangfa==1) //FIFO算法
{
int flag=0;
Loadin=first;
while(table!=NULL)
{
if (table->page==j)
{
answer=1;
table->count++;
break;
}
if(flag==0&&table->page==-1) //空闲块
{
Loadin=table;
flag=1;
}
table=table->next;
}
if(answer!=1)
{
++ffalse;
cout<<j<<"页不在内存，请求装入！\n";
if (Loadin->page!=-1)
{
cout<<Loadin->page<<"页被淘汰！\n";
first=first->next; //下次被淘汰的页
if (first==NULL)
first=head;
}
Loadin->page=j;
Loadin->count=1;
}
}
if(fangfa==4) //opt
{
while(table!=NULL)
{
if (table->page==input[index]) //访问的页已装入内存
{
answer=1;
table->count++;
break;
}
table=table->next;
}
if(answer!=1) //访问的页不在内存
{
++ffalse; //页面缺页次数加1
cout<<input[index]<<"页不在内存，请求装入！\n";
table=head;
int h,max=index;
while (table!=NULL) //查找未来最久才被访问的页temp
{
if(table->page==-1) //如果有空闲页，则不需要置换
{
temp=table;
break;
}
/*if (table->count<min) //在input中
{ //查找最久才被访问的页
temp=table; //
min=table->count; //
}*/ //
//查找table->page在input中将要被访问的地址
for(h=index;h<Options;h++)
{
if(table->page==input[h])
{
if(h>max)
{
temp=table;
max=h;
}
break;
}
}
if(h>=20)
{
temp=table;
break;
}
table=table->next;
}
if (temp->page!=-1) //淘汰temp页
cout<<temp->page<<"页被淘汰！\n";
temp->page=input[index]; //装入j页到temp块中
temp->count=1;
}
}
++i;index++;
count=++count%4;
for(ti=head; ti!=NULL; ti=ti->next)
cout<<ti->page<<"["<<ti->count<<"]"<<"\t\t";
cout<<endl;
}
cout<<"\n缺页率为：";
sum=ffalse/(Options*1.0);
cout<<sum<<endl;
}
运行效果：
程序分析：
本程序是一个模拟操作系统页面置换算法的程序，通过模拟程序的运行过程，来分析不同的页面置换算法的效率，从而选择最优的算法，以达到提高程序运行效率的目的。
程序中使用了四种页面置换算法，分别是FIFO（先进先出）、LRU（最近最少使用）、LFU（最不经常使用）和OPT（最优置换算法）。其中，FIFO算法是最简单的算法，即按顺序淘汰最先进入内存的页面；LRU算法是按页面最后一次被访问的时间来淘汰页面；LFU算法是按页面被访问的频率来淘汰页面；OPT算法是预测将来会被使用的页面，将最长时间不被使用的页面淘汰。
在程序开始运行时，需要输入分配的内存块数目，以及选择要使用的页面置换算法。程序首先进行内存块的初始化，将内存块中的页都设置为-1，表示还没有被装入页。然后程序通过随机生成指令的访问地址来模拟程序运行。每访问一次页面，程序会首先检查页面是否已经在内存中，如果在，则将其访问次数加1；如果不在，则需要进行页面置换。
在FIFO算法中，程序会检查页面是否在内存中，如果在，则将其访问次数加1；如果不在，则需要将最先进入内存的页面淘汰，将新的页面装入内存。在LRU算法和LFU算法中，程序会检查页面是否在内存中，如果在，则将其访问次数加1；如果不在，则需要淘汰最近或最不经常被使用的页面，将新的页面装入内存。在OPT算法中，程序会检查页面是否在内存中，如果在，则将其访问次数加1；如果不在，则需要预测将来会被使用的页面，并淘汰最长时间不被使用的页面，将新的页面装入内存。
程序最后输出缺页率，即页面置换的次数除以指令总数。
通过模拟程序运行过程，并比较四种不同的页面置换算法的缺页率，可以得出最优的页面置换算法。当然，不同的程序运行情况下，最优的页面置换算法可能会不同，需要根据实际情况进行选择。