WSClock 算法作为近似
WSClock algorithm as approximation
我对操作系统中用于页面替换的 WSClock 算法有疑问。
据我了解，WSClock结合了两个Working Set的特性（一个页面如果在最后T时间间隔被引用则在WS中，所以最后一个引用时间为每个页面存储R&M 位）和时钟算法（页面帧 table 存储为循环列表，当发生页面错误时，遍历列表以搜索工作集中不存在的页面）。
在每个页面引用中，硬件将其 R 位设置为 1。在某些时间间隔，OS 将所有页面的 R 位重置为 0。
当发生页面错误时，算法遍历列表并对每个页面执行以下操作：
1) If R == 1 : set R = 0, set t = process_t, go further
2) Else if R == 0 and (t - process_t) <= T, go further
3) Else if R == 0 and (t - process_t) > T
1) If M = 1 - set page for writing to disk, go further
2) If M = 0 - this is our victim, evict
If there are no pages for immediate evict are found - traverse until a disk write for any marked page is finished, then evict.
If there are no pages scheduled for a disk write - take the one which was referenced to the most time ago.
算法对我来说很好，除了一件事：
上次引用页面的时间仅在一次情况下发生变化：如果在引用此页面 (R = 1) 后发生页面错误，但 OS 尚未重置 R 位到 0 (R = 0)。因此，据我了解 - 上次使用的时间仅通过该方法进行近似，从而获得更好的性能。
因此，对于毫无疑问存在于进程的 WS 中的非常非常频繁使用的页面，一切都很好：它们的引用频率高于 OS 重置事件的频率。
但应该有一些不幸的页面被频繁引用，但不幸的是，在这些引用之后没有发生页面错误。但他们也很不幸，当页面错误发生时——他们看起来好像没有被引用，尽管这不是真的。
所以据我所知，OS 似乎只在页面错误事件期间拍摄工作集的快照。这些快照表示在 R 位重置和页面错误之间的时间间隔内引用的工作页面集。
为什么这是对真实工作集的良好近似？
逼近的质量（以及算法的有效性）是否由重置 R 位时的时间间隔值决定？
所以这个值不应该太低以至于无法捕获我上面提到的大多数这些不幸的页面，但也不应该太大以至于无法捕获实际上已经不在工作集中的页面？
实际上这里是解释：
该算法使用工作集的近似值。
这个近似值存储了进程的真实实际工作集的一部分。此外，它可能不会存储此实际工作集的某些部分。
操作系统开发人员的任务是找到算法的参数（工作集存在时间间隔、重置位时间间隔），以便该近似值足以使算法足够快地工作并且具有可接受的页面错误数与始终使用真实实际工作集的算法相比。
另外值得一提的是，在计算机工作期间，可以通过 OS 动态调整参数，以使算法与实际工作集保持足够接近。
我对操作系统中用于页面替换的 WSClock 算法有疑问。
据我了解，WSClock结合了两个Working Set的特性（一个页面如果在最后T时间间隔被引用则在WS中，所以最后一个引用时间为每个页面存储R&M 位）和时钟算法（页面帧 table 存储为循环列表，当发生页面错误时，遍历列表以搜索工作集中不存在的页面）。
在每个页面引用中，硬件将其 R 位设置为 1。在某些时间间隔，OS 将所有页面的 R 位重置为 0。
当发生页面错误时，算法遍历列表并对每个页面执行以下操作：
1) If R == 1 : set R = 0, set t = process_t, go further
2) Else if R == 0 and (t - process_t) <= T, go further
3) Else if R == 0 and (t - process_t) > T
1) If M = 1 - set page for writing to disk, go further
2) If M = 0 - this is our victim, evict
If there are no pages for immediate evict are found - traverse until a disk write for any marked page is finished, then evict.
If there are no pages scheduled for a disk write - take the one which was referenced to the most time ago.
算法对我来说很好，除了一件事：
上次引用页面的时间仅在一次情况下发生变化：如果在引用此页面 (R = 1) 后发生页面错误，但 OS 尚未重置 R 位到 0 (R = 0)。因此，据我了解 - 上次使用的时间仅通过该方法进行近似，从而获得更好的性能。
因此，对于毫无疑问存在于进程的 WS 中的非常非常频繁使用的页面，一切都很好：它们的引用频率高于 OS 重置事件的频率。
但应该有一些不幸的页面被频繁引用，但不幸的是，在这些引用之后没有发生页面错误。但他们也很不幸，当页面错误发生时——他们看起来好像没有被引用，尽管这不是真的。
所以据我所知，OS 似乎只在页面错误事件期间拍摄工作集的快照。这些快照表示在 R 位重置和页面错误之间的时间间隔内引用的工作页面集。
为什么这是对真实工作集的良好近似？
逼近的质量（以及算法的有效性）是否由重置 R 位时的时间间隔值决定？
所以这个值不应该太低以至于无法捕获我上面提到的大多数这些不幸的页面，但也不应该太大以至于无法捕获实际上已经不在工作集中的页面？
实际上这里是解释： 该算法使用工作集的近似值。
这个近似值存储了进程的真实实际工作集的一部分。此外，它可能不会存储此实际工作集的某些部分。
操作系统开发人员的任务是找到算法的参数（工作集存在时间间隔、重置位时间间隔），以便该近似值足以使算法足够快地工作并且具有可接受的页面错误数与始终使用真实实际工作集的算法相比。
另外值得一提的是，在计算机工作期间，可以通过 OS 动态调整参数，以使算法与实际工作集保持足够接近。