页面置换算法c语言代码(页面置换算法c语言代码怎么写)

置换算法

printf("FIFO:%6.4fn",1-(float)diseffect/320);

置换算法是一种页面置换法，用于在内存不足时选择哪些页面从内存中删除以便为新页面腾出空间。

页面置换算法c语言代码(页面置换算法c语言代码怎么写)

页面置换算法c语言代码(页面置换算法c语言代码怎么写)

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。

其所选择的被淘汰页面，将是以后使用的，或许是在最长（未来）时间内不再被访问的页面。采用置换算法，通常可保证获得的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其他算法。

和置换算法相类似的算法：

1、先进先出置换pl[i].pfn=INVALID; /置页面控制结构中的页号，页面为空/算法

是最简单的页面置换算法。这种算法的基本思想是当需要淘汰一个页面时，总是选择驻留生存时间最长的页面进行淘汰，即先进入的页面先淘汰。其理由是最早调入主存的页面不再被使用的可能性。即优先淘汰最早进入内存的页面。

2、最近scanf("%d",&ps);最久未使用算法

这种算法的基本思想是利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种做法的实质是当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。

作系统

实验内容

实验七 存储管理---------常用页面置换算法模拟实验

实验目的

通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。

1、淘汰算法（OPT）

2、先进先出的算法（FIFO）

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

4、最不经常使用算法（LFU）

5、最近未使用算法（NUR）

命中率＝1－页面失效次数／页地址流长度

实验准备

本实验的程序设计基本上按照实验内容进行。即首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。

（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：

A：50%的指令是顺序执行的

B：25%的指令是均匀分布在前地址部分

C：25%的指令是均匀分布在后地址部分

具体的实施方法是：

B：顺序执行一条指令，即执行地址为m+1的指令

C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’

D：顺序执行一条指令，其地址为m’+1

E：在后地址[m’+2，319]中随机选取一条指令并执行

F：重复步骤A-E，直到320次指令

（2）将指令序列变换为页地址流

设：页面大小为1K；

用户内存容量4页到32页；

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：

第 0 条-第 9 条指令为第0页（对应虚存地址为[0，9]）

第10条-第19条指令为第1页（对应虚存地址为[10，19]）

………………………………

第310条-第319条指令为第31页（对应虚存地址为[310，319]）

按以上方式，用户指令可组成32页。

实验指导

一、虚拟存储系统

UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。

当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。

为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。

二、页面置换算法

当 CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。

常用的页面置换算法有

1、置换算法（Optimal）

2、先进先出法（Fisrt In First Out）

3、最近最久未使用（Least Recently Used）

4、最不经常使用法（Least Frequently Used）

5、最近未使用法（No Used Recently）

三、参考程序：

#define TRUE 1

#define FALSE 0

#define NULL 0

#define total_instruction 320 /指令流长/

#define total_vp 32 /虚页长/

#define clear_period 50 /清0周期/

typedef struct /页面结构/

