第7次常用页面置换算法模拟实验

页面置换算法实验报告院系:****************学院班级:***********姓名:***学号:************一、实验题目: 页面置换算法二. 实验目的：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）算法。

它的原理就像排队一样，先进入内存的页面先被替换出去。

这种算法实现起来比较简单，但可能会出现一种叫做“Belady 异常”的现象，即增加分配给进程的物理块数量时，反而可能会导致缺页率增加。

这是因为可能先进入的页面是经常被使用的，而后面进来的是不常使用的，这样就容易造成错误的替换。

接下来是最近最久未使用（LRU）算法。

它的思路是把最近一段时间内最久没有被使用的页面替换出去。

这种算法的性能通常比较好，因为它更能反映页面的实际使用情况。

但它的实现相对复杂，需要额外的硬件支持或者通过软件来模拟实现。

然后是最近未使用（NRU）算法。

这个算法会把页面分为四类：未被访问且未被修改、未被访问但已被修改、已被访问但未被修改、已被访问且已被修改。

然后根据这些分类来选择替换的页面。

它的优点是实现相对简单，但可能不如 LRU 算法那么精确。

还有一种叫做时钟（Clock）算法，也称为第二次机会算法。

它把所有的页面组成一个环形链表，通过一个指针来遍历。

当需要替换页面时，如果页面的访问位是 0 ，则直接替换；如果是 1 ，则将其访问位置为 0 ，然后指针继续移动，直到找到访问位为 0 的页面。

除了以上这些，还有最优（OPT）算法。

这是一种理想的算法，它会选择未来最长时间内不会被使用的页面进行替换。

但由于它需要预先知道未来的页面访问情况，所以在实际中是无法实现的，通常只是用来作为评估其他算法性能的标准。

一、实验目的1. 理解缺页中断的概念及其在操作系统中的作用。

2. 掌握常见的页面置换算法，如先进先出（FIFO）、最近最少使用（LRU）等。

3. 通过模拟实验，验证不同页面置换算法对缺页中断次数的影响。

4. 深入了解页式虚拟存储管理中地址转换的过程。

二、实验环境1. 操作系统：Windows 102. 编程语言：C/C++3. 实验工具：Visual Studio三、实验内容1. 模拟缺页中断的产生2. 实现不同的页面置换算法3. 分析页面置换算法对缺页中断次数的影响4. 模拟地址转换过程四、实验步骤1. 模拟缺页中断的产生（1）定义一个模拟指令序列，包含多个页面号。

（2）创建一个模拟的页表，用于记录每个页面是否在内存中。

（3）根据指令序列，遍历页表，判断访问的页面是否在内存中。

（4）如果页面不在内存中，则产生缺页中断。

2. 实现不同的页面置换算法（1）先进先出（FIFO）算法：- 定义一个队列，用于存储内存中的页面号。

- 当发生缺页中断时，将新页面号入队，同时判断队列长度是否超过内存块数。

- 如果队列长度超过内存块数，则将队首元素出队，模拟页面置换过程。

（2）最近最少使用（LRU）算法：- 定义一个链表，用于存储内存中的页面号。

- 当发生缺页中断时，将新页面号插入链表尾部。

- 如果链表长度超过内存块数，则从链表头部删除元素，模拟页面置换过程。

3. 分析页面置换算法对缺页中断次数的影响（1）定义一个变量，用于记录缺页中断次数。

（2）遍历模拟指令序列，根据不同的页面置换算法处理缺页中断。

（3）统计不同算法下的缺页中断次数，并进行比较。

4. 模拟地址转换过程（1）根据指令中的逻辑地址，计算页号和偏移量。

（2）根据页号，查找页表，判断页面是否在内存中。

（3）如果页面在内存中，则根据偏移量计算物理地址。

（4）如果页面不在内存中，则产生缺页中断。

五、实验结果与分析1. 模拟缺页中断的产生通过模拟指令序列，成功产生了缺页中断。

实验报告三——内存页面置换算法的设计姓名：丛菲学号：20100830205 班级：信息安全二班一、实习内容•实现最近最久未使用（LRU）置换算法二、实习目的•LINUX中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分调入内存便可运行，还支持请求调页的存储管理方式。

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

三、实习题目1. 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。

