下载文档原格式
【精品】页面置换算法实验报告一、实验目的了解操作系统中的页面置换算法，并实现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.要求：本实验要求使用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值，表示该虚页的最后一次被访问时间。
实验编号４名称页面置换算法模拟实验目的通过请求页式存储管理中页面置换算法模拟设计，以便：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.通过编程实现请求分页存储管理系统的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）OPT 算法RLU算法C++三、前言实验目的1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。
2、掌握用随机数生成满足一定条件的指令地址流的方法。
3、掌握页面置换的模拟方法。
实验要求与内容1、采用一种熟悉的语言，如C、PASCAL 或C++等，编制程序，最好关键代码采用C/C++，界面设计可采用其它自己喜欢的语言。
2、模拟操作系统采用OPT、FIFO 和LRU 算法进行页面置换的过程。
3、设程序中地址范围为0 到32767，采用随机数生成256 个指令地址，满足50%的地址是顺序执行，25%向前跳，25%向后跳。
为满足上述条件，可采取下列方法：设d0=10000，第n个指令地址为dn，第n+1 个指令地址为dn+1，n的取值范围为0 到255。
每次生成一个1 到1024 范围内的随机数a，如果a落在1 到512 范围内，则dn+1=dn+1。
如果a落在513 到768范围内，则设置dn+1为1 到dn范围内一个随机数。
如果a落在769 到1024范围内，则设置dn+1为dn到32767 范围内一个随机数。
例如：srand();初始化一个随机函数。
a[0]＝10*rand()/32767*255+1;a[1]=10*rand()/32767*a[0]…语句可用来产生a[0]与a[1]中的随机数。
或采用以下方式：（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.程序的执行结果如下：(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 年月日【备注】。
目录一、摘要 (3)二、正文 (4)三、设计总结 (8)四、参考文献 (10)五、附录：源程序代码 (11)摘要Windows中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。
当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺页中断），由系统将其所需页面调入内存。
这种页面调入方式叫请求调页，为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。
此设计为了了解Windows XP的操作接口及系统调用方式，熟悉Windows XP常用操作的实现过程，练习并掌握Visual C++开发环境。
利用Windows SDK（System Development Kit）提供的API（应用程序接口）设计一个虚拟存储管理程序，并使用最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。
（命中率＝１－页面失效次数／页地址流长度）。
关键字Windows；请求调页；数据结构；存储管理正文一、设计思路页面置换算法：当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。
该程序通过查找页表，得到该页所在外存的物理块号。
如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。
如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。
利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。
整个页面的调入过程对用户是透明的。
此设计为了了解Windows XP的操作接口及系统调用方式，熟悉Windows XP常用操作的实现过程，练习并掌握Visual C++开发环境。
利用Windows SDK（System Development Kit）提供的API（应用程序接口）设计一个虚拟存储管理程序，并使用最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。
页面置换算法实验报告一、实验目的本次实验的目的是通过模拟页面置换算法的过程，了解不同算法的优缺点，掌握算法的实现方法，以及对算法的性能进行评估。
二、实验原理页面置换算法是操作系统中的一个重要概念，它是为了解决内存不足的问题而产生的。
当系统中的进程需要使用内存时，如果内存已经被占满，就需要将一些页面从内存中置换出去，以便为新的页面腾出空间。
页面置换算法就是用来决定哪些页面应该被置换出去的算法。
常见的页面置换算法有以下几种：1. 最佳置换算法（OPT）最佳置换算法是一种理论上的最优算法，它总是选择最长时间内不会被访问的页面进行置换。
但是，由于无法预测未来的页面访问情况，因此最佳置换算法无法在实际中使用。
2. 先进先出置换算法（FIFO）先进先出置换算法是一种简单的置换算法，它总是选择最先进入内存的页面进行置换。
但是，这种算法容易出现“抖动”现象，即频繁地将页面置换出去，然后再将其置换回来。
3. 最近最久未使用置换算法（LRU）最近最久未使用置换算法是一种比较常用的置换算法，它总是选择最长时间未被访问的页面进行置换。
这种算法可以避免“抖动”现象，但是实现起来比较复杂。
4. 时钟置换算法（Clock）时钟置换算法是一种改进的FIFO算法，它通过维护一个环形链表来实现页面置换。
当需要置换页面时，算法会从当前位置开始扫描链表，如果找到一个未被访问的页面，则将其置换出去。
如果扫描一圈后都没有找到未被访问的页面，则将当前位置的页面置换出去。
三、实验过程本次实验使用Python语言编写了一个页面置换算法模拟程序，可以模拟上述四种算法的过程，并输出算法的性能指标。
程序的主要流程如下：1. 读取输入文件，获取页面访问序列和内存大小等参数。
2. 根据选择的算法，初始化相应的数据结构。
3. 遍历页面访问序列，模拟页面置换的过程。
4. 输出算法的性能指标，包括缺页率、页面置换次数等。
下面分别介绍四种算法的实现方法。
1. 最佳置换算法（OPT）最佳置换算法需要预测未来的页面访问情况，因此需要遍历整个页面访问序列，找到最长时间内不会被访问的页面。
页面置换算法实验报告一、实验目得:设计与实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改进型Cｌock置换算法;通过支持页面访问序列随机发生实现有关算法得测试及性能比较、二、实验内容:●虚拟内存页面总数为N,页号从0到N—1●物理内存由M个物理块组成●页面访问序列串就是一个整数序列,整数得取值范围为0到N - １、页面访问序列串中得每个元素p表示对页面p得一次访问●页表用整数数组或结构数组来表示❑符合局部访问特性得随机生成算法1.确定虚拟内存得尺寸Ｎ,工作集得起始位置p,工作集中包含得页数e,工作集移动率ｍ(每处理m个页面访问则将起始位置p ＋1),以及一个范围在0与１之间得值t;2.生成ｍ个取值范围在p与ｐ+ e间得随机数,并记录到页面访问序列串中;3.生成一个随机数r,0 ≤r ≤1;4.如果r〈t,则为p生成一个新值,否则p = (p＋１) mod N;5.如果想继续加大页面访问序列串得长度,请返回第2步,否则结束。
三、实验环境:操作系统:Wiｎｄows7软件: ＶＣ++6.0四、实验设计:本实验包含六种算法,基本内容相差不太,在实现方面并没有用统一得数据结构实现,而就是根据不同算法得特点用不同得数据结构来实现:1、最佳置换与随机置换所需操作不多,用整数数组模拟内存实现;2、先进先出置换与最近最久未使用置换具有队列得特性,故用队列模拟内存来实现;3、CLOCK置换与改进得CＬOＣＫ置换具有循环队列得特性,故用循环队列模拟内存实现;4、所有算法都就是采用整数数组来模拟页面访问序列。
五、数据结构设计:／/页面访问序列数组:ｉnｔｒeｆ［ref_sｉze];//内存数组:iｎt pｈy［phy_size］;//队列数据结构定义:tｙpeｄef sｔrｕｃt QＮoｄeﻩ//定义队列数据结构｛ﻩint daｔa;struct QNｏde *ｎext;}QNodｅ,*ＱueuePtr;ｔypedｅｆstrｕct{QuｅuｅPtr ｆrｏnt;ﻩ／/头指针ﻩQuｅuｅPtr reaｒ;ﻩ//尾指针｝LinkQuｅuｅ;/／定义链表数据结构typedeｆstruct LNoｄｅ//定义循环链表数据结构｛iｎt data;iｎt flag;ﻩ//访问位int modｉfy;ﻩﻩ//修改位ﻩstｒuct LNodｅ＊ｎext;}LNｏde,＊LinｋLｉst;六、主要函数说明:1、voｉd seｔ_rａｎｄ_num()ﻩ//产生具有局部特性得随机数列;2、int Exchange_ＬNoｄｅ(LｉnkLisｔ&L,inｔe,iｎt i)//将链表Ｌ中序号为i得结点替换为内容为e得结点;3、ｂool Sｅａrch_ＬiｎkLisｔ(LinｋＬｉst＆L,ｉnt e,ｉnｔ&i)／／找到链表Ｌ中内容为ｅ得结点,并用i返回其位置,i=1表示第一个非头结点,依次类推;4、void Ｓeａrch_ＬＬ_Flａg(LiｎkLisｔ＆Ｌ,iｎt ＆i)//用i返回第一个flag为0得结点得位置,i＝1表示第一个非头结点,以此类推;5、voｉd Ｓeｔ_LL＿Ｆlag(LinkLｉsｔ&L,int i) //设置链表Ｌ中得序号为ｉ得结点得ｆlaｇ标志为1;6、iｎtＳｅarch_ＬL＿ModifyClock(LinkLｉst ＆L,ｉnt&moｄｉｆy_ｎｕm)／/找到改进得CLOＣＫ算法所需要淘汰得页,用ｍodｉfｙ_nｕm返回其位置;此函数根据书上给得思路,第一遍扫描Ａ=０且M=０得页面予以淘汰,若失败,则进行第二轮扫描A=０且M=１得页面,第二轮扫描时将所有访问过得页面得访问位Ａ置0;若失败则重复上述两部;7、voｉd Sｅｔ＿LL_moｄｉfy(ＬｉｎｋLｉst＆L,int i) //设置链表L中得序号为i得结点得ｍodiｆy标志为1;8、booｌSearｃhQuｅｕe(LｉnｋQuｅｕe ＆Q,iｎｔe,int ＆ｉ)ﻩ//寻找队列Ｑ中结点data域等于ｅ得结点,并用i返回其在Q中得位置;9、ｉnt getnum(iｎt a,intｂ)ﻩﻩ//用ｂ返回元素ａ在被引用数列中得下一个位置10、voｉd ORA() ／/实现最佳置换算法,包括判断页面就是否在内存中、页面进内存、输出内存状态等内容;11、ｖoid RＡＮD() ﻩ／/随机置换算法12、void FＩＦO() ﻩﻩﻩ//先进先出算法1３、voiｄLRＵ() ﻩﻩ//最近最久未使用算法实现最近最久未使用算法得思想就是:判断待进入内存得页面,如果与内存中得第一个页面相同,则将它移到最后一个,即标志为最近使用得页;如果与内存中得第二个页面相同,则将它删除,并在队列尾部添加相同元素,即标志为最近使用得页;ﻩ１４、vｏid CＬOＣK()ﻩﻩ／／实现CLOＣK算法1５、ｖoid Ｍｏdifiｅｄ_Ｃlock() ／/实现改进得CLOCK算法16、inｔｍain() ／/主函数,调用实现各算法得６个主要函数,并输出各算法得缺页率。
