浙江理工大学操作系统实验三页面置换算法

页面置换算法实验报告
一、实验内容
本次实验主要围绕页面置换算法进行，以实验课本的实例介绍，采用FIFO页面置换算法对后面提到的参数进行置换，最终得出页面置换的结果和比较所得结果。

二、实验步骤
(一) 熟悉FIFO算法
首先是要了解FIFO页面置换算法，FIFO全称（First In First Out），按页面进入内存的顺序来替换相应内存页面，先进先出，将先进入内存的页面先替换出去。

(二) 阅读实验课本
在阅读实验课本之前要先熟悉实验书上所介绍的FIFO算法，然后在实验书上找出需要做的实验，并对实验环境和表格进行观察，掌握实验的基本内容。

(三) 开始页面置换
在开始实验之前，熟悉实验环境，根据实验书上的参数，首先模拟进程分配内存，根据FIFO算法去进行计算，根据上表中的参数去比较，最后得出最终结果。

(四) 在本次实验的补充
这次实验中，可以把FIFO的概念应用到实际应用中，也可以模拟不同情况，例如改变页面的大小，观察不同页面置换算法的结果，实验出最合适的结果。

三、实验结论
本次实验是为了了解FIFO页面置换算法，实验出最终的结果，最后得出页面置换的结果及比较结果。

实习三内存页面置换算法的设计一、实验目的实现最近最久未使用（LRU）置换算法为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分（段或页）调入内存便可运行，还支持请求调页的存储管理方式。

当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。

这种页面调入方式叫请求调页。

当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。

该程序通过查找页表，得到该页所在外存的物理块号。

如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。

如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。

利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。

整个页面的调入过程对用户是透明的。

本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的技术特点，掌握请求页式存储管理的页面置换算法。

二、实验环境VC++6.0 MFC三、实验内容为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分（段或页）调入内存便可运行，还支持请求调页的存储管理方式。

当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。

这种页面调入方式叫请求调页。

当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。

该程序通过查找页表，得到该页所在外存的物理块号。

如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。

如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。

实验三实验报告实验源码：#include "stdio.h"#include <iostream.h>#include <stdlib.h>#define DataMax 100 // 常量DataMax#define BlockNum 10 // 常量BlockNumint DataShow[BlockNum][DataMax]; // 用于存储要显示的数组bool DataShowEnable[BlockNum][DataMax]; // 用于存储数组中的数据是否需要显示int Data[DataMax]; // 保存数据int Block[BlockNum]; // 物理块int count[BlockNum]; // 计数器int N; // 页面个数int M; // 最小物理块数int ChangeTimes; // 缺页次数void DataInput(); // 输入数据的函数void DataOutput(); // 输出数据的函数void FIFO(); // FIFO 函数void Optimal(); // Optimal函数void LRU(); // LRU函数int main(int argc, char* argv[]){DataInput();int menu;while(true){printf("\n* 菜单选择*\n");printf("*******************************************************\n");printf("* 1-Optimal *\n");printf("* 2-FIFO *\n");printf("* 3-LRU *\n");printf("* 4-返回上一级*\n");printf("* 0-EXIT *\n");printf("*******************************************************\n");scanf("%d",&menu);switch(menu){case 1:Optimal();break;case 2:FIFO();break;case 3:LRU();break;case 0:exit(0);break;case 4:system("cls");DataInput();break;}if(menu != 1 && menu != 2 && menu != 3 && menu != 0 && menu !=4) { system("cls");printf("\n请输入0 - 4之间的整数！\n");continue;}}return 0;}void DataInput(){int i,choice;printf("请输入最小物理块数：");scanf("%d",&M);// 输入最小物理块数大于数据个数while(M > BlockNum){printf("物理块数超过预定值，请重新输入：");scanf("%d",&M);}printf("请输入页面的个数：");scanf("%d",&N);// 输入页面的个数大于数据个数while(N > DataMax){printf("页面个数超过预定值，请重新输入：");scanf("%d",&N);}printf("请选择产生页面访问序列的方式(1.随机2.输入)：");scanf("%d",&choice);switch(choice){case 1:// 产生随机访问序列for(i = 0;i < N;i++){Data[i] = (int)(((float) rand() / 32767) * 10); // 随机数大小在0 - 9之间}system("cls");// 显示随机产生的访问序列printf("\n随机产生的访问序列为：");for(i = 0;i < N;i++){printf("%d ",Data[i]);}printf("\n");break;case 2:// 输入访问序列printf("请输入页面访问序列：\n");for(i = 0;i < N;i++)scanf("%d",&Data[i]);system("cls");// 显示输入的访问序列printf("\n输入的访问序列为：");for(i = 0;i < N;i++){printf("%d ",Data[i]);}printf("\n");break;default:while(choice != 1 && choice != 2){printf("请输入1或2选择相应方式:");scanf("%d",&choice);}break;}}void DataOutput(){int i,j;// 对所有数据操作for(i = 0;i < N;i++){printf("%d ",Data[i]);}printf("\n");for(j = 0;j < M;j++){// 对所有数据操作for(i = 0;i < N;i++){if( DataShowEnable[j][i] )printf("%d ",DataShow[j][i]);elseprintf(" ");}printf("\n");}printf("缺页次数: %d\n",ChangeTimes);printf("缺页率: %d %%\n",ChangeTimes * 100 / N); }// 最佳置换算法void Optimal(){int i,j,k;bool find;int point;int temp; // 临时变量，比较离的最远的时候用int m = 1,n;ChangeTimes = 0;for(j = 0;j < M;j++){for(i=0;i < N;i++){DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据}}for(i = 0;i < M;i++){count[i] = 0 ; // 初始化计数器}// 确定当前页面是否在物理块中，在继续，不在置换/////////////////////////////////////////////////////////////////////////////////// Block[0] = Data[0];for(i = 1;m < M;i++){int flag = 1;for(n = 0; n < m;n++){if(Data[i] == Block[n]) flag = 0;}if(flag == 0) continue;Block[m] = Data[i];m++;}//////////////////////////////////////////////////////////////////////////////////// 对所有数据进行操作for(i=0;i < N;i++){// 表示块中有没有该数据find = false;for(j = 0;j < M;j++){if( Block[j] == Data[i] ){find = true;}}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据，最优算法ChangeTimes++; // 缺页次数++for(j = 0;j < M;j++){// 找到下一个值的位置find = false;for( k = i;k < N;k++){if( Block[j] == Data[k] ){find = true;count[j] = k;break;}}if( !find ) count[j] = N;}// 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1if( (i + 1) > M ){//获得要替换的块指针temp = 0;for(j = 0;j < M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];// 保存要显示的数据for(j = 0;j < M;j++){DataShow[j][i] = Block[j];DataShowEnable[i < M ? (j <= i ? j : i) : j][i] = true; // 设置显示数据}}// 输出信息printf("\nOptimal => \n");DataOutput();}// 先进先出置换算法void FIFO(){bool find;int point;int temp; // 临时变量int m = 1,n;ChangeTimes = 0;for(j = 0;j < M;j++){for(i = 0;i < N;i++){DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据}}for(i = 0;i < M;i++){count[i] = 0; // 大于等于BlockNum，表示块中没有数据，或需被替换掉// 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1，// 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段}// 确定当前页面是否在物理块中，在继续，不在置换/////////////////////////////////////////////////////////////////////////////////// Block[0] = Data[0];for(i = 1;m < M;i++){int flag = 1;for(n = 0; n < m;n++){if(Data[i] == Block[n]) flag = 0;}if(flag == 0) continue;Block[m] = Data[i];m++;}//////////////////////////////////////////////////////////////////////////////////// 对有所数据操作for(i = 0;i < N;i++){// 增加countfor(j = 0;j < M;j++){count[j]++;find = false; // 表示块中有没有该数据for(j = 0;j < M;j++){if( Block[j] == Data[i] ){find = true;}}// 块中有该数据，判断下一个数据if( find ) continue;// 块中没有该数据ChangeTimes++; // 缺页次数++// 因为i是从0开始记，而M指的是个数，从1开始，所以i+1if( (i + 1) > M ){//获得要替换的块指针temp = 0;for(j = 0;j < M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0; // 更新计数值// 保存要显示的数据for(j = 0;j < M;j++){DataShow[j][i] = Block[j];DataShowEnable[i < M ? (j <= i ? j : i) : j][i] = true; // 设置显示数据}}// 输出信息printf("\nFIFO => \n");DataOutput();}// 最近最久未使用置换算法void LRU(){int i,j;bool find;int point;int temp; // 临时变量int m = 1,n;ChangeTimes = 0;for(j = 0;j < M;j++){for(i = 0;i < N;i++){DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据}}for(i = 0;i < M;i++){count[i] = 0 ; // 初始化计数器}// 确定当前页面是否在物理块中，在继续，不在置换///////////////////////////////////////////////////////////////////////////////////Block[0] = Data[0];for(i = 1;m < M;i++){int flag = 1;for(n = 0; n < m;n++){if(Data[i] == Block[n]) flag = 0;}if(flag == 0) continue;Block[m] = Data[i];m++;}//////////////////////////////////////////////////////////////////////////////////// 对有所数据操作for(i = 0;i < N;i++){// 增加countfor(j = 0;j < M;j++){count[j]++;}find = false; // 表示块中有没有该数据for(j = 0;j < M;j++){if( Block[j] == Data[i] ){count[j] = 0;find = true;}}// 块中有该数据，判断下一个数据if( find ) continue;// 块中没有该数据ChangeTimes++;// 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1 if( (i + 1) > M ){//获得要替换的块指针temp = 0;for(j = 0;j < M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0;// 保存要显示的数据for(j=0;j<M;j++){DataShow[j][i] = Block[j];DataShowEnable[i < M ?(j <= i ? j : i) : j][i] = true; // 设置显示数据}}// 输出信息printf("\nLRU => \n");DataOutput();}实验结果截图：程序运行：输入相应数据：选择相应算法：最佳置换算法：先进先出算法：最近最久未使用算法：。

