操作系统 页面替换算法

今天我们将学习操作系统中的页面替换算法。在了解操作系统中的页面替换算法之前，让我们先了解一下操作系统中的分页和虚拟内存。

只有在理解了分页的概念后，我们才能了解页面替换算法。

操作系统中的分页

分页是一种存储机制，用于从辅助内存检索进程到主内存。

主内存被划分为小块称为页面。每个页面都包含从辅助内存中检索到的进程，并存储在一帧内存中。

具有相等大小的页面和帧非常重要，对于映射和完全利用内存非常有用。

操作系统中的虚拟内存

一种称为虚拟内存的存储方法使用户感觉他们的主内存非常大。这是通过将一部分辅助内存视为主内存来实现的。

通过给用户提供有可用内存加载进程的印象，这种方法允许加载比可访问的主内存更大的程序。

操作系统将多个进程的许多组件加载到主内存中，而不是加载单个大型进程。

通过这样做，将提高多道程序设计的水平，从而增加了CPU的使用率。

需求分页

需求分页是虚拟内存中发生的一种情况。我们知道，进程的页面存储在辅助内存中。当需要时，将页面加载到主内存中。我们不知道这个需求何时发生。因此，当需要时，页面会按照页面替换算法的要求被加载到主内存中。

因此，根据需求将页面从辅助内存调用到主内存的过程称为需求分页。

在操作系统中，虚拟内存的重要任务有两个，分别是：

• 帧分配
• 页面置换

虚拟内存中的帧分配

需求分页是实现虚拟内存的一种方法，是操作系统的一个关键组成部分。为了实现需求分页，必须创建一个页面置换机制和帧分配算法。如果有很多进程，帧分配技术可用于确定为每个进程提供多少帧。

中央处理器（CPU）需要一个物理地址来创建帧，物理寻址提供实际地址给创建的帧。每个页面必须创建一个帧。

帧分配约束

• 可以分配的帧数不能大于总帧数。
• 每个进程都应该被给予一组最小数量的帧。
• 当分配的帧数较少时，页面错误比率会增加，进程的执行效率降低。
• 应该有足够的帧来容纳单个指令可能引用的所有多个页面

帧分配算法

操作系统中有三种类型的帧分配算法。它们是：

1) 相同帧分配算法

在这种帧分配算法中，我们一次考虑帧数和进程数。我们将帧数除以进程数，得到我们必须为每个进程提供的帧数。

这意味着如果我们有36个帧和6个进程，则为每个进程分配6个帧。

在具有不同大小的进程的系统中，将相同数量的帧分配给所有进程是不太合理的。如果给一个小操作分配了很多帧，最终会浪费很多已分配但未使用的帧。

2) 比例帧分配算法

在这种帧分配算法中，我们根据进程大小来确定帧数。对于大的进程，分配更多的帧数。对于小的进程，操作系统分配的帧数较少。

比例帧分配算法的问题在于有时会浪费帧数。

比例帧分配算法的优点是，每个操作根据其需求将可用帧数分配给各个操作，而不是平均分配。

3) 优先级帧分配算法

根据帧分配数量和进程数量，优先级帧分配算法分配帧。假设一个进程的优先级较高并且需要更多的帧数；在这种情况下，将额外的帧分配给该进程。然后在之后逐步执行低优先级的进程，首先只执行高优先级的进程。

页面置换算法

操作系统中有三种类型的页面置换算法。它们是：

• 最佳页面置换算法
• 先进先出页面置换算法
• 最近最少使用（LRU）页面置换算法

先进先出页面置换算法

这是页面置换算法的第一个基本算法。该算法基本上取决于所使用的帧数。然后每个帧占用特定的页面并尝试访问它。当帧已填满时，实际问题开始出现。固定数量的帧通过使用第一帧存在进行填充。这个概念是借助需求分页实现的。

在填满帧后，等待队列中的下一个页面尝试进入帧。如果帧存在，则不会出现问题。因为要搜索的页面已经存在于分配的帧中。

如果要搜索的页面在帧中找到，则此过程称为页面命中。

如果要搜索的页面在帧中找不到，则此过程称为页面错误。

当发生页面错误时，会出现此问题，然后先进先出页面置换算法出现。

先进先出（FIFO）页面置换算法会移除长时间被分配的帧中的页面。这意味着在帧中停留时间较长的无用页面将被移除，并允许准备好占用帧的新页面通过先进先出页面置换算法。

让我们通过一个示例来了解先进先出页面置换算法的工作原理。

示例：

考虑引用字符串6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0，内存中有三个帧，并使用FIFO（先进先出）页面置换算法计算页面错误的数量。

要记住的要点

找不到页面 – – – > 页面错误

找到页面 – – – > 页面命中

参考字符串：

页面点击数 = 8

页面错误数 = 12

页面点击与页面错误的比例 = 8 : 12 – – – > 2 : 3 – – – > 0.66

页面点击百分比 = 8 *100 / 20 = 40%

页面错误百分比 = 100 – 页面点击百分比 = 100 – 40 = 60%

