自适应替换缓存算法

Question

我正在尝试实现Adaptative Replacement Cache算法,但是,我正在阅读文献,我无法理解算法.任何人都可以解释我的算法？我看到它使用两个列表L1表示频率,L2表示新近度.但T1,B1和T2,B2为L1和L2列表,我无法理解.

ftp://paranoidbits.com/ebooks/Outperforming%20LRU%20with%20an%20Adaptive%20Replacement%20Cache.pdf在本文中我看到了这个信息.

Answer 1

我想强调一些关键的想法,并帮助你跟进论文的叙述.这应该可以帮助你培养一些关于ARC的直觉.

我们从大小为c的LRU缓存开始.除了页面缓存之外,我们还维护一个大小为c的缓存目录 T,它只是描述缓存中页面的元数据数组.例如,页面元数据包含存储介质中页面的物理地址.

现在,观察LRU不耐扫描.如果进程拉出一系列c页面,则缓存中的每个页面都将被逐出.这不是非常有效,我们希望能够针对新近度和频率进行优化.

关键思路#1:将缓存分成2个列表:T1和T2.T1包含最近使用的页面,T2包含常用页面.这是扫描抗性的,因为扫描将导致T1被清空,但是T2基本上不受影响.

当缓存已满时,算法必须选择从T1或T2中驱逐受害者.请注意,这些列表不必具有相同的大小,并且我们可以根据访问模式智能地将更多缓存提供给最近的页面或频繁页面.你可以在这里发明自己的启发式.

关键理念#2:保持额外的历史.让B1和B2分别从T1和T2跟踪被驱逐页面的元数据.如果我们在T1中观察到许多在B1中遇到的缓存未命中,我们会对驱逐感到遗憾,并将更多缓存提供给T1.

ARC保留一个数字p以在T1和T2之间拆分缓存.

主要观念#3:在高速缓存未命中T1和一击即B1,ARC增加p通过 .这是"delta"或"后悔率",它假设在所有页面上均匀分布,将B1中的命中概率与B2中的命中概率进行比较.