计算机科学系实验报告书课程名：《操作系统》题目：虚拟存储器管理页面置换算法模拟实验班级：学号：姓名：一、实验目的与要求1.目的：请求页式虚存管理是常用的虚拟存储管理方案之一。

通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。

2.要求：本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。

其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。

要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。

程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。

二、实验说明1．设计中虚页和实页的表示本设计利用C语言的结构体来描述虚页和实页的结构。

在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。

pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。

time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。

在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。

pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。

next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。

2．关于缺页次数的统计为计算命中率，需要统计在20次的虚页访问中命中的次数。

为此，程序应设置一个计数器count，来统计虚页命中发生的次数。

每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。

最终命中率=count/20*100%。

3．LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值，表示该虚页的最后一次被访问时间。

实验三页面置换算法#include<iostream.h>#include <stdlib.h>#include <time.h>#include <stdio.h>#define L 20int M; struct Proi nt num,time;};I nput(int m,Pro p[L]){i nt i,j,c;c out<<"请输入实际页面走向长度L(15<=L<=20)：";d o{c in>>m;i f(m>20||m<15)cout<<"实际页面长度须在15～20之间;请重新输入L：";e lse break;}while(1);j=time(NULL);s rand(j);c out<<"输出随机数: ";f or(i=0;i<m;i++){p[i].num=rand( )%10+1;p[i].time=0;c out<<p[i].num<<" ";}c out<<endl;r eturn m;}v oid print(Pro *page1){P ro *page=new Pro[M];p age=page1;f or(int i=0;i<M;i++)i f(page[i].num==-1)c out<<" ";e lsec out<<page[i].num<<" ";c out<<"√"<<endl;}i nt Search(int e,Pro *page1 ){P ro *page=new Pro[M];p age=page1;f or(int i=0;i<M;i++) if(e==page[i].num) return i; r eturn -1;}i nt Max(Pro *page1){}i nt Count(Pro *page1,int i,int t,Pro p[L]){}i nt main(){i nt c;i nt m=0,t=0;f loat n=0;P ro p[L];c out<<"********************************************* "<<endl;c out<<" * 页式存储管理*"<<endl;c out<<"********************************************* "<<endl;c out<<"请输入可用内存页面数m(3～5): ";d o{c in>>M;i f(M>5||M<3)c out<<"内存块M须在3～5之间，请重新输入M：";e lse break;}while(1);m=Input(m,p);P ro *page=new Pro[M];c out<<"^-^欢迎进入操作系统界面^-^"<<endl;c out<<"1:FIFO页面置换"<<endl;c out<<"2:LRU页面置换"<<endl;c out<<"3:OPT页面置换"<<endl;c out<<"4:退出"<<endl;d o{c out<<"按1～4键操作："<<endl;c in>>c;s ystem("cls");f or(int i=0;i<M;i++){p age[i].num=-1;p age[i].time=m-1-i;}i=0;i f(c==1){n=0;c out<<"******************************************"<<endl;c out<<endl;c out<<" FIFO算法页面置换情况如下: "<<endl;cout<<endl;c out<<"******************************************"<<endl;w hile(i<m){i f(Search(p[i].num,page)>=0) {cout<<p[i].num<<" "; p[i].numc out<<"不缺页"<<endl;i++;}e lse {i f(t==M)t=0;e lse{n++;p age[t].num=p[i].num;c out<<p[i].num<<" ";p rint(page);t++;i++;}}}c out<<"缺页次数："<<n<<" }i f(c==2){n=0;c out<<"******************************************"<<endl;c out<<endl;c out<<" LRU算法页面置换情况如下: "<<endl;c out<<endl;c out<<"******************************************"<<endl;w hile(i<m){i nt a;t=Search(p[i].num,page);i f(t>=0){p age[t].time=0;for(a=0;a<M;a++)i f(a!=t)page[a].time++;cout<<p[i].num<<" ";c out<<"不缺页"<<endl;}e lse{n++; t=Max(page);page[t].num=p[i].num; page[t].time=0;cout<<p[i].num<<" ";p rint(page);f or(a=0;a<M;a++)i f(a!=t)page[a].time++;}i++;}c out<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl;}i f(c==3){n=0;c out<<"******************************************"<<endl;c out<<endl;c out<<" OPT算法置换情况如下:"<<endl;c out<<endl;c out<<"******************************************"<<endl;w hile(i<m){i f(Search(p[i].num,page)>=0){c out<<p[i].num<<" ";c out<<"不缺页"<<endl;i++;}e lse{i nt a=0;f or(t=0;t<M;t++)i f(page[t].num==0)a++;if(a!=0) {i nt q=M;f or(t=0;t<M;t++)i f(page[t].num==0&&q>t)q=t;p age[q].num=p[i].num;n++;c out<<p[i].num<<" ";p rint(page);i++;}e lse{i nt temp=0,s;f or(t=0;t<M;t++)i f(temp<Count(page,i,t,p)){t emp=Count(page,i,t,p);s=t;}page[s].num=p[i].num;n++;c out<<p[i].num<<" ";p rint(page);i++;}}}c out<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl;}i f(c==4){c out<<" ^-^再见！^-^ "<<endl;}}while(c==1||c==2||c==3||c==4);r eturn 0;}结果：完成相关实验并且获得预期结果.。