解释

首先，用初始页面填充框架。然后，在填充框架后，我们需要为新页面创建一个可占用的空间。所以，通过先进先出页面置换算法，我们删除包含最旧页面的框架。通过删除较旧的页面，我们为新框架提供了使用先进先出页面置换算法创建的空闲空间。

最佳页面置换算法

这是页面置换算法的第二个基本算法。此算法基本上依赖于所使用的框架数。然后，每个框架占用一定的页面并尝试访问它。当填充框架时，真正的问题开始。固定数量的框架是通过第一个现有的框架填充的。这个概念通过需求分页来实现

填充完成后，等待队列中的下一个页面尝试进入框架。如果框架存在，则不会出现问题。因为要搜索的页面已经存在于分配的框架中。

如果在框架中找不到要搜索的页面，则该过程称为页面错误。

当出现页面错误时，出现这个问题，最佳页面置换算法就会出现。

最佳页面置换算法遵循某个原则。原则是:

将未来最长时间内不使用的页面替换

这个原则意味着在所有框架填满后，看看哪些页面将占用框架。不断检查已经在框架中可用的页面。选择最后一个页面。

示例:

假设参考字符串为:

0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0

6, 1, 2在占用框架。

现在我们需要通过删除一个页面从页面中输入0到框架中。

所以，让我们检查最后发生的页面编号是哪一个。

从子序列0, 3, 4, 6, 0, 2, 1可以看出，1是最后出现的页面编号。所以我们可以说通过从框架中删除1，将0放在框架中。

让我们通过一个例子来了解最佳页面置换算法的工作原理。

示例:

考虑引用字符串6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 4, 0，对于具有三个帧的内存使用OPTIMAL页面替换算法计算页面错误的数量。

要记住的要点

找不到页面 – – -＞页面错误

找到页面 – – -＞页面命中

引用字符串：

页面点击次数 = 8

页面错误次数 = 12

页面点击与错误比率 = 8 : 12 – – – > 2 : 3 – – – > 0.66

页面点击百分比 = 8 *100 / 20 = 40%

页面错误百分比 = 100 – 页面点击百分比 = 100 – 40 = 60%

说明

首先，用初始页面填充框架。然后，在填充框架后，我们需要为新的页面创建一个空间。

在这里，我们将用我们拥有的页面和空闲的框架来填充空白空间。当页面没有空间可供占用时，问题就会出现。我们已经知道，我们将在将来的时间中替换未被使用的页面。

现在出现了一个问题，如果框架中有一个不存在的页面怎么办。

假设参考字符串为：

0, 2, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0

在框架中占用框架的是6、1、5。

在这里，我们可以看到页面号为5的页面在参考字符串中不存在。但是数字5在框架中存在。因此，由于页面号5不存在，我们将其删除，并让其他页面来占据该位置。

最近最久未使用（Least Recently Used，LRU）页面替换算法

这是页面替换算法中的最后一个基本算法。此算法基本上取决于所使用的框架数。然后，每个框架占用某一页并尝试访问它。当框架填满后，实际问题开始出现。通过Demand Paging来帮助填充了固定数量的框架。

在填充框架后，等待队列中的下一个页面尝试进入框架。如果框架存在，则不会出现问题。因为要搜索的页面已经在分配的框架中。

如果在框架中找不到要搜索的页面，则称此过程为页面错误。

当页面错误发生时，最近最久未使用（LRU）页面替换算法就会出现。

最近最久未使用（LRU）页面替换算法遵循以下原则：

用过去最少的时间维度上最近使用的页面来替换页面。

例子：

假设参考字符串为：

6, 1, 1, 2, 0, 3, 4, 6, 0

页面号为6、1、2的页面在框架中占用框架。

现在，我们需要为页面号为0的页面分配一个空间。

现在，我们需要回到过去检查哪个页面可以被替换。

6 是 Frame 中最老的页面。

所以，将 6 替换为页面编号为 0 的页面。

让我们通过一个例子来了解最近最少使用 (LRU) 页面置换算法的工作原理。

示例：

考虑引用字符串 6、1、1、2、0、3、4、6、0、2、1、2、1、2、0、3、2、1、2、0，内存有三个框架，通过使用最近最少使用(LRU)页面置换算法计算页面错误的数量。

要记住的要点：

页面未找到 – – – > 页面错误

页面找到 – – – > 页面命中

引用字符串：

页面点击次数 = 7

页面错误次数 = 13

页面点击和页面错误的比率 = 7 : 12 – – – > 0.5833 : 1

页面点击的百分比 = 7 * 100 / 20 = 35%

页面错误的百分比 = 100 – 页面点击的百分比 = 100 – 35 = 65%

解释

首先，用初始页面填充框架。然后，当框架已满时，我们需要为新页面腾出空间。

在这里，我们将用我们有的页面和空白框架填充空白空间。当没有页面可以占用空间时，问题就出现了。我们已经知道，我们将替换在过去最长时间内未使用或者可以说是非常久远的页面。