algorithm - 增强的二次机会算法如何对已修改的更改有偏好？

Question

我一直在阅读教科书“操作系统概念，第 10 版，作者是 Greg Gagne、Peter B. Galvin、Abraham Silberschatz”

教科书首先对第 403 页上的修改位说了以下内容......

“如果该位被设置，我们知道该页面自从从辅助存储读入后已被修改。在这种情况下，我们必须将页面写入存储。如果未设置修改位，但是，该页面自从被读入内存后就没有被修改过。在这种情况下，我们不需要将内存页面写入存储:它已经存在。“

然而在本书后面的第 410-411 页中，它似乎自相矛盾......

“我们可以通过考虑引用位来增强二次机会算法 和修改位(在第 10.4.1 节中描述)作为有序对。用这些 两位，我们有以下四种可能的类别:

1。 (0, 0) 最近既没有使用也没有修改——最佳替换页面

2。 (0, 1) 最近未使用但已修改——不太好，因为页面 替换前需要写出来

3。 (1, 0) 最近使用过但很干净——可能很快会再次使用

4。 (1, 1) 最近使用和修改——可能很快会再次使用，并且 该页面需要先写出到辅助存储，然后才能 被替换

每个页面都属于这四个类之一。调用页面替换时 因为，我们使用与时钟算法相同的方案；但不是检查 我们指向的页面是否将引用位设置为 1， 我们检查该页面所属的类。我们替换第一页 在最低的非空类中遇到。请注意，我们可能必须扫描 循环排队几次才找到要替换的页面。专业 该算法与更简单的时钟算法之间的区别在于，这里 我们优先选择那些经过修改的页面，以减少 所需的 I/O 数量。"

如果我们优先考虑已修改的页面，这是否意味着我们正在增加所需的 IO 数量？因为如果页面已被修改，那么我们需要将更改写入存储？

抱歉，我对增强的第二次机会算法应该如何减少所需的 IO 数量感到困惑。

谢谢。

Answer 1

我认为他们的意思是首选将修改后的页面保留在内存中(尽管它读起来让我有些困惑)。

这句话:

We replace the first page encountered in the lowest nonempty class

而上面类的排序意味着它会首先丢弃一个没有被使用和修改的页面。

我还会阅读“为了减少所需的 I/O 数量”以应用于立即需要解决没有足够可用内存问题的上下文。通常这个问题需要尽快解决。当不需要写入时，这是最快的。如果操作系统可以从第一类中释放足够多的页面来解决眼前的需要，那么这就是一个非常好的结果。

操作系统通常有一个“惰性写入”或“后台写入”过程。当资源释放时(或者没有可用的未修改页面并且需要更多 RAM)，具有修改位设置的内存页面将在“稍后”写入磁盘。这是正常关机和不拔电源插头的主要原因——内存中可能有许多修改过的页面等待写入磁盘。因此，在本段的上下文中，如果可以通过释放未修改的页面来满足当前需求，那么其余页面可能会在稍后由后台写入进程写入。

有趣的是，第 2 类比第 3 类更受欢迎。通过丢弃第 3 类中的某些内容来解决眼前的问题(需要更多内存)会更快，因为不需要写入。然而，操作系统预测它可能很快就需要再次读取该内存，因此它没有。计算“最近使用”的最近程度可能涉及一些极其复杂的算法。并且它可能考虑了正在写入的媒体的速度。