页面置换算法

页面置换算法实验报告实验心得
页面置换算法是操作系统中用来管理内存的一种重要算法。

在本次实验中，我们通过模拟内存的分配和释放过程，探索了三种典型的页面置换算法：FIFO（先进先出）、LRU（最近最少使用）和OPT（最优置换）。

在实验过程中，我发现FIFO算法虽然简单易懂，但容易产生“抖动”现象，即容易出现频繁的页面置换，导致系统效率低下。

LRU算法则能够有效避免抖动现象，但需要记录每个页面最近一次的使用时间，算法实现较为复杂。

OPT算法是一种理论上的最优算法，但由于需要预测未来的页面使用情况，实际中难以实现。

通过对三种算法的实验数据分析，我发现在不同的内存使用情况下，不同的页面置换算法表现也不同。

例如在内存使用较少的情况下，FIFO算法的效率可能会更高，但在内存使用较多的情况下，LRU算法则能够更好地发挥作用。

因此，在实际应用中，需要根据实际情况选择合适的页面置换算法。

总之，本次页面置换算法的实验让我更加深入地了解了操作系统中内存管理的相关知识，也加深了我对算法选择的理解和实际应用的思考。

LRU 页面置换算法1. 简介LRU（Least Recently Used）页面置换算法是一种常用的操作系统内存管理算法，用于在内存不足时决定哪些页面应该被置换出去以腾出空间给新的页面。

LRU算法基于一个简单的原则：最近最少使用的页面应该被置换。

在计算机系统中，内存是有限的资源，而运行程序所需的内存可能超过可用内存大小。

当系统发现没有足够的空闲内存来加载新页面时，就需要选择一些已经在内存中的页面进行替换。

LRU算法就是为了解决这个问题而设计的。

2. 原理LRU算法基于一个简单的思想：如果一个页面最近被访问过，那么它将来可能会再次被访问。

相反，如果一个页面很久没有被访问过，那么它将来可能不会再次被访问。

根据这个思想，LRU算法将最近最少使用的页面置换出去。

具体实现上，可以使用一个数据结构来记录每个页面最近一次被访问的时间戳。

当需要替换一页时，选择时间戳最早（即最久未访问）的页面进行替换即可。

3. 实现方式LRU算法的实现可以基于多种数据结构，下面介绍两种常见的实现方式。

3.1 使用链表一种简单的实现方式是使用一个双向链表来记录页面的访问顺序。

链表头部表示最近访问过的页面，链表尾部表示最久未被访问过的页面。

每当一个页面被访问时，将其从原位置移动到链表头部。

当需要替换一页时，选择链表尾部的页面进行替换。

这种实现方式的时间复杂度为O(1)，但空间复杂度较高，为O(n)，其中n为内存中可用页面数。

class Node:def __init__(self, key, value):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity):self.capacity = capacityself.cache = {}self.head = Node(0, 0)self.tail = Node(0, 0)self.head.next = self.tailself.tail.prev = self.headdef get(self, key):if key in self.cache:node = self.cache[key]self._remove(node)self._add(node)return node.valueelse:return -1def put(self, key, value):if key in self.cache:node = self.cache[key]node.value = valueself._remove(node)self._add(node)else:if len(self.cache) >= self.capacity:del self.cache[self.tail.prev.key] self._remove(self.tail.prev)node = Node(key, value)self.cache[key] = nodeself._add(node)def _remove(self, node):prev = node.prevnext = node.nextprev.next = nextnext.prev = prevdef _add(self, node):head_next = self.head.nextself.head.next = nodenode.prev = self.headnode.next = head_nexthead_next.prev = node3.2 使用哈希表和双向链表另一种实现方式是使用一个哈希表和一个双向链表。

