问题标签 [lru]

我正在尝试LRU cache在 Java 中实现一个应该能够：
动态更改大小。从某种意义上说，我计划将其SoftReference订阅为ReferenceQueue. 因此，根据内存消耗，缓存大小会有所不同。

我计划使用ConcurrentHashMapwhere 值将成为软引用，然后定期清除队列以更新地图。
但是上面的问题是，我该怎么做呢LRU？

我知道我们无法控制 GC，但是我们是否可以管理对值的引用（在缓存中），使得缓存中所有可能的对象都将根据使用情况（即最后一次）变得可轻松访问（在 GC 下）它被访问了），而不是以某种随机的方式。

一个主存储器最多可以保留 4 页。如果 LRU 算法用于按顺序排列的后续页面，哪个页面将是第一个出现页面错误的页面？

1,2,3,1,2,4,1,2,3

这是一个我认为没有答案的测试问题。主内存可以保留 4 个页面，并且由于存在页面 1、2、3、4，因此不应该发生页面错误。

答案是第 4 页，但我不明白为什么。

我很好奇当应用程序从屏幕上关闭并且用户切换到其他应用程序时应用程序的活动会发生什么。在activity圈中，activity会到达onStop()，那么在activity是onRestart()还是relaunch之前系统是如何处理的呢？引擎盖下到底发生了什么？还在缓存中，被 LRU 代替了？

任何人都有一些想法或知道一些讨论这个问题的文章？

如果可能的话，任何人都可以提到一些源代码来阅读吗？

对于 LRU 缓存，我需要一种用于无锁队列的算法，类似于简单、快速和实用的非阻塞和阻塞并发队列算法一文中描述的算法

但是为了维护一个 LRU 队列，我还需要删除队列中的节点（尾部节点除外）。

我的想法是仅使用 CAS 操作将节点标记为已删除，然后使用单个清理线程，该线程稍后将从队列中删除已删除的节点。

我发现创建无锁算法比我最初预期的要复杂。所以，我的问题是：
有没有这样的算法可用？

这是我目前使用的结构：

一般的

• 一个节点具有以下结构： struct { e *entry, next pointer, prev pointer, state uint32}
• 为了避免为每个新节点分配多个内存，分配了一个节点数组。
• 指向节点的指针由数组索引值和更新计数器组成，复用到单个 uint64
• 节点状态由一个高位组成，告诉该节点是否被删除。其余位用作更新计数器

入队

• 辅助队列保存未使用节点的列表，“新”节点通过从辅助队列中的出队获取，然后设置为默认值
• node.prev 在新节点入队之前设置为当前尾部

出队

• head.next.prev 在 head dequeue 之前被 CAS 化为 NIL 值。如果 head.next.prev 设置为 CLEANUP（由清理线程处理），则不允许出队，线程将让出 CPU 并重新开始。
• 在具有未删除状态的节点成功出列时，该状态将被 CAS 删除，并且该节点将返回到辅助队列。在失败（或状态已设置为已删除）时，出队的 node.prev 将从 NIL 更改为 CLEANUP，向清理线程发出该节点已出队的信号。然后出队将重新开始，直到未删除的节点成功出队并通过 CAS 删除。

删除

• 为了标记队列中的删除，状态被 CAS'ed 删除并在成功时传递给清理队列。失败时什么也不做，但函数返回。

清理线程

• 如果 node.prev 是 CLEANUP，则 Dequeue 已将其从队列中删除。节点被传回辅助队列。
• 如果 node.prev 为 NIL，则该节点即将成为头，是头，或即将出队。如果 node == head，清理线程尝试执行出队（状态更改为已删除）。失败时，清理过程将从头开始。
• 如果 node 被设置为另一个节点，node.prev 被 CAS'ed 为 CLEANUP。如果 head.next == 节点，这可以防止任何出队。成功后，使用双链表进行队列内删除。失败时，清理过程将从头开始。

Node.prev 用于告诉：

• 队列中哪个节点在前
• 节点即将成为头/是头
• 节点正在被清理线程处理
• 节点出队

我在这个例子中使用 Boost.MultiIndex 实现了以下 LRU 实现。

问题是当我更改 index_by 部分的顺序（并相应地更新枚举 index_idx）时，我在包含以下内容的行上收到错误：

通过以下诊断：

错误 1 ​​错误 C2661: 'boost::multi_index::detail::sequenced_index::insert' : 没有重载函数需要 1 个参数 c:\code\code.cpp 79

代码如下：

修改后的索引排序：

参考LRU缓存设计

我有一个关于答案的问题。

假设我的哈希映射已满（面试官给了我一个最大尺寸）[我知道如果我需要获取映射中已经存在的一对，我会将列表条目移到前面以指示最近使用。]

但是，如果我有一个要添加的条目并且这个键散列到与不同键相同的位置怎么办。（碰撞）我该怎么办？

我做链接或探测吗？如果我进行链接，我应该增加地图大小吗？如果我删除最旧的条目，它会清空我的哈希图中的一个位置。但是一个新条目可能不会散列到这个位置？它可能会散列到另一个完整条目？（不同的键，值对）如何解决这个问题？

我已经使用哈希表+链表实现了 LRU。

哈希表具有链接。代码结构如下：

trackHead 和 trackTail 指针用于跟踪插入的顺序。这用于删除最近最少使用的元素。我在想有多个替换策略被使用，而不是一个。因此，LRU 与某些东西的组合一起使用。因此，如果在我再次访问该元素时要从 LRU 中删除一个元素，那么我需要将它从 LRU 中删除。

从本质上讲，我要维护整个序列，如果有数百万个条目，那就不好了。除了使用优先级队列+哈希表之外，还有什么方法可以改善这一点

假设 redis 实例中的所有键都设置了过期时间，那么 volatile-lru 和 allkeys-lru 是相似的。但是当一个键被移除时，两者之间是否存在显着的性能差异？

奖金问题：

在使用 allkeys-lru 策略配置的 2 个不同实例之间，具有相同的内容和相同的配置，除了：

• 实例 A 的所有键都设置了过期时间（过期值不同）
• 实例 B没有设置过期时间的键

除了由于过期位而导致实例 A 中的内存开销之外，当 allkeys-lru 算法删除密钥时，两者之间是否存在性能差异？

在这两种情况下，我都在谈论 linux 64 位上的 redis 2.4.x 实例，maxmemory = 3Gb，当达到 maxmemory 时有 4-5000 个键（大多数键是散列）。

谢谢

可能重复：
LRU 缓存设计

我在一次编程面试中得到了这个问题。随意考虑如何回答它。

您将如何在 C++ 中实现 LRU（最近最少更新）缓存？基本上，缓存可以容纳N项目。如果插入了一个新项目并且缓存中的项目数小于N，则它只是插入。但是如果插入了一个新项目并且缓存中的项目数已经是N，那么最近最少使用的项目应该从缓存中删除。

考虑一下您的每项操作需要多少运行时间。

我正在为我的操作系统课程做一个模拟页面替换的项目。我有一个模拟器，可以在 1200 个引用上运行所有三种算法。但是，我得到了页面错误率，其中 LRU 算法仅在大多数情况下获得等于或低于 FIFO 的分数。偶尔会运行一个输入，即 LRU 的页面错误率会比 FIFO 略高。这是不正确的吗？

我为每轮递增的每个页码使用计数器来实现 LRU。正在使用的页面将其计数器重置为 0。当我交换框架时，我使用具有最大计数器值的框架。我觉得我的实现应该是正确的。