操作系统实验-虚拟存储管理-最佳置换先进先出最近最久未使用

1、学号P 专业计算机科学与技术 姓名 实验日期2017/11/30 教师签字 成绩实验报告【实验名称】 虚拟存储管理 【实验目的】模拟请求分页虚拟存储管理技术中的硬件地址变换、缺页中断以及页式淘汰算法，处理缺页中断。清楚认识请求分页管理。采用最佳置换算法实现分页管理的缺页调度。采用先进先出算法实现分页管理的缺页调度。采用LRU算法实现分页管理的缺页调度。【实验原理】C语言程序设计数据结构最佳置换算法：其所选择的淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。先入先出置换算法：该算法总是淘汰最先进入内存的页面。最近最久未被访问算法

2、：选取过去中最久未被访问的页面进行替换。【实验内容】数据结构和符号说明a) 数据结构 struct PAGE_LIST int id;/ 块号 int flag;/ 自适应标志 page_listMAX; int N = 0;/ 页面表大小 int orderMAX;/ 调用串 / 调用长度 int M = 0;/ 定义输出内容 int GMAXMAX;/ 输出置换图 int I, J;/ 置换图扫描指针 int LLMAX;/ 缺页序列 int LI;/ 缺页序列扫描指针 int RLMAX;/ 置换序列 / 置换序列扫描指针 int RI;函数说明：void init();/ 初始化函数v

3、oid print();/ 输出函数void Optimal();/ 最佳置换算法void FIFO()/ 先进先出算法void LRU();/ 最近最久未使用算法流程图最佳置换算法：先进先出置换算法：最近最久未被访问算法：代码：#include #define MAX 100struct PAGE_LISTint id;/ 块号int flag;/ 自适应标志 page_listMAX;int N = 0;/ 页面表大小int orderMAX;/ 调用串 / 调用长度int M = 0;/ 定义输出内容int GMAXMAX;/ 输出置换图int I, J;/ 置换图扫描指针int LLM

4、AX;/ 缺页序列int LI;/ 缺页序列扫描指针int RLMAX;/ 置换序列/ 置换序列扫描指针int RI;/ 初始化函数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(请输入调用长度：);scanf(%d, &M);printf(请输入调用串：n);for (i = 0; iM; i+)scanf(%d, &orderi);/ 输出函数void

5、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;

6、printf(n缺页率为：n%3.2f%n, x);/ 判断页是否在页表内int IsExist(int x)int i;for (i = 0; iN; i+)if (page_listi.id = x)return 1;return 0;/ 最佳置换算法/ 此算法中自适应标志代表后面序列中是否访问到了此位置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 = orde

7、ri;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;

8、I+;I = 0;J+;LLLI = orderi;LI+;RLRI = orderi;RI+;for (j = 0; jN; j+)page_listj.flag = 999;/ 先进先出算法/ 此算法中自适应标志不需要使用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+;/ 最近最久未使用算法/ 此算法中自适应标志为起未被使用的

9、次数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;brea

10、k;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.先进先出算法（FIFO） n);printf( 3.最近最久未使用算法（LRU）n 4.退出程序 n);printf(请输入您想要执行的操作：);scanf(%d, &select);switch (select)case 1:Optimal();display();break;case 2:FIFO()

11、;display();break;case 3:LRU();display();break;case 4:return 0;default:printf(输入有误，请重新输入！n); while (1);return 0;结果截图最佳置换算法先进先出算法:最近最久未使用算法：【小结或讨论】三种算法的主要区别是确定替换物理块的方式不同：1、对于先进先出置换算法，设置一个指针，循环从block的首元素指到block的尾元素，就是物理块置换顺序2、对于LRU置换算法，遍历页表中的页号，根据这些页号最近被引用的顺序，找到最久未被引用的页号，即在输入序列中向前查找离当前页最远的页号，将其所在的物理块置换掉。3、对于LRU置换算法，遍历输入序列中的页号，根据这些页号将来被引用的顺序，找到将来最长时间未被引用的页号，即在输入序列中向后查找离