OPT最佳頁面置換演算法

⑴ 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_】
不知道能不能打開-是復制的 但也辛苦半天 忘採納~

⑵ 頁面置換演算法有哪些

頁面置換演算法包括先進先出（FIFO）、最近最久未使用（LRU）、最不常用（LFU）、時鍾（Clock）以及理想（OPT）演算法。
1. 先進先出（FIFO）演算法
該演算法的基本原則是先進入內存的頁面先被置換。當內存空間不足時，系統會選擇最早進入內存的頁面進行置換。FIFO演算法的優勢在於實現簡單，但其缺點在於未能考慮頁面的實際使用頻率和重要性，可能導致不必要的性能損耗。
2. 最近最久未使用（LRU）演算法
LRU演算法依據頁面的歷史訪問記錄來進行頁面置換。它傾向於將最長時間未被訪問的頁面置換出內存。為了有效地追蹤頁面訪問順序，LRU演算法通常需要使用特殊的數據結構，如鏈表或棧。盡管LRU演算法在理論上較為合理，但其實現復雜度較高，且需要額外的存儲空間來維護訪問順序。
3. 最不常用（LFU）演算法
LFU演算法是基於頁面訪問頻率的置換策略。它認為訪問頻率低的頁面在未來也較少會被訪問，因此將這些頁面置換出內存。LFU演算法需要跟蹤每個頁面的訪問頻率，並進行相應的排序。然而，LFU演算法可能會導致一些頻繁訪問的頁面被過早置換，影響系統性能。
4. 時鍾（Clock）演算法
Clock演算法是基於FIFO的一種改進。它使用一個時鍾指針來遍歷頁面隊列，並根據特定的標記位（如訪問位或修改位）來決定置換頁面。當新頁面需要載入時，時鍾指針繼續移動，直到找到一個標記位為0的頁面進行置換。Clock演算法的優勢在於其實現相對簡單且效率較高。
5. 理想（OPT）演算法
理想演算法是一個理論上的最優頁面置換演算法，它能夠准確預測未來的頁面訪問模式，並據此選擇最長時間內不會被訪問的頁面進行置換。然而，由於實際中無法准確預測訪問模式，OPT演算法在現實中無法完美實現。

⑶ 頁面置換演算法常見的置換演算法

頁面置換演算法在計算機內存管理中扮演重要角色，用於解決內存與處理器之間的數據交換問題。其中，不同演算法各有其特點與適用場景。

最佳置換演算法（OPT）旨在選擇未來永不訪問或最久不訪問的頁面淘汰，以此降低缺頁率，實現內存資源的高效利用。

先進先出置換演算法（FIFO）遵循「先入先出」原則，淘汰最早進入內存的頁面。該演算法簡單直觀，但可能因預測不準確而產生較多缺頁現象。

最近最久未使用（LRU）演算法基於頁面的訪問歷史，淘汰最近最久未訪問的頁面，以確保頻繁訪問的頁面得到優先訪問機會。

Clock置換演算法（LRU演算法的近似實現）通過為每幀關聯使用位，動態模擬LRU演算法的淘汰策略，實現對最近未使用的頁面的高效淘汰。

最少使用（LFU）置換演算法關注頁面的訪問頻率，淘汰訪問次數最少的頁面，旨在平衡頁面訪問頻率與內存使用效率。

工作集演算法考慮程序運行時的頁面使用情況，通過工作集的大小預測頁面需求，實現更合理的頁面置換。

工作集時鍾演算法結合Clock置換演算法與工作集概念，優化內存管理策略，提升演算法效能。

老化演算法（類似LRU的有效演算法）通過跟蹤頁面的訪問情況，對頁面進行「老化」處理，淘汰訪問頻率較低的頁面，以優化內存使用。

NRU（最近未使用）演算法追蹤頁面的使用情況，優先淘汰長時間未被訪問的頁面，減少缺頁現象。

第二次機會演算法在頁面置換策略中引入二次淘汰機會，對被淘汰頁面進行評估，若發現有較高訪問頻率，可將其重新加入內存，減少因錯誤預測帶來的缺頁成本。

在地址映射過程中，若在頁面中發現所要訪問的頁面不再內存中，則產生缺頁中斷。當發生缺頁中斷時操作系統必須在內存選擇一個頁面將其移出內存，以便為即將調入的頁面讓出空間。而用來選擇淘汰哪一頁的規則叫做頁面置換演算法

⑷ 操作系統題：頁面置換演算法 OPT FIFO LRU

fifo就是先進先出，可以想像成隊列
lru是最久未使用，當需要替換頁面的時候，向前面看，最久沒使用的那個被替換
opt是替換頁面的時候，優先替換後面最遲出現的。
不懂再問。。

⑸ 最佳置換演算法最後一個怎麼辦

最佳置換演算法(OPT)(理想置換演算法):從主存中移出永遠不再需要的頁面;如無這樣的頁面存在,則選擇最長時間不需要訪問的頁面。於所選擇的被淘汰頁面將是以後永不使用的,或者是在最長時間內不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。 最佳置換演算法可以用來評價其他演算法。