虛擬儲存器管理

淮海工學院計算機工程學院

實驗報告書

課程名：《作業系統原理》

題目：虛擬儲存器管理

班級學號

姓名一、實驗目的

請求頁式虛存管理是常用的虛擬儲存管理方案之一。通過請求頁式虛存管理中對頁面置換演算法的模擬，有助於理解虛擬儲存技術的特點，並加深對請求頁式虛存管理的頁面排程演算法的理解。

實驗環境

turbo c 2.0/3.0或vc++6.0

實驗學時

4學時，必做實驗。

二、實驗內容

本實驗要求使用c語言程式設計模擬乙個擁有若干個虛頁的程序在給定的若干個實頁中執行、並在缺頁中斷發生時分別使用fifo和lru演算法進行頁面置換的情形。其中虛頁的個數可以事先給定（例如10個），對這些虛頁訪問的頁位址流（其長度可以事先給定，例如20次虛頁訪問）可以由程式隨機產生，也可以事先儲存在檔案中。要求程式執行時螢幕能顯示出置換過程中的狀態資訊並輸出訪問結束時的頁面命中率。

程式應允許通過為該程序分配不同的實頁數，來比較兩種置換演算法的穩定性。

3、實驗說明

1．設計中虛頁和實頁的表示

本設計利用c語言的結構體來描述虛頁和實頁的結構。

虛頁結構實頁結構

在虛頁結構中，pn代表虛頁號，因為共10個虛頁，所以pn的取值範圍是0—9。pfn代表實頁號，當一虛頁未裝入實頁時，此項值為-1；當該虛頁已裝入某一實頁時，此項值為所裝入的實頁的實頁號pfn。time項在fifo演算法中不使用，在lru中用來存放對該虛頁的最近訪問時間。

在實頁結構中中，pn代表虛頁號，表示pn所代表的虛頁目前正放在此實頁中。pfn代表實頁號，取值範圍（0—n-1）由動態指派的實頁數n所決定。next是乙個指向實頁結構體的指標，用於多個實頁以鍊錶形式組織起來，關於實頁鍊錶的組織詳見下面第4點。

2．關於缺頁次數的統計

為計算命中率，需要統計在20次的虛頁訪問中命中的次數。為此，程式應設定乙個計數器count，來統計虛頁命中發生的次數。每當所訪問的虛頁的pfn項值不為-1，表示此虛頁已被裝入某實頁內，此虛頁被命中，count加1。

最終命中率=count/20*100%。

3．lru演算法中「最近最久未用」頁面的確定

為了能找到「最近最久未用」的虛頁面，程式中可引入乙個時間計數器countime，每當要訪問乙個虛頁面時，countime的值加1，然後將所要訪問的虛頁的time項值設定為增值後的當前countime值，表示該虛頁的最後一次被訪問時間。當lru演算法需要置換時，從所有已分配實頁的虛頁中找出time值為最小的虛頁就是「最近最久未用」的虛頁面，應該將它置換出去。

4．演算法中實頁的組織

因為能分配的實頁數n是在程式執行時由使用者動態指派的，所以應使用鍊錶組織動態產生的多個實頁。為了排程演算法實現的方便，可以考慮引入free和busy兩個鍊錶：free鍊錶用於組織未分配出去的實頁，首指標為free_head，初始時n個實頁都處於free鍊錶中；busy鍊錶用於組織已分配出去的實頁，首指標為busy_head，尾指標為busy_tail，初始值都為null。

當所要訪問的乙個虛頁不在實頁中時，將產生缺頁中斷。此時若free鍊錶不為空，就取下鍊錶首指標所指的實頁，並分配給該虛頁。若free鍊錶為空，則說明n個實頁已全部分配出去，此時應進行頁面置換：

對於fifo演算法要將busy_head 所指的實頁從busy鍊錶中取下，分配給該虛頁，然後再將該實頁插入到busy鍊錶尾部；對於lru演算法則要從所有已分配實頁的虛頁中找出time值為最小的虛頁，將該虛頁從裝載它的那個實頁中置換出去，並在該實頁中裝入當前正要訪問的虛頁。

4、實驗步驟

1、理解本實驗中關於兩種排程演算法的說明。

