什么是页面置换算法

进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区，其中选择调出页面的算法叫做。。。
好的页面置换算法应该有较低的页面更换频率。——也就是说应将以后不会再访问或者以后长时间不会再访问的页面先调出。

常见的页面置换算法

1 先进先出算法 （FIFO first in first out）

FIFO是最简单的页面置换算法，FIFO为每个页面记录了调到内存的时间，当必须置换页面时会选择最旧的页面，

FIFO算法当进程分配到的页面数增加时，缺页终端的次数可能增加也可能减少。

基于队列实现
注意：内存的页面中“最老“的页面，会被新的网页直接覆盖，而不是“最老“的页面先出队，然后新的网页从队尾入队。
**
注意，并不需要记录调入页面的确切时间，可以创建一个 FIFO 队列，来管理所有的内存页面。置换的是队列的首个页面。当需要调入页面到内存时，就将它加到队列的尾部
FIFO 页面置换算法易于理解和编程。然而，它的性能并不总是十分理想：
其一，所置换的页面可以是很久以前使用过但现已不再使用的初始化模块
其二，所置换的页面可以包含一个被大量使用的变量，它早就初始化了，但仍在不断使用

FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由 Belady于1969年发现，故称为Belady异常，如图3-28所示。只有FIFO算法可能出现Belady 异常，而LRU和OPT算法永远不会出现Belady异常。

2 最佳置换算法 （OPT，不可能实现）看未来

淘汰以后不会使用的页面
FIFO 和 OPT 算法的区别在于：除了在时间上向后或向前看之外，FIFO 算法使用的是**页面调入内存的时间，OPT 算法使用的是页面将来使用的时间**

3 LRU（最近最少使用算法）看过去

（淘汰最近没有使用的页面）
选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰

OPT 和 LRU 算法的区别在于：
LRU 算法根据各页以前的情况，是“向前看”的，而最佳置换算法则根据各页以后的使用情况，是“向后看”的
LRU 性能较好，但需要寄存器和栈的硬件支持
LRU 是堆栈类的算法，理论上可以证明，堆栈类算法不可能出现 Belady 异常

146. LRU缓存机制 MEDIUM

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

示例: LRUCache cache = new LRUCache( 2 / 缓存容量 / );
cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 该操作会使得关键字 2 作废

cache.get(2); // 返回 -1 (未找到)

cache.put(4, 4); // 该操作会使得关键字 1 作废

cache.get(1); // 返回 -1 (未找到)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

通过次数93,371提交次数184,769

class LRUCache:
    def __init__(self,capacity):
        self.capacity = capacity
        self.cache = {}
        self.used_list = []
    def get(self,key):
        val = self.cache.get(key,-1)
        if val != -1 :
            # key in cache 已在页表中不缺页
            # key 放在表尾表示最近刚被使用的顺序
            self.used_list.remove(key)
            self.used_list.append(key)
    def put(self,key,value):
        if key in self.cache:
            self.used_list.remove(key)
        elif len(self.cache) == self.capacity:
            self.cache.pop(self.used_list.pop(0))
        self.used_list.append(key)
        self.cache[key] = value

使用collections.OrderedDict()

class LRUCache:
    def __init__(self,capacity):
        self.capacity = capacity
        self.cache = collections.OrderedDict()
    def get(self,key):
        val = self.cache.get(key,-1)
        if key in self.cache:
            self.cache.move_to_end(last = True)    # 移动到末尾
        return val
    def put(self,key,value):
        self.cache[key] = value
        self.cache.move_to_end(key,last=True)
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False) # 先进先出返回

4 Clock 时钟置换算法

5 LFU 最不常用算法

6 MFU 最长使用算法