超越物理内存限制的内存管理策略

对于一个虚拟内存管理器来说,当有很多空闲内存时,任务是很轻松的。但是生活不会这样。

有很多的限制会迫使 OS 把内存页换出内存中。决定哪个页面被换出去是个极大的挑战。

Cache 管理

在进入具体的策略分析之前,OS 得要知道,换出一个页面对系统的整体影响的指标是什么,决定了这个页面被换出,对系统的影响是怎样的。

引用的一篇论文提出的一个指标:AMAT,Average Memory Access Time。

AMAT = (P[Hit] * T[M]) + (P[Miss] * T[D])

其中 P[Hit] 代表访问内存时名字 Cache 的概率,P[Miss] 代表访问内存时 Cache Miss 的概率(这时候就得去访问磁盘了),注意的是,P[Hit] + P[Miss] = 1
另外,T[M] 是访问内存的时间,T[D] 是访问磁盘的时间。

举个例子,一个 4KB 虚拟地址空间,256字节的页大小,4-bit VPN 号,8-bit 偏移,每个进程可访问 2^4(16) 字节的虚拟页面。

假设在这样一个内存模型下,进程产生以下内存访问序列:0x000, 0x001, 0x002, 0x003, 0x004, 0x005, 0x006, 0x007, 0x008, 0x009,就是前 10 个虚拟页的首地址。

假设现在除了 VPN=3 的页面都已在内存中,那么内存访问序列结果是:hit, hit, hit, miss, hit, hit, hit, hit, hit, hit。我们可以知道 P[Miss]=0.9, P[Hit]=0.1

通常,访问内存的时间 T[M]=100 ns,而访问磁盘的时间 T[D]=10 ms(通常可能更高),
因此 AMAT = 0.9 * 100 ns + 0.1 * 10 ms = 1.00009 ms

可以看到,访问磁盘的时间极大的主导了一次内存访问的时间。

最优替换策略

这个策略我直接写了书上的原句,很好理解为什么它是 The Optimal。

The optimal replacement policy leads to the fewest number of misses overall.

Belady showed that a simple (but, unfortunately, difficult to implement!) approach that replaces the page that will be accessed furthest in the future is the optimal policy, resulting in the fewest-possible cache misses.

Belay 是这一策略的提出者。参见引用。

我们来计算一下,还是采用上面的内存模型,并且内存是冷启动,也就说一开始内存和 Cache 都是空的。

访问序列如下图:
01

HitRate = (Hits) / (Hits + Misess) = 6 / (6 + 5) = 54.5%

但很不幸的是,这是一个非常理想的情况,因为我们不知道未来会发生什么,所以凭直觉不能淘汰最远的访问的页面。

一个简单的替换策略:FIFO

先进先出队列,把页面组织到一个队列当中,当发生 Cache Miss 时,淘汰位于队首的页面。

同前一节,访问序列如下图:
访问序列如下图:
02

此时,可以计算出 HitRate = 36.4%,相比最有策略的 54.5% 有点远,而且 FIFO 的策略是不太合理的,因为它不考虑未来一段时间内的访问策略,比如说上图的序列中,page 0 在未来将近一段时间内是会频繁访问的,但它还是被换了出去。

另外一个简单的策略:随机

这就看脸了,随机数选得好,命中率就会高。

根据历史而来的替换策略:LRU / LFU

这两个策略比较常用

LRU, Least-Recently-Used

LFU, Least-Frequently-Used

针对每个页面,保存有额外的一个值记录被访问的频率或者是最近一次方法的时间。这其实是局部性在拯救这我们。

具体的例子

原文这一段其实是分析各种策略的例子的,具体的数据建议大家去读原文,可以看到的一些数据是 LRU 是一个可以接受的策略,比较接近 OPT 吧。

近似 LRU

clock 算法(参见引用论文《A Paging Experiment with the Multics System》)

下图给出了 Policy 的效果:
03

考虑 Dirty Page

这是对 clock 算法的一个小补充,要考虑到如果页面如果被修改过了,怎么处理的问题。

The reason for this: if a page has been modified and is thus dirty, it must be written back to disk to evict it, which is expensive. If it has not been modified (and is thus clean), the eviction is free; the physical frame can simply be reused for other purposes without additional I/O.

Thus, some VM systems prefer to evict clean pages over dirty pages.
To support this behavior, the hardware should include a modified bit (a.k.a. dirty bit). This bit is set any time a page is written, and thus can be incorporated into the page-replacement algorithm.

内存抖动

这部分其实不太理解,可能得参考引用论文才能理解(偷懒了,没有看)。

引用
《Beyong Physical Memory: Policies》
《Computer Architecture: A Quantitative Approach》
《A Study of Replacement Algorithms for Virtual-Storage Computer》
《A Paging Experiment with the Multics System》

Comments
Write a Comment