操作系统最佳置换算法实验报告

实验三内存页面置换算法的设计实习内容设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换： 1. 先进先出的算法（FIFO）2. 最近最久未使用算法（LRU）3. 最佳置换算法（OPT）实习目的本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的技术特点，掌握请求页式存储管理的页面置换算法。

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

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

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

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

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

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

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

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

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

实习原理——算法思想：1．先进先出(FIFO)置换算法的思路该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

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

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

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

3.最佳（OPT）置换算法的思路其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。

第1篇一、实验目的1. 理解置换密码算法的基本原理和特点。

2. 掌握置换密码算法的实现方法。

3. 通过编程实践，加深对置换密码算法的理解。

二、实验原理置换密码算法是一种通过对明文进行字符或位顺序的重新排列来实现加密的算法。

其基本原理是将明文中的字符或位按照一定的规则重新排列，形成密文。

解密时，按照相同的规则将密文恢复为明文。

常见的置换密码算法有：1. 旋转密码（Caesar密码）：将明文中的每个字符按照密钥k向右或向左旋转k 个位置。

2. 列置换密码：将明文矩阵中的列按照密钥顺序进行置换。

3. 矩阵换位密码：将明文矩阵中的字符按照密钥顺序进行置换。

三、实验环境1. 操作系统：Windows 102. 编程语言：Python3.8.03. 开发环境：PyCharm四、实验步骤1. 旋转密码实现（1）定义密钥k，表示旋转的位数。

（2）定义明文字符串，将每个字符按照密钥k向右或向左旋转k个位置。

（3）输出密文。

2. 列置换密码实现（1）定义密钥，表示列的置换顺序。

（2）将明文矩阵中的列按照密钥顺序进行置换。

（3）输出密文。

3. 矩阵换位密码实现（1）定义密钥，表示矩阵的置换顺序。

（2）将明文矩阵中的字符按照密钥顺序进行置换。

（3）输出密文。

五、实验结果与分析1. 旋转密码实验结果明文：Hello, World!密钥：3密文：Khoor, Zruog分析：旋转密码将明文中的每个字符向右旋转3个位置，实现了加密。

2. 列置换密码实验结果明文：Hello, World!密钥：[2, 0, 3, 1]密文：oHlel, Wrold!分析：列置换密码将明文矩阵中的列按照密钥顺序进行置换，实现了加密。

3. 矩阵换位密码实验结果明文：Hello, World!密钥：[2, 0, 3, 1]密文：oHlel, Wrold!分析：矩阵换位密码与列置换密码类似，将明文矩阵中的字符按照密钥顺序进行置换，实现了加密。

六、实验总结通过本次实验，我们对置换密码算法有了更深入的了解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

置换算法实验报告置换算法实验报告一、引言计算机系统中的置换算法是一种重要的算法，它用于管理内存中的页面，以提高系统的性能和效率。

在本次实验中，我们将研究和比较三种常用的置换算法：先进先出（FIFO）、最近最久未使用（LRU）和时钟（Clock）算法。

通过对这些算法的实验和分析，我们将能够更好地理解它们的原理和特点。

二、实验目的1. 理解置换算法的原理和概念；2. 比较并分析FIFO、LRU和Clock算法的性能差异；3. 掌握如何根据实际情况选择最适合的置换算法。

三、实验过程1. 实验环境搭建我们使用了一台配置较高的计算机作为实验环境，确保能够准确测试和比较不同算法的性能。

在实验开始前，我们还对计算机进行了必要的优化和清理工作，以确保实验结果的准确性。

2. 实验设计我们编写了一个模拟程序，模拟了一个具有固定大小的内存空间和大量页面访问的场景。

在这个程序中，我们可以自定义页面的数量、访问序列和置换算法，以便进行实验和测试。

3. 实验步骤首先，我们使用FIFO算法进行了一次实验。

通过观察实验结果，我们发现FIFO算法在处理页面置换时，会将最早进入内存的页面替换出去。

这种算法的优点是简单易实现，但缺点是无法根据页面的访问频率进行调整，容易出现“抖动”现象。

接下来，我们使用LRU算法进行了一次实验。

LRU算法根据页面的最近访问时间来进行置换，即替换最长时间未被访问的页面。

通过实验结果，我们发现LRU算法相对于FIFO算法来说，能更好地适应页面访问的变化，减少了抖动现象的发生。

最后，我们使用了时钟算法进行实验。

时钟算法是一种综合了FIFO和LRU算法的置换算法，它通过设置一个时钟指针，按照页面的访问情况进行调整。

