页面置换算法模拟实验报告

实验5 页面置换算法模拟实验一．实验目的1.进一步掌握虚拟存储器的实现方法。

2.掌握各种页面置换算法。

3.比较各种页面置换算法的优缺点。

二．实验内容模拟实现页面置换算法，步骤为：①使用产生随机数函数得到一个随机的数列，作为将要载入的页面序列。

②使用先进先出（FIFO）算法、最近最久未使用（LRU）置换算法和最佳（OPT）置换算法，列出所需淘汰的页面号序列。

③列出缺页中断次数。

三．参考源程序如下：#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 10#define B 4/*------------------------------------------------------------------------函数名：IsInBuf()，返回某个数X在不在缓冲Buf[],如在，返回位置，否则返回－1--------------------------------------------------------------------------*/int IsInBuf(int buf[],int x){int i,j=-1;for(i=0;i<B;i++){if(buf[i]==x){ j=i;break; }else if(buf[i]==-1){ buf[i]=x;j=i;break; } }return j;}/*------------------------------------------------------------------------函数名：oldest()，返回最近最久未使用的页面位置--------------------------------------------------------------------------*/int oldest(int f[]){int i,j=0,max=-1;for(i=0;i<B;i++){if(f[i]>max){ max=f[i]; j=i; }f[i]++; }return j;}/*------------------------------------------------------------------------函数名：oldest2()，返回未来最久未使用的页面位置--------------------------------------------------------------------------*/int oldest2(int list[],int buf[],int f[],int start){int i,j;for(i=0;i<B;i++){for(j=start;j<N;j++){ if(buf[i]==list[j]) break; }f[i]=j; }return oldest(f);}int main(void){int list[N];int buf[B],f[B],i,j ;int old=0;int change=0;srand((int)time(NULL)); /*生成一系列随机数并初始化环境*/for(i=0;i<B;i++) {buf[i]=f[i]=-1;}printf("\nThe Random List:\n");for(i=0;i<N;i++){ list[i]=(int)rand()%10; printf("%2d",list[i]); } printf("\nFIFO\n");/*显示FIFO淘汰的页面序列*/change=0;for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){printf("%2d",buf[old]);buf[old]=list[i];old=(old+1)%(int)B;change++;}else printf(" "); }printf("\n changes %2d\n",change); /*显示有多少个缺页中断*/printf("\nLRU\n");/*显示LRU淘汰的页面序列*/change=0;for(i=0;i<B;i++) {buf[i]=f[i]=-1;}for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);old=oldest(f);if(j==-1){printf("%2d",buf[old]);buf[old]=list[i];f[old]=0;change++;}else{ f[j]=0; printf(" "); } }printf("\n changes %2d\n",change); /*显示有多少个缺页中断*/printf("\nOPT\n");/*显示OPT淘汰的页面序列*/change=0;for(i=0;i<B;i++) {buf[i]=f[i]=-1;}for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){old=oldest2(list,buf,f,i);printf("%2d",buf[old]);buf[old]=list[i];f[old]=0;change++; }else{ f[j]=0; printf(" "); } }printf("\n changes %2d\n",change); /*显示有多少个缺页中断*/ getch();return 0; }（假设当前随机产生的页面序列为：7 1 0 4 2 5 8 6 9 1)四.填表题(1).在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为4时，试计算采用先进先出淘汰算法时的缺页率(假设开始执行时主存中没有页面)，并将所得结果填表。

页面置换算法实验报告院系:****************学院班级:***********姓名:***学号:************一、实验题目: 页面置换算法二. 实验目的：1.用C语言编写OPT、FIFO、LRU三种置换算法。

2.熟悉内存分页管理策略。

3.了解页面置换的算法。

4.掌握一般常用的调度算法。

5.根据方案使算法得以模拟实现。

6.锻炼知识的运用能力和实践能力。

