操作系统实验报告6-页面置换算法模拟

实验编号４名称页面置换算法模拟实验目的通过请求页式存储管理中页面置换算法模拟设计，以便：1、了解虚拟存储技术的特点2、掌握请求页式存储管理中页面置换算法实验内容与步骤设计一个虚拟存储区和内存工作区，并使用FIFO和LRU算法计算访问命中率。

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

<程序1>#include <windows.h> //Windows版，随机函数需要，GetCurrentProcessId()需要//#include <stdlib.h>//Linux版，随机函数srand和rand需要#include <stdio.h> //printf()需要#define TRUE 1#define FALSE 0#define INV ALID -1#define NULL 0#define total_instruction 320 //共320条指令#define total_vp 32 //虚存页共32页#define clear_period 50 //访问次数清零周期typedef struct{//定义页表结构类型〔页面映射表PMT〕int pn, pfn, counter, time;//页号、页框号(块号)、一个周期内访问该页面的次数、访问时间}PMT;PMT pmt[32];typedef struct pfc_struct{//页面控制结构int pn, pfn;struct pfc_struct *next;}pfc_type;pfc_type pfc[32];pfc_type *freepf_head,*busypf_head,*busypf_tail;//空闲页头指针，忙页头指针，忙页尾指针int NoPageCount; //缺页次数int a[total_instruction];//指令流数组int page[total_instruction], offset[total_instruction];//每条指令的页和页内偏移void initialize( int );void FIFO( int );//先进先出void LRU( int );//最近最久未使用void NRU( int );//最近最不经常使用/****************************************************************************main()*****************************************************************************/ void main(){int i,s;//srand(10*getpid());//用进程号作为初始化随机数队列的种子//Linux版srand(10*GetCurrentProcessId());//用进程号作为初始化随机数的种子//Windows版s=rand()%320;//在[0，319]的指令地址之间随机选取一起点mfor(i=0;i<total_instruction;i+=4){//产生指令队列if(s<0||s>319){printf("when i==%d,error,s==%d\n",i,s);exit(0);}a[i]=s;//任意选一指令访问点m。

操作系统课程设计报告题目：页面置换算法模拟程序设计专业：软件工程院系：信息管理学院目录第一部分概述第二部分设计的基本概念和原理第三部分总体设计3.1算法流程图3.2算法的简要实现方法3.2.1 OPT页面置换算法3.2.2 FIFO页面置换算法3.2.3 LRU页面置换算法3.2.4 LFU页面置换算法第四部分详细设计4.1 main函数4.2 OPT函数4.2 FIFO函数4.3 LRU函数4.5 LFU函数4.6辅助函数4.6.1 Designer函数4.6.2 mDelay函数4.6.3 Download函数4.6.4 Compute函数4.6.5 showTable函数第五部分实现源代码第六部分简要的使用说明及主要运行界面第七部分总结第八部分参考文献第一部分概述设计任务：页面置换算法是虚拟存储管理实现的关键，通过本次课程设计理解内存页面调度的机制，在模拟实现OPT、FIFO、LRU和LFU几种经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。

第二部分设计的基本概念和原理(1)．页面淘汰机制页面淘汰又称为页面置换。

若请求调页程序要调进一个页面，而此时该作业所分得的主存块已全部用完，则必须淘汰该作业已在主存中的一个页。

这时，就产生了在诸页面中淘汰哪个页面的问题，这就是淘汰算法（或称为置换算法）。

置换算法可描述为，当要索取一个页面并送入主存时，必须将该作业已在主存中的某一页面淘汰掉，用来选择淘汰哪一页的规则就叫做置换算法。

(2)．各种页面置换算法的实现思想OPT算法是当要调入一新页而必须先淘汰一旧业时，所淘汰的那一页应是以后不要再用的或是以后很长时间才会用到的页。

FIFO算法的实质是，总是选择在主存中居留时间最长（即最老）的一页淘汰。

其理由是最先调入主存的页面，其不再被使用的可能性比最近调入主存的页的可能性大。

