操作系統(tǒng)實(shí)驗(yàn)_ 虛擬存儲管理_最佳置換先進(jìn)先出最近最久未使用.doc

學(xué)號P71514032 專業(yè)計算機(jī)科學(xué)與技術(shù) 姓名 實(shí)驗(yàn)日期2017/11/30 教師簽字 成績實(shí)驗(yàn)報告【實(shí)驗(yàn)名稱】 虛擬存儲管理 【實(shí)驗(yàn)?zāi)康摹磕M請求分頁虛擬存儲管理技術(shù)中的硬件地址變換、缺頁中斷以及頁式淘汰算法，處理缺頁中斷。清楚認(rèn)識請求分頁管理。采用最佳置換算法實(shí)現(xiàn)分頁管理的缺頁調(diào)度。采用先進(jìn)先出算法實(shí)現(xiàn)分頁管理的缺頁調(diào)度。采用LRU算法實(shí)現(xiàn)分頁管理的缺頁調(diào)度。【實(shí)驗(yàn)原理】C語言程序設(shè)計數(shù)據(jù)結(jié)構(gòu)最佳置換算法：其所選擇的淘汰頁面將是以后永不使用的，或許是在最長（未來）時間內(nèi)不再被訪問的頁面。采用最佳置換算法通?？杀ＷC獲得最低的缺頁率。先入先出置換算法：該算法總是淘汰最先進(jìn)入內(nèi)存的頁面。最近最久未被訪問算法：選取過去中最久未被訪問的頁面進(jìn)行替換?！緦?shí)驗(yàn)內(nèi)容】數(shù)據(jù)結(jié)構(gòu)和符號說明a) 數(shù)據(jù)結(jié)構(gòu) struct PAGE_LIST int id;/ 塊號 int flag;/ 自適應(yīng)標(biāo)志 page_listMAX; int N = 0;/ 頁面表大小 int orderMAX;/ 調(diào)用串 / 調(diào)用長度 int M = 0;/ 定義輸出內(nèi)容 int GMAXMAX;/ 輸出置換圖 int I, J;/ 置換圖掃描指針 int LLMAX;/ 缺頁序列 int LI;/ 缺頁序列掃描指針 int RLMAX;/ 置換序列 / 置換序列掃描指針 int RI;函數(shù)說明：void init();/ 初始化函數(shù)void print();/ 輸出函數(shù)void Optimal();/ 最佳置換算法void FIFO()/ 先進(jìn)先出算法void LRU();/ 最近最久未使用算法流程圖最佳置換算法：先進(jìn)先出置換算法：最近最久未被訪問算法：代碼：#include #define MAX 100struct PAGE_LISTint id;/ 塊號int flag;/ 自適應(yīng)標(biāo)志 page_listMAX;int N = 0;/ 頁面表大小int orderMAX;/ 調(diào)用串 / 調(diào)用長度int M = 0;/ 定義輸出內(nèi)容int GMAXMAX;/ 輸出置換圖int I, J;/ 置換圖掃描指針int LLMAX;/ 缺頁序列int LI;/ 缺頁序列掃描指針int RLMAX;/ 置換序列/ 置換序列掃描指針int RI;/ 初始化函數(shù)void init()int i;I = 0;J = 0;LI = 0;RI = 0;for (i = 0; i100; i+)page_listi.id = -1;page_listi.flag = 999;printf(請輸入頁表的大小：);scanf(%d, &N);printf(請輸入調(diào)用長度：);scanf(%d, &M);printf(請輸入調(diào)用串：n);for (i = 0; iM; i+)scanf(%d, &orderi);/ 輸出函數(shù)void display()int i, j;float x;printf(置換圖為：n);for (i = 0; iN; i+)printf(n);for (j = 0; jJ; j+)printf(= );printf(n);for (j = 0; jJ; j+)printf(%3d , Gij);printf(n);printf(n缺頁序列為：n);for (i = 0; iLI; i+)printf(%3d , LLi);printf(n置換序列為：n);for (i = 0; iRI; i+)printf(%3d , RLi);x = (float)J / (float)M;x *= 100;printf(n缺頁率為：n%3.2f%n, x);/ 判斷頁是否在頁表內(nèi)int IsExist(int x)int i;for (i = 0; iN; i+)if (page_listi.id = x)return 1;return 0;/ 最佳置換算法/ 此算法中自適應(yīng)標(biāo)志代表后面序列中是否訪問到了此位置void Optimal()int i, j, k;int cou;init();for (i = 0; iN; i+)page_listi.id = orderi;for (j = 0; jN; j+)GIJ = page_listj.id;I+;I = 0;J+;LLLI = orderi;LI+;for (; iM; i+)if (!IsExist(orderi)cou = 0;for (j = i + 1; jM; j+)if (cou = N - 1)break;for (k = 0; kN; k+)if (page_listk.id = orderj & page_listk.flag != 0)page_listk.flag = 0;cou+;for (j = 0; jN; j+)if (page_listj.flag != 0)page_listj.id = orderi;break;for (j = 0; jN; j+)GIJ = page_listj.id;I+;I = 0;J+;LLLI = orderi;LI+;RLRI = orderi;RI+;for (j = 0; jN; j+)page_listj.flag = 999;/ 先進(jìn)先出算法/ 此算法中自適應(yīng)標(biāo)志不需要使用void FIFO()int i, j;int pos = 0;init();for (i = 0; iM; i+)if (!IsExist(orderi)page_listpos.id = orderi;pos = (pos + 1) % N;for (j = 0; j= N)RLRI = orderi;RI+;/ 最近最久未使用算法/ 此算法中自適應(yīng)標(biāo)志為起未被使用的次數(shù)void LRU()int i, j;int pos, max;init();for (i = 0; iM; i+)if (!IsExist(orderi)pos = 0;max = 0;for (j = 0; j max)pos = j;max = page_listj.flag;page_listpos.id = orderi;page_listpos.flag = 0;for (j = 0; j= N)RLRI = orderi;RI+;elsefor (j = 0; jN; j+)if (page_listj.id = orderi)page_listj.flag = 0;break;for (j = 0; jN; j+)if (page_listj.id = orderi)continue;elsepage_listj.flag+;int main()int select;doprintf( 頁面置換算法n);printf( 1.最佳置換算法（Optimal）n 2.先進(jìn)先出算法（FIFO） n);printf( 3.最近最久未使用算法（LRU）n 4.退出程序 n);printf(請輸入您想要執(zhí)行的操作：);scanf(%d, &select);switch (select)case 1:Optimal();display();break;case 2:FIFO();display();break;case 3:LRU();display();break;case 4:return 0;default:printf(輸入有誤，請重新輸入！n); while (1);return 0;結(jié)果截圖最佳置換算法先進(jìn)先出算法:最近最久未使用算法：【小結(jié)或討論】三種算法的主要區(qū)別是確定替換物理塊的方式不同：1、對于先進(jìn)先出置換算法，設(shè)置一個指針，循環(huán)從block的首元素指到block的尾元素，就是物理塊置換順序2、對于LRU置換算法，遍歷頁表中的頁號，根據(jù)這些頁號最近被引用的順序，找到最久未被引用的頁號，即在輸入序列中向前查找離當(dāng)前頁最遠(yuǎn)的頁號，將其所在的物理塊置換掉。3、對于LRU置換算法，遍歷輸入序列中的頁號，根據(jù)這些頁號將來被引用的順序，找到將來最長時間未被引用的頁號，即在輸入序列中向后查找離