fifo頁面置換演算法
『壹』 頁面置換演算法FIFO 、LRU求缺頁中斷次數
(1)FIFO
123412512345
----------------------------------------
123412555344
12341222533該行是怎麼算出來的？
1234111255該行是怎麼算出來的？
----------------------------------------
缺頁中斷次數=9
FIFO是這樣的：3個內存塊構成一個隊列，前3個頁面依次入隊（3個缺頁），內存中為3-2-1；
接著要訪問4號頁面，內存中沒有（1個缺頁），按FIFO，1號頁面淘汰，內存中為4-3-2；
接著要訪問1號頁面，內存中沒有（1個缺頁），按FIFO，2號頁面淘汰，內存中為1-4-3；
接著要訪問2號頁面，內存中沒有（1個缺頁），按FIFO，3號頁面淘汰，內存中為2-1-4；
接著要訪問5號頁面，內存中沒有（1個缺頁），按FIFO，4號頁面淘汰，內存中為5-2-1；
接著要訪問1號頁面，內存中有（命中），內存中為5-2-1；
接著要訪問2號頁面，內存中有（命中），內存中為5-2-1；
接著要訪問3號頁面，內存中沒有（1個缺頁），按FIFO，1號頁面淘汰，內存中為3-5-2；
接著要訪問4號頁面，內存中沒有（1個缺頁），按FIFO，2號頁面淘汰，內存中為4-3-5；
接著要訪問5號頁面，內存中有（命中），內存中為4-3-5；
缺頁中斷次數=9（12次訪問，只有三次命中）
LRU不同於FIFO的地方是，FIFO是先進先出，LRU是最近最少用，如果1個頁面使用了，要調整內存中頁面的順序，如上面的FIFO中：
接著要訪問1號頁面，內存中有（命中），內存中為5-2-1；
在LRU中，則為
接著要訪問1號頁面，內存中有（命中），內存中為1-5-2；
『貳』 頁式管理的請求頁式管理中的置換演算法
功能：需要調入頁面時，選擇內存中哪個物理頁面被置換。稱為replacement policy。
出發點：把未來不再使用的或短期內較少使用的頁面調出，通常只能在局部性原理指導下依據過去的統計數據進行預測。
頁面鎖定(frame locking)：用於描述必須常駐內存的操作系統的關鍵部分或時間關鍵(time-critical)的應用進程。實現方法為在頁表中加上鎖定標志位(lock bit)。 輪轉法(RR,round robin)和先進先出演算法(FIFO,first in first out):輪轉法循回換出內存可用區內一個可以被換出的頁，無論該頁是剛被換進或已換進內存很長時間。FIFO演算法總是選擇在內存駐留時間最長的一員將其淘汰。
FIFO演算法認為先調入內存的頁不再被訪問的可能性要比其它頁大，因而選擇最先調入內存的頁換出。實現FIFO演算法需要把各個已分配頁面按分配時間順序鏈接起來，組成FIFO隊列，並設置一置換指針指向FIFO隊列的隊首頁面。這樣，當要進行置換時，只需把置換指針所指的FIFO隊列前頭的頁順次換出，而把換入的頁鏈接在FIFO隊尾即可。
由實驗和測試發現FIPO演算法和RR演算法的內存利用率不高。這是因為，這兩種演算法都是基於CPU按線性順序訪問地址空間這一假設。事實上，許多時候．CPU不是按線性順序訪問地址空間的。
Belady現象:一般來說，對於任一作業或進程，如果給它分配的內存頁面數越接近於它所要求的頁面數，則發生缺頁的次數會越少。在極限情況下，這個推論是成立的。因為如果給一個進程分配了它所要求的全部頁面，則不會發生缺頁現象。但是，使用FIFO演算法時，在未給進程或作業分配足它所要求的頁面數時，有時會出現分配的頁面數增多，缺頁次數反而增加的奇怪現象。這種現象稱為Belady現象。 最近最久未使用頁面置換演算法(LRU, Least Recently Used):
選擇內存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳演算法。但由於需要記錄頁面使用時間的先後關系，硬體開銷太大。硬體機構如：
(1) 一個特殊的棧：把被訪問的頁面移到棧頂，於是棧底的是最久未使用頁面。
(2) 每個頁面設立移位寄存器：被訪問時左邊最高位置1，定期右移並且最高位補0，於是寄存器數值最小的是最久未使用頁面。
比較常用的近似演算法有：
(a) 最不經常使用頁面淘汰演算法(LFU, Least Frequently Used)
(b) 最近沒有使用頁面淘汰(NRU, Not Recently Used) 理想型淘汰演算法（OPT,Optimal Replacement Algorithm）
該演算法淘汰在訪問串中將來再也不出現的或是離當前最遠的位置上出現的頁。它是一種理想化的演算法，性能最好，但在實際上難於實現。
『叄』 fifo演算法是什麼
FIFO（First Input First Output），即先進先出隊列。可以類比 我們在飯堂排隊打飯，先排到隊伍的最後，等待前面的人一個個打完飯再輪到下一個。這就是一種先進先出機制，先排隊的人先行打飯離開。
FIFO（先進先出頁面置換演算法）：看到先進先出，我們想到的數據結構就是隊列當分配的內存物理塊數量為3時。
6，7，5先進入內存，那麼出來的順序就是5，7，6 缺頁次數為3次。
2調入內存，6調出內存，那麼順序就是2，5，7 缺頁次數為4次。
6調入內存，7調出內存，那麼順序就是6，2，5 缺頁次數為5次。
7調入內存，5調出內存，那麼順序就是7，6，2 缺頁次數為6次。
3調入內存，2調出內存，那麼順序就是3，7，6 缺頁次數為7次。
6調入內存，已經存在，不需要調入。
7調入內存，已經存在，不需要調入。
5調入內存，6調出內存，那麼順序就是5，3，7 缺頁次數為8次。
2調入內存，7調出內存，那麼順序就是2，5，3 缺頁次數為9次。
3調入內存，已經存在，不需要調入。
『肆』 用C++語言編寫FIFO頁面置換演算法代碼
分別使用FIFO、OPT、LRU三種置換演算法來模擬頁面置換的過程。（Linux、Windows下皆可）
輸入：3//頁幀數
70120304230321201701//待處理的頁
輸出：頁面置換過程中各幀的變化過程和出現頁錯誤的次數
[cpp]
#include<iostream>
usingnamespacestd;
intinput[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
classpage
{
public:
intnum;
intmark;
page()
{
num=0;
mark=21;
}
};
voidFIFO()
{
cout<<"------FIFO-----------"<<endl;
interror=0;
pageframe[3];//頁幀
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
frame[((error-1)%3)].num=input[i];//換掉最舊的頁
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidOPT()
{
cout<<"------OPT------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=21;
for(intk=20;k>=i;k--)//向後遍歷，找到最長時間不用的頁
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark>frame[1].mark&&frame[0].mark>frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark>frame[0].mark&&frame[1].mark>frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidLRU()
{
cout<<"------LRU------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//處理前三個引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=0;
for(intk=0;k<=i;k++)//向前遍歷，找到最近最少使用的
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark<frame[1].mark&&frame[0].mark<frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark<frame[0].mark&&frame[1].mark<frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
intmain()
{
FIFO();
OPT();
LRU();
}
『伍』 下述什麼頁面置換演算法會產生belady現象
先進先出頁面置換演算法（FIFO）。先悶並進先出頁面置換演算法（FIFO）頁面置換演算法會產生Belady異常現數罩塌象。先進先出頁面置換演算法的基本思想：每次置換最先調入內存的頁面，即將內存中等待時間最長的頁面進行置換。此算薯圓法的適用范圍是順序結構程序。
『陸』 如何用java實現fifo頁面置換演算法
[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)
『柒』 一個程序的頁面走向，FIFO和LRU頁面置換演算法
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
void FIFO(void);
void LRU(void);
char a;
int m=4,n=12,i,y[12]={1,2,3,4,1,2,5,1,2,3,4,5}; /*m為物理塊數，n為要訪問的頁面數*/
typedef struct page{
int num;
int time;
}Page;
Page x[10];
int GetMax(page *x) /*求出那個物理塊中的頁面呆的時間最長，返回物理塊號*/
{
int i;
int max=-1;
int tag=0;
for(i=0;i<m;i++)
{
if(x[i].time>max)
{ max=x[i].time;
tag=i;
}
}
return tag;
}
void Xunhuan()
{
printf("Please select 1:FIFO演算法\n 2:LRU演算法\n");
scanf("%s",&a);
printf("物理塊數：4\n");
//scanf("%d",&m);
for(i=0;i<m;i++) /*將空的物理塊中數據置為-1*/
{
x[i].num=-1;
}
printf("所要訪問的頁面數：12\n");
//scanf("%d",&n);
//srand(time(NULL));
printf("所要訪問的頁面號序列為：");
for(i=0;i<n;i++)
printf("%d ",y[i]);
printf("\n");
printf("頁面置換步驟如下：\n");
switch(a)
{
case '1':FIFO();break;
case '2':LRU(); break;
}
}
void main()
{
char a;
Xunhuan();
while(1)
{
printf("Continue or Exit:C/Anykey:\n");
scanf("%s",&a);
if(a=='c'||a=='C')
Xunhuan();
else break;
}
exit(0);
}
void FIFO(void)
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i])
{
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1)
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0;
}
if(u!=1&&x[m-1].num==-1)
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++;
for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n");
}
}
void LRU()
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i]) /*物理塊中存在相同頁面*/
{
x[j].time=0; /*將相同的物理塊的time置為0*/
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1) /*物理塊中無相同頁面且物理塊已填滿*/
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0; /*將剛替換的頁面所在的物理塊time置為0*/
}
if(u!=1&&x[m-1].num==-1) /*物理塊中無相同頁面且物理塊未填滿*/
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++; /*每執行完一次time加1*/
for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n"); /*格式化輸出*/
}
}
『捌』 操作系統題：頁面置換演算法 OPT FIFO LRU
fifo就是先進先出，可以想像成隊列
lru是最久未使用，當需要替換頁面的時候，向前面看，最久沒使用的那個被替換
opt是替換頁面的時候，優先替換後面最遲出現的。
不懂再問。。