opt和lru算法区别

Ⅰ OPT页面置换算法最优性证明。

1常见的置换算法

1．最佳置换算法（OPT）（理想置换算法）：所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。2．先进先出置换歼燃谈算法（FIFO）：优先淘汰最早进入的页面，亦即在内存中驻留时间最久的页面。3．最近最久未使用（LRU）算法：选择最近氏碰最长时间未访问过的页面予以淘汰。4．Clock置换算法（LRU算法的近似实现）：给每一帧关联一个附加位，称为使用位。5．最少使用（LFU）置换算法6．工作集算法7 . 工作集时钟算法8. 老化算法（非常类似LRU的有效算法）9. NRU(最近未使用）算法10. 第二次机会算法2操作系统页面置换算法代码#include <stdio.h>^[1]#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;}elsepl[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;}elsepl[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下编译运行通过*/【http://wenku..com/link?url=o_】
不知道能不能打开-是复制的 但也辛苦半天 忘采纳~

Ⅱ lru算法是什么

LRU是Least Recently Used的缩写，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近培樱旦最少使用的页面予以淘汰。

特点：

LRU 算法弊端是存在偶发性、周期性的批量操会降低缓配扰存的命中率，对缓存造成污染，下面几个就是改进算法。

LRU-K会记录每条数据的访问历史，当达到 k 时，才将数据存放到缓存，在缓存内存回收时，缓存中越接近 k 的数据被优先删除。

Two queues（2Q）相当于 LRU-2，区别是访问历颂隐史（首次访问）数据缓存于 FIFO 队列，二次及以上的数据存放LRU缓存，FIFO 队列数据遵循该缓存的内存回收机制，LRU缓存数据遵循该缓存的内存回收机制。

Ⅲ OPT算法，FIFO算法，CLOCK算法和LRU算法

其实这种题目是非常简单的：

页号：2,3,2,1,4,5,2,4,5,1,3,2,5,2
O: 1 3 4 1 共有4次中断
F: 2 3 1 4 5 2 1 共有7次中断
C: 3 2 1 2 4 5 1 共有7次中断
L: 3 1 2 4 5 1 共有6次中断

Ⅳ 操作系统课程设计，用C#实现内存页面的置换。实现算法间比较

页面置换算法

一．题目要求：

通过实现页面置换算法的FIFO和LRU两种算法，理解进程运行时系统是怎样选择换出页面的，对于两种不同的算法各自的优缺点是哪些。

要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。

2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的：

1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三、设计要求

1、编写算法，实现页面置换算法FIFO、LRU；

2、针对内存地址引用串，运行页面置换算法进行页面置换； 3、算法所需的各种参数由输入产生（手工输入或者随机数产生）； 4、输出内存驻留的页面集合，页错误次数以及页错误率；

四．相关知识：

1．虚拟存储器的引入：

局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。

2．虚拟存储器的定义：

虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

3．虚拟存储器的实现方式：

分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。

请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。

4．页面分配：

平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。

考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。

5．页面置换算法：

常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、设计说明

1、采用数组页面的页号

2、FIFO算法，选择在内存中驻留时间最久的页面予以淘汰；

分配n个物理块给进程，运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。

3、LRU算法，根据页面调入内存后的使用情况进行决策；

同样分配n个物理块给进程，前n个不同页面一起装入内存，后面步骤与前一算法类似。

选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换： 六．设计思想：

OPT基本思想：

是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

FIFO基本思想：

是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。

LRU基本思想：

是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。 七．流程图：

如下页所示

六．运行结果： 1. 按任意键进行初始化：

2. 载入数据：

3. 进入置换算法选择界面：

4.运算中延迟操作：

5.三种算法演示结果：

Ⅳ 请分别给出三种不同的页面置换算法,并简要说明他们的优缺点

[fifo.rar]
-
操作系统中内存页面的先进先出的替换算法fifo
[先进先出页面算法程序.rar]
-
分别实现最佳置换算法(optimal)、先进先出(fifo)页面置换算法和最近最久未使用（LRU）置换算法，并给出各算法缺页次数和缺页率。
[0022.rar]
-
模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断
[Change.rar]
-
用java实现操作系统的页面置换
其中包括
最佳置换算法(Optimal)、先进先出算法（First-in,
First-out）
、最近最久不用的页面置换算法（LeastRecently
Used
Replacement）三种算法的实现
[M_Management.rar]
-
操作系统中内存管理页面置换算法的模拟程序，采用的是LRU置换算法
[detail_of_44b0x_TCPIP.rar]
-
TCPIP
程序包加载到44b0x
的ADS1.2工程文件的说明书。说名了加载过程的细节和如何处理演示程序和代码。演示代码已经上传，大家可以搜索
[.rar]
-
java操作系统页面置换算法：
（1）进先出的算法（fifo）
（2）最近最少使用的算法（LRU）
（3）最佳淘汰算法(OPT)
（4）最少访问页面算法(LFU)
（注：由本人改成改进型Clock算法）
（5）最近最不经常使用算法(NUR)

Ⅵ 操作系统

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

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

实验内容
设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。
1、最佳淘汰算法（OPT）
2、先进先出的算法（FIFO）
3、最近最久未使用算法（LRU）
4、最不经常使用算法（LFU）
5、最近未使用算法（NUR）
命中率＝1－页面失效次数／页地址流长度

实验准备
本实验的程序设计基本上按照实验内容进行。即首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。
（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：
A：50%的指令是顺序执行的
B：25%的指令是均匀分布在前地址部分
C：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）将指令序列变换为页地址流
设：页面大小为1K；
用户内存容量4页到32页；
用户虚存容量为32K。
在用户虚存中，按每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 INVALID -1
#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_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];

int initialize(int);
int FIFO(int);
int LRU(int);
int LFU(int);
int NUR(int);
int OPT(int);

int main( )
{
int s,i,j;
srand(10*getpid()); /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/
s=(float)319*rand( )/32767/32767/2+1; //
for(i=0;i<total_instruction;i+=4) /*产生指令队列*/
{
if(s<0||s>319)
{
printf("When i==%d,Error,s==%d\n",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==%d\n",i,a[i+2],s);

}
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---\n",i);
FIFO(i);
LRU(i);
LFU(i);
NUR(i);
OPT(i);

}
return 0;
}

int initialize(total_pf) /*初始化相关数据结构*/
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=0;i<total_pf-1;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 FIFO(total_pf) /*先进先出算法*/
int total_pf; /*用户进程的内存页面数*/
{
int i,j;
pfc_type *p;
initialize(total_pf); /*初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect+=1; /*失效次数*/
if(freepf_head==NULL) /*无空闲页面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID;
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;
}
}
printf("FIFO:%6.4f\n",1-(float)diseffect/320);

return 0;
}

int LRU (total_pf) /*最近最久未使用算法*/
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==NULL) /*无空闲页面*/
{
min=32767;
for(j=0;j<total_vp;j++) /*找出time的最小值*/
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=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.4f\n",1-(float)diseffect/320);
return 0;
}

int NUR(total_pf) /*最近未使用算法*/
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==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<total_vp;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<total_vp;j++)
pl[j].counter=0;
}
printf("NUR:%6.4f\n",1-(float)diseffect/320);