三. 实验内容及要求:设计一个虚拟存储区和内存工作区, 编程序演示下述算法的具体实现过程, 并计算访问命中率:要求设计主界面以灵活选择某算法, 且以下算法都要实现1) 最佳置换算法(OPT): 将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。

2) 先进先出算法(FIFO)：淘汰最先进入内存的页面, 即选择在内存中驻留时间最久的页面予以淘汰。

3) 最近最久未使用算法(LRU): 淘汰最近最久未被使用的页面。

四、实验结果初始化结果1, 先进先出（FIFO）算法实验结果:2, 最近最久未使用（LRU）算法实验结果: 3, 最佳使用法（OPT）实验结果:五、实验总结选择置换算法, 先输入所有页面号, 为系统分配物理块, 依次进行置换:OPT基本思想:是用一维数组page[]存储页面号序列, memery[]是存储装入物理块中的页面。

数组next[]记录物理块中对应页面的最后访问时间。

每当发生缺页时, 就从物理块中找出最后访问时间最大的页面, 调出该页, 换入所缺的页面。

若物理块中的页面都不再使用, 则每次都置换物理块中第一个位置的页面。

FIFO基本思想:是用队列存储内存中的页面, 队列的特点是先进先出, 与该算法是一致的, 所以每当发生缺页时, 就从队头删除一页, 而从队尾加入缺页。

或者借助辅助数组time[]记录物理块中对应页面的进入时间, 每次需要置换时换出进入时间最小的页面。

LRU基本思想:是用一维数组page[]存储页面号序列, memery[]是存储装入物理块中的页面。

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

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

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

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

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

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

实验报告实验2 页面置换算法实现一、实验目的通过页面置换算法的程序实现，加深理解。

二、设计内容（1）概述在进程运行过程中，若其所要访问的页面不在内存所需把他们调入内存，但内存已无空闲时，为了保证进程能够正常运行，系统必须从内存中调入一页程序或数据送磁盘的对换区中。

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

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

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

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

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

目前存在着不同的算法，他们都试图更接近与理论上的目标。

拥有页面交换机制的操作系统总是把当前进程中急需处理的部分页面换入到内存当中，而把更多暂时不需要处理的页面放置在外存当中。

由于进程需要处理的页面顺序不同，因此必须要在内存与外存之间进行页面交换，页面置换算法也就应运而生。

（2）设计原理1.先进先出（FIFO）算法这是最早出现的置换算法。

该算法总是淘汰最先进入内存的页面，即选择在内存停留时间最久的给予淘汰。

该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替代指针，使它总是指向最老的页面。

但该算法与进程实际运行的规律不相适应，因为在incheng 中，有些页面经常被访问，比如，含有全局变量，常用函数，例程等方面，FIFO 算法并不能保证这些页面不被淘汰。

当需要选择一个页面淘汰时，总是选择最先进入内存空间的那一个页面。

只要在系统中建立一个FIFO队列，以反映页面的活动情况。

被选择的页面总是处于队首的页面，而最近调入的页面永远存放在队列的尾部。

2.最近最久未使用（LRU）算法FIFO置换算法的性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后不能反映页面的使用情况。

最近最久未使用（LRU）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。

页面置换算法的模拟实现及命中率对比实验报告一、问题描述课程设计目的（1）、通过请求页式管理方式中页面置换算法的模拟设计，了解虚拟存储术的特点，掌握请求页式存储管理中的页面置换算法。

（2）、课程设计内容模拟实现OPT（最佳置换）、FIFO和LRU算法，并计算命中率。

（3）、课程设计要求：a)首先用随机数生成函数产生“指令”序列，然后将指令序列变换成相应的页地址流，再计算不同算法下的命中率。

b)通过随机数产生一个指令序列，共产生400条。

其中50%的指令是顺序执行的（灵位50%就是非顺序），且25%的指令分布在前半部分地址空间，25%的指令分布在后半部分地址空间。

c)将指令地址流变换成页地址流d)循环运行，使用户内存容量从4到40,。

计算每个内存容量下不同页面置换算法的命中率。