目录1 需求分析 (2)1.1 目的和要求 (2)1.2 研究内容 (2)2 概要设计 (2)2．1 FIFO算法 (3)2．2 LRU算法 (3)2．3 OPT算法 (3)2．4 输入新的页面引用串 (3)3 详细设计 (4)3．1 FIFO（先进先出）页面置换算法： (4)3．2 LRU（最近最久未使用）置换算法： (4)3．3 OPT（最优页）置换算法 (4)4 测试 (5)5 运行结果 (5)6 课程设计总结 (9)7 参考文献 (10)8 附录：源程序清单 (10)1 需求分析1.1 目的和要求在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。

1.2 研究内容模拟实现页式虚拟存储管理的三种页面置换算法（FIFO(先进先出)、LRU （最近最久未使用）和OPT（最长时间不使用）），并通过比较性能得出结论。

前提：（1）页面分配采用固定分配局部置换。

（2）作业的页面走向和分得的物理块数预先指定。

可以从键盘输入也可以从文件读入。

（3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。

2 概要设计本程序主要划分为4个功能模块，分别是应用FIFO算法、应用LRU算法、应用OPT算法和页面引用串的插入。

1.1各模块之间的结构图2．1 FIFO 算法该模块的主要功能是对相应页面引用串进行处理，输出经过FIFO 算法处理之后的结果。

2．2 LRU 算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过LRU 算法处理之后的结果。

2．3 OPT 算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过OPT 算法处理之后的结果。

2．4 输入新的页面引用串该模块的主要功能是用户自己输入新的页面引用串，系统默认的字符串是0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0，用户可以自定义全新的20个数字页面引用串。

页⾯置换常⽤的算法总结本⽂转载⾃：进程运⾏时，若其访问的页⾯不在内存⽽需将其调⼊，但内存已⽆空闲空间时，就需要从内存中调出⼀页程序或数据，送⼊磁盘的对换区。

选择调出页⾯的算法就称为页⾯置换算法。

好的页⾯置换算法应有较低的页⾯更换频率，也就是说，应将以后不会再访问或者以后较长时间内不会再访问的页⾯先调出。

常见的置换算法有以下四种。

1. 最佳置换算法(OPT)最佳(Optimal, OPT)置换算法所选择的被淘汰页⾯将是以后永不使⽤的，或者是在最长时间内不再被访问的页⾯,这样可以保证获得最低的缺页率。

但由于⼈们⽬前⽆法预知进程在内存下的若千页⾯中哪个是未来最长时间内不再被访问的，因⽽该算法⽆法实现。

最佳置换算法可以⽤来评价其他算法。

假定系统为某进程分配了三个物理块，并考虑有以下页⾯号引⽤串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1进程运⾏时，先将7, 0, 1三个页⾯依次装⼊内存。

进程要访问页⾯2时，产⽣缺页中断，根据最佳置换算法，选择第18次访问才需调⼊的页⾯7予以淘汰。

然后，访问页⾯0时，因为已在内存中所以不必产⽣缺页中断。

访问页⾯3时⼜会根据最佳置换算法将页⾯1淘汰……依此类推，如图3-26所⽰。

从图中可以看出⾤⽤最佳置换算法时的情况。

可以看到，发⽣缺页中断的次数为9，页⾯置换的次数为6。

访问页⾯70120304230321201701物理块1777222227物理块200004000物理块31133311缺页否√√ √√√√√√√图3-26 利⽤最佳置换算法时的置换图2. 先进先出(FIFO)页⾯置换算法优先淘汰最早进⼊内存的页⾯，亦即在内存中驻留时间最久的页⾯。

该算法实现简单，只需把调⼊内存的页⾯根据先后次序链接成队列，设置⼀个指针总指向最早的页⾯。

但该算法与进程实际运⾏时的规律不适应，因为在进程中，有的页⾯经常被访问。

【精品】页面置换算法实验报告一、实验目的了解操作系统中的页面置换算法，并实现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算法的实现需要维护一个记录页面使用时间的链表或队列。

最佳页面置换算法(Optimal)（非常专业）评价一个算法的优劣,可通过在一个特定的存储访问序列（页面走向）上运行它，并计算缺页数量来实现。

1 先入先出法（FIFO）最简单的页面置换算法是先入先出（FIFO）法。

这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。

理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。