•例如: 分配给该进程的页块数为3，一个20位长的页面访问序列为:12560,36536,56042,70435，则缺页次数和缺页率按下图给出:2. 假定分配给该进程的页块数为3，页面访问序列长度为20。

本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用LRU算法，将当前一段时间内最久未使用过的页替换出去。

•模拟程序的算法如下图：四、实现代码为：#include<stdio.h>#define M 3#define N 20#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") /*表格控制*/typedef struct page{int num; /*记录页面号*/int time; /*记录调入内存时间*/}Page; /* 页面逻辑结构，结构为方便算法实现设计*/Page b[M]; /*内存单元数*/int c[M][N]; /*暂保存内存当前的状态：缓冲区*/int queue[100]; /*记录调入队列*/int K; /*调入队列计数变量*//*初始化内存单元、缓冲区*/void Init(Page *b,int c[M][N]){int i,j;for(i=0;i<N;i++){b[i].num=-1;b[i].time=N-i-1;}for(i=0;i<M;i++)for(j=0;j<N;j++)c[i][j]=-1;}/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/ int GetMax(Page *b){int i;int max=-1;int tag=0;for(i=0;i<M;i++){if(b[i].time>max){max=b[i].time;tag=i;}}return tag;}/*判断页面是否已在内存中*/int Equation(int fold,Page *b){int i;for(i=0;i<M;i++){if (fold==b[i].num)return i;}return -1;}void Lru(int fold,Page *b) /*LRU核心部分*/{int i;int val;val=Equation(fold,b);if (val>=0){b[val].time=0;for(i=0;i<M;i++)if (i!=val)b[i].time++;}else//页面不存在{queue[++K]=fold;/*记录调入页面*/val=GetMax(b);b[val].num=fold;b[val].time=0;for(i=0;i<M;i++)if (i!=val)b[i].time++;}}main()/*主程序*/{int a[N]={1,0,5,1,7,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4};int i,j;start:K=-1;Init(b, c);for(i=0;i<N;i++){Lru(a[i],b);c[0][i]=a[i];/*记录当前的内存单元中的页面*/for(j=0;j<M;j++)c[j][i]=b[j].num;}/*结果输出*/printf("nei cun zhuang tai ：\n");Myprintf;for(j=0;j<N;j++)printf("|%2d ",a[j]);printf("|\n");Myprintf;for(i=0;i<M;i++){for(j=0;j<N;j++){if(c[i][j]==-1)printf("|%2c ",32);elseprintf("|%2d ",c[i][j]);}printf("|\n");}Myprintf;printf("\ndiao ru dui lie :");for(i=0;i<K+1;i++)printf("%3d",queue[i]);printf("\nque ye ci shu ：%6d\nque ye lv：%16.2f%%\n",K+1,(float)(K+1)/N*100);}五、在虚拟机上的具体操作及结果六、思考题•比较LRU和其他置换算法各自的优缺点，能够实现其他置换算法模拟设计，分析内存页面数的变化对各种置换算法命中率的影响。

fifo页面置换算法例题详解FIFO（First In, First Out）页面置换算法是一种最简单的页面置换算法，它根据页面调入内存的顺序进行页面置换。

当发生页面缺失时，选择最早调入内存的页面进行置换。

下面是一个使用FIFO页面置换算法解决页面置换问题的例题：假设一个系统的物理内存容量为3个页面，而作业需要访问9个页面。

作业在以下指令序列中运行：1，2，3，4，1，2，5，1，2。

假设在开始时，物理内存中没有页面。

使用FIFO页面置换算法，计算缺页次数。

解题步骤如下：1. 创建一个长度为3的队列，用于保存当前在内存中的页面。

2. 从指令序列中取出第一个页面1。

由于物理内存中没有页面，将页面1调入物理内存，并将1加入队列中。

3. 继续从指令序列中取出页面2。

由于物理内存中只有页面1，将页面2调入物理内存，并将2加入队列中。

4. 继续从指令序列中取出页面3。

由于物理内存中有页面1和2，将页面3调入物理内存，并将3加入队列中。

5. 继续从指令序列中取出页面4。

由于物理内存中已满，需要进行页面置换。

由于页面1是最早调入内存的页面，所以选择页面1进行置换。

将页面4调入物理内存，并将4加入队列中。

