核心 · 操作系统第 4 课 / 共 6 课免费阅读

页面置换与 LRU · 操作系统

内存满了，该把哪一页赶出去？

为什么需要它

内存只能放下有限的页，每次没命中都意味着一趟很慢的磁盘读取。赶走哪一页，决定了这种情况多常发生。同样的问题出现在每一种缓存里：CPU 缓存、浏览器缓存、Redis、CDN。LRU 是你会一遍又一遍实现的答案。

直觉理解

3 个页框，页请求序列 1 2 3 1 4 1 2：

FIFO 赶走最早进来的页，哪怕它一直在被使用。
LRU（最近最少使用）赶走最久没被碰过的页。最近用过的，将来很可能还会用，所以 LRU 通常缺页更少。

数缺页次数（未命中）来比较策略。在 Python 里，collections.OrderedDict 让 LRU 很好写：每次使用时 move_to_end(key)，淘汰时 popitem(last=False) 弹出最老的。

定义

LRU 最近最少使用

Least recently used: evict the item whose last use is oldest.
最近最少使用：淘汰上一次使用时间最早的那个。

命中率

The share of requests answered from the cache. 1 − hit rate is the miss rate; every miss costs a slow fetch.
直接从缓存得到答案的请求所占的比例。1 − 命中率就是未命中率；每次未命中都要付出一次慢的读取。

示例

FIFO 对比 LRU

动手试试

同样的请求，同样 3 个页框，两种策略。

from collections import OrderedDict, deque

def fifo(requests, frames):
    mem, order, faults = set(), deque(), 0
    for p in requests:
        if p not in mem:
            faults += 1
            if len(mem) == frames:
                mem.discard(order.popleft())
            mem.add(p)
            order.append(p)
    return faults

def lru(requests, frames):
    mem, faults = OrderedDict(), 0
    for p in requests:
        if p in mem:
            mem.move_to_end(p)
        else:
            faults += 1
            if len(mem) == frames:
                mem.popitem(last=False)
            mem[p] = True
    return faults

reqs = [1, 2, 3, 1, 4, 1, 2, 5, 1, 2]
print(fifo(reqs, 3), lru(reqs, 3))

逐步执行

L9FIFO 扔掉最早进来的，哪怕是被频繁使用的第 1 页。
L18LRU 每次使用都刷新一个页的位置。
L22淘汰最近最少使用的。
L27在这个访问模式下，LRU 缺页更少。8 6

常见错误

缓存越大，缺页一定越少？

对 FIFO 来说不一定：某些请求模式下，多加一个页框反而缺页更多（Bélády 异常）。LRU 没有这个问题。

命中时忘了刷新

只记录插入时间的 LRU，其实是伪装的 FIFO。每次使用都必须把它挪到最前面。

小测验

1. 页框里有 1、2、3；第 1 页最近刚用过，第 2 页最久没用。请求第 4 页。LRU 赶走……

A第 2 页
B第 1 页
C第 3 页

查看答案

答案：A

最近最少使用的那个。

2. 这段代码会输出什么？

from collections import OrderedDict
cache = OrderedDict()
for key in ["a", "b", "c", "a", "d"]:
    if key in cache:
        cache.move_to_end(key)
    else:
        if len(cache) == 3:
            cache.popitem(last=False)
        cache[key] = True
print(list(cache))

A
```
['c', 'a', 'd']
```
B
```
['b', 'c', 'd']
```
C
```
['a', 'b', 'd']
```

查看答案

答案：A

使用 a 会刷新它，所以 d 到来时 b 是最老的。

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

预测输出数 FIFO 的缺页
准确写出这段程序的输出。
改需求把 FIFO 改成 LRU
LRUCache 应该淘汰最近最少使用的键，但 get 没有刷新键的位置，所以它的行为像 FIFO。修好 get（以及 put 更新已有键的情况），让每次使用都把键挪到最后。
从零写数 LRU 的缺页
写函数 lru_faults(requests, frames)，返回在给定页框数下，LRU 处理这串请求时的缺页次数。用列表或 OrderedDict 都可以。

在互动课里练这一课

打开互动课，这些例子都能直接改、直接运行，练习题提交马上判题。免费开始，不用注册。

打开互动课课程地图

互动课按顺序解锁：前面的课还没学，会先带你到课程地图。

本课术语

术语	中文	英文定义
Cache	缓存	A small fast store holding copies of data that is slow to fetch.
LRU	最近最少使用	Evict the item not used for the longest time.
Hit rate	命中率	The share of requests served from the cache.