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

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