[What]swapping:Policies

理解交换策略,当内存吃紧时,系统是如何决定哪个内存页面应该被置换到交换分区中的?

page cache 管理

主存于硬盘来讲就是一个 cache,当使用置换策略时,目标当然是最大的保证 page cache hit,而避免 page cache miss。

有个指标叫做 内存平均访问时间(average memory access time, AMAT) 用于计算 page cache hit 和 page cache miss:

mempic/swap/AMAT.jpg
  • TM : 访问内存消耗时间
  • TD : 访问硬盘消耗时间
  • PMiss : 要访问的页面未驻留于内存的系数,取值范围 0.0 ~ 1.0

上面这个公式的意思是:当未出现 page cache miss 时,访问内存的时间就是访问物理内存的时间。 而当出现 page cache miss 时,就是访问物理内存的时间加上访问硬盘的时间。

假设一个进程的虚拟地址空间是 4KB,页大小为 256 字节,那么就需要高 4 位表示页索引,低 8 位表示页内偏移。

假设该进程依次访问虚拟地址:0x000,0x100,0x200,….,0x900,那么其就是以此访问第 1 页 ~ 第 10 页的第 1 个字节。

再假设虚拟页面 3 对应的内容并没有被读入到内存,而是需要从硬盘读取,而其他页面都驻留在了内存,那么其 PMiss 就是 0.1(10 次中有 1 次 miss)。

假设访问一次内存的时间是 100 ns,访问一次硬盘的时间是 10 ms,那么可以计算出其 AMAT 值为 1.0001 ms。

可以看到虽然仅有 10 % 的 page cache miss,但其会极大的影响内存平均访问时间。

假设 PMiss 是 0.001 ,那么最终的 AMAT 值为 10.1 us,相比前面时间也减少了 100 倍。

所以要尽量的降低 PMiss,因为它会内存平均访问时间影响显著,这个就是置换策略需要考虑的事了。

最佳理想置换策略

既然是理想置换策略,也就是说这个策略可以达到最小的 page cache miss:替换掉将来最少使用的内存页面。

假设 page cache 可存 3 个页面,此策略执行逻辑如下表:

访问的页面 是否命中 置换 当前的 page cache
0 miss   0
1 miss   0,1
2 miss   0,1,2
0 hit   0,1,2
1 hit   0,1,2
3 miss 2 0,1,3
0 hit   0,1,3
3 hit   0,1,3
1 hit   0,1,3
2 miss 3 0,1,2
1 hit   0,1,2

如上标所示:

  • 刚开始由于内存中并没有驻留对应的 page cache,所以前 3 次都会造成 page cache miss
  • 然后再次访问 0,1 页面后,预测接下来访问页面 2, 但实际上访问页面 3,所以置换出页面 2
  • 再来到下一次访问页面 2,预测接下来访问页面 3, 但实际上访问页面 2,所以置换出页面 3

上面这个理想策略的难点就在于如果实现预测接下来会访问哪个页面。

简易策略:FIFO

FIFO 策略就是将最先进入队列的页面置换出去。

还是基于上面的假设,使用 FIFO 策略的置换逻辑如下表:

访问的页面 是否命中 置换 当前的 page cache
0 miss   0
1 miss   0,1
2 miss   0,1,2
0 hit   0,1,2
1 hit   0,1,2
3 miss 0 1,2,3
0 miss 1 2,3,0
3 hit   2,3,0
1 miss 2 3,0,1
2 miss 3 0,1,2
1 hit   0,1,2

可以看到 FIFO 策略比理想策略多了两次 miss,但是其算法实现起来很简单。

另一个简易策略:随机化

随机化策略就是随机的取出一个页面置换出去。

其实现方式也比较简单,但是其效果也是随机的。

使用历史的策略:LRU

LRU 策略的核心在于其假设:如果一个页面最近访问了,那么它既有可能将来还会被访问到,这和时间局部性原理一样。

LRU 通过记录一个页面的访问顺序,来选择出最近最少使用(Least-Recently-Used,LRU)的页面置换出去。

  • 对应的还有 LFU 通过记录页面的访问频率,来选择出最近使用频率最少(Least-Frequently-Used,LFU)的页面置换出去。

使用 LRU 后的置换逻辑如下表:

访问的页面 是否命中 置换 当前的 page cache
0 miss   0
1 miss   0,1
2 miss   0,1,2
0 hit   1,2,0
1 hit   2,0,1
3 miss 2 0,1,3
0 hit   1,3,0
3 hit   1,0,3
1 hit   0,3,1
2 miss 0 3,1,2
1 hit   3,2,1

可以看到,LRU 策略的效果在这个例子中已经和理想策略一致了,真是优秀!

多策略比较

随机访问

假设随机的访问 100 个页面,一共访问 10000 次,而 page cache 的大小从 1 到 100,那么测试结果如下:

mempic/swap/policy_cmp.jpg

可以看到,在随机访问页面的情况下:

  • 各种策略的 cache hit 效率都几乎一致,只与 page cache 的大小相关
  • 当 page cache 大小等于访问页面大小时,其效率便与理论效率一致了

有规律的访问

下面假设 80% 的访问都聚集在 20% 的页面,而 20% 的访问都分散在 80% 的页面,测试结果如下:

mempic/swap/policy_cmp2.jpg

可以看到,在有规律的访问页面的情况下:

  • FIFO 和随机策略的效率差不多,而 LRU 效果确实高于前面两者
  • 只有在 page cache 大小达到一定数量时,LRU 策略才有明显优势。

循环访问

假设我们先总共只访问 50 个页面,但是是依次从 0 ~ 49 这样顺序访问,一共访问 10000 次,随着 pagecache 的增大,其曲线如下:

mempic/swap/policy_cmp3.jpg

可以看到:

  • 在 pagecache 页面小于 50 时的顺序访问,LRU 和 FIFO 策略的效率都为 0,而随机策略随着 pagecache 增大而增大
  • 当 pagecache 页面大于或等于 50 时,由于 pagecace 页面可以装下所有页面,所以效率到了 100%
  • 由于顺序执行,其预测与实际一致,所以理论效率随着 pagecache 增加而线性增加。

这些测试结果也说明了:不是在任何情况下,LRU 都是最优策略。

实现历史算法

为了实现 LRU 算法,我们需要:

  • 将访问的页面放入一个列表中,当有置换要求时取出列表头,当有新页面加入时,放入列表尾
  • 记录每次内存页面的访问,这样才能为列表排序
    • 这样一定会降低性能

为了提高性能,可以让硬件来完成每次访问页面的时间记录,比如硬件可以刷新该页对应的页表项中的时间域

  • 这样在进行页面置换时,系统可以查找出最近最少使用的页表项,而置换该物理页面

但是查找这么多页面所需要的 CPU 时间也是不容忽视的!

近似 LRU

实际上的实现是:在页表项中使用一个位(use bit / reference bit)来表示该页面是否被访问过,如果被访问则由硬件主动将此位置 1。

操作系统有一个指针指向了该进程的页表项。 在遇到需要置换的场景时,判断当前页表项的访问位是否置 1,如果为 1 则代表该页面最近被使用过,那么将其位清零。 然后继续寻找下一个,直到找到访问位为 0 的页表项,然后将对应的物理内存置换出去。

mempic/swap/policy_cmp4.jpg

上图可以看出这种近似 LRU 算法的效率接近理论上的 LRU 算法。

Last Updated 2020-03-29 日 23:05.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.1.14)