6. 继续从指令序列中取出页面1。

由于物理内存中已满，需要进行页面置换。

由于页面2是最早调入内存的页面，所以选择页面2进行置换。

将页面1调入物理内存，并将1加入队列中。

7. 继续从指令序列中取出页面2。

由于物理内存中已满，需要进行页面置换。

由于页面3是最早调入内存的页面，所以选择页面3进行置换。

将页面2调入物理内存，并将2加入队列中。

8. 继续从指令序列中取出页面5。

由于物理内存中已满，需要进行页面置换。

由于页面4是最早调入内存的页面，所以选择页面4进行置换。

将页面5调入物理内存，并将5加入队列中。

9. 继续从指令序列中取出页面1。

由于物理内存中已满，需要进行页面置换。

由于页面1是最早调入内存的页面，所以选择页面1进行置换。

一、实验目的1. 了解操作系统内存管理中缺页处理的基本原理和方法。

2. 熟悉页面置换算法在缺页处理中的应用。

3. 分析不同页面置换算法的性能，为实际应用提供参考。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3. 实验工具：Jupyter Notebook三、实验原理缺页管理是操作系统内存管理的重要组成部分，主要解决虚拟存储器中页面请求与物理内存冲突的问题。

当进程请求访问一个不在物理内存中的页面时，系统需要进行缺页处理，将所需的页面从磁盘调入内存，并将对应的物理页面换出。

常见的页面置换算法有：1. 最佳适应算法（OPT）2. 先进先出算法（FIFO）3. 最近最少使用算法（LRU）4. 最近最不经常使用算法（LFU）四、实验步骤1. 设计实验数据：创建一个包含若干页面的数组，表示虚拟存储器中的页面。

2. 实现页面置换算法：根据选择的算法，实现相应的页面置换逻辑。

3. 运行实验：模拟进程访问页面，记录缺页次数、页面置换次数等指标。

4. 分析实验结果：比较不同页面置换算法的性能。

五、实验结果与分析1. 实验数据虚拟存储器包含100个页面，进程请求访问的页面顺序为：0, 1, 2, ..., 99。

2. 实验结果（1）最佳适应算法（OPT）缺页次数：18页面置换次数：18（2）先进先出算法（FIFO）缺页次数：26页面置换次数：26（3）最近最少使用算法（LRU）缺页次数：19页面置换次数：19（4）最近最不经常使用算法（LFU）缺页次数：22页面置换次数：223. 实验结果分析通过实验结果可以看出，不同页面置换算法的性能存在差异。

在本次实验中，最佳适应算法（OPT）的性能最佳，其次是最近最少使用算法（LRU），先进先出算法（FIFO）和最近最不经常使用算法（LFU）的性能较差。

六、结论1. 最佳适应算法（OPT）在本次实验中表现出最佳性能，但实际应用中难以实现，因为需要预先知道进程访问页面的顺序。

实验二存储管理与页面置换算法一、实验目的通过模拟页式虚拟存储管理中地址转换和页面置换，了解页式虚拟存储管理的思想，掌握页式地址转换过程和缺页中断处理过程。

二、实验学时4学时三、实验内容单机模拟页式虚拟存储管理中地址转换和页面置换过程。

首先对页表进行初始化；输入要访问的逻辑地址（可为16进制或10进制），程序分离出逻辑地址的页号，查找页表，根据页表完成地址转换，输出转换后的地址；若缺页则提示中断发生，按某种页面置换算法（FIFO，LRU，LFU）进行页面置换，并修改和输出页表，输出绝对地址。

最后输出置换情况和缺页次数。

四、算法描述1 内存的分配和管理方案在进程创建时必须为它分配一定的内存资源，内存资源的分配与管理有很多方法，从动态性分有静态的和动态的分配方法，从连续性上分有连续的和不连续的分配方案。

连续的分配方案是程序的执行速度加快但会使内存出现碎片而不能得到应用，而不连续的分配方案可以使内存碎片得到充分的应用，但由于访问内存次数的增多使程序执行的速度下降。

2 内存的分配的过程在作业执行前，向系统提供内存的请求表，在系统为作业创建进程时，要为进程分配内存资源。