操作系统实验报告_页面置换算法模拟学生实验报告姓名: 年级专业班级学号成绩验证设计实验3 请求分页系统的页面实验类型课程名称实验名称操作系统综合创新置换算法【实验目的、要求】1.通过编程实现请求分页存储管理系统的Optimal、FIFO、LRU调度算法，使学生掌握计算机虚拟存储管理中有关缺页处理方法等内容，巩固有关虚拟存储管理的知识。

2.了解Windows2000/XP中内存管理机制，掌握页式虚拟存储技术。

3.理解内存分配原理，特别是以页面为单位的虚拟内存分配方法。

【实验内容】在Windows XP或Windows 2000等操作系统环境下，使用VC、VB、Delphi、java或C等编程语言，实现请求分页存储管理系统的Optimal、FIFO、LRU调度算法。

【实验环境】(含主要设计设备、器材、软件等)计算机 C语言编程软件【实验步骤、过程】(含原理图、流程图、关键代码，或实验过程中的记录、数据等)1.启动计算机，运行C语言编程软件。

2.分析理解页面的几种基本算法的特点和原理，在纸上画出原理图。

3.编辑源程序，关键代码如下。

(1)先进先出页面置换算法。

#include<stdio.h>void main(){int i,n,t,k=3,a[100];scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=3;i<n;i++)if(a[i]!=a[0]&&a[i]!=a[1]&&a[i]!=a[2]) //该页面在内存中，不需要置换。

{t=a[i];a[i]=a[k%3]; //通过对k值对3取余的值来确定需要置换的当前页面。

a[k%3]=t;k++; //仅当发生了页面置换时，k的值才发生改变。

printf("%d %d %d\n",a[0],a[1],a[2]);}else{printf("%d %d %d\n",a[0],a[1],a[2]);}}(2)最佳置换算法#include<stdio.h>void main(){int i,j,,n,a[100];int c1,c2,c3; // 标志该页面再次被访问时在引用串中的位置int p,k,r;printf("请输入页面数:\n");scanf("%d",&n);printf("请输入页面号引用串:\n");for(i=0;i<n;i++)scanf("%d",&a[i]);for(j=3;j<n;j++){if((a[j]!=a[0])&&(a[j]!=a[1])&&(a[j]!=a[2])) //页面在内存不发生置换～{for(p=j;p<n;p++)if(a[0]==a[p]){ c1=p;break; //跳出循环，直接置c1=n!} else c1=n; //标志该页面再次被访问时在引用串中的位置～若该页面不会再次被访问，则将c1置为最大n!for(k=j;k<n;k++)if(a[1]==a[k]){ c2=k;break; }elsec2=n;for(r=j;r<n;r++)if(a[2]==a[r]){ c3=r;break;}else c3=n; //通过比较c1,c2,c3的大小确定最长时间内不再访问的页面～if((c1>c2)&&(c1>c3)||(c1==c3)||(c1==c2)) //当前a[0]页面未来最长时间不再访问!{t=a[j];a[j]=a[0];a[0]=t; //把当前访问页面和最佳页面交换～printf("%d %d %d\n",a[0],a[1],a[2]);}if((c2>c1)&&(c2>c3)||(c2==c3)) //当前a[1]页面未来最长时间不再访问!{t=a[j];a[j]=a[1];a[1]=t;printf("%d %d %d\n",a[0],a[1],a[2]);}if((c3>c1)&&(c3>c2)) //当前a[2]页面未来最长时间不再访问!{t=a[j];a[j]=a[2];a[2]=t;printf("%d %d %d\n",a[0],a[1],a[2]); //输出置换后页框中的物理块组成～}}elseprintf("%d %d %d\n",a[0],a[1],a[2]);}}(3)LRU算法。

学生实验报告姓名：年级专业班级学号成绩【实验结果或总结】（对实验结果进行相应分析，或总结实验的心得体会，并提出实验的改进意见1.程序的执行结果如下：(1)先进先出页面置换算法(2)最佳页面置换法(3)最近最久未使用置换算法2.以上三个程序通过数组和排序语句实现页面的三种基本调度算法。

(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算法)改进的方法为在c1,c2,c3间的大小比较判断语句中增加关系语句的默认处理办法，当三者间有部分相同时，默认选择按从前到后的顺序执行。

比如当c2=c3的时候选择页面a[2]进行置换。

当c1=c2=c3时则选择页面a[0]进行置换。

