问题标签 [page-replacement]

我知道这两种让 LRU 算法错过 100% 的方法。

1. 循环访问略大于缓存大小的数据集。

2. 对不经常访问的数据集的任意突发访问，通过替换更频繁使用的条目来污染缓存。

红色表示缓存未命中。

但它有另一种方式“访问具有不同访问频率的块”。

我不知道如何用一个例子来描述它。

我需要证明最优页面替换算法确实是最优的，我不确定如何开始。我想也许可以通过矛盾来证明，但是一旦我提出了一个替代声明，我就不确定如何证明它的页面错误会与 OPT 相同或更少。

有人可以解释一下为什么 LRU 对于页面替换算法不实用，它对于替换缓冲区缓存中的文件缓冲区是完全可以接受的。

我目前正在阅读有关页面替换算法的内容，我发现对我来说很复杂的问题。

问题是：

页面替换算法应该尽量减少页面错误的数量。

描述：

我们可以通过将大量使用的页面均匀地分布在所有内存中来实现这种最小化，而不是让它们竞争少量的页框。我们可以为每个页面框架关联一个与该框架关联的页面数的计数器。然后，要替换页面，我们可以搜索计数器最小的页框。

b)对于以下具有四个页框的引用字符串，您的算法发生了多少页错误？

1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2

我正在为我的期末操作系统考试而学习，目前陷入了一个问题：

假设系统使用按需分页作为其获取策略。

常驻大小为 2 页。

替换策略是最近最少使用 (LRU)。

初始空闲帧列表：10、20、30、40、50

假设程序使用以下页面引用序列运行：
3（读取）、2（读取）、3（写入）、1（写入）、1（写入）、0（写入）、3（读取）

我被要求显示空闲帧列表、修改列表和页表的最终内容。

这是模型答案。

这就是我设法做到的。

最终的驻留集是正确的，但自由帧列表和修改列表不正确。我只是看不到修改后的列表如何不包含页码 0（因为它被写入内存），而页码 1 没有被写入，即使它在它之前被引用。

任何帮助，将不胜感激。

我知道在迭代期间无法在不抛出 ConcurrentModificationException 的情况下编辑 HashMap 或 LinkedHashMap 内容。但是，我有一种情况需要应用它。我正在使用 Second Chance 算法的时钟实现编写虚拟内存模拟。注意：RAM 是一个 LinkedHashMap，因此迭代顺序遵循插入顺序。这是我目前的方法（其中 tmp、hand 和 entry 是在主循环逻辑之外声明的变量：

这会产生几乎正确的输出，但我的问题是每次使用算法时都不应该重新创建迭代器。我需要一种方法来存储迭代器将指向的下一个元素，以便我可以从 LinkedHashMap 中删除 tmp 并用新的 PageTableEntry 替换它，以便下次迭代器运行时它从停止的地方恢复，而不是看到新添加的条目，直到它到达末尾并且必须循环回来。

在我们的讲座中，页面替换的 LRU 算法通过查看在最后一个“纪元”中是否被访问过的页面来解释（不确定这是否是正确的英文术语）。在每个 epoch 之后，所有页面上的 A-Bit 都设置回 0。懒惰的我没有正确听并在分配期间以不同的方式实现了模拟器：

只需将最近使用的页面放在堆栈顶部，这样我们的页面就按照它们最近使用的顺序排列，很明显这两个想法是等效的。

这在维基百科上也是这样做的，所以我想知道，你为什么还要用 A-Bit-way 来做呢？它只是过去的幼稚实现还是具有更好的运行时？我会怀疑，因为你有那些时代并一直重置 A-Bit。

在为一门课程进行实验后，我很好奇。我在文本中读到 LRU 效率更高，但在我所有的测试中似乎并非如此。地方有玩这个对吗？我使用的文件流一定没有足够紧密地遵循局部性原则，否则LRU会更有效率，不是吗？

假设我们为每个算法都有一个计数器，Second Chance 算法比最近最少使用的算法有更多的页面替换是正常的吗？

该程序尝试模拟 FIFO 和 LRU 页面替换。我正在尝试使用为 FIFO 队列动态分配的数组来实现一个简单的队列。我希望将“页面”存储在数组中。

该文件保存为 virtmem.c。这是生成文件：

运行“make”命令后，我使用这些输入运行可执行文件

但它在条件“if(queue[i] == NULL)”处给出了分段错误，表示无法访问内存位置。gdb 输出如下：