以分页系统为例，系统首先确定进程需要的页面数量，然后顺序查找位图(系统为每一个页面分配一位内存中的各个页面组成一个数组，如果该位为1说明该位所指示的页正在被使用，如果该位为0说明该位指示的页面空闲)若存在所需要的空闲页面则此次分配成功，否则分配失败，若分配成功系统首先把分配出去的页面所属的位置为1，然后形成进程所需的页表。

3算法思想本程序有两个功能：一是地址转换；二是模拟页面置换情况。

(1)地址转换:add_tran将逻辑地址中的页号分离出来，查找页表，将查找到的块号与逻辑地址中的页内偏移量合成实际地址，若查找不到则产生缺页中断，按FIFO的方法置换页面。

(a)数据结构：array[max][2]为页表，其中array[n][0]为页号，array[n][1]为块号，size_PT表示系统分配给进程的块数，即页表中的页数。

第1篇一、实验目的通过本次实验，掌握操作系统存储管理的基本原理，了解不同存储管理策略的实现方法，并能够通过代码模拟实现其中的一种策略，以加深对存储管理机制的理解。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验内容本次实验主要模拟实现页式存储管理中的FIFO（先进先出）页面置换算法。

四、实验步骤1. 定义一个类Page，用于表示页面，包含页号、标志位和物理块号等信息。

```pythonclass Page:def __init__(self, page_number):self.page_number = page_numberself.flag = 0 0表示不在内存，1表示在内存self.frame_number = -1 物理块号，-1表示未分配```2. 定义一个类Memory，用于模拟内存，包含物理页列表、页面置换算法和页面替换操作。

```pythonclass Memory:def __init__(self, frames):self.frames = framesself.page_table = []def allocate_page(self, page_number):for page in self.page_table:if page.page_number == page_number:return pagefor page in self.page_table:if page.flag == 0:page.flag = 1page.frame_number = self.frames.pop(0) return pageFIFO页面置换算法for page in reversed(self.page_table):if page.flag == 0:self.frames.append(page.frame_number) page.flag = 1page.frame_number = self.frames.pop(0) return page页面置换失败raise Exception("Memory full")def deallocate_page(self, page_number):for page in self.page_table:if page.page_number == page_number:page.flag = 0page.frame_number = -1self.frames.append(page.frame_number)return```3. 定义一个类PageReplacementSimulator，用于模拟页面置换过程。

广东海洋大学学生实验报告书（学生用表）实验名称 LRU页面之后算法模拟课程名称操作系统课程号学院（系）专业班级学生姓名学号实验地点实验日期LRU页面置换算法模拟一．实验目的（1）掌握页式管理基本原理（2）掌握LRU页面置换算法二．实验内容（1）按照最近最久未使用页面置换算法（LRU）设计页面置换模拟程序。

（2）对于给定的页面访问序列，输出其访问过程中的页面置换序列，并记录缺页次数。

70120304230321201701页面访问序列页面0 77722224440001111111页面10000000033333300000页面2111333222222222777缺页Y Y Y Y Y Y Y Y Y Y Y Y置换7 1 2 3 0 4 0 3 2 （3）输出内容参考三．相关数据结构（1）页表结构数组页号块号状态（2）页面访问序列数组：保存进程执行过程中的页面访问序列。

（3）寄存器数组：每个物理块对应一个16bit的寄存器。

（4）物理块分配表（bool数组）：标识每个物理块是否已经分配四．实现流程（1）主线程：实现页面访问过程中的物理块分配和页面置换（假设每间隔80ms访问一个页面）。

（2）寄存器周期性移位线程：周期性（每隔100ms）将所有寄存器右移一位。

