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，中文名稱是「線性可更換單元」。