也就相当于无法运用LRU算法调用的时候折衷采取先进先出置换算法，以实现页面的合理调度，提高页面的利用效率。

指导教师签名：20 年月日【备注】。

操作系统实验三(页面置换算法)实验报告int N; // 页面个数int M; // 最小物理块数int ChangeTimes; // 缺页次数void DataInput(); // 输入数据的函数void DataOutput(); // 输出数据的函数void FIFO(); // FIFO 函数void Optimal(); // Optimal函数void LRU(); // LRU函数int main(int argc, char* argv[]){DataInput();int menu;while(true){printf("\n* 菜单选择 *\n");printf("*******************************************************\n");printf("*1-Optimal *\n");printf("* 2-FIFO *\n");printf("* 3-LRU *\n");printf("* 4-返回上一级 *\n");printf("* 0-EXIT *\n");printf("*******************************************************\n");scanf("%d",&menu);switch(menu){case 1:Optimal();break;case 2:FIFO();break;case 3:LRU();break;case 0:exit(0);break;case 4:system("cls");DataInput();break;}if(menu != 1 && menu != 2 && menu != 3 && menu != 0 && menu !=4) {system("cls");printf("\n请输入0 - 4之间的整数！\n");continue;}}return 0;}void DataInput(){int i,choice;printf("请输入最小物理块数：");scanf("%d",&M);// 输入最小物理块数大于数据个数while(M > BlockNum){printf("物理块数超过预定值，请重新输入：");scanf("%d",&M);}printf("请输入页面的个数：");scanf("%d",&N);// 输入页面的个数大于数据个数while(N > DataMax){printf("页面个数超过预定值，请重新输入：");scanf("%d",&N);}printf("请选择产生页面访问序列的方式(1.随机 2.输入)：");scanf("%d",&choice);switch(choice){case 1:// 产生随机访问序列for(i = 0;i < N;i++){Data[i] = (int)(((float) rand() / 32767) * 10); // 随机数大小在0 - 9之间}system("cls");// 显示随机产生的访问序列printf("\n随机产生的访问序列为：");for(i = 0;i < N;i++){printf("%d ",Data[i]);}printf("\n");break;case 2:// 输入访问序列printf("请输入页面访问序列：\n");for(i = 0;i < N;i++)scanf("%d",&Data[i]);system("cls");// 显示输入的访问序列printf("\n输入的访问序列为：");for(i = 0;i < N;i++){printf("%d ",Data[i]);}printf("\n");break;default:while(choice != 1 && choice != 2){printf("请输入1或2选择相应方式:");scanf("%d",&choice);}break;}}void DataOutput(){int i,j;// 对所有数据操作for(i = 0;i < N;i++){printf("%d ",Data[i]);}printf("\n");for(j = 0;j < M;j++){// 对所有数据操作for(i = 0;i < N;i++){if( DataShowEnable[j][i] )printf("%d ",DataShow[j][i]);elseprintf(" ");}printf("\n");}printf("缺页次数: %d\n",ChangeTimes);printf("缺页率: %d %%\n",ChangeTimes * 100 / N);}// 最佳置换算法void Optimal(){int i,j,k;bool find;int point;int temp; // 临时变量，比较离的最远的时候用int m = 1,n;ChangeTimes = 0;for(j = 0;j < M;j++){for(i=0;i < N;i++){DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据}}for(i = 0;i < M;i++){count[i] = 0 ; // 初始化计数器}// 确定当前页面是否在物理块中，在继续，不在置换/////////////////////////////////////// ///////////////////////////////////////// ///Block[0] = Data[0];for(i = 1;m < M;i++){int flag = 1;for(n = 0; n < m;n++){if(Data[i] == Block[n]) flag = 0;}if(flag == 0) continue;Block[m] = Data[i];m++;}/////////////////////////////////////// ///////////////////////////////////////// //// 对所有数据进行操作for(i=0;i < N;i++){// 表示块中有没有该数据find = false;for(j = 0;j < M;j++){if( Block[j] == Data[i] ){find = true;}}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据，最优算法ChangeTimes++; // 缺页次数++for(j = 0;j < M;j++){// 找到下一个值的位置find = false;for( k = i;k < N;k++){if( Block[j] == Data[k] ){find = true;count[j] = k;break;}}if( !find ) count[j] = N;}// 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1if( (i + 1) > M ){//获得要替换的块指针temp = 0;for(j = 0;j < M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];// 保存要显示的数据for(j = 0;j < M;j++){DataShow[j][i] = Block[j];DataShowEnable[i < M ? (j <= i ? j : i) : j][i] = true; // 设置显示数据}}// 输出信息printf("\nOptimal => \n");DataOutput();}// 先进先出置换算法void FIFO(){int i,j;bool find;int point;int temp; // 临时变量int m = 1,n;ChangeTimes = 0;for(j = 0;j < M;j++){for(i = 0;i < N;i++){DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据}}for(i = 0;i < M;i++){count[i] = 0; // 大于等于BlockNum，表示块中没有数据，或需被替换掉// 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1，// 同时其它的块计数值加 1 ，成了（1 3 2 ），见下面先进先出程序段}// 确定当前页面是否在物理块中，在继续，不在置换/////////////////////////////////////// ///////////////////////////////////////// ///Block[0] = Data[0];for(i = 1;m < M;i++){int flag = 1;for(n = 0; n < m;n++){if(Data[i] == Block[n]) flag = 0;}if(flag == 0) continue;Block[m] = Data[i];m++;}/////////////////////////////////////// ///////////////////////////////////////// //// 对有所数据操作for(i = 0;i < N;i++){// 增加countfor(j = 0;j < M;j++){count[j]++;}find = false; // 表示块中有没有该数据for(j = 0;j < M;j++){if( Block[j] == Data[i] ){find = true;}}// 块中有该数据，判断下一个数据if( find ) continue;// 块中没有该数据ChangeTimes++; // 缺页次数++ // 因为i是从0开始记，而M指的是个数，从1开始，所以i+1if( (i + 1) > M ){//获得要替换的块指针temp = 0;for(j = 0;j < M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0; // 更新计数值// 保存要显示的数据for(j = 0;j < M;j++){DataShow[j][i] = Block[j];DataShowEnable[i < M ? (j <= i ? j : i) : j][i] = true; // 设置显示数据}}// 输出信息printf("\nFIFO => \n");DataOutput();}// 最近最久未使用置换算法void LRU(){int i,j;bool find;int point;int temp; // 临时变量int m = 1,n;ChangeTimes = 0;for(j = 0;j < M;j++){for(i = 0;i < N;i++)DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据}}for(i = 0;i < M;i++){count[i] = 0 ; // 初始化计数器}// 确定当前页面是否在物理块中，在继续，不在置换/////////////////////////////////////// ///////////////////////////////////////// ///Block[0] = Data[0];for(i = 1;m < M;i++){int flag = 1;for(n = 0; n < m;n++){if(Data[i] == Block[n]) flag = 0;if(flag == 0) continue;Block[m] = Data[i];m++;}/////////////////////////////////////// ///////////////////////////////////////// //// 对有所数据操作for(i = 0;i < N;i++){// 增加countfor(j = 0;j < M;j++){count[j]++;}find = false; // 表示块中有没有该数据for(j = 0;j < M;j++){if( Block[j] == Data[i] ){count[j] = 0;find = true;}}// 块中有该数据，判断下一个数据if( find ) continue;// 块中没有该数据ChangeTimes++;// 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1if( (i + 1) > M ){//获得要替换的块指针temp = 0;for(j = 0;j < M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0;// 保存要显示的数据for(j=0;j<M;j++){DataShow[j][i] = Block[j];DataShowEnable[i < M ?(j <= i ? j : i) : j][i] = true; // 设置显示数据}}// 输出信息printf("\nLRU => \n");DataOutput();}实验结果截图：程序运行：输入相应数据：选择相应算法：最佳置换算法：先进先出算法：最近最久未使用算法：。

