页面置换算法OPT+FIFO+LRU+clock

页式管理OPT、LRU、FIFO置换算法详解指令：1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6若内存最多容纳4个页面，则……一、OPT（理想型淘汰）算法该算法无法实现。

置换规则：（1）淘汰内存中以后不再访问的页面；（2）如果没有（1），则淘汰将要访问指令之后的将来最迟被访问的指令的页面。

分析：（1）当访问5时，内存1,2,3,4,发生第5次中断，淘汰不再访问的4，换入5，内存1,2,3,5；（2）当访问6时，内存1,2,3,5,发生第6次中断，淘汰不再访问的5，换入6，内存1,2,3,6；（3）当访问7时，内存1,2,3,6,发生第7次中断，由于之后的指令（1、2、3、6）都是现在内存页面都存在的指令，无法淘汰，但可以根据指令访问顺序，先淘汰将来最迟被访问的1，换入7，置换后的内存7,2,3,6；（4）当访问1时，内存7,2,3,6,发生第8次中断，淘汰不再访问的7，换入1，内存1,2,3,6；即OPT算法一共会出现8次缺页中断。

二、LRU（最近最久未使用）算法该算法利用堆栈实现，每次访问都调整堆栈中页面顺序。

把被访问页面从栈移出再压入栈顶。

置换规则：（1）栈顶始终为最新访问过的页面；（2）栈底始终为最近最久未被访问的页面；（3）访问存在的页面要调到栈顶。

分析：（1）访问第5个指令2时，由于内存页面中已经存在2，所以不置换，但调整2在栈中顺序，即将2调到栈顶，其它页面依次后置。

调整前内存4,3,2,1,调整后内存2,4,3,1；（2）访问第7个指令5时，发生第5次中断，原内存1,2,4,3,淘汰栈底3，栈顶调入5，调整后内存5,1,2,4；（3）访问第8个指令6时，发生第6次中断，原内存5,1,2,4,，淘汰栈底4，栈顶调入6，调整后内存6,5,1,2；……即LRU算法一共会出现10次缺页中断。

三、FIFO（先进先出）算法该算法利用队列实现。

FIFO与LRU的区别是FIFO遇到内存中存在的页面不需要调换页面顺序。

