折叠 编辑本段 基本简介
在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫360百科做页面置换算法。
折叠 提编辑本段 置换算法
最佳置换算法
这是一种理想情况下的页面置换算以天眼球法，但实际上是不可能实现的。该算法的基本思想是:发生缺页时，有些页面在内存中，其中有一页将很快被访问(也包含紧接着的下一条指令的那页)，而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可 以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定:标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操越厚略座夜克作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能据进行衡量比较。
先进先出置换算法
最简单的页面置换算法是先入先出(FIFO)法。这种算法的实质是，总是选择在主存中停留时间最长(即最老)的一页置换，即先进入内存的页，先退出内存。理由是:最早调入内存的页，其不玉杆声今伟官粒乱再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换古收书附阳活页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间 时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变"老"而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而方氢是则方零香世时师使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
城团未图跟话增益受材最近最久未使用算法
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间居采范搞无。如果以最近的过去作为不久将来的近似，那波六带可优命表厚么就可以把过去最八汽给基有得怀系针长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称给然械罪为最久未使用算法(Least Recently Used，LRU)波血进课候右。
LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面必选甲分都开同以。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需明要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法:
1.计数器。最简单的情况是使每个页表项对应一个使用时既常架洋容种式构问燃百间字段，并给CPU增加一个逻迅眼么着所衡先辑时钟或计数器。每次存储访问，该时钟都加1来感。每当访问一个页面时，时钟寄存广赶半器的内容就被复制到相应页表项的使用时间字段中依转月绿友略者龙。这样我们就可以始终保留着每个页面最后访问的"时间"。在置换页面时，选择该时间值最小的页面。这样做， 不仅要查页表，而且当页表改变时(因CPU调度以)要 维护这个页表中的时间，还要考虑到时钟值溢出的问题。
2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由较半背派纸粮论于要从栈的中间移走一项，所以给唱种答笔助院要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个略导强有双重是好相奏象页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，助还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算语很国沿样降层与统法(Not Recently Used，NUR)。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪如些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。
4)Clock置换算法(LRU算法的近似实现)
5)最少使用(LFU)置换算法
在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 m副事呢族s时间内可能对某页面连续访 问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在标现终值激不只最近一段时间使用最少的页面将是∑Ri最小的页。
LFU置换算法的页面访问图与LRU置换算法的访问图完全相同;跳倒象练或者说，利用这样一套硬件既可实现LRU算法，又可实南掉议须草破特战破资现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。
6)工作集算法
7)工作集时钟算法
8)老化算法(非常类似LRU长急府端验的有效算法)
9)巴游愿却NRU(最近未使用)算法
10)第二次机会算法
第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用财月正的页面置换出去。当选择置换页面时，检查它的访问位。如果是 0，就淘汰这页;如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面距流般威得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前农洲断时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其身显所续注各他页面被淘汰过(或者也给了第二次机会)。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。
第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个 存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把略选较伟白超威节名记专访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。
折叠 编辑本段 置换算法代码
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h> #define TRUE 1
#define FALSE 0
#define INVALID -1
#define NU燃远收数居生L 0
#define 民立练械致万total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清零周期*/
typedef s批怀剂客知例truct{ /*页面结构*/
int pn,pfn,counter,time;
}pl_type;
pl_type pl[total_vp]办地值味找李互矛坏须吸; /*页面结构数组*/
struct pfc_struct{ /*页面控制结构*/
int pn,pfn;
struct pfc_struct *next;
};
假织本跳typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_h作呢封校ead,*busypf_tail;
int di剂术格对接评独seffect,a[tota执留深钢毛l_instruction];
int page[total_instruction], offset[tota夜细l_instruction];
void initialize(int);
void FIFO(int);
void LRU(i急算拿出待存盾nt);
void NUR(int);
int main()
{
int S,i;
srand((int)getpid());
S=(int)rand()%390;
for(i=0;i<total_instruction;i+=1) /*产生指令队列*/
{
a=S; /*任选一指令访问点*/
a[i+1]=a+1; /*顺序执行一条指令*/
a[i+2]=(int)rand()%390; /*执行前地址指令m'*/
a[i+3]=a[i+2]+1; /*执行后地址指令*/
S=(int)rand()%390;
}
for(i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
{
page=a/10;
offset=a%10;
}
for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/
{
printf("%2d page frames",i);
FIFO(i);
LRU(i);
NUR(i);
printf("\n");
}
return 0;
}
void FIFO(int total_pf) /*FIFO(First in First out)ALGORITHM*/
/*用户进程的内存页面数*/
{
int i;
pfc_type *p, *t;
initialize(total_pf); /*初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NUL; /*忙页面队列头，对列尾链接*/
for(i=0;i<total_instruction;i++)
{
if(pl[page].pfn==INVALID) /*页面失效*/
{
diseffect+=1; /*失效次数*/
if(freepf_head==NUL) /*无空33闲页面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID; /*释放忙页面队列中的第一个页面*/
freepf_head=busypf_head;
freepf_head->next=NUL;
busypf_head=p;
}
p=freepf_head->next; /*按方式调新页面入内存页面*/
freepf_head->next=NUL;
freepf_head->pn=page;
pl[page].pfn=freepf_head->pfn;
if(busypf_tail==NUL)
busypf_head=busypf_tail=freepf_head;
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf("FIFO:%6.4F",1-(float)diseffect/320);
}
void LRU(int total_pf)
{
int min,minj,i,j,present_time;
initialize(total_pf);present_time=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NUL) /*无空闲2页面*/
{
min=32767;
for(j=0;j<total_vp;j++)
if(min>pl[j].time&&pl[j].pfn!=INVALID)
{
min=pl[j].time;
minj=j;
}
freepf_head=&pfc[pl[minj].pfn];
pl[minj].pfn=INVALID;
pl[minj].time=-1;
freepf_head->next=NUL;
}
pl[page].pfn=freepf_head->pfn;
pl[page].time=present_time;
freepf_head=freepf_head->next;
}
else
pl[page].time=present_time;
present_time++;
}
printf("LRU:%6.4f",1-(float)diseffect/320);
}
void NUR(int total_pf)
{
int i,j,dp,cont_flag,old_dp;
pfc_type *t;
initialize(total_pf);
dp=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NUL) /*无空闲1页面*/
{
cont_flag=TRUE;old_dp=dp;
while(cont_flag)
if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)
cont_flag=FALSE;
else
{
dp++;
if(dp==total_vp)
dp=0;
if(dp==old_dp)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NUL;
}
pl[page].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
else
pl[page].counter=1;
if(i%clear_period==0)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
printf("NUR:%6.4f",1-(float)diseffect/320);
}
void initialize(int total_pf) /*初始化相关数据结构*/
/*用户进程的内存页面数*/
{
int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl.pn=i;pl.pfn=INVALID; /*置页面控制结构中的页号，页面为空*/
pl.counter=0;pl.time=-1; /*页面控制结构中的访问次数为0，时间为-1*/
}
for(i=1;i<total_pf;i++)
{
pfc[i-1].next=&pfc;pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc之间的连接*/
}
pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*页面队列的头指针为pfc[0]*/
}
/*说明:本程序在Linux的gcc下和c-free下编译运行通过*/