Linux用的是什么页面置换算法

第二次机会算法： 与FIFO、OPT、LRU、NRU等同为 *** 作系统中请求分页式管理方式的页面置换算法。 第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，依然和FIFO一样

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

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

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

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

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

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

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

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

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

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

lru算法是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

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

特点：

LRU 置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：寄存器或栈。

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。

---