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

1、学号P71514032 专业计算机科学与技术 姓名 实验日期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();

3、/ 初始化函数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;/ 输出置换图in

4、t 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("%

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

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、在页表内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;

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;/ 先进先出算法/ 此算法中自适应标志不需要使用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+;/ 最近最久未使用算法/ 此算法中自适应标志为起未被使用的次数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("请输入您想要执行的操作：");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;结果截图最佳置换算法先进先出算法:最近最久未使用算法：【小结或讨论】三种算法的主要区别是确定替换物理块的方式不同：1、对于先进先出置换算法，设置一个指针，循环从block的首元素指到block的尾元素，就是物理块置换顺序2、对于LRU置换算法，遍历页表中的页号，根据这些页号最近被引用的顺序，找到最久未被引用的页号，即在输入序列中向前查找离当前页最远的页号，将其所在的物理块置换掉。3、对于LRU置换算法，遍历输入序列中的页号，根据这些页号将来被引用的顺序