operating-system - 虚拟内存页面替换算法

Question

我有一个项目，要求我开发一个应用程序来模拟不同页面替换算法的执行方式(具有不同的工作集大小和稳定期)。我的结果:

纵轴:页面错误

横轴:工作集大小

深度轴:稳定期

我的结果合理吗？我希望 LRU 比 FIFO 有更好的结果。在这里，它们大致相同。

对于随机，稳定期和工作集大小似乎根本不影响性能？我期望与 FIFO 和 LRU 类似的图表只是性能最差？如果引用字符串是高度稳定的(小分支)并且工作集大小较小，那么与具有许多分支和大工作集大小的应用程序相比，它的页面错误应该更少吗？

更多信息

My Python Code | The Project Question

引用字符串长度 (RS):200,000

虚拟内存大小(P):1000

主存大小(F):100

引用的时间页数 (m): 100

工作集大小 (e):2 - 100

稳定性(t):0 - 1

工作集大小 (e) 和稳定期 (t) 会影响引用字符串的生成方式。

|-----------|--------|------------------------------------|
0           p        p+e                                  P-1

所以假设上面的虚拟内存大小为 P。要生成引用字符串，使用以下算法:

重复直到生成引用字符串

挑选 m [p, p+e] 中的数字。 m模拟或引用页面被引用的次数

选择随机数，0 <= r < 1

如果 r < t

生成新 p

否则 (++p)%P

更新(回应@MrGomez 的回答)

However, recall how you seeded your input data: using random.random, thus giving you a uniform distribution of data with your controllable level of entropy. Because of this, all values are equally likely to occur, and because you've constructed this in floating point space, recurrences are highly improbable.

我正在使用 random ，但它也不是完全随机的，虽然使用工作集大小和页数引用参数，但在某些地方生成了引用？

我尝试增加 numPageReferenced相对于 numFrames希望它会更多地引用当前内存中的页面，从而显示 LRU 优于 FIFO 的性能优势，但这并没有给我一个明确的结果。仅供引用，我尝试了具有以下参数的相同应用程序(页面/帧比率仍然保持不变，我减小了数据大小以加快速度)。

--numReferences 1000 --numPages 100 --numFrames 10 --numPageReferenced 20

结果是



仍然没有那么大的差异。如果我增加 numPageReferenced 我说得对吗？相对于 numFrames ，LRU应该有更好的性能，因为它更多地引用内存中的页面？或者我可能误解了什么？

对于随机，我的想法是:

假设有高稳定性和小工作集。这意味着引用的页面很可能在内存中。那么运行页面替换算法的需求会降低吗？

嗯，也许我得再考虑一下:)

更新:在稳定性较低时垃圾不太明显



在这里，我试图将垃圾显示为工作集大小超过内存中的帧数(100)。然而，在稳定性较低(高 t)的情况下，注意抖动似乎不太明显，为什么会这样？是否解释为随着稳定性变低，页面错误接近最大值，因此工作集大小无关紧要？

Answer 1

考虑到您当前的实现，这些结果是合理的。 然而，这背后的理由值得讨论。

在考虑一般算法时，最重要的是考虑当前正在检查的算法的属性。具体来说，请注意他们的corner cases以及最好和最坏的情况。您可能已经熟悉这种简洁的评估方法，所以这主要是为了那些可能没有算法背景的读者的利益。

让我们通过算法分解您的问题，并在上​​下文中探索它们的组件属性:

随着工作集(长度轴)大小的增加，FIFO 显示页面错误的增加。

这是正确的行为，与 Bélády's anomaly 一致用于 FIFO 替换。随着工作页面集大小的增加，页面错误的数量也应该增加。

随着系统稳定性(1 - 深度轴)的降低，FIFO 显示页面错误的增加。

注意你的播种稳定性算法(if random.random() < stability)，随着稳定性(S)接近1，你的结果变得不太稳定。随着你急剧增加entropy在您的数据中，页面错误的数量也急剧增加并传播了 Bélády 异常。

到现在为止还挺好。

LRU 显示与 FIFO 的一致性。为什么？

请注意您的播种算法。 Standard LRU当您的寻呼请求被构建为较小的操作帧时，这是最佳选择。对于有序的、可预测的查找，它通过老化当前执行帧中不再存在的结果来改进 FIFO，这对于分阶段执行和封装的模态操作非常有用。再说一次，到目前为止，很好。

但是，回想一下您是如何播种输入数据的:使用 random.random ，从而给你一个uniform distribution具有可控熵水平的数据。因此，所有值都同样可能出现，并且因为您在 floating point space 中构建了它。 , 复发的可能性很小。

结果，您的 LRU 会感知每个元素发生少量次数，然后在计算下一个值时被完全丢弃。因此，它会在每个值落出窗口时正确地对其进行分页，从而为您提供与 FIFO 完全可比的性能。如果您的系统正确考虑了重复或压缩字符空间，您会看到明显不同的结果。

对于随机性，稳定期和工作集大小似乎根本不会影响性能。为什么我们在整个图表上都看到这个涂鸦，而不是给我们一个相对的 smooth manifold ?

在随机分页方案的情况下，您将老化每个条目 stochastically .据称，这应该给我们某种形式的流形，它与我们工作集的熵和大小有关……对吧？

还是应该？对于每组条目，您随机分配一个子集作为时间的函数进行分页。这应该提供相对均匀的分页性能，无论稳定性和您的工作集如何，只要您的访问配置文件再次统一随机。

因此，根据您正在检查的条件，这是完全正确的行为 consistent with what we'd expect .您获得的分页性能不会因其他因素而降低(但相反，不会因其他因素而降低)，适用于高负载、高效操作。不错，只是不是您可能直观地期望的。

因此，简而言之，这就是您的项目当前实现时的故障。

作为在输入数据的不同处理和分布的上下文中进一步探索这些算法的属性的练习，我强烈建议深入研究 scipy.stats 。看看，例如，高斯或逻辑分布可能对每个图做什么。然后，我会回到 the documented expectations of each algorithm并草拟案例，其中每个案例都是最合适和最不合适的。

总而言之，我认为您的老师会感到自豪。 :)