超越物理内存:策略

Saturday, November 2, 2019

交换空间:策略

缓存

由于内存只是包含系统所有页的一部分,所以我们可以视为虚拟内存页的缓存,我们的选择页替换策略的时候,目的就是让缓存未命中最少,也就是尽量不要从磁盘获取页。

最优替换策略

最优替换策略将替换内存中在最远处才会被访问的页,从而达到缓存未命中率最低。但这是很难实现的,因为我们并不知道未来的访问是怎样,但与这个策略对比能让我们找到一个接近此策略的参考。

简单策略:FIFO

先进先出,当发生替换时,尾部的页被踢出。FIFO 的优势就是实现非常简单。

FIFO 的问题是根本无法确定页的重要性,即使某页经常被访问,FIFO 仍会将其踢出。

随机策略

随机策略取决于运气

利用历史数据:LRU

这种基于历史的算法有,LFU(最不经常使用),LRU(最少最近使用)等。

如图所示的 LRU 替换记录:

OS22.1

另外还有一些相反的策略,最经常使用策略(MFU),最近使用策略(MRU),但这类策略在大多数情况下并不好用,因为忽视了程序的局部性特点。

工作负载示例

我们看看80-20的负载环境下,不同的策略效果如何,可以看到,LRU 策略明显优于 FIFO 和随机策略

OS22.2

再看看循环顺序的工作负载

OS22.3

可以看到,此时 FIFO 和 LRU 表现的都非常差,是0%,比如缓存大小是49页,而50个页面循环工作,这两种策略方式命中率都会为0,远不如随机策略表现的出色。

实现基于历史信息的算法

为了实现 LRU,我们需要做很多工作,在每次访问时,都必须更新一些数据,从而将该页移动到列表的前侧,这种操作如果不小心,这样的记录反而会极大的影响性能。

有一种方法可以加速,就是增加硬件的支持,在访问每个页的时候,更新内存中的时间字段(可以在页表中,也可以在某个单独的数组中,每个物理页有一个),当需要替换时,简单扫描所有页的时间段可以找到最近最少使用的页。

但是当内存变大时,扫描的页将急剧增大,扫描时间需要很长。所以实现 LRU 成本太高,我们需要实现一个近似的算法。

近似 LRU

近视 LRU 是许多现代操作系统的做法,这个需要硬件增加一个使用位,比如使用位存在每个进程的页表中,或者单独一个数组中。每当页被引用,就设为1,但是硬件不会清除该位(即设为0),这个由操作系统负责。

操作系统使用一个始终算法,将所有页放在一个循环列表中,时钟指针指向其中一页,哪一页并不重要。当要进行替换时,操作系统检查时钟指针指向的页是否为0,如果为0则替换该页。如果为1,则置为0,并指向下一页,再检查是否为0,直到检查到一页为0的为止。

OS23.4

OS

并发:介绍

超越物理内存:机制