虚拟内存页面替换算法

Question

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

• 垂直轴:页面错误
• 水平轴:工作集大小
• 深度轴:稳定期

我的结果合理吗？我期望LRU比FIFO更好.在这里,它们大致相同.

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

更多信息

我的Python代码 | 项目问题

• 参考字符串长度(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的回答)

但是,回想一下您如何播种输入数据:使用random.random,从而为您提供具有可控熵级别的统一数据分布.因此,所有值都可能同样发生,并且因为您在浮点空间中构造了这些值,所以重现非常不可能.

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

我尝试增加numPageReferenced亲戚,numFrames希望它能更多地引用当前在内存中的页面,从而显示LRU相对于FIFO的性能优势,但这并没有给我一个明确的结果.仅供参考,我尝试使用以下参数的同一个应用程序(页面/框架比率仍然保持不变,我减少了数据的大小以使事情更快).

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

结果是

仍然没有这么大的差异.我是否正确地说,如果我numPageReferenced相对增加numFrames,LRU应该有更好的性能,因为它更多地引用内存中的页面？或许我错误地理解了什么？

对于随机,我正在思考:

• 假设高稳定性和小工作集.这意味着引用的页面很可能在内存中.那么页面替换算法运行的需求是否较低？

嗯,也许我要考虑更多:)

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

在这里,我试图显示垃圾,因为工作集大小超过内存中的帧数(100).然而,通知捶打似乎不太明显,稳定性较低(高t),为什么会这样？解释是,当稳定性变低时,页面错误接近最大值,因此工作集大小是多少并不重要？

Answer 1

鉴于您当前的实施,这些结果是合理的.然而,其背后的基本原理有一些讨论.

在考虑一般算法时,最重要的是要考虑当前正在检查的算法的属性.具体来说,请注意他们的角落情况以及最佳和最差情况.您可能已经熟悉了这种简洁的评估方法,因此这主要是为了那些阅读时可能没有算法背景的人的利益.

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

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

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

2. 当系统稳定性(1 - 深度轴)减小时,FIFO显示页面错误增加.

   注意你的播种稳定性算法(if random.random() < stability),你的结果变得不那么稳定,因为稳定性(S)接近1.当你急剧增加数据中的熵时,页面错误的数量也会急剧增加并传播Bélády的异常.

   到现在为止还挺好.

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

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

   但是,回想一下您如何播种输入数据:使用random.random,从而为您提供具有可控熵级别的统一数据分布.因此,所有值都可能同样发生,并且因为您在浮点空间中构造了这些值,所以重现非常不可能.

   结果,您的LRU感知每个元素发生的次数很少,然后在计算下一个值时被完全丢弃.因此,它可以正确地将每个值从窗口中分页,从而使您的性能与FIFO完全相当.如果您的系统正确地考虑了重复或压缩的字符空间,您会看到明显不同的结果.

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

   在的情况下,随机分页方案,你的年龄过的每个条目随机.据称,这应该给我们一些与我们的工作集的熵和大小相关的流形......对吗？

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

   因此,根据您检查的条件,这是完全正确的行为,与我们期望的一致.您可以获得均匀的分页性能,这种性能不会因其他因素而降低(但相反,它们并未得到改善),这些因素适用于高负载,高效运行.不错,不是你可能直觉所期望的.

因此,简而言之,这就是您的项目目前正在实施的细分.

作为在输入数据的不同配置和分布的背景下进一步探索这些算法的属性的练习,我强烈建议深入研究scipy.stats,例如,高斯或逻辑分布可能对每个图做什么.然后,我将回到每个算法和草案的记录期望,其中每个算法都是唯一最独特且最不合适的.

总而言之,我认为你的老师会感到自豪.:)