二、概要设计1.程序的数据结构：#define total_instruction 100 /*指令流长*/#define M 100 /*实际页数*/#define N 5 //可用页面数struct Pro{int num,time;};int a[total_instruction];int page[N];2.程序的主函数：int main(){Pro p[total_instruction];Pro *page=new Pro[N];char c;int t=0,i;float n=0;Input(p);do{for( i=0;i<N;i++)//初试化页面基本情况{page[i].num=-1;page[i].time=2-i;}printf("系统产生的随机数为：");for(int e=0;e<M;e++)cout<<p[e].num<<" ";cout<<endl;i=0;cout<<"f:FIFO页面置换"<<endl;cout<<"l:LRU页面置换"<<endl;cout<<"o:OPT页面置换"<<endl;cout<<"按其它键结束"<<endl;cin>>c;if(c=='f')//FIFO页面置换{n=0;cout<<"页面置换情况: "<<endl;while( i< total_instruction){if(Search(p[i].num,page)>=0)i++;//找到相同的页面else{if(t==N)t=0;else{n++;//page[t].num=p[i].num;print(page);t++;}}}cout<<"缺页次数："<<n<<" 命中率："<<1-n/total_instruction<<endl; }if(c=='l')//LRU页面置换{n=0;cout<<"页面置换情况: "<<endl;while(i<total_instruction){int k;k=t=Search(p[i].num,page);if(t>=0)page[t].time=0;else{n++;t=Max(page);page[t].num=p[i].num;page[t].time=0;}for(int j=0;j<N;j++){if(j!=t)page[j].time++;}/*if(t==0){page[t+1].time++;page[t+2].time++;}if(t==1){page[2].time++;page[0].time++;}if(t==2){page[1].time++;page[0].time++;}*/if(k==-1) print(page);i++;}cout<<"缺页次数："<<n<<" 命中率："<<1-n/total_instruction<<endl; }if(c=='o')//OPT页面置换{n=0;while(i<total_instruction){if(Search(p[i].num,page)>=0)i++;else{if(page[N-1].num==-1){for(int g=0;g<N;g++)if(page[g].num==-1){page[g].num=p[i].num;i++;n++;print(page);break;}}else{int temp=-1,cn;for(t=0;t<N;t++){if(temp<Compfu(page,i,t,p)){temp=Compfu(page,i,t,p);cn=t;}}page[cn]=p[i];n++;print(page);i++;}}}cout<<"缺页次数："<<n<<" 命中率："<<1-n/total_instruction<<endl;}}while(c=='f'||c=='l'||c=='o');return 0;}三、详细设计程序代码如下：#include<stdlib.h>#include<iostream>#include<time.h>#include<stdio.h>using namespace std;#define total_instruction 100 /*指令流长*/#define M 100 /*实际页数*/#define N 5 //可用页面数struct Pro{int num,time;};int a[total_instruction];int page[N];void Input(Pro p[total_instruction]){int m,i,m1,m2;srand( (unsigned int )time(NULL));m=rand( )%400; //for(i=0;i<total_instruction;) /*产生指令队列*/{if(m<0||m>399){printf("When i==%d,Error,m==%d\n",i,m);exit(0);}a[i]=m; /*任选一指令访问点m*/ a[i+1]=a[i]+1;a[i+2]=a[i]+2; /*顺序执行两条指令*/int m1=rand( )%m; /*执行前地址指令m1 */a[i+3]=m1;a[i+4]=m1+1;a[i+5]=m1 + 2;/*顺序执行两条指令*/// s=(158-a[i+5])*rand( )/32767/32767/2+a[i+5]+2;m2 = rand()%(157-m1)+m1+3;a[i+6]=m2;if( (m2+2) > 159 ){a[i+7] = m2+1;i +=8;}else{a[i+7] = m2+1;a[i+8] = m2+2;i = i+9;}m = rand()%m2;}for (i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/ {p[i].num=a[i]/10;p[i].time = 0;}}void print(Pro *page1)//打印当前的页面{Pro *page=new Pro[N];page=page1;for(int i=0;i<N;i++)printf("%-4d",page[i].num);//cout<<page[i].num<<" ";cout<<endl;//free(page);}int Search(int e,Pro *page1 ){Pro *page=new Pro[N];page=page1;for(int i=0;i<N;i++)if(e==page[i].num)return i;return -1;}int Max(Pro *page1){Pro *page=new Pro[N];page=page1;int e=page[0].time,i=0;while(i<N)//找出离现在时间最长的页面{if(e<page[i].time)e=page[i].time;i++;}for( i=0;i<N;i++)if(e==page[i].time)return i;return -1;}int Compfu(Pro *page1,int i,int t,Pro p[M]){Pro *page=new Pro[N];page=page1;int count=0;for(int j=i;j<M;j++){if(page[t].num==p[j].num )break;else count++;}return count;}int main(){Pro p[total_instruction];Pro *page=new Pro[N];char c;int t=0,i;float n=0;Input(p);do{for( i=0;i<N;i++)//初试化页面基本情况{page[i].num=-1;page[i].time=2-i;}printf("系统产生的随机数为：");for(int e=0;e<M;e++)cout<<p[e].num<<" ";cout<<endl;i=0;cout<<"f:FIFO页面置换"<<endl; cout<<"l:LRU页面置换"<<endl;cout<<"o:OPT页面置换"<<endl;cout<<"按其它键结束"<<endl; cin>>c;if(c=='f')//FIFO页面置换{n=0;cout<<"页面置换情况: "<<endl;while( i< total_instruction){if(Search(p[i].num,page)>=0)i++;//找到相同的页面else{if(t==N)t=0;else{n++;//page[t].num=p[i].num;print(page);t++;}}}cout<<"缺页次数："<<n<<" 命中率："<<1-n/total_instruction<<endl”}if(c=='l')//LRU页面置换{n=0;cout<<"页面置换情况: "<<endl;while(i<total_instruction){int k;k=t=Search(p[i].num,page);if(t>=0)page[t].time=0;else{n++;t=Max(page);page[t].num=p[i].num;page[t].time=0;}for(int j=0;j<N;j++){if(j!=t)page[j].time++;}/*if(t==0){page[t+1].time++;page[t+2].time++;}if(t==1){page[2].time++;page[0].time++;}if(t==2){page[1].time++;page[0].time++;}*/if(k==-1) print(page);i++;}cout<<"缺页次数："<<n<<" 命中率："<<1-n/total_instruction<<endl;}if(c=='o')//OPT页面置换{n=0;while(i<total_instruction){if(Search(p[i].num,page)>=0)i++;else{if(page[N-1].num==-1){for(int g=0;g<N;g++)if(page[g].num==-1){page[g].num=p[i].num;i++;n++;print(page);break;}}else{int temp=-1,cn;for(t=0;t<N;t++){if(temp<Compfu(page,i,t,p)){temp=Compfu(page,i,t,p);cn=t;}}page[cn]=p[i];n++;print(page);i++;}}}cout<<"缺页次数："<<n<<" 命中率："<<1-n/total_instruction<<endl; }}while(c=='f'||c=='l'||c=='o');return 0;}四、调试与分析程序的主界面：这里测试用的数据是M=40，N=5，三种算法置换结果如以下的图：FIFO算法：LRU算法：OPT算法：多运行几次，产生不同的随机数组，查看对比结果。