实验结果显示，时钟算法在减少抖动的同时，也能保持较好的性能表现。

四、实验结果分析通过对实验结果的比较和分析，我们可以得出以下结论：1. FIFO算法在处理页面置换时，简单高效，但容易出现抖动现象；2. LRU算法能更好地适应页面访问的变化，减少抖动现象的发生；3. 时钟算法综合了FIFO和LRU算法的优点，既能减少抖动，又能保持较好的性能表现。

页面置换算法实践报告页面置换算法（Page Replacement Algorithm）是操作系统中用于管理虚拟内存的重要算法之一。

其目的是在有限的物理内存空间中，将进程所需的页面加载到内存中，并根据一定的策略替换掉不再被使用的页面，以提高内存利用率和系统性能。

在本次实践报告中，我将重点介绍三种常见的页面置换算法：先进先出（FIFO）、最近最久未使用（LRU）和最不经常使用（LFU）。

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

它根据页面进入内存的先后顺序进行页面置换。

当一个页面需要被替换时，选择最早进入内存的页面进行替换。

虽然FIFO算法的实现简单，但它无法很好地反映页面的使用频率和重要性，容易发生“缺页率抖动”的问题。

缺页率抖动指的是在某些场景下，缺页率会频繁地快速上升，然后又快速下降。

最近最久未使用（LRU）算法是一种基于页面历史访问记录的页面置换算法。

它认为最近被访问过的页面是最有可能在未来被访问的，因此选择最近最久未使用的页面进行替换。

LRU算法可以较为准确地反映页面的使用频率，避免了FIFO算法的缺点。

但由于需要记录页面的访问历史，因此实现相对复杂，需要额外的开销。

最不经常使用（LFU）算法是一种基于页面使用频率的页面置换算法。

它认为使用频率最低的页面是最不重要的，因此选择最不经常使用的页面进行替换。

LFU算法可以较好地反映页面的使用频率，对于一些热点页面和冷门页面的处理较为准确。

但由于需要记录页面的使用次数，因此实现相对复杂，需要额外的开销。

根据实际情况选择合适的页面置换算法对于系统的性能影响非常重要。

一般来说，FIFO算法比较适用于缺页率较低的情况，而LRU算法则适用于需要较高精确度的场景，而LFU算法则适用于需要特别关注页面使用频率的场景。

在实践中，我们可以使用模拟算法来进行页面置换算法的实验。

通过构造不同的页面访问序列，我们可以测试不同算法的效果并进行比较。

在实验过程中，我们可以观察不同算法的缺页率、替换次数、访问延迟等指标，以评估算法的性能。

学号P7******* 专业计算机科学与技术姓名实验日期2017/11/30 教师签字成绩实验报告【实验名称】虚拟存储管理【实验目的】模拟请求分页虚拟存储管理技术中的硬件地址变换、缺页中断以及页式淘汰算法，处理缺页中断。

清楚认识请求分页管理。

采用最佳置换算法实现分页管理的缺页调度。

采用先进先出算法实现分页管理的缺页调度。

采用LRU算法实现分页管理的缺页调度。

【实验原理】C语言程序设计数据结构最佳置换算法：其所选择的淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。

采用最佳置换算法通常可保证获得最低的缺页率。

先入先出置换算法：该算法总是淘汰最先进入内存的页面。

最近最久未被访问算法：选取过去中最久未被访问的页面进行替换。

