2

O(1)我们能否在（即恒定时间）内获得 LRU（最近最少使用）页面替换算法？

如果可能，请给出算法。

4

2 回答 2

2

双向链表可以使用 O(1) 操作实现 LRU 队列。已使用的节点可以从其旧位置取消链接，并在恒定时间内重新链接到队列的头部。

请注意，如果您想将其用作页面替换方法，您仍然需要弄清楚如何使用 MMU 统计信息来有效地更新队列。

于 2012-04-11T17:31:18.467 回答
0

在维基百科中，有几个 LRU 页面算法的引用，包括实现的链接。选项包括：

  • 链表
  • LRU-K
  • 弧
  • 硬件支持
于 2012-04-11T17:33:52.940 回答