面置換演算法

頁面置換管理

【實驗目的】

通過本次實驗加深對儲存管理的理解，掌握最佳置換演算法、先進先出置換演算法、lru置換演算法；通過缺頁率比較各種置換演算法的優劣。

【實驗內容】

設計乙個虛擬儲存區和記憶體工作區，程式設計序演示下述演算法的具體實現過程，並計算訪問命中率。要求設計主介面以靈活選擇某演算法，且以下演算法都要實現

1) 最佳置換演算法(opt)：將以後永不使用的或許是在最長(未來)時間內不再被訪問的頁面換出。

2) 先進先出演算法(fifo)：淘汰最先進入記憶體的頁面，即選擇在記憶體中駐留時間最久的頁面予以淘汰。

3) 最近最久未使用演算法(lru)：淘汰最近最久未被使用的頁面。

【實驗要求】

1) 定義為程序分配的物理塊數；

2）定義程序執行所需訪問的頁串；

3）模擬三種頁面置換演算法；

4）計算頁面置換演算法的命中率；

5）比較三種演算法的優劣。

先進先出演算法（fifo）

最簡單的頁面置換演算法是先入先出（fifo）法。這種演算法的實質是，總是選擇在主存中停留時間最長（即最老）的一頁置換，即先進入記憶體的頁，先退出記憶體。

理由是：最早調入記憶體的頁，其不再被使用的可能性比剛調入記憶體的可能性大。建立乙個fifo佇列，收容所有在記憶體中的頁。

被置換頁面總是在佇列頭上進行。當乙個頁面被放入記憶體時，就把它插在隊尾上。這種演算法只是在按線性順序訪問位址空間時才是理想的，否則效率不高。

因為那些常被訪問的頁，往往在主存中也停留得最久，結果它們因變「老」而不得不被置換出去。fifo的另乙個缺點是，它有一種異常現象，即在增加儲存塊的情況下，反而使缺頁中斷率增加了。當然，導致這種異常現象的頁面走向實際上是很少見的。

該演算法將所有使用的記憶體頁面構成乙個迴圈列隊，每次置換時將佇列中的隊

首喚出，隊首指標後移一位即可，演算法容易實現牡丹石最先進入記憶體的野末必將來就不用再到，甚至可能很快就會用到，所以不能保證有效的缺頁率，演算法效能較差。

最近最久未使用演算法（lru）

fifo演算法和opt演算法之間的主要差別是，fifo演算法利用頁面進入記憶體後的時間長短作為置換依據，而opt演算法的依據是將來使用頁面的時間。如果以最近的過去作為不將來的近似，那麼就可以把過去最長一段時間裡不曾被使用的頁面置換掉。它的實質是，當需要置換一頁時，選擇在最近一段時間裡最久沒有使用過的頁面予以置換。

這種演算法就稱為最久未使用演算法（leastrecentlyused，lru）。

因實現lru演算法必須有大量硬體支援，還需要一定的軟體開銷。所以實際實現的都是一種簡單有效的lru近似演算法。

一種lru近似演算法是最近未使用演算法（notrecentlyused，nur）。它在儲存分塊表的每一表項中增加乙個引用位，作業系統定期地將它們置為0。當某一頁被訪問時，由硬體將該位置1。

過一段時間後，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在最近一段時間裡它未被訪問過。

最佳置換演算法（opt）

最佳置換（optimalreplacement）是在理論上提出的一種演算法。其實質是：當調入新的一頁而必須預先置換某個老頁時，所選擇的老頁是將來不再被使用，或者是在最遠的將來才被訪問。

採用這種頁面置換演算法，保證有最少的缺頁率。但是最優頁面置換演算法的實現是困難的，因為它需要人們預先就知道乙個程序整個執行過程中頁面走向的全部情況。不過，這個演算法可用來衡量（如通過模擬實驗分析或理論分析）其他演算法的優劣。

該演算法能保證有最低的缺頁率，所以稱為最佳置換演算法，但是該演算法緊緊是一種理想狀況下的演算法，因為在程序實際執行過程中，

將來會執行到那兒頁是不可預知的，所以無法選擇該置換那個頁出去。因此，本演算法在實際中無法使用，只能作為一種標準來衡量其他演算法的效能

【程式**】

1、先進先出演算法（fifo）

#include <>

#define msize 3

#define psize 8

static int memery[msize] = ;

static int process[psize] = ;

//static int process[psize] = ;

void build(); //生成乙個隨機數序列

void fifo(); //最近最久未使用(lru)置換演算法

int main(int argc, char *ar**)

void build()

printf("\n");

} void fifo()

; int i = 0, j = 0;

int m = -1, n = -1;

int max = -1,maxtime = 0;

int count = 0;

for(i = 0; i

} //找與程序相同的標號

for(j = 0; j < msize; j++) }

//找time值最大的

for(j = 0; j < msize;j++) }

if(n == -1) //不存在相同程序

m = -1;

} else //不存在空閒物理塊

max = -1;

maxtime = 0;

count++;

} }else //存在相同的程序

n = -1;

} for(j = 0 ;j < msize; j++)

printf("\n");

} printf("頁面換算次數為：%d\n",count);

} 2、最近最久未使用演算法（lru）

#include <>

#define msize 3

#define psize 8

static int memery[msize] = ;

static int process[psize] = ;

//static int process[psize] = ;

void build(); //生成乙個隨機數序列

void lru(); //最近最久未使用(lru)置換演算法

int main(int argc, char *ar**)

void build()

printf("\n");

} void lru()

; int i = 0, j = 0;

int m = -1, n = -1;

int max = -1,maxflag = 0;

int count = 0;

for(i = 0; i

} //找與程序相同的標號

for(j = 0; j < msize; j++) }

//找flag值最大的

for(j = 0; j < msize;j++) }

if(n == -1) //不存在相同程序

{if(m != -1) //存在空閒物理塊

{memery[m] = process[i];

面置換演算法

頁面置換演算法

頁面置換演算法模擬設計

頁面置換演算法問題實驗報告

面置換演算法

頁面置換演算法

頁面置換演算法模擬設計

頁面置換演算法問題實驗報告

相關推薦