页面置换算法实验报告页面置换算法实验报告一、引言在计算机操作系统中，页面置换算法是一种重要的内存管理策略。

当物理内存不足以容纳所有需要运行的进程时，操作系统需要根据一定的算法将部分页面从内存中换出，以便为新的页面腾出空间。

本实验旨在通过实际操作，对比不同的页面置换算法在不同场景下的性能表现。

二、实验背景在计算机系统中，每个进程都有自己的虚拟内存空间，而物理内存空间是有限的。

当进程需要访问某个页面时，如果该页面不在物理内存中，就会发生缺页中断，操作系统需要根据页面置换算法选择一个页面将其换出，然后将需要访问的页面换入。

常见的页面置换算法有先进先出（FIFO）、最近最久未使用（LRU）、时钟（Clock）等。

三、实验目的本实验旨在通过模拟不同的页面置换算法，比较它们在不同情况下的缺页率和效率。

通过实验结果，评估各个算法在不同场景下的优劣，为实际系统的内存管理提供参考。

四、实验设计与方法本实验选择了三种常见的页面置换算法进行比较：FIFO、LRU和Clock。

我们使用C++编程语言模拟了一个简单的内存管理系统，并通过产生不同的访存序列来模拟不同的场景。

实验中，我们设置了不同的物理内存大小，访存序列长度和页面大小，以模拟不同的系统环境。

五、实验结果与分析在实验中，我们分别测试了FIFO、LRU和Clock算法在不同的系统环境下的表现。

通过统计不同算法的缺页率和运行时间，得出以下结论：1. FIFO算法FIFO算法是最简单的页面置换算法，它按照页面进入内存的顺序进行置换。

实验结果表明，FIFO算法在缺页率方面表现一般，特别是在访存序列具有局部性的情况下，其性能明显下降。

这是因为FIFO算法无法区分不同页面的重要性，可能会将经常使用的页面换出，导致缺页率升高。

2. LRU算法LRU算法是一种基于页面访问时间的置换算法，它认为最近被访问的页面很可能在未来会被再次访问。

实验结果表明，LRU算法在缺页率方面表现较好，特别是在访存序列具有较强的局部性时，其性能明显优于FIFO算法。

页面置换算法实验报告一、实验目的本次实验的目的是通过模拟页面置换算法的过程，了解不同算法的优缺点，掌握算法的实现方法，以及对算法的性能进行评估。

二、实验原理页面置换算法是操作系统中的一个重要概念，它是为了解决内存不足的问题而产生的。

当系统中的进程需要使用内存时，如果内存已经被占满，就需要将一些页面从内存中置换出去，以便为新的页面腾出空间。

页面置换算法就是用来决定哪些页面应该被置换出去的算法。

常见的页面置换算法有以下几种：1. 最佳置换算法（OPT）最佳置换算法是一种理论上的最优算法，它总是选择最长时间内不会被访问的页面进行置换。

但是，由于无法预测未来的页面访问情况，因此最佳置换算法无法在实际中使用。

2. 先进先出置换算法（FIFO）先进先出置换算法是一种简单的置换算法，它总是选择最先进入内存的页面进行置换。

但是，这种算法容易出现“抖动”现象，即频繁地将页面置换出去，然后再将其置换回来。

3. 最近最久未使用置换算法（LRU）最近最久未使用置换算法是一种比较常用的置换算法，它总是选择最长时间未被访问的页面进行置换。

这种算法可以避免“抖动”现象，但是实现起来比较复杂。

4. 时钟置换算法（Clock）时钟置换算法是一种改进的FIFO算法，它通过维护一个环形链表来实现页面置换。

当需要置换页面时，算法会从当前位置开始扫描链表，如果找到一个未被访问的页面，则将其置换出去。

如果扫描一圈后都没有找到未被访问的页面，则将当前位置的页面置换出去。

三、实验过程本次实验使用Python语言编写了一个页面置换算法模拟程序，可以模拟上述四种算法的过程，并输出算法的性能指标。

程序的主要流程如下：1. 读取输入文件，获取页面访问序列和内存大小等参数。

2. 根据选择的算法，初始化相应的数据结构。

3. 遍历页面访问序列，模拟页面置换的过程。

4. 输出算法的性能指标，包括缺页率、页面置换次数等。

下面分别介绍四种算法的实现方法。

1. 最佳置换算法（OPT）最佳置换算法需要预测未来的页面访问情况，因此需要遍历整个页面访问序列，找到最长时间内不会被访问的页面。

四种页面置换算法一、实验原理：在存运行过程中，若其所要访问的页面不在存而需要把他们调入存，但存已经没有空闲空间时，为了保证该进程能正常运行，系统必须从存中调出一页程序或数据送磁盘的对换区中。

但应将那个页面调出，需根据一定的算法来确定。

通常，把选择换出页面的算法成为页面置换算法。

置换算法的好坏，将直接影响到系统的性能。

一个好的页面置换算法，应具有较低的页面更换频率。

从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间不会在访问的页面调出。

目前存在着许多种置换算法（如FIFO，OPT，LRU），他们都试图更接近理论上的目标。

二、实验目的1．通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。

2．掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。

3．通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。