#include<iostream>#include<fstream>using namespace std;#define BlockSize 10#define PageSize 100int page[PageSize]; //页面数组存放页面int block[BlockSize]; //物理块数组int result[PageSize][BlockSize]; //存放页面和物理块二维数组int pSize = 0; //用户使用页面数int bSize = 0; //用户使用物理块数int blockFlag[BlockSize]; //用于LRU与最佳置换算法中，辅助判断该换出的页面int noPageCount = 0; //缺页次数//输入数据void inputData(){cout<<endl<<"请输入物理块数(1<=bSize<="<<BlockSize<<')'<<endl;cin>>bSize;cout<<"请输入页面数(1<=pSize<="<<PageSize<<')'<<endl;cin>>pSize;while(bSize<=0||bSize>BlockSize||pSize<=0||pSize>PageSize){//判断用户输入是否在范围内cout<<"输入范围错误，请重新输入："<<endl;cout<<"请输入物理块数(1<=F<="<<BlockSize<<')';cin>>bSize;cout<<endl<<"请输入页面数(1<=p<="<<PageSize<<')';cin>>pSize;}cout<<"请输入页面走向"<<endl;for(int i = 0;i <pSize;i++)cin>>page[i];}//初始化page数组void initPage(){for(int i = 0;i<PageSize;i++)page[i] = -1;}//初始化block与result数组void initBlockResult(){int i = 0;for(i = 0;i<BlockSize;i++)block[i] = -1;for(i = 0;i < PageSize;i++)for(int j = 0; j < BlockSize;j++)result[i][j] = -1;}//查找物理块中是否存在要调用的页面int Exist(int i){for(int j = 0;j < bSize;j++)if(block[j] == i)return j;return -1;}//显示结果void display(int noPageCount){for(int i =0 ;i < pSize;i++){cout<<" "<<page[i]<<" ";for(int j = 0;j < bSize;j++){if(result[i][j] == -1) break;else cout<<'['<<result[i][j]<<']'<<' ';}cout<<endl;}cout<<"____________________________________"<<endl;cout<<endl<<"缺页次数："<<noPageCount<<endl;cout<<"缺页率："<<((double)noPageCount/pSize)*100<<'%'<<endl;cout<<"===================================="<<endl;}//最佳置换算法OPTvoid OPT(){int i = 0,j = 0;int position = 0,noPageCount = 0;int pageFlag = 0,resultFlag = 0; //页面标记（下标）指向下一个页面,结果标记表示结果的行，即result数组的行标for(i = 0;i < BlockSize;i++)blockFlag[i] = 0;while(pageFlag < pSize){if(Exist(page[pageFlag]) != -1) //判断页面是否已经存在resultFlag++;else{if(position < bSize) //判断有无空闲物理块{ //若有则将页面放入空闲块block[position] = page[pageFlag];position++;noPageCount++;for(i = 0;i < position;i++)result[resultFlag][i] = block[i];resultFlag++;}else{for(i = 0;i < bSize;i++){for(j = pageFlag+1;j < pSize;j++){if(block[i] == page[j]){blockFlag[i] = j;break;}}if(j == pSize) blockFlag[i] = 999;}int optPos = 0,max = blockFlag[0];for(int i = 0;i < bSize;i++)if(max < blockFlag[i]){max = blockFlag[i];optPos = i;}block[optPos] = page[pageFlag];noPageCount++;for(i = 0;i < bSize;i++)result[resultFlag][i] = block[i];resultFlag++;}}pageFlag++;}cout<<endl<<"最佳置换算法:"<<endl;display(noPageCount);return;}//先进先出页面置换算法FIFOvoid FIFO(){int blockFlag = 0,pageFlag = 0,resultFlag = 0; //物理块标记，确定该换出的物理块下标int i = 0,j = 0,noPageCount = 0;int position = 0; //指示物理块，查找有无空闲while (pageFlag < pSize){if(Exist(page[pageFlag]) != -1)resultFlag++;else{if(position < bSize){block[position] = page[pageFlag];position++;noPageCount++;for(i = 0;i <= position;i++)result[resultFlag][i] = block[i];resultFlag++;}else{block[blockFlag] = page[pageFlag]; //blockFlag指示要换出的页面noPageCount++;for(i = 0;i < bSize;i++)result[resultFlag][i] = block[i];resultFlag++;blockFlag++;blockFlag = blockFlag % bSize;}}pageFlag++;}cout<<endl<<"先进先出页面置换算法FIFO:"<<endl;display(noPageCount);return;}//最近最久未用算法LRUvoid LRU(){int i = 0,noPageCount = 0;int pageFlag = 0,resultFlag = 0,position = 0;for(i = 0;i < BlockSize;i++) //初始化时间记录数组blockFlag[i] = 0;while(pageFlag < pSize){if(Exist(page[pageFlag]) != -1){ //判断页面是否已经在主存中resultFlag++;blockFlag[Exist(page[pageFlag])] = 0; //若在则将时间记录数组对应位置为0 }else{if(position < bSize){block[position] = page[pageFlag];blockFlag[position] = 0;position++;noPageCount++;for(i = 0;i <= position;i++)result[resultFlag][i] = block[i];resultFlag++;}else{int last = 0,min = blockFlag[0];for(int i = 0;i < bSize;i++)if(min < blockFlag[i]){min = blockFlag[i];last = i;}block[last] = page[pageFlag]; //置换最久未用页面blockFlag[last] = 0;noPageCount++;for(i = 0;i < bSize;i++)result[resultFlag][i] = block[i];resultFlag++;}}for(i = 0;i < bSize;i++)blockFlag[i]++;pageFlag++;}cout<<endl<<"最近最久未用算法LRU:"<<endl;display(noPageCount);return;}//时钟(clock)置换算法void clock(){int i = 0,position = 0,noPageCount = 0;bool boolBlockFlag[BlockSize];int flag = 0; //访问位循环标记int pageFlag = 0,resultFlag = 0;while(pageFlag < pSize){if(Exist(page[pageFlag]) != -1){resultFlag++;boolBlockFlag[Exist(page[pageFlag])] = true;}else{if(position < bSize){block[position] = page[pageFlag];noPageCount++;boolBlockFlag[position] = true;position++;for(i = 0;i < position;i++)result[resultFlag][i] = block[i];resultFlag++;}else{while(true){ //无限循环，找出访问位为false 的页面if(boolBlockFlag[flag] == false) break;boolBlockFlag[flag] = false; //若为true，置为falseflag++;flag = flag%bSize;}block[flag] = page[pageFlag];boolBlockFlag[flag] = true;flag++;flag = flag%bSize;noPageCount++;for(i = 0;i < position;i++)result[resultFlag][i] = block[i];resultFlag++;}}pageFlag++;}cout<<endl<<"时钟(clock)置换算法:"<<endl;display(noPageCount);return;}int main(){initPage();int func;while(func!=5){cout<<"请选择所需要的功能："<<endl;cout<<"0.输入数据"<<endl;cout<<"1.最佳（optimal）置换算法"<<endl;cout<<"2.先进先出（FIFO）置换算法"<<endl;cout<<"3.最近最久未用（LRU）置换算法"<<endl;cout<<"4.时钟（clock）置换算法"<<endl;cout<<"5.退出"<<endl;switch(func){case 0:inputData();break;case 1:initBlockResult();OPT();break;case 2:initBlockResult();FIFO();break;case 3:initBlockResult();LRU();break;case 4:initBlockResult();clock();break;case 5:break;}cout<<"请选择功能:";cin>>func;system("cls");}return 0;}。

