第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作为最久未使用的两个页面之一。