三、实验分析在进程运行过程中，若其所访问的页面不存在存而需要把它们调入存，但存已无空闲时，为了保证该进程能够正常运行，系统必须从存中调出一页程序或数据送磁盘的对换区中。

但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。

四、运行结果五、代码#include"stdafx.h"#define M 3 //物理页数#define N 20 //需要调入的页数typedef struct page {int num;int time;int temp;}Page; //物理页项，包括调入的页号和时间Page pp[M]; //M个物理页int queue1[20], queue2[20], queue3[20]; //记录置换的页int K = 0, S = 0, T = 0; //置换页数组的标识int pos = 0;//记录存在最长时间项int changenum = 0;int A[N];//初始化存页表项及存储存情况的空间void INIT(){int i;for (i = 0; i<M; i++){pp[i].num = -1;pp[i].time = 0;pp[i].temp = 0;} }//取得存中存在时间最久的位置int GetMax(){int max = -1;int i;for (i = 0; i<M; i++){if (pp[i].time > max){max = pp[i].time;pos = i;}}return pos;}//检查最长时间不使用页面int longestTime(int mxatimep,int temp) {int i;int max = -1;for (i = 0; i<M; i++){pp[i].temp = 0;}for (i = temp; i<N; i++){if (pp[0].temp == 1 && pp[1].temp == 1 && pp[2].temp == 1){ break;}if (pp[0].num != A[i]){pp[0].time++;if (pp[0].temp >= 1){pp[0].time--;}}else{pp[0].temp++;}if (pp[1].num != A[i]){pp[1].time++;if (pp[1].temp >= 1){pp[1].time--;}}else{pp[1].temp++;}if (pp[2].num != A[i]){pp[2].time++;if (pp[2].temp >= 1){pp[2].time--;}else{pp[2].temp++;}}for (i = 0; i<M; i++){if (pp[i].time>max){max = pp[i].time;pos = i;}}return pos;}//检查某页是否在存int Equation(int fold){int i;for (i = 0; i<M; i++){if (pp[i].num == fold)return i;}return -1;}//检查物理存是否已满,-1表满，其他不满int Check(){int i;for (i = 0; i<M; i++){if (pp[i].num == -1)return i;}return -1;}void FIFO(int fold,int temp){int i;int a, b, c;a = Equation(fold);//页已存在if (a != -1){}//页不存在else{b = Check();//存还有空闲if (b != -1){pp[b].num = fold;//存已满，需要置换else {c = GetMax();pp[c].num = fold;pp[c].time = 0;changenum++;}queue1[K++] = fold;}for (i = 0; i<M; i++){if (pp[i].num != -1){pp[i].time++;}}}void OPT(int fold,int temp){int a, b, c;a = Equation(fold);if (a == -1){//页不在存b = Check();//存还有空闲if (b != -1){pp[b].num = fold;}//存已满，需要置换else{c = longestTime(fold,temp);pp[c].num = fold;pp[c].time = 0;changenum++;}queue3[T++] = fold;}}void LRU(int fold,int temp){int i;int a, b;int p;a = Equation(fold);if (a != -1)//页已在存{//把此项移动到链表最后一项if (a == 2)//此项已经在最后，不需要做任何改动{}else{p = Equation(-1);if (p == -1)//链表是满的{for (; a<2; a++)pp[a].num = pp[a + 1].num;pp[2].num = fold;}else if (p <= 3)//链表不满{for (; a<p - 1; a++)pp[a].num = pp[a + 1].num;pp[a].num = fold;}}}else{b = Check();if (b != -1)//不满pp[b].num = fold;else{for (i = 0; i<2; i++)pp[i].num = pp[i + 1].num;pp[2].num = fold;changenum++;}queue2[S++] = fold;}}int_tmain(int argc, _TCHAR* argv[]){int B[N];int i;INIT();changenum = 0;printf("请依次输入%d个页面号：\n", N);for (i = 0; i<N; i++){scanf_s("%d", &A[i]);}//OPTprintf("\n");printf("1.最佳置换算法（Opt）\n");INIT();changenum = 0;for (i = 0; i<N; i++){B[i] = A[i];}for (i = 0; i<N; i++){OPT(B[i], i);}printf("\n");printf("OPT算法，调入页面顺序为：");for (i = 0; i<T; i++)printf("%3d", queue3[i]);printf("\n页面置换次数为：%6d\n缺页率：%16.2f\n\n", changenum, (float)changenum / N); //FIFOprintf("2.先进先出页面置换算法（FIFO)\n");INIT();changenum = 0;for (i = 0; i<N; i++){B[i] = A[i];}for (i = 0; i<N; i++){FIFO(B[i], i);}printf("FIFO算法，调入页面顺序为：");for (i = 0; i<K; i++)printf("%3d", queue1[i]);printf("\n页面置换次数为：%6d\n缺页率：%16.2f\n\n", changenum, (float)changenum / N);//LRUprintf("3.最近最久未使用算法（LRU)\n");INIT();changenum = 0;for (i = 0; i<N; i++){B[i] = A[i];}for (i = 0; i<N; i++){LRU(B[i], i);}printf("LRU算法，调入页面顺序为：");for (i = 0; i<S; i++)printf("%3d", queue2[i]);printf("\n页面置换次数为：%6d\n缺页率：%16.2f\n\n", changenum, (float)changenum / N);printf("\n");printf("四种算法已全部执行完毕！\n");return 0;}。

页面置换算法实现一、实验目的（1）了解内存分页管理及调页策略（2）掌握一般常用的调度算法（3）学会各种存储分配算法的实现方法。

（4）了解页面大小和内存实际容量对命中率的影响。

（5）通过页面访问序列随机发生器实现对上述算法的测试及性能比较二、实验内容采用页式分配存储方案,通过分别计算不同算法的命中率来比较算法的优劣,同时也考虑页面大小及内存实际容量对命中率的影响,设计一个虚拟存储区和内存工作区,并使用下述算法来模拟实现页面的置换：1. 先进先出的算法（FIFO）(是最简单的页面置换算法)2. 最近最久未使用算法（LRU）3. 最佳置换算法（OPT）（理想置换算法）实验分析在进程运行过程中,若其所访问的页面不存在内存而需要把它们调入内存, 但内存已无空闲时,为了保证该进程能够正常运行,系统必须从内存中调出一页程序或数据送磁盘的对换区中。

但应调出哪个页面,需根据一定的算法来确定, 算法的好坏,直接影响到系统的性能。

一个好的页面置换算法,应该有较低的页面更换频率。

