【概念介紹&案例解析】
最佳(Optimal)置換算法
最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，将是以後永不使用的，或是在最長(未來)時間内不再被通路的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。
但由于人們目前還無法預知一個程序在記憶體的若幹個頁面中，哪一個頁面是未來最長時間内不再被通路的，因而該算法是無法實作的，但可以利用該算法去評價其它算法。現舉例說明如下。
假定系統為某程序配置設定了三個實體塊，并考慮有以下的頁面号引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
>采用最佳(Optimal)置換算法的結果如下
>缺頁率=缺頁次數/頁面的總個數=6/20=30%(有的教材把前面三個也加進來了算出的缺頁率為9/20=45%，一般情況下我們還是以大多數教材為主選擇前面那種算法，除非教材明确規定才用後者)
【解析】
>首先将前面三個頁面裝進3個實體塊中，當程序要通路頁面2時，将會産生缺頁中斷，是以此時需要按照最佳置換算法将其中最長時間未被通路的頁面7置換出來，當程序通路下一個頁面0時，由于實體塊含有頁面0此時不會産生中斷，當通路頁面3時又會産生缺頁中斷，是以需要将頁面1置換出去，當程序通路頁面0時，由于實體塊含有頁面0也不會産生缺頁中斷，是以排在最上面的頁面2不需要被置換出去，接下來就是通路頁面4，由于實體塊不包含頁面4，是以會将實體塊中長時間未被通路的0置換出去，後面的一次類推。
>我的總結:對于這類題目，我們隻需要抓住核心就是首先看實體塊中有沒有包含被通路的頁面，如果包含，則實體塊最先進來的(最長時間未被通路的)無需替換，接下來當程序通路下一個頁面的時候，在判斷實體塊是否含有這個被通路的界面，如果沒有則看實體塊中着三個頁面哪個頁面與程序此時通路的頁面的後面不常用的頁面就将這個頁面置換出來，比如:
圖示第五個實體塊2,0,3，當要通路下一個頁面也就是0，因為實體塊包含是以不需要置換出來，接下來通路頁面4因為實體塊不包含頁面4，是以需要看看頁面4後面的哪些頁面在實體塊長時間未出現通過比較我們知道了頁面4後面0是相對于2,3最晚出現是以将0替換就變成了2,4,3，後面的以此類推。
先進先出(FIFO)頁面置換算法：
FIFO算法是最早出現的置換算法、該算法總是淘汰最先進入記憶體的頁面，即選擇在記憶體中駐留時間最久的頁面給予淘汰。
假定系統為某程序配置設定了三個實體塊，并考慮有以下的頁面号引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
>采用FIFO置換算法的結果如下
>缺頁率=缺頁次數/頁面的總個數=12/20=60%
【解析】
我們從第四個實體塊也就是2,0,1開始，因為FIFO置換算法的特點就是淘汰停留最久的頁面，當程序通路頁面2時，因為頁面7最先進入停留的時間最久，是以把7置換出來，當通路頁面0，因為2,0,1含有頁面0是以不需要置換，當通路頁面3的時候，因為實體塊不含頁面3則需要淘汰停留時間最久的頁面0，是以此時的實體塊變為2,3,1接下來程序通路頁面0因為實體塊不含頁面0是以需要淘汰停留時間最長的頁面1也就變成2,3,0，這裡需要注意的一個問題就是實體塊從0,2,3----->0,1,3，因為在4,2,3——————>0,2,3的時候最上面的頁面置換一次是以當通路到頁面1的時候不是置換0而是置換2
最近最久未使用(LRU)置換算法：
FIFO置換算法性能之是以較差，是因為它所依據的條件是各個頁面調入記憶體的時間，而頁面調入的先後并不能反映頁面的使用情況。最近最久未使用(LRU)的頁面置換算法，是根據頁面調入記憶體後的使用情況進行決策的。由于無法預測各頁面将來的使用情況，隻能利用“最近的過去”作為“最近的将來”的近似，是以，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。
假定系統為某程序配置設定了三個實體塊，并考慮有以下的頁面号引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
>采用LRU置換算法的結果如下
>缺頁率=缺頁次數/頁面的總個數=9/20=45%
【解析】
>對于LRU置換算法我們采用的時選擇最近最久未使用的頁面給予淘汰，但這個最近最久該如何了解呢，這時候我們可以想到之前的最佳置換算法，它選擇的時最遠最久未使用的頁面給予淘汰，是以呢我們可以這樣了解LRU中的最近最久，就是當通路某個頁面時候我們往左邊看，比如我們就拿這個例子來進行剖析:我們從2,0,1看起，之前是7,0,1，我們往頁面2的左邊看有7,0,1，這三個頁面是以最近的最久的就是7了是以将7置換出去，當程序通路頁面3時，我們看頁面3最左邊 的那幾個頁面7,0,1,2,0在于實體塊中的2,0,1作比較，那麼最近最久未使用的不就是1嗎，是以我們将1替換，以此類推....
好了上述就是虛拟記憶體的三種置換算法的題目解析了，接下來我們通過代碼來驗證下一個習題(注意:下面的代碼運作在Vc++下的，用Devc++則會報錯)
【代碼展示】
頭檔案FIFO.h
#include<iostream>
#include "iostream.h"
const int MaxNumber=100;
const int BlockNum=10;
typedef struct Page_struct{ //定義頁面結構快
int PageOrder[MaxNumber]; //儲存作業的頁面通路序列
int Simulate[BlockNum][MaxNumber]; //儲存頁面
int Block[BlockNum]; //實體塊
int PageCount[MaxNumber]; //頁面計數
int PageNum,LackNum; //頁面個數、缺頁次數
double PageRate; //缺頁率
bool found;
}Page;
Page p;
bool PageShowEnable[BlockNum][MaxNumber]; //用于存儲數組中的資料是否需要顯示
int N; //頁面個數
int M; //最小實體塊數
int LackCount; //缺頁計數
void Pinput()
{
cout<<"******************虛拟記憶體頁面置換算法***********************"<<endl;
cout<<"請輸入最小實體塊數：";
cin>>M;
while(M > BlockNum) //大于資料個數
{
cout<<"實體塊數超過預定值，請重新輸入：";
cin>>M;
}
cout<<"請輸入頁面的個數：";
cin>>N;
while(N > MaxNumber) //大于資料個數
{
cout<<"頁面個數超過預定值，請重新輸入：";
cin>>N;
}
cout<<"請輸入頁面通路序列："<<endl;
for(int i=0;i<N;i++)
cin>>p.PageOrder[i];
}
void Poutput()
{
int i,j;
for(i=0;i<N;i++)
{
cout<<p.PageOrder[i]<<" ";
}
cout<<endl;
for(j=0;j<M;j++)
{
cout<<" ";
for(i=0;i<N;i++)
{
if(PageShowEnable[j][i])
cout<<p.Simulate[j][i]<<" ";
else
cout<<" ";
}
cout<<endl;
}
cout<<"缺頁次數："<<LackCount<<endl;
cout<<"缺頁率："<<LackCount*100/N<<"%"<<endl;
}
void FIFO(); //FIFO函數
void FIFO()
{
int i,j;
int point;
int temp; //臨時變量
LackCount=0;
for(j=0;j<M;j++)
for(i=0;i<N;i++)
PageShowEnable[j][i]=false; //初始化為false,表示沒有要顯示的資料
for(i=0;i<M;i++)
{
p.PageCount[i]=0;
}
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
p.PageCount[j]++;
p.found=false; //表示塊中有沒有該資料
for(j=0;j<M;j++)
{
if(p.Block[j] == p.PageOrder[i])
{
p.found=true;
}
}
if(p.found)
continue; //塊中有該資料，判斷下一個資料
LackCount++; //塊中沒有該資料,缺頁次數加1
if((i+1)>M)
{
temp=0;
for(j=0;j<M;j++)
{
if(temp<p.PageCount[j])
{
temp=p.PageCount[j];
point=j; //獲得離得最遠的指針
}
}
}
else
point=i;
p.Block[point]=p.PageOrder[i]; //替換
p.PageCount[point]=0; //更新計數值
for(j=0;j<M;j++) //儲存要顯示的資料
{
p.Simulate[j][i]=p.Block[j];
PageShowEnable[i<M?(j<=i?j:i):j][i]=true; //設定顯示資料
}
}
cout<<endl; //輸出資訊
cout<<"先進先出FIFO頁面置換算法:"<<endl;
Poutput();
} 頭檔案Optimal.h
#include<iostream>
void Optimal(); //Optimal函數
void Optimal()
{
int i,j,k;
int point;
int temp; //臨時變量,比較離得最遠的時候用
LackCount=0;
for(j=0;j<M;j++)
for(i=0;i<N;i++)
PageShowEnable[j][i]=false; //初始化為false,表示沒有要顯示的資料
for(i=0;i<N;i++)
{
p.found=false; //表示塊中有沒有該資料
for(j=0;j<M;j++)
{
if(p.Block[j] == p.PageOrder[i])
{
p.found=true;
}
}
if(p.found)
continue;
LackCount++; //塊中沒有該資料，缺頁次數加1
for(j=0;j<M;j++)
{
p.found=false; //找到下一個值的位置
for(k=i;k<N;k++)
{
if(p.Block[j] == p.PageOrder[k])
{
p.found=true;
p.PageCount[j]=k;
break;
}
}
if( !p.found )
p.PageCount[j]=N;
}
if((i+1)>M)
{
temp=0; //獲得要替換的塊指針
for(j=0;j<M;j++)
{
if(temp<p.PageCount[j])
{
temp=p.PageCount[j];
point=j; //獲得離得最遠的指針
}
}
}
else
point=i;
p.Block[point]=p.PageOrder[i]; //替換
p.PageCount[point]=0; //更新計數值
for(j=0;j<M;j++) //儲存要顯示的資料
{
p.Simulate[j][i]=p.Block[j];
PageShowEnable[i<M?(j<=i?j:i):j][i]=true; //設定顯示資料
}
}
cout<<endl; //輸出資訊
cout<<"最佳Optimal頁面置換算法:"<<endl;
Poutput();
} 頭檔案LRU.h
#include<iostream.h>
void LRU()
{
int i,j;
int point;
int temp; //臨時變量
LackCount=0;
for(j=0;j<M;j++)
for(i=0;i<N;i++)
PageShowEnable[j][i]=false; //初始化為false,表示沒有要顯示的資料
for(i=0;i<M;i++)
{
p.PageCount[i]=0;
}
for(i=0;i<N;i++) //對有所資料操作
{
for(j=0;j<M;j++) //增加count
p.PageCount[j]++;
p.found=false; //表示塊中有沒有該資料
for(j=0;j<M;j++)
{
if(p.Block[j] == p.PageOrder[i])
{
p.PageCount[j]=0;
p.found=true;
}
}
if(p.found)
continue;
LackCount++; //塊中沒有該資料,缺頁次數加1
if((i+1)>M)
{
temp=0;
for(j=0;j<M;j++)
{
if(temp<p.PageCount[j])
{
temp=p.PageCount[j];
point=j; //獲得離得最遠的指針
}
}
}
else
point=i;
p.Block[point]=p.PageOrder[i]; //替換
p.PageCount[point]=0; //更新計數值
for(j=0;j<M;j++) //儲存要顯示的資料
{
p.Simulate[j][i]=p.Block[j];
PageShowEnable[i<M?(j<=i?j:i):j][i]=true; //設定顯示資料
}
}
cout<<endl; //輸出資訊
cout<<"最近最久未使用LRU頁面置換算法:"<<endl;
Poutput();
} 主程式Main.cpp
#include<iostream>
#include "FIFO.h"
#include "Optimal.h"
#include "LRU.h"
void Pinput(); //程序參數輸入
void Poutput(); //排程結果輸出
int main(int argc,char *argv[])
{
Pinput(); //資料輸入
int option;
while(true)
{
cout<<endl;
cout<<"請選擇算法：1-FIFO，2-OPL，3-LRU，0-EXIT"<<endl;
cout<<"請輸入你選擇的算法的序号:"<<endl;
cin>>option;
switch(option)
{
case 1:
FIFO();
break;
case 2:
Optimal();
break;
case 3:
LRU();
break;
default:
break;
}
if(option != 1 && option != 2 && option != 3)
break;
}
return 0;
} 【運作結果】
>缺頁次數:8
>缺頁率:40%
>缺頁次數:12
>缺頁率:60%
>缺頁次數:14
>缺頁率:70%