（3）主线程参考流程图：详细代码：import java.io.BufferedReader;import java.io.InputStreamReader;public class LRU {int blockCount;int seriaCount;static int num=0;int[] address;int[] stack;BufferedReader br;public static void main(String[] args) {int address[] = { 7, 0,1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};LRU lru = new LRU();lru.init();lru.display();}public void init() {try {br = new BufferedReader(new InputStreamReader(System.in));}catch (Exception e) {e.printStackTrace();System.exit(0);}blockCount = 3;stack = new int[blockCount];System.out.println("请输入访问内存的块序列的个数为3:");seriaCount = readInt();System.out.println("读入的访问序列是:");address = readIntArray();}public void display() {boolean flag;System.out.println("--------------------------------------");System.out.print("最近最久未使用页面置换算法（LRU）页面置换序列：");for (int i = 0; i< address.length; i++) {int j =0;flag =false;int t, temp =address[i];while(stack[j] != address[i]) {t= stack[j];stack[j]= temp;temp= t;j++;if(temp == 0 || j == stack.length)break;}if (j< stack.length)stack[j]= temp;if (temp != 0&& j != stack.length)flag= true;try {ng.Thread.sleep(500);} catch(InterruptedException e) {e.printStackTrace();}for (int m= 0; m < i - blockCount + 1; m++) System.out.print(" ");for (int m =0; m < stack.length; m++)System.out.print(stack[m]+ " ");System.out.print(",");if(flag){num=num;}else{num++;}}System.out.println("");System.out.println("总缺页数："+num); }public int readInt() {try {String s =br.readLine();return Integer.parseInt(s);} catch (Exception e) {return 3;}}public int[] readIntArray() {try {String s =br.readLine();System.out.println(s);String tmp[]= s.split(" ");int value[] =new int[tmp.length];for (int i =0; i < value.length; i++)value[i]= Integer.parseInt(tmp[i]);return value;} catch (Exception e) {System.out.println(e);return null;}}}五．实现结论通过这次的实验，我对LRU页面置换算法有了更深的了解，LRU置换算法是理想性的算法，因为使用LRU置换算法要花费很大的系统开销，所以在实际系统中并不会直接采用LRU算法。

clock页面置换算法例题详解Clock页面置换算法（也称为时钟置换算法或FIFO算法）是一种简单的页面置换算法，它总是选择当前最久未使用的页面进行置换。

下面是一个关于Clock页面置换算法的例题详解：假设有一个程序需要使用6个页面，分别为A、B、C、D、E和F，而且它需要使用4个内存块（也可以说是4个页面框）。

让我们跟随程序的执行，看看这个程序使用Clock页面置换算法时会发生什么。

1、初始状态：程序开始执行时，内存中没有任何页面。

2、第一次缺页中断：程序需要访问页面A，但内存中没有该页面。

于是，发生一次缺页中断。

现在内存中只有一个空闲的内存块，所以可以将页面A加载到内存中。

3、第二次缺页中断：程序需要访问页面B，但内存中没有该页面。

同样地，发生一次缺页中断。

此时内存中仍然只有一个空闲的内存块，所以可以将页面B加载到内存中。

4、第三次缺页中断：程序需要访问页面C，但内存中没有该页面。

再次发生一次缺页中断。

此时内存中仍然只有两个空闲的内存块，所以可以将页面C加载到内存中。

5、第四次缺页中断：程序需要访问页面D，但内存中没有该页面。

再次发生一次缺页中断。

此时内存中仍然只有三个空闲的内存块，所以可以将页面D加载到内存中。

6、第五次缺页中断：程序需要访问页面E，但内存中没有该页面。

再次发生一次缺页中断。

此时内存中仍然只有四个空闲的内存块，所以可以将页面E加载到内存中。

7、第六次缺页中断：程序需要访问页面F，但内存中没有该页面。

再次发生一次缺页中断。

此时内存中已经满了，不能再加载任何页面了。

此时需要使用Clock页面置换算法来决定哪个页面应该被置换出去。

在这个例子中，我们假设Clock页面置换算法的参数是k=2（即每次只淘汰两个最近最少使用的页面之一）。

首先，我们需要找到当前最久未使用的两个页面。

根据算法的规则，总是选择当前最久未使用的页面进行置换。

在这个例子中，我们可以选择A和B作为最久未使用的两个页面之一。

课本第九章21题实验ytinrete1．实验目的：学习页面置换算法2．实验内容Write a program that implements the FIFO and LRU page-replacement algorithms presented in this chapter. First, generate a random page reference string where page numbers range from 0..9. Apply the random page-reference string to each algorithm and record the number of page faults incurred by each algorithm. Implement the replacement algorithms such that the number of page frames can vary from 1..7. Assume that demand paging is used.写一个程序来实现本章中介绍的FIFO和LRU页置换算法。

首先产生一个随机的页面引用序列，页面数从0~9。

