操作系統(tǒng)實驗_ 虛擬存儲管理_最佳置換先進先出最近最久未使用

1、學號P71514032 專業(yè)計算機科學與技術(shù) 姓名 實驗日期2017/11/30 教師簽字 成績實驗報告【實驗名稱】 虛擬存儲管理 【實驗?zāi)康摹磕M請求分頁虛擬存儲管理技術(shù)中的硬件地址變換、缺頁中斷以及頁式淘汰算法，處理缺頁中斷。清楚認識請求分頁管理。采用最佳置換算法實現(xiàn)分頁管理的缺頁調(diào)度。采用先進先出算法實現(xiàn)分頁管理的缺頁調(diào)度。采用LRU算法實現(xiàn)分頁管理的缺頁調(diào)度?！緦嶒炘怼緾語言程序設(shè)計數(shù)據(jù)結(jié)構(gòu)最佳置換算法：其所選擇的淘汰頁面將是以后永不使用的，或許是在最長（未來）時間內(nèi)不再被訪問的頁面。采用最佳置換算法通?？杀ＷC獲得最低的缺頁率。先入先出置換算法：該算法總是淘汰最先進入內(nèi)存的頁面。最近

2、最久未被訪問算法：選取過去中最久未被訪問的頁面進行替換?！緦嶒瀮?nèi)容】數(shù)據(jù)結(jié)構(gòu)和符號說明a) 數(shù)據(jù)結(jié)構(gòu) struct PAGE_LIST int id;/ 塊號 int flag;/ 自適應(yīng)標志 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();

3、/ 初始化函數(shù)void print();/ 輸出函數(shù)void Optimal();/ 最佳置換算法void FIFO()/ 先進先出算法void LRU();/ 最近最久未使用算法流程圖最佳置換算法：先進先出置換算法：最近最久未被訪問算法：代碼：#include <stdio.h>#define MAX 100struct PAGE_LISTint id;/ 塊號int flag;/ 自適應(yīng)標志 page_listMAX;int N = 0;/ 頁面表大小int orderMAX;/ 調(diào)用串 / 調(diào)用長度int M = 0;/ 定義輸出內(nèi)容int GMAXMAX;/ 輸出置換圖in

4、t 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; i<100; i+)page_listi.id = -1;page_listi.flag = 999;printf("請輸入頁表的大?。?quot;);scanf("%d", &N);printf("請輸入調(diào)用長度：");scanf("%

5、d", &M);printf("請輸入調(diào)用串：n");for (i = 0; i<M; i+)scanf("%d", &orderi);/ 輸出函數(shù)void display()int i, j;float x;printf("置換圖為：n");for (i = 0; i<N; i+)printf("n");for (j = 0; j<J; j+)printf("= ");printf("n");for (j = 0; j<J;

6、 j+)printf("%3d ", Gij);printf("n");printf("n缺頁序列為：n");for (i = 0; i<LI; i+)printf("%3d ", LLi);printf("n置換序列為：n");for (i = 0; i<RI; i+)printf("%3d ", RLi);x = (float)J / (float)M;x *= 100;printf("n缺頁率為：n%3.2f%n", x);/ 判斷頁是否

7、在頁表內(nèi)int IsExist(int x)int i;for (i = 0; i<N; i+)if (page_listi.id = x)return 1;return 0;/ 最佳置換算法/ 此算法中自適應(yīng)標志代表后面序列中是否訪問到了此位置void Optimal()int i, j, k;int cou;init();for (i = 0; i<N; i+)page_listi.id = orderi;for (j = 0; j<N; j+)GIJ = page_listj.id;I+;I = 0;J+;LLLI = orderi;LI+;for (; i<M;

8、 i+)if (!IsExist(orderi)cou = 0;for (j = i + 1; j<M; j+)if (cou = N - 1)break;for (k = 0; k<N; k+)if (page_listk.id = orderj && page_listk.flag != 0)page_listk.flag = 0;cou+;for (j = 0; j<N; j+)if (page_listj.flag != 0)page_listj.id = orderi;break;for (j = 0; j<N; j+)GIJ = page_l

9、istj.id;I+;I = 0;J+;LLLI = orderi;LI+;RLRI = orderi;RI+;for (j = 0; j<N; j+)page_listj.flag = 999;/ 先進先出算法/ 此算法中自適應(yīng)標志不需要使用void FIFO()int i, j;int pos = 0;init();for (i = 0; i<M; i+)if (!IsExist(orderi)page_listpos.id = orderi;pos = (pos + 1) % N;for (j = 0; j<N; j+)GIJ = page_listj.id;I+;I

10、= 0;J+;LLLI = orderi;LI+;if (i >= N)RLRI = orderi;RI+;/ 最近最久未使用算法/ 此算法中自適應(yīng)標志為起未被使用的次數(shù)void LRU()int i, j;int pos, max;init();for (i = 0; i<M; i+)if (!IsExist(orderi)pos = 0;max = 0;for (j = 0; j<N; j+)if (page_listj.flag > max)pos = j;max = page_listj.flag;page_listpos.id = orderi;page_li

11、stpos.flag = 0;for (j = 0; j<N; j+)GIJ = page_listj.id;I+;I = 0;J+;LLLI = orderi;LI+;if (i >= N)RLRI = orderi;RI+;elsefor (j = 0; j<N; j+)if (page_listj.id = orderi)page_listj.flag = 0;break;for (j = 0; j<N; j+)if (page_listj.id = orderi)continue;elsepage_listj.flag+;int main()int select

12、;doprintf(" 頁面置換算法n");printf(" 1.最佳置換算法（Optimal）n 2.先進先出算法（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();disp

13、lay();break;case 4:return 0;default:printf("輸入有誤，請重新輸入！n"); while (1);return 0;結(jié)果截圖最佳置換算法先進先出算法:最近最久未使用算法：【小結(jié)或討論】三種算法的主要區(qū)別是確定替換物理塊的方式不同：1、對于先進先出置換算法，設(shè)置一個指針，循環(huán)從block的首元素指到block的尾元素，就是物理塊置換順序2、對于LRU置換算法，遍歷頁表中的頁號，根據(jù)這些頁號最近被引用的順序，找到最久未被引用的頁號，即在輸入序列中向前查找離當前頁最遠的頁號，將其所在的物理塊置換掉。3、對于LRU置換算法，遍歷輸入序列中的頁號，根據(jù)這些頁號將來被引用的順序