{int pn,pfn,counter,time;

pl_type pl[total_vp]; /页面结构数组/

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

int FIFO(int);

int LRU(int);

int LFU(int);

int OPT(int);

int main( )

{int s,i,j;

srand(10getpid()); /由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”/

s=(float)319rand( )/32767/32767/2+1; //

{if(s<0||s>319)

{printf("When i==%d,Error,s==%dn",i,s);

exit(0);

}a[i]=s; /任选一指令访问点m/

a[i+1]=a[i]+1; /顺序执行一条指令/

a[i+2]=(float)a[i]rand( )/32767/32767/2; /执行前地址指令m' /

a[i+3]=a[i+2]+1; /顺序执行一条指令/

s=(float)(318-a[i+2])rand( )/32767/32767/2+a[i+2]+2;

if((a[i+2]>318)||(s>319))

printf("a[%d+2],a number which is :%d and s==%dn",i,a[i+2],s);

}for (i=0;i

{page[i]=a[i]/10;

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

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

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

FIFO(i);

LFU(i);

NUR(i);

OPT(i);

}return 0;

}int initialize(total_pf) /初始化相关数据结构/

int total_pf; /用户进程的内存页面数/

{int i;

diseffect=0;

for(i=0;i

{pl[i].pn=i;

pl[i].counter=0;

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

}for(i=0;i

{pfc[i].next=&pfc[i+1];

pfc[i].pfn=i;

} /建立pfc[i-1]和pfc[i]之间的链接/

pfc[total_pf-1].next=NULL;

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

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

ret{int min,minj,i,j,present_time;urn 0;

{int i,j;

pfc_type p;

initialize(total_pf); /初始化相关页面控制用数据结构/

busypf_head=busypf_tail=NULL; /忙页面队列头，队列尾链接/

{if(pl[page[i]].pfn==INVALID) /页面失效/

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

if(freepf_head==NULL) /无空闲页面/

{p=busypf_head->next;

freepf_head=busypf_head; /释放忙页面队列的个页面/

freepf_head->next=NULL;

busypf_head=p;

}p=freepf_head->next; /按FIFO方式调新页面入内存页面/

freepf_head->next=NULL;

freepf_head->pn=page[i];

pl[page[i]].pfn=freepf_head->pfn;

if(busypf_tail==NULL)

busypf_head=busypf_tail=freepf_head;

else

{busypf_tail->next=freepf_head; /free页面减少一个/

busypf_tail=freepf_head;

}freepf_head=p;

}}

return 0;

}int LRU (total_pf) /最近最久未使用算法/

int total_pf;

initialize(total_pf);

present_time=0;

{if(pl[page[i]].pfn==INVALID) /页面失效/

{diseffect++;

if(freepf_head==NULL) /无空闲页面/

{min=32767;

{min=pl[j].time;

minj=j;

}freepf_head=&pfc[pl[minj].pfn]; //腾出一个单元

pl[minj].pfn=INVALID;

pl[minj].time=-1;

freepf_head->next=NULL;

}pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效

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

freepf_head=freepf_head->next; //减少一个free 页面

}else

pl[page[i]].time=present_time; //命中则增加该单元的访问次数

present_time++;

}printf("LRU:%6.4fn",1-(float)diseffect/320);

return 0;

}int NUR(total_pf) /最近未使用算法/

int total_pf;

{ int i,j,dp,cont_flag,old_dp;

initialize(total_pf);

dp=0;

{ if (pl[page[i]].pfn==INVALID) /页面失效/

{diseffect++;

if(freepf_head==NULL) /无空闲页面/

{ 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

pl[j].counter=0;

}freepf_head=&pfc[pl[dp].pfn];

pl[dp].pfn=INVALID;

freepf_head->next=NULL;

}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

pl[j].counter=0;

}printf("NUR:%6.4fn",1-(float)diseffect/320);

return 0;

}int OPT(total_pf) /置换算法/

int total_pf;

{int i,j, max,maxpage,d,dist[total_vp];

initialize(total_pf);

{ //printf("In OPT for 1,i=%dn",i); //i=86;i=176;206;;220,221;192,193,194;258;274,275,276,277,278;

if(pl[page[i]].pfn==INVALID) /页面失效/

{diseffect++;

if(freepf_head==NULL) /无空闲页面/

{for(j=0;j

if(pl[j].pfn!=INVALID) dist[j]=32767; / "距离" /

else dist[j]=0;

d=1;

for(j=i+1全局页面算法:不是由于页不够，缺页率页面置换算法Q(PFF，page fault frequency):动态调整常驻集的大小缺页率:缺页次数/内存Q访问次数。;j

{if(pl[page[j]].pfn!=INVALID)

dist[page[j]]=d;

}max=-1;

for(j=0;j

if(max

{max=dist[j];

}freepf_head=&pfc[pl[maxpage].pfn];

freepf_head->next=NULL;

pl[maxpage].pfn=INVALID;

}pl[page[i]].pfn=freepf_head->pfn;

freepf_head=freepf_head->next;

}}

printf("OPT:%6.4fn",1-(float)diseffect/320);

return 0;

}int LFU(total_pf) /最不经常使用置换法/

int total_pf;

{int i,j,min,minpage;

initialize(total_pf);

{ if(pl[page[i]].pfn==INVALID) /页面失效/

{ diseffect++;

if(freepf_head==NULL) /无空闲页面/

{ min=32767;

for(j=0;j

{if(min>pl[j].counter&&pl[j].pfn!=INVALID)

minpage=j;

}pl[j].counter=0;

pl[minpage].pfn=INVALID;

freepf_head->next=NULL;

}pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效

pl[page[i]].counter++;

freepf_head=freepf_head->next; //减少一个free 页面

}else

pl[page[i]].counter++;

}printf("LFU:%6.4fn",1-(float)diseffect/320);

return 0;

}四、运行结果

4 page frams

LRU: 0.7094

LFU: 0.5531

NUR: 0.7688

OPT: 0.9750

…………

1、从几种算法的命中率看，OPT，其次为NUR相对较高，而FIFO与LRU相无几，的是LFU。但每个页面执行结果会有所不同。

2、OPT算法在执行过程中可能会发生错误

五、思考

作系统页面置换算法题，谁会？

1 先来先服务

第二次机会算法：

与FIFO、OPT、LRU、NRU等同为作系统中请求分FIFO: 0.7312页式管理方式的页面置换算法。

第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，依然和FIFO一样，选择最早置入内存的页A：在[0，319]的指令地址之间随机选取一起点m面。但是二次机会法还设置了一个访问状态位。所以还要检查页面的的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置为1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。

第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。

用C语言或者其他语言编写替代密码和置换密码

pfc_type t;

给你，自己再稍微改造一下吧：

pl[busypf_head->pn].pfn=INVALID;

#include "stdio.h"

#include "conio.h"

main()

{int k,i=0;

char a[100],b[100];

printf("qing shu ni de mi wen n");

gets(a);

printf("qing shu mi shi n");

scanf("%d",&k);

printf("n");

do{

b[i]=(char)(a[i]+k);

if(b[i]>122){

b[i]=(char)(b[i]-26在先进先出算法的基础上进行该机而来的，此算法按照先进先出算法选择某一页面，检查其访问位 R ，如果为 0 ，则置换该页；如果为 1 ，则给第二次机会，并将访问位置零，并将其从链头取下放到链尾。);

}i++;

}while(a[i]!='0');

puts(b);

getch();

}

页面置换算法之LRU算法

if(min>pl[j].time&&pl[j].pfn!=INVALID)

三种常见的页面置换算法:FIFO、LFU、LRU

参考for(i=0;i

缓存算法（页面置换算法）-FIFO、LFU、LRU

LRU（Least Recently Used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是： 如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小 。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

设 序列为 4 3 4 2 3 1 4 2

物理块有3个 则

首轮 4调入内存 4

次轮 3调入内存 3 4

之后 4调入内存 4 3

之后 2调入内存for(j=0;j

之后 3调入内存 3 2 4

之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）

之后 4调入内存 4 1 3（原理同上）

2调入内存 2 4 1

如果让我们设计一个LRU Cache的数据结构，它应该支持两个作：

一种是采用数组来存储每个数据项，再对每个key关联一个时间戳，在cache中维护一个时间戳，其设计要点如下：

另一种是采用hashmap+双向链表的数据结构，其设计要点如下：

对比上一节的两种设计思路，不难发现，设计1需要为每个key维护一个时间戳，而且set和get作的时间复杂度都是O(n)。显而易见，随着数据量的增大，set和get作的速度越来越慢。而设计2通过采用hashmap+双向链表，set和get作的时间复杂度只需O(1)，下面给出设计2的具体实现。

运行结果为：

参考：

LRU Cache

LRU原理和Redis实现——一个今日的面试题

磁盘调度算法SSTF算法 不限制编程语言，可以选用C/C++等

int total_pf; /用户进程的内存页面数/

Ja版的磁盘调度算法，

其中五、分析算法包含

2 最短时5 page frams间优先

3 最短时间优先

4 单向扫描算法

程序是动画演示的，程序以圆模拟磁道，以方块模拟磁头根据算法在界面上演示。

12、存储模型2（作系统笔记）

#define INVALID -1

我们将虚拟存储技术和页式存储管理方案结合起来得到了虚拟页式存储管理系统。具体有两种方式，一是请求调页，二是预先调页。以 cpu 时间和磁盘换取昂贵内存空间，这是作系统中的资源转换技术。

LRU(i);

通常，页表项是硬件设计的。

又称页面淘汰算法。算法-->先进先出-->第二次机会-->时钟算法-->最近未使用-->最近最少使用-->最不经常使用-->老化算法-->工作集-->工作集时钟

在第二次机会算法中当给某个页面第二次机会的时候，将其访问位置零，然后将其挂到链尾，这都是需要开销的，于是我们改进为时钟算法。

选择一次访问时间距离当前时间最长的一页并置换，即置换未使用时间最长的一页。

即 Not frequently Used ，选择访问次数最少的页面置换

例子：

要求：

计算应用 FIFO、LRU、OPT 算法时的缺页次数

应用 FIFO、LRU 页面置换算法

应用OPT页面置换算法

例子：系统给某进程分配 m 个页框，初始为空页面访问顺序为

1 2 3 4 1 2 5 1 2 3 4 5 ，采用 FIFO 算法，计算当 m=3 和 m=4 时的缺页中断次数。

结论： m=3 时，缺页中断九次； m=4 时，缺页中断十次。注意： FIFO 页面置换算产生异常现象（ Belady 现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加。

缺页越多，系统的性能越，这称为颠簸（当缺页中断发生时，当你有很多内存时，可以从空闲页链表中取出一个空闲页映射到虚拟页。当内存不足时，会发生页面置换。由于访问磁盘的时间比访问内存的时间慢10万倍（磁盘时间：10ms，内存时间：100ns）,哪怕SSD也就只有普通磁盘的10倍速度以上。平均访问时间 = 访问RAM的时间+ 丢失率访问DISK时间，而访问磁盘时间为内存时间的几万倍，所以降低丢失率，哪怕很小的比重，都对平均访问时间有个很大的提升。所以一个好的页面置换算法尤为重要。抖动）：虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多，这样导致系统效率急剧下降，这种现象称为颠簸或抖动。

例子：

分配了一个页框，页面大小为 128 个整数，矩阵 A(128 x 128) 按行存放。

如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数，这是由 Denning 提出的。

用c语言分页式存储管理的地址转换过程实现

用户虚存容量为32K。

逻辑地址}int FIFO(total_pf) /先进先出算法/转换为物理地址

#include

main()

{int p,d,la,pa,ps,a[100],n,i;/pa为物理地址，la为物理地址，ps为页面大小，a[100]存放页表中对应主存的页号，n为页面数/

printf("请输入逻辑地址la=");/输入逻辑地址/

scanf("%d",&la);

printf("请输入页面大小ps=");/输入页面大小/

printf("请输入页面数n=");/输入页面数/

scanf("%d",&n);

for(i=0;i

{printf("输入页表中第%d页项中主存页号=",i);

scanf("%d",&a[i]);

}/输入页表中主存的页号/

paint NUR(int);=a[p]ps+d;

}

DES算法，求c++代码。IP置换。 1.随机产生64位二进制数 2.根据IP置换表，将此64位二？

}pl_type;

DES算法，IP置换的功能是把输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位，其置换规则见下表：

其典型C代码实现如下：

58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,

62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,

57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,

61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7,

即将输入的第58位换到位，第50位换到第2位，...，依此类推，一位是原来的第7位。L0、R0则是换位输出后的两部分，L0是输出的左32位，R0 是右32位，例

如：设置换前的输入值为D1D2D3......D64，则经过初始置换后的结果为：L0=D58D50...D8；R0=D57D49...D7。

定义IP置换表如上表，char类型数组，长printf("逻辑地址为%d的物理地址为%d",la,pa);度为64；

然后，在从0到64循环，把源数组的数据按IP置换表的内容填到目的数组，即实现了IP置换；

// initial permutation (IP)

const static char IP_Table[64] = {

58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,

62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,

57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,

61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7

};

void DES_InitialPermuteData(char src,char dst)

{//IP

int i=0;

for(i=0;i<64;i++)

{dst[i] =src[IP_Table[i]-1];

}}

作系统

1、为什么OPT在执行时会有错误产生？

实验七 存储管理---------常用页面置换算法模拟实验

for(i=0;i实验目的

通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。

1、淘汰算法（OPT）

2、先进先出的算法（FIFO）

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

4、最不经常使用算法（LFU）

5、最近未使用算法（NUR）

命中率＝1－页面失效次数／页地址流长度

实验准备

本实验的程序设计基本上按照实验内容进行。即首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。

（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：

A：50%的指令是顺序执行的

B：25%的指令是均匀分布在前地址部分

C：25%的指令是均匀分布在后地址部分

具体的实施方法是：

B：顺序执行一条指令，即执行地址为m+1的指令

C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’

D：顺序执行一条指令，其地址为m’+1

E：在后地址[m’+2，319]中随机选取一条指令并执行

F：重复步骤A-E，直到320次指令

（2）将指令序列变换为页地址流

设：页面大小为1K；

用户内存容量4页到32页；

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：

第 0 条-第 9 条指令为第0页（对应虚存地址为[0，9]）

第10条-第19条指令为第1页（对应虚存地址为[10，19]）

………………………………

第310条-第319条指令为第31页（对应虚存地址为[310，319]）

按以上方式，用户指令可组成32页。

实验指导

一、虚拟存储系统

UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。

当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。

为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。

二、页面置换算法

当 CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。

常用的页面置换算法有

1、置换算法（Optimal）

2、先进先出法（Fisrt In First Out）

3、最近最久未使用（Least Recently Used）

4、最不经常使用法（Least Frequently Used）

5、最近未使用法（No Used Recently）

三、参考程序：

#define TRUE 1

#define FALSE 0

#define NULL 0

#define total_instruction 320 /指令流长/

#define total_vp 32 /虚页长/

#define clear_period 50 /清0周期/

typedef struct /页面结构/

{int pn,pfn,counter,time;

pl_type pl[total_vp]; /页面结构数组/

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}freepf_head=&pfc[pl[minpage].pfn]; diseffect, a[total_instruction];

int page[total_instruction], offset[total_instruction];

int FIFO(int);

int LRU(int);

int LFU(int);

int OPT(int);

int main( )

{int s,i,j;

srand(10getpid()); /由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”/

s=(float)319rand( )/32767/32767/2+1; //

{if(s<0||s>319)

{printf("When i==%d,Error,s==%dn",i,s);

exit(0);

}a[i]=s; /任选一指令访问点m/

a[i+1]=a[i]+1; /顺序执行一条指令/

a[i+2]=(float)a[i]rand( )/32767/32767/2; /执行前地址指令m' /

a[i+3]=a[i+2]+1; /顺序执行一条指令/

s=(float)(318-a[i+2])rand( )/32767/32767/2+a[i+2]+2;

if((a[i+2]>318)||(s>319))

printf("a[%d+2],a number which is :%d and s==%dn",i,a[i+2],s);

}for (i=0;i

{page[i]=a[i]/10;

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

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

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

FIFO(i);

LFU(i);

NUR(i);

OPT(i);

}return 0;

}int initialize(total_pf) /初始化相关数据结构/

int total_pf; /用户进程的内存页面数/

{int i;

diseffect=0;

for(i=0;i

{pl[i].pn=i;

pl[i].counter=0;

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

}for(i=0;i

{pfc[i].next=&pfc[i+1];

pfc[i].pfn=i;

} /建立pfc[i-1]和pfc[i]之间的链接/

pfc[total_pf-1].next=NULL;

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

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

return 0;

{int i,j;

pfc_type p;

initialize(total_pf); /初始化相关页面控制用数据结构/

busypf_head=busypf_tail=NULL; /忙页面队列头，队列尾链接/

{if(pl[page[i]].pfn==INVALID) /页面失效/

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

if(freepf_head==NULL) /无空闲页面/

{p=busypf_head->next;

freepf_head=busypf_head; /释放忙页面队列的个页面/

freepf_head->next=NULL;

busypf_head=p;

}p=freepf_head->next; /按FIFO方式调新页面入内存页面/

freepf_head->next=NULL;

freepf_head->pn=page[i];

pl[page[i]].pfn=freepf_head->pfn;

if(busypf_tail==NULL)

busypf_head=busypf_tail=freepf_head;

else

{busypf_tail->next=freepf_head; /free页面减少一个/

busypf_tail=freepf_head;

}freepf_head=p;

}}

return 0;

}int LRU (total_pf) /最近最久未使用算法/

int total_pf;

initialize(total_pf);

present_time=0;

{if(pl[page[i]].pfn==INVALID) /页面失效/

{diseffect++;

if(freepf_head==NULL) /无空闲页面/

{min=32767;

{min=pl[j].time;

minj=j;

}freepf_head=&pfc[pl[minj].pfn]; //腾出一个单元

pl[minj].pfn=INVALID;

pl[minj].time=-1;

freepf_head->next=NULL;

}pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效

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

freepf_head=freepf_head->next; //减少一个free 页面

}else

pl[page[i]].time=present_time; //命中则增加该单元的访问次数

present_time++;

}printf("LRU:%6.4fn",1-(float)diseffect/320);

return 0;

}int NUR(total_pf) /最近未使用算法/

int total_pf;

{ int i,j,dp,cont_flag,old_dp;

initialize(total_pf);

dp=0;

{ if (pl[page[i]].pfn==INVALID) /页面失效/

{diseffect++;

if(freepf_head==NULL) /无空闲页面/

{ 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

pl[j].counter=0;

}freepf_head=&pfc[pl[dp].pfn];

pl[dp].pfn=INVALID;

freepf_head->next=NULL;

}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

pl[j].counter=0;

}printf("NUR:%6.4fn",1-(float)diseffect/320);

return 0;

}int OPT(total_pf) /置换算法/

int total_pf;

{int i,j, max,maxpage,d,dist[total_vp];

initialize(total_pf);

{ //printf("In OPT for 1,i=%dn",i); //i=86;i=176;206;;220,221;192,193,194;258;274,275,276,277,278;

if(pl[page[i]].pfn==INVALID) /页面失效/

{diseffect++;

if(freepf_head==NULL) /无空闲页面/

{for(j=0;j

if(pl[j].pfn!=INVALID) dist[j]=32767; / "距离" /

else dist[j]=0;

d=1;

for(j=i+1;j

{if(pl[page[j]].pfn!=INVALID)

dist[page[j]]=d;

}max=-1;

for(j=0;j

if(max

{max=dist[j];

}freepf_head=&pfc[pl[maxpage].pfn];

freepf_head->next=NULL;

pl[maxpage].pfn=INVALID;

}pl[page[i]].pfn=freepf_head->pfn;

freepf_head=freepf_head->next;

}}

printf("OPT:%6.4fn",1-(float)diseffect/320);

return 0;

}int LFU(total_pf) /最不经常使用置换法/

int total_pf;

{int i,j,min,minpage;

initialize(total_pf);

{ if(pl[page[i]].pfn==INVALID) /页面失效/

{ diseffect++;

if(freepf_head==NULL) /无空闲页面/

{ min=32767;

for(j=0;j

{if(min>pl[j].counter&&pl[j].pfn!=INVALID)

minpage=j;

}pl[j].counter=0;

pl[minpage].pfn=INVALID;

freepf_head->next=NULL;

}pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效

pl[page[i]].counter++;

freepf_head=freepf_head->next; //减少一个free 页面

}else

pl[page[i]].counter++;

}printf("LFU:%6.4fn",1-(float)diseffect/320);

return 0;

}四、运行结果

4 page frams

LRU: 0.7094

LFU: 0.5531

NUR: 0.7688

OPT: 0.9750

…………

1、从几种算法的命中率看，OPT，其次为NUR相对较高，而FIFO与LRU相无几，的是LFU。但每个页面执行结果会有所不同。

2、OPT算法在执行过程中可能会发生错误

五、思考