c++ - 了解 OPT 算法

Question

好的，我正在尝试理解 OPT 算法，然后它将使我更容易对其进行编码。我无法跟随幻灯片，它没有任何意义。有人可以逐步指导我如何操作吗？

这看起来与 LRU 算法相同。我们是否使用计数器保留第二个数组？

Answer 1

您显然必须事先知道将要使用哪些页面以及以什么顺序使用；这是1, 2, 3, ..., 4, 5您示例中的列表。当您必须替换页面时，您选择包含将在所有页面中最后使用的页面的框架。

在此示例中，您访问页面 1、2、3、4、1 和 2 时不会出现任何页面错误（因为当前所有页面都已换入）。

您的下一页访问，第 5 页，不在任何框架中，因此您必须选择一个框架将其放入。根据即将到来的页面命中（1、2、3、4），页面 4（在第 4 帧中）将最后被访问，因此您将第 5 页交换到第 4 帧（如图所示）。

接下来的页面 1、2 和 3 可以正常访问。

现在第 4 页已被访问，但它先前已被换出，因此出现页面错误。您即将访问的列表显示仅需要第 5 页，因此可以换出 1、2 和 3 中的任何一个。选择了1，大概是因为它是第一个。

Answer 2

最佳算法只是理论上导致缓存未命中最少的算法。

换句话说，在您了解缓存的使用方式之前，不可能知道最佳值。这意味着您无法提前编写最佳算法；因为，您不知道缓存将如何实际使用。

最优算法作为实际算法的基准非常有用。每个重要的缓存问题最终都会缓存未命中。了解特定运行的“绝对最小”未命中数可以为比较两种缓存算法提供基准。

例如，如果你必须错过缓存四次，那么与错过缓存七次的算法相比，错过缓存六次的算法看起来相当不错。如果您必须错过缓存 1000 次，那么错过缓存 1006 次的算法和错过缓存 1007 次的算法几乎是等价的。

根据缓存的使用模式，一些算法比其他算法更频繁地访问缓存。一个例子是 LRU，它会从缓存中删除很少使用的项目：如果你倾向于在一小段时间内对相同的项目进行多次访问，这是很好的。另一方面，如果您需要多次访问每个项目，但按顺序访问一次（如在循环中），那么 LRU 的性能可能会很糟糕（~100% 缓存未命中），因为每次访问只会将一个项目踢出缓存. 巧合的是，在这些条件下，MRU（新项目替换最近使用的项目）缓存将比 LRU 执行得更好，因为至少前几个项目的缓存命中一次。