建立一个FIFO队列，收容所有在内存中的页。

被置换页面总是在队列头上进行。

当一个页面被放入内存时，就把它插在队尾上。

这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。

因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。

FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。

当然，导致这种异常现象的页面走向实际上是很少见的。

现在来看下4块的情况：0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2【解答】刚开始内存并没有这个作业，所以发生缺页中断一次。

作业的0号页进入内存。

(1次缺页中断)而页1又不在内存，又发生缺页中断一次。

作业页1进入内存。

(2次缺页中断) 页2不在内存，发生缺页中断。

页2进入内存。

(3次缺页中断)页3不在内存，发生缺页中断。

页3进入内存。

(4次缺页中断)接下来调入页2，页1，页3，页2。

由于都在内存中，并不发生缺页中断。

页5不在内存，发生缺页中断。

页5进入内存，页5置换页0。

(5次缺页中断) 接下来调入页2，页3。

由于都在内存中，并不发生缺页中断。

页6不在内存，发生缺页中断。

页6进入内存。

页6置换页1。

(6次缺页中断) 页2在内存，不发生缺页中断。

页1不在内存(在发生第6次缺页中断时被置换了)，发生缺页中断。

页1进入内存，页2被置换。

(7次缺页中断)页4置换页3，页4进入内存。

(8次缺页中断)现在调入页2，但页2在发生第7次缺页中断时被置换掉了。

常见页⾯置换算法图解前⾔缓存⽂件置换的原因是电脑存储器空间固定,不可能将服务器上所有数据都加载在存储空间中,当需要调⽤不⽤的数据时,那么势必需要将需要的数据进来存储空间替换原有数据常见的缓存⽂件置换⽅法有:先进先出算法（FIFO）：最先进⼊的内容作为替换对象最久未使⽤算法（LRU）：最久没有访问的内容作为替换对象最近最少使⽤算法（LFU）：最近最少使⽤的内容作为替换对象⾮最近使⽤算法（NMRU）：在最近没有使⽤的内容中随机选择⼀个作为替换对象内存的平均引⽤时间为：其中T= 内存平均引⽤时间m= 未命中率 = 1 - (命中率)Tm= 未命中时访问主内存需要的时间 (或者在多层缓存中对下级缓存的访问时间)Th= 延迟，即命中时引⽤缓存的时间E= 各种次级因素, 如多处理器系统中的队列效应衡量缓存的指标主要有两个：延迟和命中率。

同时也存在其他⼀些次级因素影响缓存的性能。

缓存的命中率是指需要的对象在缓存中被找到的频率。

⾼效的置换策略会保留较多的实⽤信息来提升命中率（在缓存⼤⼩⼀定的情况下）。

缓存的延迟是指命中后，从发出请求到缓存返回指定对象所需的时间。

快速的置换策略通常会保留较少的置换信息，甚⾄不保留信息，来减少维护该信息所需要的时间。

每种置换策略都是在命中率和置换之间妥协。

先进先出算法(FIFO)如上图,在⼀个队列中,如果队列未满,添加资源时添加在末尾,如果队列资源已经满了,那么再添加资源时需要先将队列头部的资源移除,腾出空间后再将待添加的资源加⾄队列尾。

