内存管理特性分析(十八):MGLRU(Multi-Gen LRU)技术原理分析 已经整理的很全面了, 本文只是对其进行少量的再加工
由于cache比DRAM贵和快,DRAM比flash贵和快,这在未来一段时间里也将会如此.在这样的背景下,DRAM的性能在现代操作系统性能中仍然扮演着重要角色.要获得最好的性能,就需要假装我们的内存比真实性能更多. 那么问题的关键就是系统需要决定什么时候应该将哪些对象缓存在内存中
现代操作系统中使用经典「LRU」 (Least Recently Used)已经相当长时间了,它虽然效果在一些场景的性能欠佳,表现不是特别令人满意,但其简单易懂的算法逻辑和多年使用保持稳定使得它在内核中多年坚强地成为默认的内存回收算法.
Zhao Yu认为当前经典LRU存在明显缺陷:
另一个角度看, 我们希望操作系统做到的页面 LRU 应该是:
Google的Zhao yu工程师对内核内存管理子系统进行了重大改造,提出了MGLRU.MGLRU 是一种替代的 LRU 实现,它可以优化页面回收,并能在内存压力下提高性能.页面回收决定了内核的缓存策略,也决定了内核过载使用内存的能力.它直接影响 kswapd 内核线程的 CPU 占用率和 RAM 的利用效率.MGLRU在6.1内核合入主线
查找哪些页面是最近访问过的是所有LRU实现的核心.MGLRU使用多个代中的每一代来表示具有类似访问顺序的页面组.每个"代"是一个页面群体,它们的访问时间相似."代"的建立形成了一个基于时间的共同参考框架,有助于更好地做出决策.
通过代的划分,MGLRU可以做出更明智的选择,比如选择计算机上合适的memcg (内存控制组)或在数据中心中将任务分配给不同的计算机进行作业调度.通过考虑每个代内页面访问的顺序,MGLRU能够更准确地跟踪和管理内存资源,提高效率和性能.
举个例子,当我们打开一个浏览器并开始浏览网页时,我们往往会访问一系列相关的页面,例如打开一个新的标签,然后在该标签上进行搜索,点击搜索结果中的链接等等.这些页面的访问顺序可能非常相似.在MGLRU中,我们将这些相关的页面划分为一个代.假设我们在浏览器中打开了五个页面,并且按照顺序访问它们:网站A、网站B、网站C、网站D和网站E.在代1中,我们会将这五个页面作为一个整体记录,并记住它们的访问时间. 现在,当我们继续浏览其他页面,然后再次回到之前浏览的这组相关页面时,MGLRU会注意到代1的这五个页面的访问时间是较为接近的.这意味着这些页面很可能与我们当前的浏览会话相关,因此对于这些页面的缓存和管理,MGLRU会更加重视和优先考虑.
通过这种方式,MGLRU能够根据页面的访问顺序将其分组,从而更准确地确定哪些页面是当前活跃的,以便更好地进行资源分配和决策.这个例子显示了MGLRU设计目标中 「良好的表示页面访问的最近性」 的意图,即通过将页面分组,提供对访问顺序的更准确表示
利用空间局部性可以提高获取访问位时的效率.这意味着当数据和指令在时间和空间上紧密相邻地访问时,我们可以更高效地获取访问位信息.
MGLRU目的是优化两种方法,并将它们结合使用.这样可以在不引入不必要开销的情况下,同时利用空间局部性和年轻PTE的信息,从而提高MGLRU算法的效率和性能.通过优化这两种方法,可以更好地支持访问位信息的获取,并提高系统的整体性能.
举个例子,假设我们有一个虚拟内存系统,其中有一段连续的物理页面被分配给一个进程.进程在执行期间会频繁地访问这些页面.在MGLRU中,当反向映射看某单一页面的PTE的reference bit,通过使用"look around"的策略,考虑特定 PTE 周围的几十个 PTE的reference bit.具体来说,当一个页面被访问时,MGLRU会检查其相邻的页面,并记录下它们被访问的信息.通过这种方式,MGLRU能够更高效地获取访问位信息,而不仅仅依赖于单个页面的访问情况.这样可以更好地利用空间局部性,并提高访问位信息的获取速度,从而提高整个系统的效率和性能. 因此,"look around"的实现确实是为了实现作者所描述的目标,即利用空间局部性来提高访问位信息的获取效率.这对于优化MGLRU算法的性能非常重要
通过系统调用(syscall)访问的文件数据仅存储在内核的 pagecache 缓存中,没有映射到任何进程的虚拟内存,因此不需要反向映射操作,内核处理这些页面时开销较低.
被多个进程映射的页面(例如通过 mmap):这些页面被多个进程共享,当内核扫描或回收这些页面时,需要使用反向映射找到所有进程并更新页表,开销更大.
操作系统需要回收内存中的页面以腾出空间给新数据.当选择回收哪些页面时,系统会优先回收很久没有被访问的页面,而不是最近经常使用的页面
Refault 是指页面被系统回收后,又很快被重新访问,导致缺页异常(即该页面需要重新加载到内存中).这是一个重要的信号,表明该页面可能在短期内仍然有用,因此当初回收它是一个不好的决定. 因此如果系统回收了很多很快发生 refault 的页面,说明它的页面选择策略需要调整,以避免频繁的缺页异常
MGLRU 的一个特点是,它在同一代中的页面可以根据其他因素进行进一步的分类,例如页面的访问频率、类型(比如代码页面 vs. 数据页面)、页面的映射状态等.这种分类使得系统可以基于更细粒度的信息来做页面回收的决策,而不仅仅依赖页面属于哪一代
在页面回收后,系统会监控哪些页面很快发生了 refault.通过统计和比较不同类别中发生 refault 的比例,系统可以判断哪些类型的页面容易被错误回收,并相应调整回收策略.这种反馈回路可以帮助系统"学习"哪些页面在回收时更容易造成错误,从而逐渐优化其选择策略.
MGLRU 加入了 PID 控制器(proportional-integral-derivative 比例-积分-衍生), 这是一种经典的反馈控制机制,常用于自动调节系统的行为.它通过以下三部分来调整系统:
根据当前的错误(在这里指的是 refault 的发生率),立即调整页面回收策略.例如,如果最近回收的页面 refault 率较高,系统可能会减少对这一类型页面的回收频率.
通过对过去一段时间内的累计误差(总的 refault 次数)进行调整.它会考虑历史上的错误决定并相应进行调整,以防止页面回收的决策反复偏向同一个错误方向.
比如,如果过去一段时间一直有较高的 refault 率,系统会更大幅度地调整策略,以减少进一步错误.
通过预测未来的趋势来做出预判,防止系统过于剧烈地调整.它根据错误变化的速度来决定是否调整得太快或者太慢.
如果 refault 率开始上升但变化趋势较平缓,PID 控制器可能会避免过度调整,保持稳定的回收决策.
MGLRU 的核心思想是将内存分为若干个 bucket,称为 "generations (世代)".一个 page 的 generation 值就反映了它的 "年龄",即距离该 page 被最后一次访问有多长时间了.这些 page 的管理是由 "两个表针的时钟" 的机制完成的.
MGLRU通过以下核心改动来改善上面提到的现有LRU存在有不足: