在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法

常见的置换算法有：

1．最佳置换算法（OPT）（理想置换算法）

2．先进先出置换算法（FIFO）：

3．最近最久未使用（LRU）算法

4．Clock置换算法（LRU算法的近似实现）

5．最少使用（LFU）置换算法

6．工作集算法

7 . 工作集时钟算法

8. 老化算法（非常类似LRU的有效算法）

9. NRU(最近未使用）算法

10. 第二次机会算法

操作系统页面置换算法代码

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h> #define TRUE 1

#define FALSE 0

#define INVALID -1

#define NUL 0

#define total_instruction 320 /*指令流长*/

#define total_vp 32 /*虚页长*/

#define clear_period 50 /*清零周期*/

typedef struct{ /*页面结构*/

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_head,*busypf_tail;

int diseffect,a[total_instruction];

int page[total_instruction], offset[total_instruction];

void initialize(int);

void FIFO(int);

void LRU(int);

void NUR(int);

int main()

{

int S,i;

srand((int)getpid());

S=(int)rand()%390;

for(i=0;i<total_instruction;i+=1) /*产生指令队列*/

{

a[i]=S; /*任选一指令访问点*/

a[i+1]=a[i]+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[i]=a[i]/10;

offset[i]=a[i]%10;

}

for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/

{

printf("%2d page frames",i);

FIFO(i);

LRU(i);

NUR(i);

printf("\");

}

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[i]].pfn==INVALID) /*页面失效*/

{

diseffect+=1; /*失效次数*/

if(freepf_head==NUL) /*无空闲页面*/

{

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[i];

pl[page[i]].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[i]].pfn==INVALID) /*页面失效*/

{

diseffect++;

if(freepf_head==NUL) /*无空闲页面*/

{

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[i]].pfn=freepf_head->pfn;

pl[page[i]].time=present_time;

freepf_head=freepf_head->next;

}

else

pl[page[i]].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[i]].pfn==INVALID) /*页面失效*/

{

diseffect++;

if(freepf_head==NUL) /*无空闲页面*/

{

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[i]].pfn=freepf_head->pfn;

freepf_head=freepf_head->next;

}

else

pl[page[i]].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[i].pn=i;pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/

pl[i].counter=0;pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/

}

for(i=1;i<total_pf;i++)

{

pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[i]之间的连接*/

}

pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;

freepf_head=&pfc[0]; /*页面队列的头指针为pfc[0]*/

}

/*说明：本程序在Linux的gcc下和c-free下编译运行通过*/