页面置换算法简介

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

页面置换算法的好坏，将直接影响系统的性能，常见的页面置换算法：

• 最佳置换算法（OPT）
• 最近未使用页面置换算法（NRU）：
• 先进先出置换算法（FIFO）
• 最近最久未使用算法（LRU）
• 最少使用置换算法（LFU）

一个好的页面置换算法，应做到减少页面置换的频率，尽量将以后不会用到的或较长时间不会使用的页面给置换出。

下面，我们主要介绍一下应用比较广泛的页面置换算法：LRU 和 LFU 算法。

LRU和LFU算法

它们的区别如下：

• LRU：最近最少使用(最长时间)淘汰算法（Least Recently Used），LRU会淘汰最长时间没有被使用的页面。
• LFU：最不经常使用(最少次)淘汰算法（Least Frequently Used），LFU会淘汰一段时间内，使用次数最少的页面。

它们的应用场景：

• LRU：消耗CPU资源较少，适合较大的文件比如游戏客户端（最近加载的地图文件）;
• LFU：消耗CPU资源较多，适合较小的文件和零碎的文件比如系统文件、应用程序文件 。

算法实现

LRU算法

题目：Leetcode.16.25

面试题 16.25. LRU 缓存

思路

利用Hash表和双向链表维护所有的节点数据，Hash表能在\(O(1)\)的时间内查找数据，双向链表能在\(O(1)\)时间内进行数据插入和删除。

代码实现

class DLinkedNode(object):
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    @staticmethod
    def _remove_node(node: DLinkedNode):
        """ 双向链表删除一个节点 """
        node.next.prev = node.prev
        node.prev.next = node.next
        return node

    def _add_to_head(self, node: DLinkedNode):
        """ 将一个节点插入到双向链表的头部 """
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        return

    def _remove_tail(self) -> DLinkedNode:
        """ 删除双向链表尾部的元素 """
        return self._remove_node(self.tail.prev)

    def _move_to_head(self, node: DLinkedNode):
        """ 将一个任意节点移动到双向链表头部 """
        self._remove_node(node)
        self._add_to_head(node)

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache.get(key)
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            new_node = DLinkedNode(key, value)
            self.cache.update({key: new_node})
            self._add_to_head(new_node)
            self.size += 1
            if self.size > self.capacity:
                old_node = self._remove_tail()
                self.cache.pop(old_node.key)
                self.size -= 1
        else:
            node = self.cache.get(key)
            node.value = value
            self._move_to_head(node)

LFU算法

思路

代码实现

原文地址：http://www.cnblogs.com/larry1024/p/16906492.html