#include<iostream>using namespace std;void Print(int bc[],int blockCount){for(int i=0;i<blockCount;i++){cout<<bc[i]<<" ";}cout<<endl;}bool Travel(int bc[],int blockCount,int x){bool is_found=false;int i;for(i=0;i<blockCount;i++){if(bc[i]==x){is_found=true;break;}}return is_found;}void FIFO(int pc[],int bc[],int pageCount,int blockCount) {cout<<"0：FIFO置换算法"<<endl;int i;if(pageCount<=blockCount){cout<<"缺页次数为"<<0<<endl;cout<<"缺页率为"<<0<<endl;}else{int noPage=0;int p=0;for(i=0;i<pageCount;i++){cout<<"引用页："<<pc[i]<<endl;if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];}else{if(p==blockCount){p=0;}bc[p]=pc[i];p++;}noPage++;cout<<"物理快情况：";Print(bc,blockCount);}cout<<endl;}cout<<"缺页次数为:"<<noPage<<endl;cout<<"缺页率为:"<<(float)noPage/pageCount<<endl;}}int FoundMaxNum(int a[],int n){int k,j;k=a[0];j=0;for (int i=0;i<n;i++){if(a[i]>=k){k=a[i];j=i;}}return j;}void LRU(int pc[],int bc[],int pageCount,int blockCount){cout<<"1：LRU置换算法"<<endl;if(pageCount<=blockCount){cout<<"缺页次数为"<<0<<endl;cout<<"缺页率为"<<0<<endl;}else{int noPage=0;int i,j,m;int *bc1=new int[blockCount];for(i=0;i<blockCount;i++){bc1[i]=0;}for(i=0;i<pageCount;i++){cout<<"引用页："<<pc[i]<<endl;if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];for(int p=0;p<=i;p++){bc1[p]++;}}else{for(j=0;j<blockCount;j++){bc1[j]++;}int k=FoundMaxNum(bc1,blockCount);bc[k]=pc[i];bc1[k]=1;}noPage++;cout<<"物理快情况：";Print(bc,blockCount);}else if(Travel(bc,blockCount,pc[i])){if(i<blockCount){for(j=0;j<=i;j++){bc1[j]++;}for(m=0;m<=i;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}else{for(j=0;j<blockCount;j++){bc1[j]++;}for(m=0;m<blockCount;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}}cout<<endl;}cout<<"缺页次数为:"<<noPage<<endl;cout<<"缺页率为:"<<(float)noPage/pageCount<<endl;delete bc1;}}void Optiomal(int pc[],int bc[],int pageCount,int blockCount){cout<<"2：最佳置换算法"<<endl;if(pageCount<=blockCount){cout<<"缺页次数为"<<0<<endl;cout<<"缺页率为"<<0<<endl;}else{int noPage=0;int i,j,k;for(i=0;i<pageCount;i++){cout<<"引用页："<<pc[i]<<endl;if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];}else{int max=0;int blockIndex;;for(j=0;j<blockCount;j++){for(k=i;k<pageCount;k++){if(bc[j]==pc[k]){break;}}if(k>=max){max=k;blockIndex=j;}}bc[blockIndex]=pc[i];}noPage++;cout<<"物理快情况：";Print(bc,blockCount);}cout<<endl;}cout<<"缺页次数为:"<<noPage<<endl;cout<<"缺页率为:"<<(float)noPage/pageCount<<endl;}}void NRU(int pc[],int bc[],int pageCount,int blockCount){cout<<"3：Clock置换算法"<<endl;if(pageCount<=blockCount){cout<<"缺页次数为"<<0<<endl;cout<<"缺页率为"<<0<<endl;}else{int noPage=0;int i,j;int *bc1=new int[blockCount];for(i=0;i<blockCount;i++){bc1[i]=0;}for(i=0;i<pageCount;i++){cout<<"引用页："<<pc[i]<<endl;if(!Travel(bc,blockCount,pc[i])){for(j=0;j<blockCount;j++){if(bc1[j]==1){bc1[j]=0;}else if(bc1[j]==0){break;}if(j==blockCount-1){j=-1;}}bc[j]=pc[i];bc1[j]=1;noPage++;cout<<"物理快情况：";Print(bc,blockCount);}cout<<endl;}cout<<"缺页次数为:"<<noPage<<endl;cout<<"缺页率为:"<<(float)noPage/pageCount<<endl;delete bc1;}}int main(){int pageCount,blockCount,i;cout<<"输入页面数"<<endl;cin>>pageCount;int *pc=new int[pageCount];cout<<"输入页面走向"<<endl;for(i=0;i<pageCount;i++){cin>>pc[i];}cout<<"输入物理块数"<<endl;cin>>blockCount;cout<<"0：FIFO置换算法"<<endl;cout<<"1：LRU置换算法"<<endl;cout<<"2：最佳置换算法"<<endl;cout<<"3：Clock置换算法"<<endl;cout<<"按数字选择算法类别："<<endl;int n;while(cin>>n){if(n==0){int *bc=new int[blockCount];FIFO(pc,bc,pageCount,blockCount);delete bc;}else if(n==1){int *bc=new int[blockCount];LRU(pc,bc,pageCount,blockCount);delete bc;}else if(n==2){int *bc=new int[blockCount];Optiomal(pc,bc,pageCount,blockCount);delete bc;}else if(n==3){int *bc=new int[blockCount];for(i=0;i<blockCount;i++){bc[i]=-1;}NRU(pc,bc,pageCount,blockCount);delete bc;}else break;}delete pc;return 0;}。