【实验内容】数据结构和符号说明a)数据结构②struct PAGE_LIST③{④int id;// 块号⑤int flag;// 自适应标志⑥} page_list[MAX];⑦int N = 0;// 页面表大小⑧int order[MAX];// 调用串⑨// 调用长度⑩int M = 0;// 定义输出内容⑪int G[MAX][MAX];// 输出置换图⑫int I, J;// 置换图扫描指针⑬int LL[MAX];// 缺页序列⑭int LI;// 缺页序列扫描指针⑮int RL[MAX];// 置换序列⑯// 置换序列扫描指针⑰int RI;函数说明：void init();// 初始化函数void print();// 输出函数void Optimal();// 最佳置换算法void FIFO()// 先进先出算法void LRU();// 最近最久未使用算法流程图最佳置换算法：先进先出置换算法：最近最久未被访问算法：代码：#include<stdio.h>#define MAX 100struct PAGE_LIST{int id;// 块号int flag;// 自适应标志} page_list[MAX];int N = 0;// 页面表大小int order[MAX];// 调用串// 调用长度int M = 0;// 定义输出内容int G[MAX][MAX];// 输出置换图int I, J;// 置换图扫描指针int LL[MAX];// 缺页序列int LI;// 缺页序列扫描指针int RL[MAX];// 置换序列// 置换序列扫描指针int RI;// 初始化函数void init(){int i;I = 0;J = 0;LI = 0;RI = 0;for (i = 0; i<100; i++){page_list[i].id = -1;page_list[i].flag = 999;}printf("请输入页表的大小：");scanf("%d", &N);printf("请输入调用长度：");scanf("%d", &M);printf("请输入调用串：\n");for (i = 0; i<M; i++)scanf("%d", &order[i]);}// 输出函数void display(){int i, j;float x;printf("置换图为：\n");for (i = 0; i<N; i++){printf("\n");for (j = 0; j<J; j++)printf("=== ");printf("\n");for (j = 0; j<J; j++)printf("%3d ", G[i][j]);printf("\n");}printf("\n缺页序列为：\n");for (i = 0; i<LI; i++)printf("%3d ", LL[i]);printf("\n置换序列为：\n");for (i = 0; i<RI; i++)printf("%3d ", RL[i]);x = (float)J / (float)M;x *= 100;printf("\n缺页率为：\n%3.2f%%\n", x);}// 判断页是否在页表内int IsExist(int x){int i;for (i = 0; i<N; i++){if (page_list[i].id == x){return 1;}}return 0;}// 最佳置换算法// 此算法中自适应标志代表后面序列中是否访问到了此位置void Optimal(){int i, j, k;int cou;init();for (i = 0; i<N; i++){page_list[i].id = order[i];for (j = 0; j<N; j++){G[I][J] = page_list[j].id;I++;}I = 0;J++;LL[LI] = order[i];LI++;}for (; i<M; i++){if (!IsExist(order[i])){cou = 0;for (j = i + 1; j<M; j++){if (cou == N - 1)break;for (k = 0; k<N; k++)if(page_list[k].id == order[j] &&page_list[k].flag != 0){page_list[k].flag = 0;cou++;}}for (j = 0; j<N; j++)if (page_list[j].flag != 0){page_list[j].id = order[i];break;}for (j = 0; j<N; j++){G[I][J] = page_list[j].id;I++;}I = 0;J++;LL[LI] = order[i];LI++;RL[RI] = order[i];RI++;}for (j = 0; j<N; j++)page_list[j].flag = 999;}}// 先进先出算法// 此算法中自适应标志不需要使用void FIFO(){int i, j;int pos = 0;init();for (i = 0; i<M; i++){if (!IsExist(order[i])){page_list[pos].id = order[i];pos = (pos + 1) % N;for (j = 0; j<N; j++){G[I][J] = page_list[j].id;I++;}I = 0;J++;LL[LI] = order[i];LI++;if (i>= N){RL[RI] = order[i];RI++;}}}}// 最近最久未使用算法// 此算法中自适应标志为起未被使用的次数void LRU(){int i, j;int pos, max;init();for (i = 0; i<M; i++){if (!IsExist(order[i])){pos = 0;max = 0;for (j = 0; j<N; j++){if (page_list[j].flag > max){pos = j;max = page_list[j].flag;}}page_list[pos].id = order[i];page_list[pos].flag = 0;for (j = 0; j<N; j++){G[I][J] = page_list[j].id;I++;}I = 0;J++;LL[LI] = order[i];LI++;if (i>= N){RL[RI] = order[i];RI++;}}else{for (j = 0; j<N; j++)if (page_list[j].id == order[i]){page_list[j].flag = 0;break;}}for (j = 0; j<N; j++)if (page_list[j].id == order[i])continue;elsepage_list[j].flag++;}}int main(){int select;do{printf(" 页面置换算法\n");printf(" 1.最佳置换算法（Optimal）\n 2.先进先出算法（FIFO） \n");printf(" 3.最近最久未使用算法（LRU）\n 4.退出程序\n");printf("请输入您想要执行的操作：");scanf("%d", &select);switch (select){case 1:Optimal();display();break;case 2:FIFO();display();break;case 3:LRU();display();break;case 4:return 0;default:printf("输入有误，请重新输入！\n");}} while (1);return 0;}结果截图最佳置换算法先进先出算法:最近最久未使用算法：【小结或讨论】三种算法的主要区别是确定替换物理块的方式不同：1、对于先进先出置换算法，设置一个指针，循环从block的首元素指到block 的尾元素，就是物理块置换顺序2、对于LRU置换算法，遍历页表中的页号，根据这些页号最近被引用的顺序，找到最久未被引用的页号，即在输入序列中向前查找离当前页最远的页号，将其所在的物理块置换掉。