操作系统页面置换算法实验报告

1、学 生 实 验 报 告姓名： 年级专业班级 学号 成绩 课程名称操作系统实验名称实验3 请求分页系统的页面置换算法 实验类型验证 设计综合 创新【实验目的、要求】1.通过编程实现请求分页存储管理系统的Optimal、FIFO、LRU调度算法，使学生掌握计算机虚拟存储管理中有关缺页处理方法等内容，巩固有关虚拟存储管理的知识。2.了解Windows2000/XP中内存管理机制，掌握页式虚拟存储技术。3.理解内存分配原理，特别是以页面为单位的虚拟内存分配方法。【实验内容】在Windows XP或Windows 2000等操作系统环境下，使用VC、VB、Delphi、java或C等编程语言，实现请求分

2、页存储管理系统的Optimal、FIFO、LRU调度算法。【实验环境】（含主要设计设备、器材、软件等）计算机 C语言编程软件【实验步骤、过程】（含原理图、流程图、关键代码，或实验过程中的记录、数据等）1.启动计算机，运行C语言编程软件。2.分析理解页面的几种基本算法的特点和原理，在纸上画出原理图。3.编辑源程序，关键代码如下。(1)先进先出页面置换算法。#include<stdio.h>void main()int i,n,t,k=3,a100;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&

3、amp;ai);for(i=3;i<n;i+)if(ai!=a0&&ai!=a1&&ai!=a2) /该页面在内存中，不需要置换。 t=ai; ai=ak%3; /通过对k值对3取余的值来确定需要置换的当前页面。 ak%3=t;k+; /仅当发生了页面置换时，k的值才发生改变。 printf("%d %d %dn",a0,a1,a2); else printf("%d %d %dn",a0,a1,a2);(2)最佳置换算法#include<stdio.h>void main()int i,j,n,a100

4、;int c1,c2,c3; / 标志该页面再次被访问时在引用串中的位置 int p,k,r;printf("请输入页面数:n");scanf("%d",&n);printf("请输入页面号引用串:n");for(i=0;i<n;i+)scanf("%d",&ai);for(j=3;j<n;j+)if(aj!=a0)&&(aj!=a1)&&(aj!=a2) /页面在内存不发生置换！for(p=j;p<n;p+)if(a0=ap)c1=p;break;

5、 /跳出循环，直接置c1=n!else c1=n; /标志该页面再次被访问时在引用串中的位置！若该页面不会再次被访问，则将c1置为最大n! for(k=j;k<n;k+)if(a1=ak) c2=k;break; elsec2=n;for(r=j;r<n;r+) if(a2=ar)c3=r; break;else c3=n; /通过比较c1,c2,c3的大小确定最长时间内不再访问的页面！if(c1>c2)&&(c1>c3)|(c1=c3)|(c1=c2) /当前a0页面未来最长时间不再访问! t=aj; aj=a0;a0=t; /把当前访问页面和最佳页面

6、交换！printf("%d %d %dn",a0,a1,a2);if(c2>c1)&&(c2>c3)|(c2=c3) /当前a1页面未来最长时间不再访问! t=aj;aj=a1;a1=t;printf("%d %d %dn",a0,a1,a2); if(c3>c1)&&(c3>c2) /当前a2页面未来最长时间不再访问!t=aj; aj=a2; a2=t; printf("%d %d %dn",a0,a1,a2); /输出置换后页框中的物理块组成！ else printf(&qu

7、ot;%d %d %dn",a0,a1,a2);(3)LRU算法。#include<stdio.h>void main() int i,j,n,a100; int c1,c2,c3; /标志最近最久不使用的页面在页面引用串中的先后位置！ int p,k,r;scanf("%d",&n); /输入页面数for(i=0;i<n;i+) scanf("%d",&ai); /输入页面引用串for(j=3;j<n;j+)if(aj!=a0)&&(aj!=a1)&&(aj!=a2) /

8、当前访问页面不在内存中！for(p=j-1;p>=0;p-)if(a0=ap)c1=p; /用c1记录和内存中a0的相同向前最近的页面在引用串中的位置!break;else c1=-1; /，若未找到相同的页面，则把c1赋值为：-1！ for(k=j-1;k>=0;k-)if(a1=ak) c2=k;break; elsec2=-1;for(r=j-1;r>=0;r-) if(a2=ar) /用c1记录和内存中a1的相同向前最近的页面在引用串中的位置! c3=r; break;else c3=-1; /若未找到相同的页面，则把c1赋值为：-1！if(c1<c2)&

9、;&(c1<c3)|(c1=c3)|(c1=c2) a0=aj; /当前内存中a0最近最久不使用时,把要访问的页面放至a0中！printf("%d %d %dn",a0,a1,a2); /输出置换后的页面!if(c2<c1)&&(c2<c3)|(c2=c3)a1=aj; /当前内存中a0最近最久不使用时,把要访问的页面放至a1中！printf("%d %d %dn",a0,a1,a2); if(c3<c1)&&(c3<c2) a2=aj; /当前内存中a0最近最久不使用时,把要访问的页

10、面放至a2中！ printf("%d %d %dn",a0,a1,a2); else printf("%d %d %dn",a0,a1,a2); /当要访问的页面存在于内存时,原样输出原物理块中的3个页面!4.编译链接程序，在编译正确的情况下执行程序。5.记录程序执行结果并分析。6.整理实验器材。 2010年12月16日 【实验结果或总结】（对实验结果进行相应分析，或总结实验的心得体会，并提出实验的改进意见1.程序的执行结果如下：(1)先进先出页面置换算法 (2)最佳页面置换法(3)最近最久未使用置换算法2.以上三个程序通过数组和排序语句实现页面的三种基

11、本调度算法。(1)先进先出算法事先设定标志k=3，页面每发生一次置换k值增加1。通过取k对3的余数来确定被置换的内存中的页面，当被访问页面存在于内存时，不置换，而直接输出原内存中的3个页面。(2)最佳置换算法通过设定c1,c2,c3来记录当前内存中的页面被下一次访问的位置(时间)，通过对c1,c2,c3的大小比较确定内存中需要被置换的页面。三者中值最大的对应的内存页面选择被置换。即实现了未来最长时间未访问的机制，即最佳置换算法。(3)最近最久未使用置换算法的原理跟最佳置换算法类似。初始设定变量c1,c2,c3记录当前内存中的以前的最近一次未被访问的位置(时间)，比较三者的大小来确定需要被置换的页面。三者中至最小的对应的内存页面选择被置换。即实现了最近最久未使用的机制，即最近最久未使用置换算法。3.上述三个程序分别能较好的模拟页面的基本调度算法，实现页面的置换，保证进程的正常执行。但也分别存在一些不足。(1)当内存中三个页面有部分相同时，程序不能很好的实现调度。即c1,c2,c3中有部分变量值相等，源程序可能不能准确的找到调度顺序，如图所示。(LRU算法)