operating-system - Virtual Memory Page Replacement Algorithms

Question

I have a project where I am asked to develop an application to simulate how different page replacement algorithms perform (with varying working set size and stability period). My results:

• Vertical axis: page faults
• Horizontal axis: working set size
• Depth axis: stable period

Are my results reasonable? I expected LRU to have better results than FIFO. Here, they are approximately the same.

For random, stability period and working set size doesnt seem to affect the performance at all? I expected similar graphs as FIFO & LRU just worst performance? If the reference string is highly stable (little branches) and have a small working set size, it should still have less page faults that an application with many branches and big working set size?

More Info

My Python Code | The Project Question

• Length of reference string (RS): 200,000
• Size of virtual memory (P): 1000
• Size of main memory (F): 100
• number of time page referenced (m): 100
• Size of working set (e): 2 - 100
• Stability (t): 0 - 1

Working set size (e) & stable period (t) affects how reference string are generated.

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

So assume the above the the virtual memory of size P. To generate reference strings, the following algorithm is used:

• Repeat until reference string generated
  • pick m numbers in [p, p+e]. m simulates or refers to number of times page is referenced
  • pick random number, 0 <= r < 1
  • if r < t
    • generate new p
    • else (++p)%P

UPDATE (In response to @MrGomez's answer)

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.

I am using random, but it is not totally random either, references are generated with some locality though the use of working set size and number page referenced parameters?

I tried increasing the numPageReferenced relative with numFrames in hope that it will reference a page currently in memory more, thus showing the performance benefit of LRU over FIFO, but that didn't give me a clear result tho. Just FYI, I tried the same app with the following parameters (Pages/Frames ratio is still kept the same, I reduced the size of data to make things faster).

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

The result is

Still not such a big difference. Am I right to say if I increase numPageReferenced relative to numFrames, LRU should have a better performance as it is referencing pages in memory more? Or perhaps I am mis-understanding something?

For random, I am thinking along the lines of:

• Suppose theres high stability and small working set. It means that the pages referenced are very likely to be in memory. So the need for the page replacement algorithm to run is lower?

Hmm maybe I got to think about this more :)

UPDATE: Trashing less obvious on lower stablity

Here, I am trying to show the trashing as working set size exceeds the number of frames (100) in memory. However, notice thrashing appears less obvious with lower stability (high t), why might that be? Is the explanation that as stability becomes low, page faults approaches maximum thus it does not matter as much what the working set size is?

Answer 1

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

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

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

1. 随着工作集（长度轴）大小的增加， FIFO显示页面错误的增加。

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

2. 随着系统稳定性（ 1 深度轴）的降低， FIFO显示页面错误的增加。

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

   到目前为止，一切都很好。

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

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

   但是，回想一下您是如何播种输入数据的：使用random.random，从而以可控的熵水平为您提供均匀的数据分布。正因为如此，所有值都同样可能出现，并且因为您已经在浮点空间中构造了它，所以重复发生的可能性非常小。

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

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

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

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

   因此，根据您正在检查的条件，这是完全正确的行为，符合我们的预期。您获得的分页性能不会因其他因素而降低（但相反，不会因其他因素而降低），适用于高负载、高效操作。不错，只是不是您可能直观地期望的。

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

作为在输入数据的不同处置和分布的上下文中进一步探索这些算法的属性的练习，我强烈建议深入scipy.stats研究，例如，高斯或逻辑分布可能对每个图产生什么影响。然后，我会回到每个算法的记录期望和草稿案例，其中每个都是最合适和最不合适的。

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