操作系统：页面替换算法

科技2022-08-15 94

什么是分页？

在计算机操作系统中，分页是一种内存管理方案，计算机可以通过它来存储和从辅助存储器中检索数据，以供在主存储器中使用。在这种方案中，操作系统从二级存储中以相同大小的块（称为page）检索数据。分页是现代操作系统中虚拟内存实现的重要组成部分，它使用二级存储来使程序超出可用物理内存的大小。

为简单起见，主存储器称为“ RAM”（“随机存储器”的缩写），辅助存储器称为“磁盘”（“硬盘存储器，或固态存储器”的简写），但是概念并不取决于这些术语是否从字面上适用于特定的计算机系统。

什么是内存管理？

内存管理是应用于计算机内存的一种资源管理形式。内存管理的基本要求是提供一种方法，可以根据它们的请求为程序动态分配内存的一部分，并在不再需要时释放它们以供重用。这对于任何随时可能进行多个进程的高级计算机系统都是至关重要的。

已经设计出几种方法来提高存储器管理的有效性。虚拟内存系统将进程使用的内存地址与实际物理地址分开，从而允许进程分离，并使用分页或交换到辅助存储来增加虚拟地址空间的大小，使其超出可用的RAM数量。虚拟内存管理器的质量可能会对整体系统性能产生广泛影响。

什么是页面替换？

现代操作系统使用分页进行内存管理，并且很多时候需要页面替换。页面替换是将内存中当前存在的页面替换为需要但内存中不存在的页面的过程。这种情况称为页面错误。关于百科详细解释如下：

在计算机操作系统使用分页的虚拟化内存管理，页面置换算法决定哪些内存页页出，有时也被称为换出，或写入到磁盘上，当一个页面被分配的内存需求。当请求的页面不在内存中时发生页面替换（页面错误），并且空闲页面不能用于满足分配，这是因为没有页面，或者空闲页面的数量低于某个阈值。

当再次选择被替换的页面并调出页面时，必须将其调入页面（从磁盘读入），这需要等待I / O完成。这决定了页面替换算法的质量：等待页面插入的时间越短，算法越好。页面替换算法查看有关硬件提供的页面访问的有限信息，并尝试猜测应该替换哪些页面以最大程度地减少页面遗漏的总次数，同时平衡此操作的成本（主存储和处理器时间）算法本身。从竞争分析的角度来看，页面替换问题是一个典型的在线问题，从某种意义上说，最佳确定性算法是已知的。

页面替换算法的目标是减少页面错误的数量，从而提高整体性能。有许多用于页面替换的算法。我们在这里讨论一些。

先进先出（FIFO）

先进先出页面替换算法是最简单的页面替换算法。它维护一个队列以跟踪所有页面。我们总是将新页面添加到队列的末尾。当队列已满并且出现页面错误时，我们将删除队列前面的页面，并在队列末尾添加一个新页面。通过这种方式，我们将保持先进先出的技术，即，首先从内存中删除首先插入内存的页面。

例令页面引用字符串为{1、0、1、2、5、7、3、4、3、4、1}，总共有4个页面槽。然后，

贝拉迪的异常

Belady证明，某些页面参考字符串可能会增加页面槽，从而导致更多的页面错误。

示例考虑具有3个页面插槽和4个页面插槽的页面引用字符串{3，2，1，0，3，2，4，3，2，1，1，0，4}。具有3个页面插槽的页面错误= 3

具有4个页面插槽的页面错误= 4

最佳页面替换

该算法表示，如果我们知道将来要使用哪个页面，则可以优化页面替换技术。根据最佳页面替换算法，始终最好替换将来将最少使用的页面。

例令页面引用字符串为{2，3，4，2，1，3，7，5，5，4，3}，共有3个页面槽。然后，

LRU(最近最少使用)

该算法基于缓存技术。该算法表示替换最近最少使用的页面。

例令页面参考字符串为{1、2、3、4、1、2、5、1、2、3、4}，总共有3个页面槽。然后，

FIFO先进先出的实现

Java实现代码：

import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; class FirstInFirstOutPageReplacement { private static int pageFaults(int[] pageString, int pageSlots) { int faults = 0; // Set to store the elements present in queue, used to check if a page is present or not HashSet<Integer> set = new HashSet<>(); // Queue to maintain the order of insertion Queue<Integer> queue = new LinkedList<>(); // traverse the page string for (int i = 0; i < pageString.length; i++) { // if there are some empty slots if (queue.size() < pageSlots) { if (!set.contains(pageString[i])) { // and the current page is missing // add the page to set set.add(pageString[i]); // add the page to queue queue.add(pageString[i]); // it is a page fault, increment faults faults++; } } else { // there are no empty slots and if current page is absent if (!set.contains(pageString[i])) { // remove the first page in queue int removedPage = queue.poll(); // remove the page from set set.remove(removedPage); // add the new page to set set.add(pageString[i]); // add the new page to queue queue.add(pageString[i]); // it is page fault, increment faults faults++; } } } // return total number of page faults return faults; } public static void main(String[] args) { // Example int pageString[] = new int[] {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}; int pageSlots = 4; System.out.println(pageFaults(pageString, pageSlots)); } }

输入：

Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1} Page Slots = 4

输出：

C++实现代码：

#include <bits/stdc++.h> using namespace std; int pageFaults(int *pageString, int pageSlots, int n) { int faults = 0; // Set to store the elements present in queue, used to check if a page is present or not unordered_set<int> set; // Queue to maintain the order of insertion queue<int> q; // traverse the page string for (int i = 0; i < n; i++) { // if there are some empty slots if (q.size() < pageSlots) { if (set.find(pageString[i]) == set.end()) { // and the current page is missing // add the page to set set.insert(pageString[i]); // add the page to queue q.push(pageString[i]); // it is a page fault, increment faults faults++; } } else { // there are no empty slots and if current page is absent if (set.find(pageString[i]) == set.end()) { // remove the first page in queue int removedPage = q.front(); q.pop(); // remove the page from set set.erase(removedPage); // add the new page to set set.insert(pageString[i]); // add the new page to queue q.push(pageString[i]); // it is page fault, increment faults faults++; } } } return faults; } int main() { // Example int pageString[] = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}; int pageSlots = 4; cout<<pageFaults(pageString, pageSlots, sizeof(pageString) / sizeof(pageString[0]))<<endl; return 0; }

输入：