操作系统页⾯置换算法（opt,lru,fifo,clock ）实现选择调出页⾯的算法就称为页⾯置换算法。

好的页⾯置换算法应有较低的页⾯更换频率，也就是说，应将以后不会再访问或者以后较长时间内不会再访问的页⾯先调出。

常见的置换算法有以下四种（以下来⾃操作系统课本）。

1. 最佳置换算法(OPT)最佳(Optimal, OPT)置换算法所选择的被淘汰页⾯将是以后永不使⽤的，或者是在最长时间内不再被访问的页⾯,这样可以保证获得最低的缺页率。

但由于⼈们⽬前⽆法预知进程在内存下的若千页⾯中哪个是未来最长时间内不再被访问的，因⽽该算法⽆法实现。

最佳置换算法可以⽤来评价其他算法。

假定系统为某进程分配了三个物理块，并考虑有以下页⾯号引⽤串： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1进程运⾏时，先将7, 0, 1三个页⾯依次装⼊内存。

进程要访问页⾯2时，产⽣缺页中断，根据最佳置换算法，选择第18次访问才需调⼊的页⾯7予以淘汰。

然后，访问页⾯0时，因为已在内存中所以不必产⽣缺页中断。

访问页⾯3时⼜会根据最佳置换算法将页⾯1淘汰……依此类推，如图3-26所⽰。