【精品】页面置换算法实验报告一、实验目的了解操作系统中的页面置换算法，并实现FIFO、LRU和Clock算法。

二、实验原理页面置换算法是操作系统中用到的一种算法，其作用是在内存不够用时，选择牺牲已经在内存中的一些页，腾出更多的空间给新的内容。

本次实验主要实现了FIFO、LRU和Clock算法。

1、FIFO算法FIFO算法是最简单的页面置换算法，它采用先进先出的原则，即最先进入内存的页面应该最早被替换出去。

该算法的实现非常简单，只需要维护一个队列即可。

当需要置换页面时，选择队列的第一个页面进行替换即可。

2、LRU算法LRU算法是Least Recently Used的缩写，即最近最少使用算法。

该算法的核心思想是选择最久没有被使用的页面进行替换。

为了实现该算法，需要维护记录页面使用时间的链表、栈或队列等结构。

3、Clock算法Clock算法也叫做二次机会算法，是一种改良的FIFO算法。

它是基于FIFO算法的思想，并且每个页面都设置了一个使用位（use bit），用于记录该页面是否被使用过。

当需要置换一个页面时，检查该页面的使用位，如果该页面的使用位为1，则将该页面的使用位设置为0并移到队列的末尾，表示该页面有“二次机会”继续待在内存中；如果该页面的使用位为0，则选择该页面进行替换。