2、根據排程演算法的說明，畫出相應的程式流程圖。

3、按照程式流程圖，用c語言程式設計並實現。

五、分析與思考

比較不同實頁數下的頁面命中率，兩種置換演算法的穩定性方面可以得出何種結論？

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

但該演算法與程序實際執行的規律不相適應，因為在程序中，有些頁面經常被訪問，比如，含有全域性變數、常用函式、例程等的頁面，fifo演算法並不能保證這些頁面不被淘汰。fifo置換演算法效能之所以較差，是因為它所依據的條件是各個頁面調入記憶體的時間，而頁面調入的先後並不能反映頁面的使用情況。

最近最久未使用（lru）置換演算法，是根據頁面調入記憶體後的使用情況進行決策的。由於無法**各頁面將來的使用情況，只能利用「最近的過去」作為「最近的將來」的近似，因此，lru置換演算法是選擇最近最久未使用的頁面予以淘汰。該演算法賦予每個頁面乙個訪問字段，用來記錄乙個頁面自上次被訪問以來所經歷的時間t,，當須淘汰乙個頁面時，選擇現有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。

最佳（opt）頁面置換演算法是所有演算法中產生頁錯誤率最低的，而且絕對沒有belady異常的問題。它會置換最長時間不會使用的頁。最佳頁面（opt）置換演算法，是根據最長時間不會使用的頁來決策的。

這就意味著，需要注意記憶體中的頁面和頁面的距離了。因此opt演算法是選擇最久未使用的頁面進行淘汰的。該演算法賦予記憶體中每個頁面乙個訪問字段，用來記錄距離此處的最近頁面的距離，這樣通過比較，就能把最久未使用的頁面淘汰掉。

六、測試資料與實驗結果

流程圖如下圖所示：

實驗結果：

fifo 演算法

opt演算法

lru演算法

七、實驗心得與體會

這次實驗，通過請求頁式虛存管理中對頁面置換演算法的模擬，加深了對於虛擬儲存技術的特點的理解，並且加深了對請求頁式虛存管理的頁面排程演算法的理解。

最佳（optimal）置換演算法，選擇「以後用不再使用的」或「在最長未來時間內不再被訪問」的頁面被置換，使用opt演算法通常可以保證獲得最低的缺頁率；先進先出（fifo）頁面置換演算法，選擇進入記憶體最早的頁面被置換，實現簡單，功能較差；最近最近未使用（lru）置換演算法，無法**各頁面將來的使用情況，只能利用「最近的過去」作為「最近的將來」的相似，即選擇最近最久未使用的頁面予以淘汰。

通過這次實驗，更加加深熟悉了opt，fifo，lru三種頁面分配和置換演算法的過程。

附錄:yemianzhihuan.cpp

#include "iostream.h"

const int datamax=100;

const int blocknum = 10;

int datashow[blocknum][datamax]; // 用於儲存要顯示的陣列

bool datashowenable[blocknum][datamax]; // 用於儲存陣列中的資料是否需要顯示

//int data[datamax]=; // 測試資料

//int n = 20; // 輸入頁面個數

int data[datamax]; // 儲存資料

int block[blocknum]; // 物理塊

int count[blocknum]; // 計數器

int n ; // 頁面個數

int m;//最小物理塊數

int changetimes;

void datainput(); // 輸入資料的函式

void dataoutput();

void fifo(); // fifo 函式

void optimal(); // optimal函式

void lru(); // lru函式

///*

int main(int argc, char* argv)

{ datainput();// datainput();

// fifo();

// optimal();

// lru();

// return 0;

int menu;

while(true)

{cout< cout《選單選擇< cout<<< cout<<1-fifo< cout<<2-optimal< cout<<3-lru< cout<<0-exit< cout<<< cin>>menu;

switch(menu)

{case 1: fifo();break;

虛擬儲存器管理

第15講儲存器管理之虛擬儲存器

作業系統實驗五虛擬儲存器管理

VMware虛擬機器儲存管理

虛擬儲存器管理

第15講儲存器管理之虛擬儲存器

作業系統實驗五虛擬儲存器管理

VMware虛擬機器儲存管理

相關推薦