2.1 先进先出（FIFO ）页面置换算法当需要访问一个新的页面时,首先查看物理块中是否就有这个页面,若要查看的页面物理块中就有,则直接显示,不需要替换页面；如果要查看的页面物理块中没有,就需要寻找空闲物理块放入,若存在有空闲物理块,则将页面放入；若没有空闲物理块,则替换页面。

并将物理块中所有页面 timer++,是最简单的页面置换算法。

这种算法的基本思想是：当需要淘汰一个页面时,总是选择驻留主存时间最长的页面进行淘汰,即先进入主存的页面先淘汰。

其理由是：最早调入主存的页面不再被使用的可能性最大。

2.2 最近久未使用 (LRU) 置换算法的思路最近久未使用置换算法的替换规则,是根据页面调入内存后的使用情况来进行决策的。

该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间,当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。

页面置换算法实验报告实验心得
本次实验是关于页面置换算法的实验，页面置换算法是操作系统中一个非常重要的算法，用于管理内存中的页面。

在本次实验中，我们学习了三种页面置换算法：FIFO、LRU和OPT。

FIFO算法是最简单的页面置换算法，它按照页面进入内存的顺序来选择要被替换的页面。

但是FIFO算法存在一个问题，就是它无法考虑页面是否频繁使用，因此可能会大量使用不常用的页面，而且在内存不足时，会频繁地将常用的页面替换出去。

LRU算法是一种比较高效的页面置换算法，它按照页面最近的使用时间来选择要被替换的页面。

LRU算法考虑了页面的使用频率，能够保证常用的页面不会被替换出去，因此在内存不足时，LRU算法的性能比FIFO算法要好。

OPT算法是一种理论上最优的页面置换算法，它根据未来最长时间内不再使用的页面来选择要被替换的页面。

但是实际上，由于难以预测未来的页面使用情况，因此实际上很难实现OPT算法。

在实验中，我们使用了Python编程语言来模拟这三种页面置换算法，并对算法的性能进行了测试。

通过实验，我对页面置换算法有了更深入的了解，也提升了自己的编程能力。

实验三页面替换算法3.1实验简介本实验要求实现多种页面替换算法，然后利用随机产生的引用串测试其性能。

3.2 页面替换算法我们做如下假设：• 虚拟内存页面总数为P，标号从0 到P -1• 引用串RS(reference string) 是一个整数序列，整数的取值范围为0到P -1。

RS 中的每个元素p 表示对页面p 的一次引用• 物理内存由F 帧组成，标号从0 到F -1。

我们引入一个数组M[F]，数组元素M[f] 中包含数字p，它表示帧f 中包含页面p页面替换算法顺次读取RS 中的每个元素。

对于RS 中的元素值p，算法搜索数组M[F]，判断是否存在某个f，使得M[f] == p。

如果未发现，则表示页面缺失。

这时，算法必须根据其特定的替换规则，选择一帧M[i]，用页面p 替换其中的内容，即令M[i] = p。

下面讨论各种替换算法所需要的不同数据结构：• 最佳替换算法和随机替换算法不需要其它的数据结构。

对于最佳替换算法，通过搜索RS 即足以确定应被替换的页面；对于随机替换算法，产生一个取值范围在0 和F -1 之间的随机数，该随机数即可表示应被替换的页面。

• FIFO 需要一个指向最老页面的指针（数组索引）。

每当该页面被替换的时候，把该指针加1(模F) 即可。

• LRU 算法则需要一个尺寸为F 的数组，该数组用来实现排队功能：每次处理一个新的页面引用时，则把该页放置在队列的末尾。

这样，每当需要淘汰一个页面时，从队首取到的即最长时间未被用到的页面。

• Clock 算法（也叫second -chance 算法）和FIFO 算法一样，需要一个指针。

此外，它还需要一个数组，用来记录每一帧的使用情况。

3.3 试验程序#include<stdio.h>#include <windows.h>static int a,b,c;//三个存储单元static int flag_a,flag_b,flag_c;//存储单元标志位int optimal(int rs[200]){int *p1,*p2;int count=0;a=0;b=0;c=0;a=rs[0];b=rs[1];c=rs[2];p1=&rs[3];do{flag_a=0;flag_b=0;flag_c=0;p2=p1;if ((*p2!=a)&&(*p2!=b)&&(*p2!=c)){while(flag_a+flag_b+flag_c<2&&p2<=&rs[200]){if(*p2==a){flag_a=1;p2++;}else if(*p2==b){flag_b=1;p2++;}else if(*p2==c){flag_c=1;p2++;}else p2++;}if (flag_a+flag_b+flag_c==0){do{a=*p1;p1++;count++;}while(p1<=&rs[199]);}else if(flag_a+flag_b+flag_c==1) {if((*p1==a)||(*p1==b)||(*p1==c)) {p1++;}else{if(p1!=&rs[199]){a=*p1;p1++;}else{flag_a=0;flag_b=0;flag_c=0;}}}else{if (flag_a==0){a=*p1;p1++;count++;}else if (flag_b==0){b=*p1;p1++;count++;}else if (flag_c==0){c=*p1;p1++;count++;}}}else p1++;}while(p1<=&rs[199]&&p2<=&rs[199]); return count;}int FIFO(int rs[200]){int *p1,*p2;int count=0;a=0;b=0;c=0;a=rs[0];b=rs[1];c=rs[2];p1=&rs[3];p2=p1;while(p1<=&rs[200]&&p2<=&rs[200]){ p2=p1;if ((*p2!=a)&&(*p2!=b)&&(*p2!=c)) {a=*p2;b=c;c=*p2;count++;}else p1++;}return count;}int rand(int rs[200]){int *p1,*p2;int count=0;a=0;b=0;c=0;a=rs[0];b=rs[1];c=rs[2];p1=&rs[3];p2=p1;while(p1<=&rs[200]&&p2<=&rs[200]){ p2=p1;if ((*p2!=a)&&(*p2!=b)&&(*p2!=c)) {int k=rand();if(k%3==0){a=*p2;count++;}else if(k%3==1){b=*p2;count++;}else if(k%3==2){c=*p2;count++;}}else p1++;}return count;}int LRU(int rs[200]){int *p1,*p2;int count=0;a=0;b=0;c=0;a=rs[0];b=rs[1];c=rs[2];p1=&rs[3];p2=p1;while(p1<=&rs[200]&&p2<=&rs[200]){ p2=p1;if ((*p2!=a)&&(*p2!=b)&&(*p2!=c)) {c=b;b=a;a=*p2;count++;}else{if (*p2==a){p1++;}else if (*p2==b){b=a;a=*p2;p1++;}else{c=b;b=a;a=*p2;p1++;}}}return count;}int main(){int count1=0;int count2=0;int count3=0;int count4=0;int RS[200];for(int a=0;a<200;a++) {RS[a]=rand()%10;printf("%d,",RS[a]);}count1=optimal(RS);count2=FIFO(RS);count3=LRU(RS);count4=rand(RS);printf("最佳值换算法的次数是：%d次\n",count1);printf("先进先出算法的次数是：%d次\n",count2);printf("最近最久未使用算法的次数是：%d次\n",count3);printf("随机算法的次数是：%d次\n",count4);return 0;}3.4 实验结果3.5 性能评测测试不同的引用串以及不同的虚拟内存尺寸，回答如下问题：1. FIFO 算法是否比随机替换算法优越LRU 算法比FIFO 算法优越多少？解:FIFO算法比随机替换算法优越，最近最久未使用算法在rs长度为200的引用串中，替换了148次而先进先出算法替换了164次。