代码实现:public class FIFO implements Cacheable {private int maxLength = 0;private Queue<Object> mQueue = null;public FIFO(int _maxLength) {... ...}@Overridepublic void offer(Object object) {if (mQueue == null) {throw new NullPointerException("策略队列对象为空");}// check is need swap or notif (mQueue.size() == maxLength) {clean();}mQueue.offer(object);}@Overridepublic void visitting(Object object) {System.out.println("Visited " + object);}private void clean() {mQueue.poll();}}最久未使⽤算法(LRU)最久未使⽤算法图⽰:对⽐FIFO原理图和LRU原理图，可以很明显地看到只是在被使⽤的资源部分有⼀些⼩的改动。

清华大学操作系统公开课（五）页面置换算法下面介绍在虚拟存储管理中有哪些页面置换算法。

局部页面置换算法最优页面置换算法（OPT，optimal）? 先进先出算法（FIFO）? 最近最久未使用算法（LRU，Least Recently Used）? 时钟页面置换算法（Clock）? 最不常用算法（LFU，Least Frequently Used）? Belady现象? LRU、FIFO和Clock的比较全局页面置换算法工作集模型? 工作集页置换算法? 缺页率置换算法2.页面置换算法当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。

尽可能地减少页面的换进换出次数（即缺页中断的次数）。

具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测。

页面锁定（frame locking）页面锁定技术是用来锁定物理内存中不应该被换出的内存数据。

用于描述必须常驻内存的操作系统的关键部分或时间关键（time-critical）的应用进程。

实现的方法是：在页表中添加锁定标志位（lock bit）。

我们该如何评估不同页面置换算法的优劣？通过程序运行时的效率来比较是不容易实现的，可以记录下一个进程对页面的访问轨迹，然后模拟一个页面置换的行为并且记录产生页缺失的数量，以此比较优劣。

3.最优页面置换算法基本思路当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它下一次访问之前，还需要等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。

这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从知道每一个页面要等待多长时间后才会再次被访问。

可用作其它算法的性能评价的依据（在一个模拟器上运行某个城西，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法）。

物理内存大小为4个帧，刚开始存入的物理帧是a、b、c、d，一共需要载入5个帧，当访问e时发生缺页中断，此时置换入e，置换出d，因为下一次访问d的等待时间最长，暂时用不到d，可以让d待在外存。

页⾯置换算法 页⾯置换算法根据置换页⾯的选择范围分为局部页⾯置换算法和全局页⾯置换算法。

局部页⾯置换算法只置换本进程内的物理页⾯，进程中⼀个页⾯进内存，就代表⼀个页⾯已经被替换出内存，所以⼀个进程所占⽤的物理页⾯的总数是确定的。

全局页⾯置换算法置换内存中所有可换出的物理页⾯，即换进内存的是进程A的页⾯，换出内存的可能是进程B的页⾯，所以进程在内存中占⽤的页⾯总数是可变的。

⼀、局部页⾯置换算法： 1.最优页⾯置换算法：　预测未来最晚被使⽤的页⾯，然后把它置换到外存中去。

缺页最少，但⽆法实现，只是⼀种理想状态，所以作为其他置换算法的评测标准。

2.先进先出算法 有⼀个逻辑页⾯的链表，链表头在内存中呆的时间最长，链表尾最短，所以每次置换都是把链表头的页⾯置换到外存中去，把新加进来的页⾯放到链表尾。

这个算法虽然简单，但是造成的缺页率⽐较⾼，性能⽐较差。

3.最近最久未使⽤算法/最近最少使⽤算法 替换内存中上次被引⽤时间最早的⼀个页⾯。

可以⽤链表或栈来记录按被引⽤时间长短排序的页⾯，但不管是栈还是链表，每次替换都会牵扯到整个链表或栈的移动，算法性能⽐较好，但开销⽐较⼤。

4.时钟算法 ⽤环形链表存储各页⾯。

初始化时各页⾯的访问位为0。

如果不缺页，则把相应页⾯的访问位设置为1。

如果缺页，则从最先进⼊链表的页⾯开始遍历，遇到访问位为1的页⾯，则访问位设置为0；遇到访问位为0的页⾯，则把它替换到外存中去，然后把需要的页⾯替换进内存，且访问位为1。

然后把当前指针移到下⼀个页⾯上，再进⾏下⼀次页⾯请求处理。

⽐FIFO多了个访问位来记录页⾯的访问情况，但⽐LRU少了访问的先后顺序，所以说是FIFO和LRU的折中。

5.改进的时钟算法 在页⾯中增加了修改位，1为修改过，0为未修改过。

因为当发⽣缺页中断时，把未修改过的页⾯替换进外存就相当于把页⾯直接从内存中删除，因为内存和外存中所对应的该页⾯的内容相同，处理时间只有⼀次缺页中断访问外存的时间。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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