頁面置換演算法模擬設計

課程設計報告

課程名稱作業系統

課題名稱頁面置換演算法模擬設計

專業通訊工程

班級學號

姓名指導教師

2023年 6 月 29 日

湖南工程學院

課程設計任務書

課程名稱作業系統

課題頁面置換演算法模擬設計

專業班級

學生姓名

學號指導老師

審批任務書下達日期 2014 年 6 月 23 日

任務完成日期 2014 年 6 月 29 日

目錄1課題概述 4

1.1設計要求 4

1.2 理論分析 4

2系統分析 4

3程式實現 4

4程式測試 4

5心得體會 4

6附錄 4

7 評分表 4

計算並輸出下述各種演算法在不同記憶體容量下的命中率。

a. fifo先進先出的演算法

b. lrr最近最少使用演算法

c. opt最佳淘汰演算法（先淘汰最不常用的頁位址）

d. lfr最少訪問頁面演算法

e. nur最近最不經常使用演算法

設計技術引數：

（1）命中率=1-頁面失效次數/頁位址流長度

（2）本實驗中，頁位址流長度為320，頁面失效次數為每次訪問相應指令時，該指令所對應的頁不在記憶體的次數。

（3）隨機數產生方法，採用系統提供函式srand()和rand ()來產生

在程序執行過程中，若其所要訪問的頁面不在記憶體所需把他們調入記憶體，但記憶體已無空閒時，為了保證程序能夠正常執行，系統必須從記憶體中調入一頁程式或資料送磁碟的對換區中。但應將那個頁面調出，須根據一定的演算法來確定。通常，把選擇換出頁面的演算法稱為頁面置換演算法。

置換演算法的好壞，將直接影響到系統的效能。

乙個好的頁面置換演算法，應具有較低的頁面更換頻率。從理論上將講，應將那些以後不再訪問的頁面換出，或把那些較長時間內不再訪問的頁面調出。目前存在著不同的演算法，他們都試圖更接近與理論上的目標。

擁有頁面交換機制的作業系統總是把當前程序中急需處理的部分頁面換入到記憶體當中，而把更多暫時不需要處理的頁面放置在外存當中。由於程序需要處理的頁面順序不同，因此必須要在記憶體與外存之間進行頁面交換，頁面置換演算法也就應運而生。

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

這是最早出現的置換演算法。該演算法總是淘汰最先進入記憶體的頁面，即選擇在記憶體停留時間最久的給予淘汰。該演算法實現簡單，只需把乙個程序已調入記憶體的頁面，按先後次序鏈結成乙個佇列，並設定乙個指標，稱為替代指標，使它總是指向最老的頁面。

但該演算法與程序實際執行的規律不相適應，因為在incheng中，有些頁面經常被訪問，比如，含有全域性變數，常用函式，例程等方面，fifo

演算法並不能保證這些頁面不被淘汰。當需要選擇乙個頁面淘汰時，總是選擇最先進入記憶體空間的那乙個頁面。只要在系統中建立乙個fifo佇列，以反映頁面的活動情況。

被選擇的頁面總是處於隊首的頁面，而最近調入的頁面永遠存放在佇列的尾部。

2.最近最少使用（lrr）演算法

fifo置換演算法的效能之所以較差，是因為它所依據的條件是各個頁面調入記憶體的時間，而頁面調入的先後不能反映頁面的使用情況。最近最少使用（lrr）的頁面置換演算法，是根據頁面調入記憶體後的使用情況進行決策的。由於無法**各個頁面將來的使用情況，只能利用「最近的過去」，作為「最近的將來」的近似。

該演算法的基本思想是用最近的過去估計最近的將來。假定在記憶體中的某個頁面，在最近一段時間內未被使用的時間最長，那麼在最近的將來也可能不再被使用。

3.理想頁面置換（opt）演算法（本次程式中作兩個置換演算法對比作用）

最佳置換演算法由belady於2023年提出，這是一種理想情況下的頁面置換演算法，但實際上不可能實現。但人們目前把還無法預知乙個程序在內的若干頁面中，哪乙個頁面是未來最長時間內不再被訪問，因而該演算法無法實現。基本思想是記憶體中每個頁都用該頁面首次被訪問前所要執行的指令數進行標記，標記最大的頁應該被置換

最佳淘汰演算法（先淘汰最不常用的頁位址）

optimal replacement（opt）它是一種理想化的演算法，效能最好，但在實際上難於實現。即選擇那些永不使用的，或者是在最長時間內不再被訪問的頁面置換出去。但是要確定哪乙個頁面是未來最長時間內不再被訪問的，目前來說是很難估計的，所以該演算法通常用來評價其它演算法

最近最不經常使用演算法

為每頁設定一位訪問位，當每頁被訪問時，其訪問位置1.置換演算法在替換頁面時，只需要檢查它的訪問位，如果是0，就將該頁換出，如果是1，則重新將它置為0，從而給該頁第二次駐留記憶體的機會，再依次檢查下乙個頁面。如果最後乙個頁面依然沒有被換出，則到第乙個頁面去重新檢查。

1．進入系統模組。進入登陸介面，輸入記憶體頁面數和實際頁數

2．頁面號列印模組。列印輸入的頁面號。

3．選單選擇模組。選擇相應的頁面的置換方式，選擇相應的字母，進入相應的功能。

4．演算法模組。選擇相應的頁面置換演算法。

5．顯現輸出模組。顯示頁面被置換的情況。

5.缺頁次數和缺頁率模組。計算頁面號輸入的計算結果。

6.退出系統模組。退出置換頁面。

如圖2.1 模組劃分:

圖2.1 模組劃分

之後進入系統模組如圖2.2:

圖2.2 系統流程圖

1. 首先貫穿全域性的全域性需要一系列的函式來實現本作業系統的各種功能。需要函式自帶的檔案和 .

2.以下通過fifo、opt、lrr三個進行舉例：

fifo頁面置換和缺頁次數及缺頁率模組實現如下：

void fifo()

; int time[10]=;

int i,j,k,m;

int max=0;

int count=0;

for(i=0;i

for(i=msize;i

if(k==msize)

else

compute();

print(count);

}lrr頁面置換和缺頁次數及缺頁率模組實現如下：

void lrr()

; int flag[10]=;

int i,j,k,m;

int max=0;

int count=0;

for(i=0;i

for(i=msize;i

if(k==msize)

{count++;

max=flag[0]for(m=2;mif(flag[m]max=m;

memery[max]=page[i];

頁面置換演算法模擬設計

頁面置換演算法

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

請求頁式儲存管理的頁面置換演算法

頁面置換演算法模擬設計

頁面置換演算法

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

請求頁式儲存管理的頁面置換演算法

相關推薦