操作系统实验--虚拟存储管理-最佳置换先进先出最近最久未使用(共15页).docx

精选优质文档-倾情为你奉上学号P 专业计算机科学与技术 姓名 实验日期2017/11/30 教师签字 成绩实验报告【实验名称】 虚拟存储管理 【实验目的】模拟请求分页虚拟存储管理技术中的硬件地址变换、缺页中断以及页式淘汰算法，处理缺页中断。清楚认识请求分页管理。采用最佳置换算法实现分页管理的缺页调度。采用先进先出算法实现分页管理的缺页调度。采用LRU算法实现分页管理的缺页调度。【实验原理】C语言程序设计数据结构最佳置换算法：其所选择的淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。先入先出置换算法：该算法总是淘汰最先进入内存的页面。最近最久未被访问算法：选取过去中最久未被访问的页面进行替换。【实验内容】数据结构和符号说明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();/ 初始化函数void print();/ 输出函数void Optimal();/ 最佳置换算法void FIFO()/ 先进先出算法void LRU();/ 最近最久未使用算法流程图最佳置换算法：先进先出置换算法：最近最久未被访问算法：代码：#include <stdio.h>#define MAX 100struct PAGE_LISTint 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()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("请输入页表的大小：");scanf("%d", &N);printf("请输入调用长度：");scanf("%d", &M);printf("请输入调用串：n");for (i = 0; i<M; i+)scanf("%d", &orderi);/ 输出函数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; 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);/ 判断页是否在页表内int IsExist(int x)int i;for (i = 0; i<N; i+)if (page_listi.id = x)return 1;return 0;/ 最佳置换算法/ 此算法中自适应标志代表后面序列中是否访问到了此位置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; 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_listj.id;I+;I = 0;J+;LLLI = orderi;LI+;RLRI = orderi;RI+;for (j = 0; j<N; j+)page_listj.flag = 999;/ 先进先出算法/ 此算法中自适应标志不需要使用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 = 0;J+;LLLI = orderi;LI+;if (i >= N)RLRI = orderi;RI+;/ 最近最久未使用算法/ 此算法中自适应标志为起未被使用的次数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_listpos.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;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();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置换算法，遍历输入序列中的页号，根据这些页号将来被引用的顺序，找到将来最长时间未被引用的页号，即在输入序列中向后查找离当前页最远的页号，将其所在的物理块置换掉。4、通过本次实验，我对于虚拟存储中的分页管理有了更加深入的了解。理解了最佳页面置换算法、先入先出页面置换算法以及最近最久未被使用页面置换算法的中心思想。同时发现，最佳页面置换算法得到的缺页率最低，但其要求也更加严格，必须要求知道未来调用的所有序列。先进先出算法最为简单，但是缺页率最高。最近最久未被访问算法居中。专心-专注-专业