将这个序列应用到每个算法并记录发生的页错误的次数。

实现这个算法时，要将页帧的数量设为可变（从1~7）。

假设使用请求调页。

3．设计说明FIFO算法：每次请求先查找是否有空块，有则替换，并标记为最晚到达，若没有则从标记中寻找最新到达的块，替换，并更新标记表。

标记数字越小，到达时间最早。

LRU算法：每次请求先查找是否有空块，有则替换，并标记为最近使用时间最短者，若没有则从标记中寻找最近使用时间最长者，替换，并更新标记表。

标记数字越小，最近使用频率越低。

4．实验环境windows7 ultimate x64 with sp1Dev-c++5．程序源码#include<stdlib.h>#include<cstdlib>#include<time.h>#include <iostream>#include <vector>#include <windows.h>using namespace std;typedef struct block//页帧块结构{int num;int lable;}block;int page_size, frame_size;//序列数，页帧大小vector <int> order;//存放序列vector <block> frame;//页帧void page_replacement (int kind)//kind=1为FIFO,kind=2为LRU {//初始化frame.clear();block init;init.num=-1;ble=-1;for(int i=0; i<frame_size; i++){frame.push_back(init);}int error=0;//错误次数int seq=0;//标记数字int position=-1;//匹配位置for(int i=0; i<order.size(); i++){position=-1;cout<<i<<":"<<"引用请求为"<<order.at(i)<<" :"<<endl; cout<<"引用前页帧情况（-1为空）:";for(int j=0; j<frame.size(); j++){cout<<(frame.at(j)).num<<", ";if(order.at(i)==(frame.at(j)).num)position=j;}cout<<endl;if(-1!=position){cout<<"匹配成功！"<<endl;//更新标记这也是LRU算法比FIFO唯一多出来的地方if(kind==2){int temp=(frame.at(position)).lable;(frame.at(position)).lable=seq+1;for(int j=0; j<frame.size(); j++){if(-1!=(frame.at(j)).num)//不是空块{if((frame.at(j)).lable>temp){(frame.at(j)).lable--;}}}}//多余部分结束}else{cout<<"匹配失败！"<<endl;error++;//开始置换//先查找空页for(int j=0; j<frame.size(); j++){if(-1==(frame.at(j)).num){position=j;break;}}if(-1!=position)//有空页{(frame.at(position)).num=order.at(i);//置换seq++;(frame.at(position)).lable=seq;//标记数字}else//没有空页{for(int j=0; j<frame.size(); j++)//找相应的置换项{if(1==(frame.at(j)).lable){position=j;break;}}(frame.at(position)).num=order.at(i);//置换(frame.at(position)).lable=seq+1;//标记进入顺序for(int j=0; j<frame.size(); j++)//更新标记{(frame.at(j)).lable--;}}}cout<<"引用后页帧情况（-1为空）:";for(int j=0; j<frame.size(); j++){cout<<(frame.at(j)).num<<", ";}cout<<endl<<endl;}cout<<endl<<"算法结束，总页错误的次数为："<<error<<endl<<endl; }int main(){cout<<"请输入测试的页面序列数：" ;cin>>page_size;if(page_size<=0){cout<<"序列数有误";return 0;}cout<<"请输入页帧数量(1~7):";cin>>frame_size;if(frame_size<=0||frame_size>7){cout<<"页帧数有误";return 0;}int number;srand(unsigned(time(NULL)));//设置随机数种子for(int i=0; i<page_size; i++){number=rand()%10;//页面数从0到9order.push_back(number);}/* 课本例子，使用这个时将上面的随机数注释掉order.push_back(7);order.push_back(0);order.push_back(1);order.push_back(2);order.push_back(0);order.push_back(3);order.push_back(0);order.push_back(4);order.push_back(2);order.push_back(3);order.push_back(0);order.push_back(3);order.push_back(2);order.push_back(1);order.push_back(2);order.push_back(0);order.push_back(1);order.push_back(7);order.push_back(0);order.push_back(1);*/cout<<endl<<"随机生成的页面引用序列为："<<endl;for(int i=0; i<order.size(); i++){cout<<order.at(i);if(order.size()-1!=i)cout<<", ";}cout<<endl<<endl;page_replacement (1);cout<<endl<<endl;page_replacement (2);system("pause");return 0;}6．结果测试首先以课本上为例：20个序列：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 帧序列为3FIFO错误数15，置换顺序课件与课本完全相符。

