我正在尝试实现自适应替换缓存算法，但是我正在阅读文献，但我无法理解该算法。任何人都可以解释我的算法？我看到它使用两个列表 L1 表示频率，L2 表示新近度。但是对于 L1 和 L2 列表的 T1、B1 和 T2、B2，我无法理解。
ftp://paranoidbits.com/ebooks/Outperforming%20LRU%20with%20an%20Adaptive%20Replacement%20Cache.pdf在这篇论文中我看到了这个信息。
问问题
3180 次
2 回答
9
我想强调一些关键思想，并帮助您遵循论文的叙述。这应该有助于您对 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中的命中概率进行比较，假设所有页面的分布均匀。
于 2015-11-26T00:01:18.810 回答
3
T1 and T2 hold the actual data that is being cached. T1 holds all the data (pages) that has been referenced exactly once. T2 holds pages that have been referenced 2 or more times. B1 is a ghost list which is used to remember which pages once were in the T1 cache. B2 is the same, only for the T2 cache. When you add T1 and B1 together, you get a set (called L1) of references to pages that were or currently are cached because they were referenced once. The same goes for L2, only it contains references to which pages have been referenced at least twice.
T1 and T2 share a fixed sized set of slots (each slot can hold one page), and we use B1 and B2 to decide how to share these slots among T1 and T2. This is what makes ARC adaptive - the automatic adjustment of who gets the most slots. If B1 holds multiple references to the same page, it means that we don't allow T1 to hold on to its pages long enough, and that it should be allowed more slots to counter this. The same goes for B2.
I won't try and explain the entire algorithm here, but this is at least my understanding of the ARC lists.
于 2015-09-18T14:25:44.530 回答