Running Noob

Do Something Meaningful

0%

L25-内存换出

发表于 更新于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟
  • 如果只有内存换入，那么物理内存迟早会满，所以还应该有内存换出。但具体是把哪一页内存换出，就需要用算法来决定。

L25 内存换出

  • 如果只有内存换入，那么物理内存迟早会满，所以还应该有内存换出。但具体是把哪一页内存换出，就需要用算法来决定。

FIFO页面置换

  • 在下图例子中，A、B、C 依次换入物理内存页，根据 FIFO 算法，A、B、C 也应该依次换出物理内存页。

    但在这个例子中，最先换出 C 其实是最合适的。

MIN页面置换

  • MIN 算法是选择最远将使用的页换出，在下图例子中，在换入 D 时，由于 C 是最远将使用的页，所以将 C 换出；然后在换入 C 时，A、D 都可以换出，这里是选择了换出 A。

    MIN 算法的缺点是需要知道“未来“的样子，实际上是不可能的。

★LRU页面置换

  • LRU（Least Recently Used）算法，借鉴于程序的局部性原理，是根据过去的历史预测将来，选择最近最长一段时间没有使用（最近最少使用）的页进行换出。

LRU页面置换的实现

时间戳

  • 最先想到的想法是为每个页维护一个时间戳，如下图所示，在利用 LRU 算法进行页的换出时，就选取时间戳最小的页进行换出。

    但这个方法也有一些缺点，首先是在进程每次通过地址访问内存时，都要对被访问的物理内存页进行时间戳的维护；其次，在进行物理内存页的换入换出时，需要找到时间戳最小的页进行换出；而且时间戳在不断增大，最后肯定会导致溢出问题。因此并不能利用时间戳的方法来实现 LRU 算法。

页码栈

  • 然后想到的是利用页码栈来实现 LRU 算法，如下图所示。

    这个方法同样有一些问题，在进程每次通过地址访问内存时，都要对页码栈进行修改，实现代价仍然较大。

★LRU 算法近似实现 - Clock算法

  • 实际中准确实现 LRU 算法还是比较困难，所以对其进行近似实现——SCR 算法，又称为 Clock Algorithm。

    如下图所示，为每个页加一个引用位，进程每次通过地址访问某一具体物理内存页时，就将该页的引用位 R 置 1；在进行内存的换入换出时，就从上一次访问的物理内存页开始进行扫描，若 R = 1 时就将 R 置为 0，若 R = 0 时就将该页换出，并从磁盘中将要使用的物理内存页换入，并将该物理内存页的引用位置为 1。

★Clock 算法的改进

  • 由于在实际的操作系统中，缺页的情况是比较少的，所以如果采用上面所述的 Clock 算法，就会退化为 FIFO 算法。

    原因在于，Clock 算法是将“最近没有使用”的物理内存页换出，而 LRU 算法是将“最近最少使用”的物理内存页换出，所以在 Clock 算法中，引用位其实记录了太长的历史信息（因为如果没有缺页的情况，那 R 将一直为 1 ）。

    为了解决这个问题（引用位记录太长的历史信息的问题），需要定时清除 R 位，因此又加了一个指针，用于清除 R 位。

---------------The End---------------