【操作系统】页⾯置换算法（最佳置换算法）（C语⾔实现）【操作系统】页⾯置换算法（最佳置换算法）（C语⾔实现）（编码⽔平较菜，写博客也只是为了个⼈知识的总结和督促⾃⼰学习，如果有错误，希望可以指出）1.页⾯置换算法：在地址映射过程中，若在页⾯中发现所要访问的页⾯不在内存中，则产⽣缺页中断。

当发⽣缺页中断时，如果操作系统内存中没有空闲页⾯，则操作系统必须在内存选择⼀个页⾯将其移出内存，以便为即将调⼊的页⾯让出空间。

⽽⽤来选择淘汰哪⼀页的规则叫做页⾯置换算法。

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

从理论上讲，应该保留最近重复访问的页⾯，将以后都不再访问或者很长时间内不再访问的页⾯调出。

----百度百科2.具体的页⾯置换算法：2.1 最佳置换算法：⼀个进程在内存的若⼲个页⾯中，哪⼀个页⾯是未来最长时间内不再被访问的，那么如果发⽣缺页中断时，就将该页⾯换出，以便存放后⾯调⼊内存中的页⾯。

1.这是计算机操作系统（第四版）中的⼀个例⼦。

系统⾸先为进程分配了三个物理块。

上⾯⼀排数字是作业号。

在转满三个物理块后，要访问2号作业，2号作业不在内存，所以会发⽣缺页中断，然后系统需要将2号作业调⼊内存，但是此时物理块已经装满。

2.依据最佳置换算法，会将7号页换出（0号页在2号页后第1个就会被访问，1号页在2号页后第10个会被访问，7号页在2号页后第14个会被访问，7号页在已经装⼊内存的作业中是未来最长时间不会被访问的，所以换出7号页）。

3.后⾯依次类推。

2.2 先进先出算法：如果发⽣缺页中断，需要换出⼀个页⾯的时候，总是选择最早进⼊内存的页⾯，即选择在内存中驻留时间最久的页⾯进⾏换出。

有点不清楚。

就是每次发⽣缺页就将最早进⼊内存的页⾯换出，然后将刚调⼊的页⾯换⼊该物理块。

2.3 最近最久未使⽤（LRU）置换算法：LRU算法是缺页中断发⽣时选择最久未使⽤的页⾯进⾏换出。

这个算法其实也很好判断。

分享⼀个⼩技巧。

内存分配了k个物理块，发⽣缺页中断将要往内存调⼊某个页⾯的时候，在该页⾯往前⾯数K个物理块最前⾯的那个就会是要换出的，因为该页⾯最长时间未被使⽤过。

IV 页面置换算法 1 项目概述 2 全局页面置换算法 3 局部页面置换算法 4 产生引用串 5 性能评价 6 具体任务总结 5 附加任务的建议

1 项目概述 在本项目中，我们将实现不同的全局和局部页面置换算法，并利用随机产生的引用串一比较它们的相对性能。

2 全局页面置换算法 全局页面置换算法采用固定数目的页框。我们考虑一个单进程系统并做如下假设：  进程的虚拟内存由P个页面组成，编号从0~P-1。  引用串RS是范围从0~P-1的的连续的整数。RS的每一个元素p表示对页面p的一次引用。  内存由F个页框组成，编号从0~F-1。使用数组M[F]表示。数组的每一项M[f]包含当前驻留在页框f中的页面的页面号。 原理教材中讨论了几种不同的全局页面置换算法。每一个算法顺序读取RS的元素。对于RS中的每一个元素p，置换算法会搜索内存数组以便找到匹配的项，也就是要找到 一个f满足M[f]==p。如果没有找到匹配项，便会发生缺页。算法必须根据其实施的策略选择一个页框M[i]，并用p置换该页框的内容，即M[i]=p。 为了实现置换算法，必须根据不同的算法而提供辅助的数据结构。以下列表总结了不同算法的需求：  最佳置换算法和随机置换算法不需要辅助的数据结构。在最佳置换算法中，算法搜索RS来寻找要置换的页。随机置换算法为了选择要置换的页，必须在0~F-1之间产生一个随机数。  FIFO置换算法只需要在内存中维持一个指向最旧的页面的指针（数组索引）。只要当前页面被置换了，该指针就递增1（以F为模）。  LRU置换算法需要维护一个大小为F、用来实现队列的辅助数组；在每次引用时该队列都会重新排序，以便把被引用的页面放在队列的末尾。  第二次机会置换算法（即时钟置换算法）必须维护一个和FIFO算法相似的指针。此外，它需要一个a位的数组，每位表示一个页框。  第三次机会置换算法必须维护一个指针和3个数组；这些数组分别表示u位、w位和marker位。 一旦开发出这些算法，就可以使用第4 节中叙述和各种引用串进行测试了。