三、实验过程本次实验采用Python语言实现页面置换算法，并使用样例进行测试。

1、FIFO算法实现FIFO算法的实现非常简单，只需要用一个队列来维护已经在内存中的页面，当需要置换页面时，选择队列的第一个元素即可。

代码如下：```pythonfrom collections import dequeclass FIFO:def __init__(self, frame_num):self.frame_num = frame_numself.frames = deque(maxlen=frame_num)def access(self, page):if page in self.frames:return Falseif len(self.frames) >= self.frame_num:self.frames.popleft()self.frames.append(page)return True```2、LRU算法实现LRU算法的实现需要维护一个记录页面使用时间的链表或队列。

页面置换实习报告在计算机系统中，页面置换是一项至关重要的内存管理技术。

为了更深入地理解和掌握这一技术，我进行了相关的实习。

一、实习目的页面置换的目的在于当内存空间不足时，将一些暂时不使用的页面换出到外存，以腾出空间给当前需要的页面。

通过这次实习，我希望能够：1、深入理解页面置换算法的工作原理和特点。

2、掌握不同算法在实际应用中的性能差异。

3、提高自己的编程能力和问题解决能力。

二、实习环境本次实习使用的编程语言为 Python，开发环境为 PyCharm。

操作系统为 Windows 10。

三、页面置换算法简介1、先进先出（FIFO）算法FIFO 算法是最简单的页面置换算法之一。

它总是淘汰最先进入内存的页面。

这种算法实现简单，但可能会导致一些频繁使用的页面被过早置换出去。

2、最近最久未使用（LRU）算法LRU 算法根据页面最近的使用情况来决定置换。

即淘汰最长时间未被使用的页面。

该算法性能较好，但实现相对复杂，需要记录页面的使用时间。

3、最优置换（OPT）算法OPT 算法是一种理论上的最优算法，它淘汰未来最长时间内不会被使用的页面。

然而，由于在实际中无法准确预测未来的页面使用情况，所以该算法更多地用于理论分析。

四、实习过程1、算法实现首先，我使用 Python 实现了上述三种页面置换算法。

在实现过程中，我使用了数据结构来存储页面的相关信息，并通过模拟页面的调入和调出过程来计算缺页次数。

以 FIFO 算法为例，我使用一个队列来存储页面进入内存的顺序。

当需要置换页面时，将队首的页面淘汰。

2、性能测试为了比较不同算法的性能，我设计了一系列的测试用例。

测试用例包括不同的页面访问序列和不同的内存大小。

通过运行测试用例，我记录了每种算法在不同情况下的缺页次数。

3、结果分析对测试结果进行分析是实习的重要环节。

我发现，在不同的页面访问模式下，不同算法的表现差异较大。

例如，当页面访问序列具有局部性时，LRU 算法的表现通常优于FIFO 算法。

学生实验报告姓名：年级专业班级学号成绩【实验结果或总结】（对实验结果进行相应分析，或总结实验的心得体会，并提出实验的改进意见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 年月日【备注】。