先進先出頁面淘汰演算法
1. 請分別給出三種不同的頁面置換演算法,並簡要說明他們的優缺點
[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)
2. lru 淘汰演算法
最佳演算法（OPT演算法）
當需要淘汰一個內存頁面時，這種演算法力圖選擇該進程內存各個頁面中永遠不再需要的頁，若找不到，則選擇最久以後才會用到的頁。這種演算法有最小的缺頁率。問題是它需要知道運行進程今後的整個訪問蹤跡，這往往難以做到，因而它只有理論上的意義。
先進先出演算法（FIFO演算法）
FIFO演算法維護一個先進先出隊列，隊列長度為分配給這個進程的頁面數M。開始時隊列是空的，裝入進程的第一頁即可啟動運行，當訪問到某個不在內存的頁面時，把它從輔存調入，加入FIFO隊列的尾部。
最久未使用淘汰演算法（LRU演算法）
LRU（least recently used）演算法維護一個後進先出棧，棧大小為分配給這個進程的頁面數M。開始時棧是空的，裝入進程的第一頁即可啟動運行，當訪問到某個不在內存的頁面時，把它從輔存調入，加入棧頂。
FIFO和LRU演算法的例子：http://osjx.8100988.net/LWR/RAM/HLM/FIFOsf.HTM
CLOCK演算法
又叫NRU（Not Recently Used）演算法，NRU又名近似的LRU置換演算法。
當一存儲塊中的頁面訪問時，其相應的「頁面訪問」位由硬體自動置「1」，而由頁面管理體制軟體周期性地（設周期為T，其值通常為幾百毫秒），把所有的頁面訪問位重新置為「0」。這樣，在時間T內，某些被訪問的頁面，其對應的訪問位為「1」而未訪問的頁面，其對應的訪問位為「0」。查尋頁面訪問位為「0」的頁面。在查找過程中，那些被訪問的頁所對應的訪問位被重新置為「0」。由此可見，實際上這種近似LRU演算法，已經退化成一種「最近不用」的演算法NRU（Not Recently Used）。
CLOCK演算法的例子：http://www.cskaoyan.com/thread-4898-1-1.html
其實這個問題我也不太會，去臨時查的資料，第一個例子是我自己算的，不知道我理解得對不對；如果有錯誤的地方還請指正，共同進步~其他的演算法的例子我都給了鏈接，你自己去看吧。
3. 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_】
不知道能不能打開-是復制的 但也辛苦半天 忘採納~
4. 關於先進先出（FIFO）頁面淘汰演算法
輸入：1，2，3，4，1，2，5，1，2，3，4，5
先進先出，就是保存最近3個訪問的記錄在內存中
, , <—1 中斷1次
, ,1<—2 中斷1次
, 1,2<—3 中斷1次
1,2,3 <—4 中斷1次
2,3,4 <—1 中斷1次
3,4 ,1<—2 中斷1次
4,1,2<—5 中斷1次
1,2,5<—1 命中，不中斷
2,5,1 <—2 命中，不中斷
5,1,2<—3 中斷1次
1,2,3 <—4 中斷1次
2,3,4 <—5 中斷1次
3,4,5
累計中斷12次
5. 儲存管理中,分頁式虛擬儲存管理的頁面淘汰演算法有
儲存管理中，分頁式虛擬儲存管理的頁面淘汰鏈森演算法有先進先出法，最近最少使用頁面陸櫻先淘汰，最優淘汰演算法。最優淘汰演算法(OPT)：系統預測作業今後要訪問的頁面，淘汰頁是將來不被訪問的頁面或者在最長時間早喚叢後才被訪問的頁面。它保證有最少的缺頁率，但它實現困難，只能通過理論分析用來衡量其它演算法的優劣。
6. 頁面置換演算法
上文說到，請求分頁管理方式中，當需要調入頁面到內存中，但此時內存已滿，就需要從內存中按照一定的置換演算法決定將哪個頁面取出將內存給調入的頁面。本文將介紹幾種頁面置換算方法。
本文內容
演算法思想：每次選擇 淘汰的頁面 將是 以後永不使用 ，或者 在最長時間內不再被訪問的頁面 ，這樣可以保證最低的缺頁率。
舉例說明，假設系統為進程分配了三個內存塊，並考慮到有以下頁面號引用串（會依次訪問這些頁面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
....按照此演算法依次執行，最後的結果如下
結果圖
註：缺頁時未必發生頁面置換，若還有可用的空閑內存空間就不用進行頁面置換。
最佳置換演算法可以保證最低的缺頁率，但是實際上，只有進程執行的過程中才能知道接下來會訪問到的是哪個頁面。操作系統無法提前預判頁面的訪問序列。因此， 最佳置換演算法是無法實現的 。
演算法思想：每次選擇 淘汰的頁面是最早進入內存的頁面。
該演算法很簡單，每次淘汰最在內存中待時間最久的各個，下面分別給出系統為進程分為配三個內存塊和四個內存塊的執行情況圖。訪問序列為3,2,1,0,3,2,4,3,2,1,0,4
分配三個內存塊的情況：
分配四個內存塊的情況：
當為進程分配的物理塊數增大時，缺頁次數不減反增的異常現象稱為 貝萊迪（Belay）異常 。
只有FIFO演算法會產生Belay異常。 另外，FIFO演算法雖然實現簡單，但是該演算法與進程實際運行時的規律不適應。因為先進入的頁面也有可能最經常被訪問。因此， 演算法性能差。
演算法思想： 每次淘汰的頁面是最近最久未使用的頁面。
實現方法：賦予每個頁面對應的頁表項中，用 訪問欄位記錄該頁面純虧自上次被訪問以來所經歷的時間t。 當需要淘汰一個頁面時，選擇現有頁面中t最大的頁面，即最近最久未使用。
舉例說明，加入某系統為某進程分配了四個內存塊，並考慮到有以下頁面號引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
這里先直接給出答案
結果圖
最佳置換演算法那性能最好，但無法實現。先進先出置換演算法實現簡單，但是演算法性能差。最近最久未使用置換演算法性能好，是最接近OPT演算法性能的，但是實現起來需要專門的硬體支持，演算法開銷大。 時鍾置換演算法 是一種 性能和開銷均春褲配平衡 的演算法。又稱 CLOCK演算法 ，或 最近未用演算法 （ NRU ，Not Recently Used）
簡單CLOCK演算法 演算法思想：為每個頁面設置一個 訪問位 ，再將內存中的頁面都通過 鏈接指針鏈接成一個循環隊列 。當某個頁被訪問時，其訪問位置1.當需要淘汰一個頁面時，只需檢查頁的訪問位。如果是0，就選擇該頁換出；如果是1，暫不換出，將訪問位改為0，繼續檢查下一個頁面，若第一輪掃描中所有的頁面都是1，則將這些頁面的訪問位一次置為0後，再進行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面，因此簡單的CLOCK演算法選擇一個扒指淘汰頁面最多會經過 兩輪掃描 ）。
這個演算法指針在掃描的過程就像時鍾一樣轉圈，才被稱為時鍾置換演算法。
簡單的時鍾置換演算法僅考慮到了一個頁面最近是否被訪問過。事實上，如果淘汰的頁面沒有被修改過，就不需要執行I/O操作寫回外存。 只有淘汰的頁面被修改過時，才需要寫回外存。
因此，除了考慮一個頁面最近有沒有被訪問過之外，操作系統還需要考慮頁面有沒有被修改過。
改進型時鍾置換演算法的 演算法思想 ： 在其他在條件相同時，應該優先淘汰沒有被修改過的頁面， 從而來避免I/O操作。
為了方便討論，用（訪問位，修改位）的形式表示各頁面的狀態。如（1,1）表示一個頁面近期被訪問過，且被修改過。
演算法規則 ：將所有可能被置換的頁面排成一個循環隊列
由於第二輪已將所有的頁的訪問位都設為0，因此第三輪、第四輪掃描一定會選中一個頁，因此 改進型CLOCK置換演算法最多會進行四輪掃描。
假設系統為進程分配了5個內存塊，某時刻，各個頁的狀態如下圖
如果此時有新的頁要進入內存，開始第一輪掃描就找到了要替換的頁，即最下面的狀態為（0,0）的頁。
某一時刻頁面狀態如下
如果此時有新的頁要進入內存，開始第一輪掃描就發現沒有狀態為（0，0）的頁，第一輪掃描後不修改任何標志位。所以各個頁狀態和上圖一樣。
然後開始第二輪掃描，嘗試找到狀態為（0,1）的頁，並將掃描過後的頁的訪問位設為0，第二輪掃描找到了要替換的頁。
某一時刻頁面狀態如下
第一輪掃描沒有找到狀態為（0,0）的頁，且第一輪掃描不修改任何標志位，所以第一輪掃描後狀態和上圖一致。
然後開始第二輪掃描，嘗試找狀態為（0,1）的頁，也沒有找到，第二輪掃描需要將訪問位設為1，第二輪掃描後，狀態為下圖
某一時刻頁面狀態如下
具體的掃描過程和上面相同，這里只給出最後的結果，如下圖
所以，改進型的CLOCK置換演算法最多需要四輪掃描確定要置換的頁。從上面的分析可以看出，改進型的CLOCK置換演算法
(1) 第一優先順序淘汰的是 最近沒有訪問且沒有修改 的頁面。
(2) 第二優先順序淘汰的是 最近沒有訪問但修改 的頁面。
(3) 第三優先順序淘汰的是 最近訪問但沒有修改 的頁面。
(4) 第四優先順序淘汰的是 最近訪問且修改 的頁面。
7. 先進先出頁面淘汰演算法
#include<stdio.h>
#include<stdlib.h>
#define max 30
typedef struct{
int visit_number;//要訪問的頁面號
}nu,number[max];
int *memoryblock;//主存中有三個主存塊，可裝三個頁面
void init_memoryblock(int n)//初始化主存塊
{
int i=1;
memoryblock=(int*)malloc(sizeof(int));//分配空間
for(i=1;i<=n;i++)
{
memoryblock[i]=-1;//開始時候沒有頁面進入，初始為-1
}
}
void init_visitpage(number num,int n)//n表示要訪問的頁面的個數
{
int i=0;
int j=3;
printf("輸入要訪問的頁面號: ");
for(i=1;i<=n;i++)
{
scanf("%d",&num[i].visit_number);
}
printf("\n");
}
void FIFO_page_dispatch(number num,int n)//FIFO頁面調度演算法
{
int i,j=3,temp,counter=0;
for(i=1;i<=n;i++)
{
//----------------------------頁面在主存中-------------------------------
for(j=3;j>=1;j--)
{
if(num[i].visit_number==memoryblock[j])//////要訪問的頁面在主存中
{
printf("(%d)頁面在主存塊中，換出和換進都是%d號頁面:\n",i,memoryblock[j]);
}
break;
}
//-----------------------------------------------------------------------
//----------------------------頁面不在主存中-----------------------------
if(num[i].visit_number!=memoryblock[1]&&num[i].visit_number!=memoryblock[2]&&
num[i].visit_number!=memoryblock[3])/////////////[ 1 ]
/*內存中沒有要訪問的頁面，中斷*/
{
if(memoryblock[1]!=-1&&memoryblock[2]!=-1&&memoryblock[3]!=-1)
{
temp=memoryblock[3];
memoryblock[3]=memoryblock[2];
memoryblock[2]=memoryblock[1];
memoryblock[1]=num[i].visit_number;
//---------------------------------
printf("(%d)——頁面發生置換:",i);
printf("換出(%d號)頁面—",temp);
printf("換進(%d)號頁面\n",num[i].visit_number);
counter++;
}
for(j=3;j>=1;j--)//////////////[ 2 ]
{
if(memoryblock[j]==-1)//還有空閑主存塊
{
printf("(%d)有空閑主存塊，%d號頁面直接調入:\n",i,i);
memoryblock[j]=num[i].visit_number;
break;
}
}
//-----------------------------移動主存塊-------------------
}
//------------------------------------------------------------------------
}
printf("\n共產生 %d 次頁面置換:",counter);
}
void main()
{
number num;
int m,n;
printf("輸入要訪問頁面串的個數(<30)和內存塊個數：");
{
scanf("%d%d",&n,&m);
getchar();
}
init_memoryblock(m);//初始化主存塊
init_visitpage(num,n);//輸入要訪問的頁面號順序
FIFO_page_dispatch(num,n);//FIFO調度
printf("\n");
}
8. 頁面淘汰演算法
LRU（2個塊）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 3 3 2 2 5 5 2 2 2 2 7 7 3 3 1 1 3 3
2 2 4 4 1 1 6 6 1 1 3 3 6 6 2 2 2 2 6
缺頁中斷18次
LRU（4個塊）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 5 3 3 3 3 3 3 3 3 3
4 4 4 4 6 6 6 6 6 7 7 7 7 1 1 1 1
缺頁中斷次數10次
FIFO（2個塊）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 3 3 6 6 2 2 2 3 3
2 2 4 4 1 1 6 6 1 1 2 7 7 3 3 1 1 1 6
缺頁中斷次數18次
FIFO（4個塊）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 5 5 5 5 5 3 3 3 3 3 1 1 1 1
2 2 2 2 2 2 6 6 6 6 6 7 7 7 7 7 7 3 7
3 3 3 3 3 3 2 2 2 2 2 6 6 6 6 6 6 6
4 4 4 4 4 4 1 1 1 1 1 1 2 2 2 2 2
缺頁中斷次數：14次
9. 頁面調度先進先出演算法（FIFO） 用c語言描述 歡迎高手前來挑戰
c語言實現的頁面調度演算法,用三種演算法實現調度1.先進先出2.OPT3.LRU 2.頁面序列從指定的文本文件（TXT文件）中取出3.輸出：第一行：每次淘汰的頁面號 第二行：顯示缺頁的總次數(上機已經運行通過!!)-pages scheling algorithm, a three-Scheling Algorithm 1. FIFO 2.OPT3.LRU 2. Pages from the designated sequence of text files (TXT) out of three. Output : the first line : each of the pages out of the second line : show na the total number of pages (on the plane had run through! !)
10. 最佳頁面淘汰演算法是怎樣計算的
<1> 先進先出調度演算法
先進先出調度演算法根據頁面進入內存的時間先後選擇淘汰頁面，先進入內存的頁面先淘汰，後進入內存的後淘汰。本演算法實現時需要將頁面按進入內存的時間先後組成一個隊列，每次調度隊首頁面予以淘汰。
<2>最近最少調度演算法
先進先出調度演算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程序執行的局部性特點，程序一旦訪問了某些代碼和數據，則在一段時間內會經旅旅常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。演算法實現時需要為每個頁面設置數據結構記錄頁面自上次訪問以來所經歷的時間。
<3>最近最不常用調度演算法
由於程序設計中經常使用循環結構，根據程序執行的局部性特點，可以設想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度演算法啟擾總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。演算法實現時需要為每個頁面設置計數器，記錄訪問次數。計數器由硬體或操作系統自動定時清零。
（2）拆旁凳缺頁調度次數和缺頁中斷率、缺頁置換率計算
缺頁中斷次數是缺頁時發出缺頁中斷的次數。
缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100%
缺頁調度次數是調入新頁時需要進行頁面調度的次數
缺頁置換率=缺頁調度次數/總的頁面引用次數*100%