一、概述

MGLRU是一种新型内存管理算法，它的出现是为了弥补传统LRU（Least Recently Used）和LFU（Least Frequently Used）算法在缓存替换选择上的不足,LRU和LFU的共同缺点就是在做内存页面替换时，只考虑内存页面在最近一段时间内被访问的次数和最后一次的访问时间，但是一个页面的最近访问次数少或者最近一次的访问时间较早，可能仅仅是因为这个内存页面新近才被创建，属于刚刚完成初始化的年代代页面，它的频繁访问往往会出现在初始化之后的一段时间里，那么这时候就把这种年轻代的页面迁移出去，一般都会造成不必要的内存消耗与进程卡顿，为了解决这一问题MRLRU算法Linux6版本内核中逐步引入用于Linux内核的虚拟内存子系统。

MGLRU在Android系统中的应用旨在改进应用程序的启动时间和整体性能，特别是通过更有效地管理和回收内存来缓解“杀后台”问题。在Android 13及之后版本中，Google开始将MGLRU整合到Android系统中，以改善内存分配和回收策略。该算法通过引入多代LRU列表组织内存页，根据页面的使用频率和活跃程度将其划分到不同的世代，从而使得操作系统能够更快地识别出哪些内存页是较旧且可能不再需要的，进而提升内存利用率和App启动速度。

到了Android 14，谷歌进一步默认启用Linux内核的MGLRU功能，这一举措预期可以减少应用程序的启动时间，并有助于增强用户体验，特别是在资源有限的移动设备上，有效避免因内存不足导致的应用程序被强制关闭的问题。根据谷歌在 Linux Plumbers 大会上的演示，Pixel 6 手机开启 MGLRU 后App 的总体启动时间减少了约 6.60%，总体杀后台减少 8.04%，kswapd CPU 使用减少了 54.50%，直接回收次数减少 81.10%。

二、工作原理

MGLRU结合了LRU和LFU（Least Frequently Used）算法的优点，通过引入频率信息，从而提高内存缓存命中率和性能。在多代垃圾回收或内存管理中，“年龄层次”是指将内存中的对象或者页面根据其存活时间的长短进行分层。每一层代表一个“年龄层次”，也称为“世代”。当对象或页面首次创建时，它会被放入最年轻的世代（如新生代）。随着每次垃圾回收或内存扫描过程的进行，如果对象或页面仍然存活，则会将其晋升到更老的一个世代。

Linux内核的内存管理中：

1. 新创建的对象首先被分配到新生代空间。

2. 如果对象经过一次垃圾回收后仍存在，那么它会被移动到较老的世代，比如幸存者空间。

3. 经历了多次垃圾回收仍然存活的对象最终可能会被提升到老年代。

在上述提到的多代LRU机制中，页面也会按照类似的方式来划分世代。新激活或访问过的页面会被置于年轻世代，随着时间推移，如果页面没有被访问，它们会被移动到更老的世代。当需要回收内存时，系统优先从最老的世代开始查找可回收的页面，这样可以更准确地识别并释放长期未使用的内存资源。

MGLRU的工作原理相对比较容易理解，它是一种多级全局最近最少使用的策略，将内存区域划分为多个层级，每个层级遵循LRU原则，但不同层级间的调度则根据访问频率和历史行为进行动态调整，这样既保留了LRU的优点，又解决了单一LRU面对复杂访问模式时的局限性。

1.多级分层管理

MGLRU的核心在于其多层次的结构设计。例如，可以将内存空间划分为年轻代、中年代和老年代。

新访问的数据首先会被放入年轻代；

若一段时间内未被访问，则降级至中年代，再次长时间未访问则进一步降至低老年代;

反之，如果在老年代的数据又被重新访问，它会逐层晋升回年轻代。

2. 动态迁移策略

当内存需要替换页面时，MGLRU算法会按照一定顺序考虑各世代的页面。首先选择最新访问的页面，这些页面是程序运行中最常访问的，因此替换掉它们可能会导致更多的页面访问错误。然后依次考虑其他世代的页面。这样做的好处是可以提高内存的利用率和程序的运行效率。MGLRU算法通过合理地管理内存中的页面，可以使得程序更高效地运行，同时减少内存的浪费。

每当有新的数据访问请求时，算法会检查该数据所在的层级，并做出相应操作：

如果数据在当前层级的LRU队列头部，则不做任何变动。

若数据不在头部，那么将其移动到头部，并依据层级迁移规则决定是否需要提升数据层级。

当某个层级满载需要淘汰数据时，遵循LRU原则淘汰队尾的数据。

3. 效率与适应性优势

相较于传统LRU，MGLRU的优势体现在能够更好地适应多样化的访问模式。对于经常访问的数据，它可以快速响应并保持在易于访问的位置，而对于访问频率较低的数据，则避免了不必要的频繁替换。这种智能分级的方式大大提高了内存利用率和整体系统性能。

除了按照年轻、中年、老年的三代分层，其实MGLRU算法还有应用更为先进的世代划分技术的可能性。如：针对应用程序复杂多变的页面需求，采用按需动态生成世代页面的方法，实现在不同需求下均能达到最佳的内存利用效果；在某些极端情况下，通过优化算法逻辑与时间参数，MGLRU算法可以扩展至更高的世代数量，进一步提高内存利用率。

三、性能优势

通过结合LRU和LFU的优点，MGLRU能够在不同负载情况下保持较好的性能。与LRU算法相比，MGLRU引入了频率信息，因此能够更准确地预测未来的缓存需求。与LFU算法相比，MGLRU能够更好地维护缓存块的关联性，避免因频繁访问而导致一些低频但重要的缓存块被替换。因此，MGLRU在缓存命中率、响应时间和系统吞吐量等方面均具有较好的表现。

除了提高内存利用率，MGLRU算法还具有很高的安全性和稳定性。在多任务并发执行的环境中，各种程序状态和数据量都可能随时发生变化，但MGLRU算法却始终能够稳定地运行，有效保障程序的正确性和效率。同时，它还具备高度的可扩展性和灵活性，可以轻松应对不同规模、类型和要求的应用程序，具有很强的应用价值。

四、总结

通过结合LRU和LFU的优点，MGLRU能够更准确地预测未来的缓存需求，从而提高缓存命中率和性能。同时，通过引入频率信息和优化策略，MGLRU能够更好地维护缓存块的关联性，适应不同负载情况下的缓存需求。在实际应用中，MGLRU可以作为内存管理的一种有效手段，提高系统的整体性能和效率。从理论上讲，MGLRU算法还能带来更加精细化和高效的内存管理，有利于延长设备电池寿命、提高响应速度和系统稳定性。