了解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性能更好，因为对于前几个项目，缓存至少命中一次。