存储管理的页面置换算法存储管理的页面置换算法在考试中常常会考到，操作系统教材中主要介绍了3种常用的页面置换算法，分别是：先进先出法（FIFO）、最佳置换法（OPT）和最近最少使用置换法（LRU）。

大家要理解3种置换算法的含义，然后能熟练地运用在具体的练习中就可以了。

1.为什么要进行页面置换在请求分页存储管理系统中，由于使用了虚拟存储管理技术，使得所有的进程页面不是一次性地全部调入内存，而是部分页面装入。

这就有可能出现下面的情况：要访问的页面不在内存，这时系统产生缺页中断。

操作系统在处理缺页中断时，要把所需页面从外存调入到内存中。

如果这时内存中有空闲块，就可以直接调入该页面；如果这时内存中没有空闲块，就必须先淘汰一个已经在内存中的页面，腾出空间，再把所需的页面装入，即进行页面置换。

有助于理解的关键词有：请求分页、虚拟存储、缺页中断、页面置换。

2.常用的页面置换算法教材中介绍的常用页面置换算法有：先进先出法（FIFO）、最佳置换法（OPT）和最近最少使用置换法（LRU）。

（1）先进先出法（FIFO）算法描述：由于认为最早调入内存的页不再被使用的可能性要大于刚调入内存的页，因此，先进先出法总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。

先进先出法把一个进程所有在内存中的页按进入内存的次序排队，淘汰页面总是在队首进行。

如果一个页面刚被放入内存，就把它插在队尾。

【例1】教材第4章课后习题。

考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。

当内存块数量分别为3，5时，试问先进先出置换算法（FIFO）的缺页次数是多少？（注意，所有内存块最初都是空的，凡第一次用到的页面都产生一次缺页。

）解打叉的表示发生了缺页，共缺页16次。

提示：当FIFO算法执行到蓝色的4号页面时，这时内存中有三个页面，分别是1，2，3。

按照FIFO算法，在内存中停留时间最长的页面被淘汰。

页面置换算法实验总结
在操作系统中，页面置换算法是为了解决内存不足的问题，当内存中的页面不足时，需要选择一些页面进行置换，将其换出到磁盘上，从而为新的页面腾出空间。

在本次实验中，我实现了三种页面置换算法，分别是FIFO（先进先出）、LRU（最近最少使用）和OPT（最佳置换）。

下面是对这三种算法的总结：
1. FIFO算法：FIFO算法是最简单的页面置换算法，它按照页面进入内存的顺序进行置换。

实验结果显示，FIFO算法在某些情况下可能会导致“抖动”现象，即不断发生页面置换，性能较差。

2. LRU算法：LRU算法是根据页面的使用历史进行置换，将最长时间没有被使用的页面置换出去。

实验结果显示，LRU算法相比于FIFO算法在减少页面抖动方面表现更好，但是实现起来较为复杂，需要维护一个访问历史记录的数据结构。

3. OPT算法：OPT算法是一种理想情况下的页面置换算法，它通过预测未来的页面访问情况来选择最佳的页面进行置换。

实验结果显示，OPT算法在减少页面抖动方面表现最好，但是实现起来较为困难，需要对未来的页面访问情况进行预测。

综上所述，不同的页面置换算法在不同的场景下有着不同的表现。

FIFO算法简单易实现，但性能较差；LRU算法在某些情况下能够较好地减少页面抖动；OPT算法在理论上是最佳的页面置换算法，但实现起来较为困难。

实际中的选择需要根据具体的应用场景
和系统需求来确定。