从图中可以看出⾤⽤最佳置换算法时的情况。

可以看到，发⽣缺页中断的次数为9，页⾯置换的次数为6。

图3-26 利⽤最佳置换算法时的置换图2. 先进先出(FIFO)页⾯置换算法优先淘汰最早进⼊内存的页⾯，亦即在内存中驻留时间最久的页⾯。

该算法实现简单，只需把调⼊内存的页⾯根据先后次序链接成队列，设置⼀个指针总指向最早的页⾯。

但该算法与进程实际运⾏时的规律不适应，因为在进程中，有的页⾯经常被访问。

图3-27 利⽤FIFO 置换算法时的置换图这⾥仍⽤上⾯的实例，⾤⽤FIFO 算法进⾏页⾯置换。

进程访问页⾯2时，把最早进⼊内存的页⾯7换出。

然后访问页⾯3时，再把2, 0, 1中最先进⼊内存的页换出。

目录1 需求分析 (2)1.1 目的和要求 (2)1.2 研究内容 (2)2 概要设计 (2)2．1 FIFO算法 (3)2．2 LRU算法 (3)2．3 OPT算法 (3)2．4 输入新的页面引用串 (3)3 详细设计 (4)3．1 FIFO（先进先出）页面置换算法： (4)3．2 LRU（最近最久未使用）置换算法： (4)3．3 OPT（最优页）置换算法 (4)4 测试 (5)5 运行结果 (5)6 课程设计总结 (9)7 参考文献 (10)8 附录：源程序清单 (10)1 需求分析1.1 目的和要求在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。

1.2 研究内容模拟实现页式虚拟存储管理的三种页面置换算法（FIFO(先进先出)、LRU （最近最久未使用）和OPT（最长时间不使用）），并通过比较性能得出结论。

前提：（1）页面分配采用固定分配局部置换。

（2）作业的页面走向和分得的物理块数预先指定。

可以从键盘输入也可以从文件读入。

（3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。

2 概要设计本程序主要划分为4个功能模块，分别是应用FIFO算法、应用LRU算法、应用OPT算法和页面引用串的插入。

1.1各模块之间的结构图2．1 FIFO 算法该模块的主要功能是对相应页面引用串进行处理，输出经过FIFO 算法处理之后的结果。

2．2 LRU 算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过LRU 算法处理之后的结果。

2．3 OPT 算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过OPT 算法处理之后的结果。

2．4 输入新的页面引用串该模块的主要功能是用户自己输入新的页面引用串，系统默认的字符串是0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0，用户可以自定义全新的20个数字页面引用串。

常见的页面置换电梯算法
电梯算法是一种常用于操作系统中的页面置换算法，它可以有效地管理计算机内存，保证系统的稳定性和高效性。

在电梯算法中，页面在内存中的位置类似于电梯中的乘客在不同楼层中的位置，根据页面使用的频率和优先级，系统可以将页面从内存中置换出来，从而为新的页面腾出空间。

常见的页面置换策略包括FIFO（先进先出）、LRU（最近最少使用）、LFU（最不经常使用）、Clock（时钟置换）、OPT（最优置换）等。

其中，FIFO算法是最简单的页面置换算法，它按照页面进入内存的顺序将最先进入内存的页面置换出去；LRU算法则是根据页面最近的访问时间来判断哪些页面最有可能被再次使用，将最近最少使用的页面置换出去。

LFU算法则是根据页面使用的频率来进行置换，频率最低的页面被置换出去；Clock算法则是将内存中的页面放置在一个环中，每个页面有一个使用位，如果页面被访问，则把使用位设置为1，如果页面没有被访问，则使用位为0。

每次置换页面时，找到第一个使用位为0的页面进行置换。

最优置换算法则是根据未来的访问情况来预测哪些页面可能会被再次访问，将最长时间内不会被访问的页面置换出去。

虽然最优置换算法可以保证系统的最佳性能，但是它需要对未来的访问情况进行预测，因此在实际应用中难以实现。

总之，不同的页面置换算法都有其优缺点，需要根据具体应用场
景进行选择。

