页面置换算法比较

❶ 页面置换算法的常见的置换算法

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间 时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。
LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
1.计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做， 不仅要查页表，而且当页表改变时（因CPU调度）要 维护这个页表中的时间，还要考虑到时钟值溢出的问题。
2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。
4）Clock置换算法（LRU算法的近似实现）
5）最少使用（LFU）置换算法
在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访 问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。
LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。
6）工作集算法
7）工作集时钟算法
8）老化算法（非常类似LRU的有效算法）
9）NRU(最近未使用）算法
10）第二次机会算法
第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是 0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。
第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个 存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。

❷ 操作系统题：页面置换算法 OPT FIFO LRU

fifo就是先进先出，可以想象成队列
lru是最久未使用，当需要替换页面的时候，向前面看，最久没使用的那个被替换
opt是替换页面的时候，优先替换后面最迟出现的。
不懂再问。。

❸ 操作系统课程设计，用C#实现内存页面的置换。实现算法间比较

页面置换算法

一．题目要求：

通过实现页面置换算法的FIFO和LRU两种算法，理解进程运行时系统是怎样选择换出页面的，对于两种不同的算法各自的优缺点是哪些。

要求设计主界面以灵活选择某算法，且以下算法都要实现 1) 最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。

2) 先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。 4) 最不经常使用算法(LFU) 二．实验目的：

1、用C语言编写OPT、FIFO、LRU，LFU四种置换算法。 2、熟悉内存分页管理策略。 3、了解页面置换的算法。 4、掌握一般常用的调度算法。 5、根据方案使算法得以模拟实现。 6、锻炼知识的运用能力和实践能力。 三、设计要求

1、编写算法，实现页面置换算法FIFO、LRU；

2、针对内存地址引用串，运行页面置换算法进行页面置换； 3、算法所需的各种参数由输入产生（手工输入或者随机数产生）； 4、输出内存驻留的页面集合，页错误次数以及页错误率；

四．相关知识：

1．虚拟存储器的引入：

局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。

2．虚拟存储器的定义：

虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

3．虚拟存储器的实现方式：

分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。

请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。

4．页面分配：

平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法，根据进程的大小按比例分配物理块。

考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。

5．页面置换算法：

常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、设计说明

1、采用数组页面的页号

2、FIFO算法，选择在内存中驻留时间最久的页面予以淘汰；

分配n个物理块给进程，运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。

3、LRU算法，根据页面调入内存后的使用情况进行决策；

同样分配n个物理块给进程，前n个不同页面一起装入内存，后面步骤与前一算法类似。

选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换： 六．设计思想：

OPT基本思想：

是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

FIFO基本思想：

是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。

LRU基本思想：

是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。 七．流程图：

如下页所示

六．运行结果： 1. 按任意键进行初始化：

2. 载入数据：

3. 进入置换算法选择界面：

4.运算中延迟操作：

5.三种算法演示结果：

❹ 页面置换算法

在瞎启虚程序的执行过程中，当所访问的信息不在内存时，会由操作系统负责将所需信息从外存调入内存，然后再继续执行程序，如果在调入内存时，发现内存空间不够，会由操作系统负责将内存中暂时用不到的信息换出到外存,由于频繁的进行IO操作会影响计算机性能，所以我们需要使用合适的算法来进行页面的置换。这里介绍几种常见的页面置换算法：

每次选择淘汰的页面将是以后永不使用，或者在最长时间不再被访问的页面，这样可以保证最低的缺页率。但是实际上进程执行的过程才能知道接下来会访问到的是哪个页面，操作系统无法预知，因此最佳置换算法是一种 理想化 算法，无法实现。

每次旁纯选择淘汰的页面是最早进入内存的页面，这种算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问，因此该算法性能磨燃很差。

每次淘汰的页面是最近最久未被使用的页面，需要有额外的内存空间来记录该页面自上次被访问以来所经过的时间，但是性能很好。

该算法是一种性能和开销较均衡的算法，又称最近未使用算法（NRU）。每个页面需要额外添加两个标志位：访问位（0代表最近没有被访问，1代表最近被访问）、修改位（0代表最近没有被修改，1代表最近被修改过）。如果淘汰的页面最近是被修改过，那么淘汰该页面前会进行写入外存的IO操作，使性能变差，所以在其他条件都相同的情况下，应优先淘汰没有修改过的页面。

算法规则：将所有可能被置换的页面排成一个循环队列 （访问位， 修改位）

第一轮：从当前位置开始扫描到第一个（0，0）的页用于替换。

第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0，1）的页面用于替换，同时将扫描过的页面的访问位设为0。例如（1，0）变成（0，0）

第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0，0）的页面用于替换。

第四轮：若第三轮扫描识别，则重新扫描，查找第一个（0，1）的页面用于替换。本次扫描必定会有一个页面被选中。

❺ 计算机操作系统页面置换算法的问题

第二次机会算法：

与FIFO、OPT、LRU、NRU等同为操作系统中请求分页式管理方式的页面置换算法。

第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，依然和FIFO一样，选择最早置入内存的页面。但是二次机会法还设置了一个访问状态位。所以还要检查页面的的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置为1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。

❻ 页面置换算法

  上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
   本文内容

  算法思想：每次选择 淘汰的页面 将是 以后永不使用 ，或者 在最长时间内不再被访问的页面 ，这样可以保证最低的缺页率。
  举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

  ....按照此算法依次执行，最后的结果如下

  结果图

  注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
  最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此， 最佳置换算法是无法实现的 。

  算法思想：每次选择 淘汰的页面是最早进入内存的页面。
  该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4
  分配三个内存块的情况：

  分配四个内存块的情况：

  当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为 贝莱迪（Belay）异常 。
   只有FIFO算法会产生Belay异常。 另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此， 算法性能差。

  算法思想： 每次淘汰的页面是最近最久未使用的页面。
  实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面纯亏自上次被访问以来所经历的时间t。 当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。

  举例说明，加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
  这里先直接给出答案

  结果图

  最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法 是一种 性能和开销均春裤配平衡 的算法。又称 CLOCK算法 ，或 最近未用算法 （ NRU ，Not Recently Used）
   简单CLOCK算法 算法思想：为每个页面设置一个 访问位 ，再将内存中的页面都通过 链接指针链接成一个循环队列 。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个扒指淘汰页面最多会经过 两轮扫描 ）。

  这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。

  简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。 只有淘汰的页面被修改过时，才需要写回外存。
  因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
  改进型时钟置换算法的 算法思想 ： 在其他在条件相同时，应该优先淘汰没有被修改过的页面， 从而来避免I/O操作。
  为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
   算法规则 ：将所有可能被置换的页面排成一个循环队列

  由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此 改进型CLOCK置换算法最多会进行四轮扫描。

  假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图

  如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。

  某一时刻页面状态如下

  如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
  然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。

  某一时刻页面状态如下

  第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
  然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图

  某一时刻页面状态如下

  具体的扫描过程和上面相同，这里只给出最后的结果，如下图

  所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
  (1) 第一优先级淘汰的是 最近没有访问且没有修改 的页面。
  (2) 第二优先级淘汰的是 最近没有访问但修改 的页面。
  (3) 第三优先级淘汰的是 最近访问但没有修改 的页面。
  (4) 第四优先级淘汰的是 最近访问且修改 的页面。