LRU算法的实质是，当需要置换一页时，选择最长时间未被使用的那一页淘汰。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二、实验内容模拟实现各种页面置换算法。

具体步骤为：1. 使用产生随机数函数得到一个随机的数列，作为将要载入的页面序列。

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

3. 列出缺页中断次数。

三、实验源程序/* 程序说明：本程序假设内存为程序分配的内存块数为4。

*//* 进入程序后可以根据菜单项进入不同的模块 *//* 1.使用首次适应算法分配空间 *//* 2.最近最久未使用的页面 *//* 3.使用最佳适应算法分配空间 *//* 4.显示有多少个缺页中断 *//* 5.推出系统 */#include<stdio.h>#include<stdlib.h>#include<time.h>#define N 39 /* 随机数序列的长度*/#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);}/函数名：main（）/main(){ int list[N];int buf[B],f[B],i,j,k,max,min;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]);}/显示FIFO淘汰页面的序列/printf(“\nFIFO:\n”);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++;}elseprintf(“”);}/显示有多少个缺页中断/printf(“\nchanges:%d\n”,change);/显示LRU淘汰页面的序列/printf(“LRU :\n”);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(“\nchanges:%d\n”,change);/显示OPT淘汰页面的序列/printf(“OPT :\n”);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{ printf(“”);}}/显示有多少个缺页中断/printf(“\nchanges:%d\n”,change);}说明：多次运行结果并不相同，分析一下原因。

计算机科学系实验报告书课程名：《操作系统》题目：虚拟存储器管理页面置换算法模拟实验班级：学号：姓名：一、实验目的与要求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值，表示该虚页的最后一次被访问时间。

操作系统实验报告_页面置换算法模拟学生实验报告姓名: 年级专业班级学号成绩验证设计实验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算法。

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

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

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

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

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

常见的页面置换算法有先进先出（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）最佳置换算法需要预测未来的页面访问情况，因此需要遍历整个页面访问序列，找到最长时间内不会被访问的页面。

页面置换算法实验报告背景页面置换算法是计算机操作系统中的一个重要概念，它用于解决操作系统需要共享有限的物理内存资源给多个进程使用的问题。

在操作系统中，每个进程都有自己的虚拟地址空间，但实际的物理内存资源是有限的。

当物理内存不足时，操作系统需要根据一定的策略将一部分进程暂时从内存中移出，以便为其他进程让出空间，而后再从外存中将其重新加载到内存中。

这个过程就是页面置换。

页面置换算法有很多种，比如最优页面置换算法（Optimal）、先进先出页面置换算法（FIFO）、最近最久未使用页面置换算法（LRU）等等。

不同的算法对于系统性能、响应时间等指标有着不同的影响，因此在实际应用中需要选择合适的算法来平衡各种需求。

本实验旨在通过模拟页面置换算法，并对不同算法进行性能分析，以便了解各种算法的优缺点，为实际系统的选择提供依据。

分析在实验中，我们选择了三种常用的页面置换算法，分别是FIFO、LRU和Optimal。

下面对这三种算法进行详细的分析和说明。

先进先出页面置换算法（FIFO）FIFO算法是最简单和最直观的页面置换算法。

它按照页面进入内存的顺序来选择被淘汰的页面。

当内存不足时，选择最早进入内存的页面进行置换，即将其从内存中移出。

FIFO算法不需要进行进一步的页面访问计算，只需要维护一个页面进入内存的队列即可，因此实现起来比较简单。

然而，由于FIFO算法没有考虑页面的访问频率和重要性，所以可能会导致被频繁访问的页面被淘汰出内存，从而影响系统的性能。

最近最久未使用页面置换算法（LRU）LRU算法是一种基于”最近使用原则”的页面置换算法。

它根据页面最近被访问的时间来选择被淘汰的页面。

当内存不足时，选择最长时间未被访问的页面进行置换，即将其从内存中移出。

LRU算法需要维护一个页面访问时间的记录，以便在需要置换时能够快速找到最近最久未使用的页面。

相比于FIFO算法，LRU算法更加合理地利用了页面的访问情况，但实现起来相对复杂一些。