在操作系统中，通常会采用多种页面置换策略相结合的方式来管理内存，以达到最优的系统性能和稳定性。

常见的页面置换算法1.概述页面置换算法是操作系统中用于管理内存的一种算法，其目的是确保可用内存的最大化并实现对内存的高效使用。

在操作系统中，当进程所需的内存空间超出了可用的物理内存空间时，操作系统就需要从主存中选择一些页面腾出空间来装载进程所需的页面。

这就需要使用页面置换算法。

2.常见的页面置换算法2.1最优页面置换算法(OPT)最优页面置换算法是一种理论上的置换算法。

它的核心思想是通过计算进程未来访问各个页面的时间和距离，来推断出离当前时间最久的页面。

这种算法的优点是能够保证页面置换的最优性，但是它需要预先知道进程未来所有的页面调度情况，这在实际应用中是不可行的。

2.2先进先出(FIFO)置换算法先进先出置换算法是一种很简单的置换算法，它选取主存中驻留时间最长的页面作为替换目标。

优点是实现简单，但是缺点是可能会引发置换震荡问题。

2.3最近最久未使用算法(LRU)最近最久未使用算法是一种比较常用的页面置换算法，其核心思想是将驻留时间久且最近一次使用时间早的页面视为需要置换的页面。

相对于FIFO算法，LRU算法能够保证更高的页面命中率和更小的置换次数。

2.4时钟置换算法(Clock)时钟置换算法是一种改进型的FIFO算法。

该算法使用一个环形队列来存储主存中的页面位置信息。

当需要置换页面时，指针先指向队列首位置，遍历队列并且在第一遍扫描时，将页框的访问位ACC设置为0。

第一遍扫描结束后，如果有页面的ACC位为0，就将其替换出去。

如果找不到未访问页面，指针再回到队列首位置，以此类推，直到找到为止。

3.总结以上所述的几种页面置换算法是操作系统中常见的算法。

它们各有优点和缺点，在实际应用中，需要根据实际情况进行选择。

在选择算法后，还需要对其进行适当的调整，以满足实际需求。

时钟(CLOCK)置换算法L RU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。

所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。

简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。

当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。

对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。

当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。

当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。

每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。

由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。

CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得CLOCK算法更加高效。

在使用位的基础上再增加一个修改位，则得到改进型的CLOCK置换算法。

这样，每一帧都处于以下四种情况之一：1.最近未被访问，也未被修改(u=0, m=0)。

2.最近被访问，但未被修改(u=1, m=0)。

3.最近未被访问，但被修改(u=0, m=1)。

4.最近被访问，被修改(u=1, m=1)。

算法执行如下操作步骤：1.从指针的当前位置开始，扫描帧缓冲区。

在这次扫描过程中，对使用位不做任何修改。

选择遇到的第一个帧(u=0, m=0)用于替换。

2.如果第1)步失败，则重新扫描，查找(u=0, m=1)的帧。

选择遇到的第一个这样的帧用于替换。

在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。

一、实验目的通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

二、实验内容基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。

1、最佳淘汰算法（OPT）2、先进先出的算法（FIFO）3、最近最久未使用算法（LRU）4、简单时钟(钟表)算法（CLOCK）命中率＝１－页面失效次数／页地址流(序列)长度三、实验原理UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。

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

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

为实现请求调页，核心配置了四种数据结构：页表、页帧（框）号、访问位、修改位、有效位、保护位等。

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

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

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

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

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

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

四、算法描述本实验的程序设计基本上按照实验内容进行。

即使用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。

（1）通过随机数产生一个指令序列，共320条指令。

指令的地址按下述原则生成：A：50%的指令是顺序执行的B：25%的指令是均匀分布在前地址部分C：25%的指令是均匀分布在后地址部分具体的实施方法是：A：在[0，319]的指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1的指令C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’D：顺序执行一条指令，其地址为m’+1E：在后地址[m’+2，319]中随机选取一条指令并执行F：重复步骤A-E，直到320次指令（2）将指令序列变换为页地址流设：页面大小为1K；用户内存（页帧）容量为4页~32页；用户虚存容量为32K。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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