return 0;
}

int OPT(total_pf) /*最佳置换算法*/
int total_pf;
{int i,j, max,maxpage,d,dist[total_vp];
pfc_type *t;
initialize(total_pf);
for(i=0;i<total_instruction;i++)
{ //printf("In OPT for 1,i=%d\n",i); //i=86;i=176;206;250;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<total_vp;j++)
if(pl[j].pfn!=INVALID) dist[j]=32767; /* 最大"距离" */
else dist[j]=0;
d=1;
for(j=i+1;j<total_instruction;j++)
{
if(pl[page[j]].pfn!=INVALID)
dist[page[j]]=d;
d++;
}
max=-1;
for(j=0;j<total_vp;j++)
if(max<dist[j])
{
max=dist[j];
maxpage=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.4f\n",1-(float)diseffect/320);

return 0;
}

int LFU(total_pf) /*最不经常使用置换法*/
int total_pf;
{
int i,j,min,minpage;
pfc_type *t;
initialize(total_pf);
for(i=0;i<total_instruction;i++)
{ if(pl[page[i]].pfn==INVALID) /*页面失效*/
{ diseffect++;
if(freepf_head==NULL) /*无空闲页面*/
{ min=32767;
for(j=0;j<total_vp;j++)
{if(min>pl[j].counter&&pl[j].pfn!=INVALID)
{
min=pl[j].counter;
minpage=j;
}
pl[j].counter=0;
}
freepf_head=&pfc[pl[minpage].pfn];
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.4f\n",1-(float)diseffect/320);

return 0;
}

四、运行结果
4 page frams
FIFO: 0.7312
LRU: 0.7094
LFU: 0.5531
NUR: 0.7688
OPT: 0.9750
5 page frams
…………
五、分析
1、从几种算法的命中率看，OPT最高，其次为NUR相对较高，而FIFO与LRU相差无几，最低的是LFU。但每个页面执行结果会有所不同。
2、OPT算法在执行过程中可能会发生错误
五、思考
1、为什么OPT在执行时会有错误产生？

Ⅶ lru/lfu可以称为近似opt算法吗

LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面!
LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!
比如,第二种方法的时期T为10分钟,如果每分钟进行一次调页,主存块为3,若所需页面走向为2 1 2 1 2 3 4
注意,当调页面4时会发生缺页中断
若按LRU算法,应换页面1(1页面最久未被使用) 但按LFU算法应换页面3(十分钟内,页面3只使用了一次)
可见LRU关键是看页面最后一次被使用到发生调度的时间长短,
而LFU关键是看一定时间段内页面被使用的频率!

Ⅷ 操作系统题：页面置换算法 OPT FIFO LRU

fifo就是先进先出，可以想象成队列
lru是最久未使用，当需要替换页面的时候，向前面看，最久没使用的那个被替换
opt是替换页面的时候，优先替换后面最迟出现的。
不懂再问。。

Ⅸ lru算法是什么

lru算法是一种页面置换算法，在对于内存中但是又不用的数据块，叫做LRU，操作系统会根据那些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。

LRU算法：最近最少使用，简单来说就是将数据块中，每次使用过的数据放在数据块的最前端，然后将存在的时间最长的，也就是数据块的末端的数据剔除掉这就是LRU算法。

如果进程被调度，该进程需要使用的外存页（数据）不存在于数据块中，这个现象就叫做缺页。如果这个数据此时不在，就会将这个数据从加入到数据块首部。

数据块插入与剔除：每次有新数据到来时，会将其放入数据块首部，当数据每次被访问时，将这个数据插入数据块的首部如果数据块满了，每次新进的数据都会将数据块尾部的数据挤出数据块。

差距

为了尽量减少与理想算法的差距，产生了各种精妙的算法，最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。

反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是着名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最少使用的那个页面调出内存。这就是LRU算法的全部内容。

LRU在电子系统中的解释：

Line Replaceable Unit—LRU，电子系统中常采用模块化设计，这种可更换的模块单元则被叫做LRU，中文名称是“线性可更换单元”。