目录
页面置换算法简介
在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
页面置换算法的好坏，将直接影响系统的性能，常见的页面置换算法：
- 最佳置换算法（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
思路
利用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)