页式虚拟随机淘汰算法.docx
《页式虚拟随机淘汰算法.docx》由会员分享，可在线阅读，更多相关《页式虚拟随机淘汰算法.docx（16页珍藏版）》请在冰点文库上搜索。
页式虚拟随机淘汰算法
页式虚拟存储管理缺页中断的
随机淘汰算法
为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，和在内存的时间的长短。
请求分页中的页表如表1：
表1
虚拟页号
物理块号
状态位
辅存地址
访问字段
修改位
各字段说明如下：
状态位：
用于指示该页是否已调入内存，供程序访问时参考。
访问字段：
用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供替换页面时参考。
修改位：
表示该页面在调入内存后是否被修改过。
由于内存中的每一页都在外存上保留有副本，因此，若未被修改，在替换该页时就不需要再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。
外存地址：
用于指出该页在外存上的地址，通常是物理块号，供调入页面时参考。
在模拟系统的实现中，只需要用到虚拟页号，物理块号和中断位。
页表可用一个结构体的数组实现。
请求分页的具体实现过程如图1
图1请求分页流程图
2算法分析
在进程运行过程中，若其所要访问的页面不在内存，这时候会产生一个缺页中断，并需要把它们调入内存，但内存已无空闲已空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区。
但应将哪个页面调出，必须根据一定的算法来确定。
通常，把选择换出页面的算法称为页面替换算法。
虚拟内存性能的好坏很大程度上由替换算法的好坏，替换算法的好坏，也将直接影响系统的性能，一个好的页面置换算法，应具有较低的页面更换频率。
常见置换算法有随机淘汰算法（RandomGlongram）、轮转法（RoundRobin）和先进先出（FIFO）、最近最久未使用页面置换算法和理想型淘汰算法OPT（OptimalReplacementAlgorithm）。
本次所设计的模拟系统根据题目要求利用随机淘汰算法，先进先出算法和理想型淘汰算法进行页面替换，详细算法原理如下：
随机淘汰算法：
在系统设计人员无法确定哪些页被访问的概率较低时，明智的作法是随机地选择某个用户的页并将其换出。
随机淘汰算法实现简单，但是缺页率高。
先进先出算法：
总是选择在内存驻留时间最长的一页将其淘汰，因为最早调入内存的页，不再被使用的可能性比近期调入内存的大。
该算法实现简单，只需要把一个进程调入内存的页面，按先后次序连结成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
但是该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如有全局变量、常用函数，例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
假定系统为某进程分配了三个可用物理块，并考虑有以下的页面号引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
进程运行时，先将7，0，1三个页面装入内存，且采用FIFO替换算法。
当有请求页面2时，内存中页面7，0，1三个页号可知道7先进入内存，所以替换页面1；当请求页面0时，可知，0在内存中，不需要替换；当请求页面号3时内存中0，1，2三个页面0先进入内存，替换0号页。
如此进行下去，可得出利用FIFO替换算法，以上请求页面号序列共进行了12次页面替换，比理想型算法要多出一倍。
使用FIFO替换算法效率低的原因是：
基于处理器按线性顺序访问地址空间这一假设。
事实上，许多时候，处理器不是按线性顺序访问地址空间的。
例如，执行循环结构的程序段。
使用FIFO算法时，在未给进程或作业分配足够它所需要的页面数时，有时会出现分配的页面数增，缺页次数反而增加的现象（Belady现象）。
例如针对请求序列：
123412512345，若分配3个可用内存块，使用FIFO算法，一共会缺页9次，缺页率：
75%；而如果分配4个可用内存块，则一共会缺页10次，缺页率：
83.3%。
理想型淘汰算法基本思想：
当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。
采用理想型替换算法，通常可保证获得最低的缺页率。
但是由于人们目前无法预知一个进程在内存的若干个页面中，哪个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是在模拟设计中，由于是事先给定一个页面序列，即知道各个时刻以前和以后的页面出现情况，所以可实现该算法。
在实际系统中，虽无法实现理想型淘汰算法，但是可用它来评价其他替换算法。
用上面的例子，先将7，0，1三个页面装入内存。
以后当进程要访问页面2时，将会产生缺页中断。
此时OS根据最佳替换算法，将选择页面7予以淘汰，这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面1则要在第18次页面访问时才需要调入。
下次访问页面0时，因它已经在内存而不必产生缺页中断。
当进程访问页面3时，又将引起页面1被淘汰；因为，它在现有的1，2，0三个页面中，将是最后被访问的。
如此继续，这个作业序列将会产生6次页面置换。
理想型淘汰算法的具体工作流程如图2：
图2
3数据结构
模拟设计时，页表用数组模拟。
数组的数据类型为结构体，结构体有三个成员：
intpageNum表示页面号；intmemoryNum表示页面所对应的内存块号；intisInmemory是存在状态位标志，表示页面是否在内存，0表示不在内存，1表示在内存。
程序中设定虚拟页面号共10个，所以页表大小为10，即10个元素的数组pageTable。
在每一个算法函数中都要初始化页表，否则，后面的算法会受前面算法结果的影响。
structpage
{
intpageNum;
intmemoryNum;
intisInmemory;
};
pagepageTable[10];
初始化页表：
for（inti=0;i<10;i++）
{
pageTable[i].pageNum=i;
pageTable[i].memoryNum=-1;//初始化时，内存块号为-1，即没在内存块中。
pageTable[i].isInmemory=0;//初始化时，各页面均不在内存
}
页面请求序列：
int*in=newint[inputSize]。
模拟内存：
int*memory=newint[memorySize]，在程序中模拟内存存放页面号。
4各模块函数功能说明
intMain（）函数提示并接受用户输入等待调入页面数inputSize，可用物理块数memorySize，并随机生成inputSize个请求页面，或提示用户自己输入页面序列。
然后调用FIFO（）、random（）和OPT（）函数实现按不同替换算法调入页面进内存。
voidFIFO（）函数实现先进先出的替换算法调入页面。
voidrandom（）函数实现随机替换算法调入页面。
voidOPT（）函数实现理想型替换算法。
intgetOPTPage（intpage）用于获取最优替换页面所在的内存块。
该函数的算法实现流程图如图2。
三源程序的主要部分
1main函数
intmain（）
{
for（inti=0;i<10;i++）//初始化页表
{
pageTable[i].pageNum=i;
pageTable[i].memoryNum=-1;
pageTable[i].isInmemory=0;
}
cout<<"输入待调入页面数"<cin>>inputSize;
cout<<"输入可使用的物理块数：
"<cin>>memorySize;
inttemp;
srand（（unsigned）time（NULL））;
cout<<"随机生成页面请求序列（0-9）"<for（i=0;i{
temp=rand（）%10;
cout<in[i]=temp;
}
cout<random（）;
return0;
}
四使用说明
运行程序替换算法.exe，根据提示输入等待调入页面数和可使用的物理块数，程序会提示是否随机生成并显示一个页面请求序列，如果是，则随机生成序列，否则，要求自行输入序列。
然后显示利用各算法处理请求页面的结果：
如果页面在内存则显示“‘页面号’isinmemory”，若不在内存则显示“‘页面号’notinmemory！
takeplaceof‘被替换的页面号’”。
处理完各页面后，统计并显示缺页次数和缺页率。
五运行结果与运行情况分析
待调入页面数：
25
可用物理块数：
3
随机生成页面请求序列，如图3：
0394016015095276888252530
图3
3随机替换算法
运行结果，如图5：
图5
结果分析，如表3（×表示缺页，并在下方填被替换的页面号，√表示不缺页）：
表3
0
3
9
4
0
1
6
0
1
5
0
9
5
2
7
6
8
8
8
2
5
2
5
3
0
0
0
0
4
4
4
4
0
0
0
0
0
0
0
0
6
6
6
6
6
5
5
5
5
5
3
3
3
0
1
6
6
1
1
1
9
9
9
7
7
7
7
7
7
7
7
7
7
0
9
9
9
9
9
9
9
5
5
5
5
2
2
2
8
8
8
2
2
2
2
3
3
×
×
×
×
×
×
×
√
√
×
×
×
√
×
×
×
×
√
√
×
×
√
√
×
×
0
3
0
1
4
6
9
1
5
9
0
2
8
6
2
7
通过表可以看出，利用随机替换算法，请求序列共缺页19次，替换序列依次是：
0301469159028627缺页率为76%，运行结果与分析结果一致。
附录
#include
#include
usingnamespacestd;
intinputSize;
intmemorySize;
int*in;//请求序列
int*memory;//模拟内存
voidrandom（）;
intgetOPTPage（intinPage）;
structpage
{
intpageNum;
intmemoryNum;
intisInmemory;
};
pagepageTable[10];//假设虚拟页面数10个，页表长度10
intmain（）
{
for（inti=0;i<10;i++）//初始化页表
{
pageTable[i].pageNum=i;
pageTable[i].memoryNum=-1;
pageTable[i].isInmemory=0;
}
cout<<"输入待调入页面数"<cin>>inputSize;
cout<<"输入可使用的物理块数"<cin>>memorySize;
in=newint[inputSize];
memory=newint[memorySize];
inttemp;
intselect;
srand（（unsigned）time（NULL））;
cout<<"随机生成请求序列？
（1是）"<cin>>select;
if（select==1）
{
cout<<"随机生成页面请求序列（0-9）"<for（i=0;i{
temp=rand（）%10;
cout<in[i]=temp;
}
}
else
{
cout<<"输入"<for（i=0;i{
cin>>temp;
in[i]=temp;
}
}
cout<random（）;
delete[]in;
delete[]memory;
return0;
}
voidrandom（）//随机替换算法实现函数
{
for（inti=0;i<10;i++）//初始化页表
{
pageTable[i].pageNum=i;
pageTable[i].memoryNum=-1;
pageTable[i].isInmemory=0;
}
srand（（unsigned）time（NULL））;
cout<<"随机替换算法:
"<for（i=0;i{
memory[i]=-1;
}
intlackTime=0;
intreplace=0;////////被替换的物理块号
intisFull=0;
intpage=0;
do
{
if（pageTable[in[page]].isInmemory==1）//in[i]在memory中
{
cout<page++;
if（page==inputSize）break;
elsecontinue;
}
else
{
lackTime++;
cout<"<for（intj=0;j<10;j++）
{
if（pageTable[j].memoryNum==isFull）
{
pageTable[j].memoryNum=-1;
pageTable[j].isInmemory=0;
break;
}
}
memory[isFull]=in[page];//装入内存
pageTable[in[page]].isInmemory=1;
pageTable[in[page]].memoryNum=isFull;
isFull++;
page++;if（page==inputSize）break;
}
}while（isFull!
=memorySize）;
for（i=page;i{
if（pageTable[in[i]].isInmemory==1）//in[i]在memory中
{
cout<continue;
}
else//in[i]不在memory中
{
lackTime++;
replace=rand（）%memorySize;
for（intj=0;j<10;j++）
{
if（pageTable[j].memoryNum==replace）
{
cout<takeplaceofpage"<pageTable[j].memoryNum=-1;
pageTable[j].isInmemory=0;
break;
}
}
memory[replace]=in[i];
pageTable[in[i]].isInmemory=1;
pageTable[in[i]].memoryNum=replace;
}
}
cout<<"缺页次数：
"<cout<<"缺页率：
"<}
intgetOPTPage（intpage）//获得理想的替换页面
{
int*opt=newint[memorySize];
for（inti=0;iopt[i]=0;
for（i=0;i{
for（intj=0;j<10;j++）
{
if（pageTable[j].memoryNum==i）
{
for（intt=page+1;t{
if（j==in[t]）
{
opt[i]=t;
break;
}
}
if（opt[i]==0）
{
opt[i]=inputSize;
}
break;
}
}
}
intoptNum=0;
for（i=0;i{
if（opt[i]>opt[optNum]）
optNum=i;
}
returnoptNum;
}
升级会员 