页面置换算法实验总结
在操作系统中，页面置换算法是为了解决内存不足的问题，当内存中的页面不足时，需要选择一些页面进行置换，将其换出到磁盘上，从而为新的页面腾出空间。

在本次实验中，我实现了三种页面置换算法，分别是FIFO（先进先出）、LRU（最近最少使用）和OPT（最佳置换）。

下面是对这三种算法的总结：
1. FIFO算法：FIFO算法是最简单的页面置换算法，它按照页面进入内存的顺序进行置换。

实验结果显示，FIFO算法在某些情况下可能会导致“抖动”现象，即不断发生页面置换，性能较差。

2. LRU算法：LRU算法是根据页面的使用历史进行置换，将最长时间没有被使用的页面置换出去。

实验结果显示，LRU算法相比于FIFO算法在减少页面抖动方面表现更好，但是实现起来较为复杂，需要维护一个访问历史记录的数据结构。

3. OPT算法：OPT算法是一种理想情况下的页面置换算法，它通过预测未来的页面访问情况来选择最佳的页面进行置换。

实验结果显示，OPT算法在减少页面抖动方面表现最好，但是实现起来较为困难，需要对未来的页面访问情况进行预测。

综上所述，不同的页面置换算法在不同的场景下有着不同的表现。

FIFO算法简单易实现，但性能较差；LRU算法在某些情况下能够较好地减少页面抖动；OPT算法在理论上是最佳的页面置换算法，但实现起来较为困难。

实际中的选择需要根据具体的应用场景
和系统需求来确定。

操作系统之页⾯置换算法（最佳置换OPT，先进先出FIFO，最近最久未使⽤LRU）最近学习操作系统时，实验要求实现常见的三种页⾯置换算法，博主按照书上要求试着编写，实现了案例，并记录在博客随记中，以便后续⾃⼰复习并也给需要的同学分享参考⼀下!⽔平有限，若有错，请悄悄告诉博主！博主好⽴即改正。

最佳置换算法（optimal replacement，OPT）是从内存中选择今后不再访问的页⾯或者在最长⼀段时间后才需要访问的页⾯进⾏淘汰。

如下例⼦：根据页⾯⾛向依次处理，得到最终的置换结果如下图表，整个页⾯缺页次数为7，缺页率为7/12=58%。

1 #include <iostream>2 #include <stdio.h>3 #include <stdlib.h>4#define N 125#define B 36using namespace std;78int pageArr[N]={1,2,3,4,1,2,5,1,2,3,4,5};//页⾯⾛向9int block[B]={0};//物理块3个，其数值是页号10 typedef struct FLAG {11int flags[B];12int counts;13 } FLAG;1415void opt(int pageArr[],int block[]);16int inBlock(int which);17int findFar(int next);18void Replace(int index,int value);19void disPlay();2021int main(void){22 cout << "begin:" <<endl;23 opt(pageArr,block);24 cout << "end!" <<endl;25return0;26 }2728void opt(int pageArr[],int block[]){29int getIndex;30for(int i=0;i<N;i++){31if(i<3){//前3页号#短缺#进队列32 block[i]=pageArr[i];33 printf("缺页：(null)-->%d\n",pageArr[i]);34 }35else {36if(i==3){37 disPlay();3839 }40if(inBlock(pageArr[i])!=-1){//下⼀个页⾯if在物理块中返回index并跳过,反-141 disPlay();4243continue;44 }45 getIndex=findFar(i+1);//从下⼀个页号，找到最远出现的页⾯,替换的下标46if(getIndex==-1){47 cout<<"error,not replace obj!"<<'\t';48 }49else{50 Replace(getIndex,pageArr[i]);//由下标找到上⼀组替换⽬标，⽤第⼆参数替换51 disPlay();5253 }54 }55 }56return;57 }5859//替换block中的物理块60void Replace(int index,int value){61 printf("缺页：%d--被替换为-->%d\n",block[index],value);62 block[index]=value;63return;64 }656667//找到最远出现的页⾯68int findFar(int next){69int index=-1;//error，默认返回不存在的索引70 FLAG myflag;71 myflag.flags[0]=0;72 myflag.flags[1]=0;73 myflag.flags[2]=0;74 myflag.counts=0;75int stop = N-next;76while(stop--){77 index=inBlock(pageArr[next++]);78if(index!=-1){79 myflag.flags[index]=1;80 myflag.counts++;83break;84 }85 }86for(index=0;index<B;index++){87if(myflag.flags[index]==0)88break;89 }90return index;91 }929394//下⼀个页⾯if在物理块中返回index,反-195int inBlock(int which){96//int i=0;97//while(i<B)98// if(block[i++]==which)99// return i-1;100for(int i=0;i<B;i++){101if(block[i]==which)102return i;103 }104return -1;105 }106107//打印⼀元组108void disPlay(){109int i=0;110while(i<B){111 printf("%d\t",block[i++]);112 }113 printf("\n");114return;115 }上⾯是博主使⽤C++（基本是C语法）编写的代码，运⾏结果如下：//////////////////////////////////////////////////////////////////////////begin:缺页：(null)-->1缺页：(null)-->2缺页：(null)-->31 2 3缺页：3--被替换为-->41 2 41 2 41 2 4缺页：4--被替换为-->51 2 51 2 51 2 5缺页：1--被替换为-->33 2 5缺页：3--被替换为-->44 2 54 2 5end!//////////////////////////////////////////////////////////////////////////先进先出算法：先进先出置换算法（first in first out,FIFO）是淘汰最先进⼊内存的页⾯，即选择在内存中驻留时间最长的页⾯进⾏淘汰的算法。