操作系统中的页面置换算法 (OS)

12 Feb 2025 | 阅读 10 分钟

Page Replacement Algorithms in Operating Systems (OS)

页面置换算法是操作系统内存管理子系统中的重要组成部分。当需要将新页面调入内存但内存空间不足时，它们决定要将哪个内存页面换出。高效的页面置换算法可以显著提高系统整体性能，而低效的算法可能导致抖动和设备性能下降。

虚拟内存概述

在深入研究页面置换算法之前，了解虚拟内存的概念非常重要。虚拟内存是一种内存管理方法，它为应用程序提供了拥有大量连续内存块的假象，尽管物理内存是碎片化的或容量远远小于所需的内存。操作系统通过将虚拟内存划分为页面（通常为 4 KB 大小）并将其映射到物理内存帧来管理虚拟内存。

当应用程序访问内存位置时，内存管理单元（MMU）会将虚拟地址翻译成物理地址。如果页面不在物理内存中，则会发生页面错误，操作系统必须将页面从二级存储（如硬盘）提供到物理内存中。

页面置换的必要性

当发生页面错误且物理内存已满时，操作系统需要决定要逐出哪个页面，以便为当前页面腾出空间。这个决定至关重要，因为错误的决定可能导致内存利用效率低下和系统性能缓慢。页面置换算法旨在做出最佳决策，以减少页面错误数量并确保内存利用效率。

常见的页面置换算法

多年来，已经开发了许多页面置换算法，它们各有优缺点。最常见的包括：

先进先出 (FIFO)
最佳页面置换 (OPT)
最近最少使用 (LRU)
时钟 (第二次机会)
最不常使用 (LFU)
最近最少使用 (NRU)
老化

让我们详细探讨一下这些算法。

1. 先进先出 (FIFO)

FIFO 算法是最简单的页面置换算法。它维护一个内存中页面的队列，最老的页面位于队列的头部。当需要替换页面时，最老的页面（队列头部的页面）将被逐出。

示例

页面引用序列 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7

帧数 3

页面引用	1	2	3	4	2	1	5	6	2	1	2	3	7
帧 1	1	1	1	4	4	4	5	5	5	1	1	1	1
帧 2	-	2	2	2	2	2	2	6	6	6	6	3	3
帧 3	-	-	3	3	3	1	1	1	2	2	2	2	7
页面错误	是的	是的	是的	是的	不能	是的	是的	是的	是的	是的	不能	是的	是的

优点

易于实现
易于理解

缺点

这可能导致糟糕的性能（Belady 异常），即增加页面帧的数量会增加页面错误的数量。

2. 最佳页面置换 (OPT)

OPT 算法是理论上的，不适用于实际实现，因为它需要对页面引用字符串的未来知识。它会替换将在未来最长时间内不会被使用的页面。

示例

页面引用序列 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7

帧数 3

页面引用	1	2	3	4	2	1	5	6	2	1	2	3	7
帧 1	1	1	1	4	4	4	4	6	6	6	6	6	7
帧 2	-	2	2	2	2	2	5	5	5	5	5	3	3
帧 3	-	-	3	3	3	1	1	1	2	2	2	2	2
页面错误	是的	是的	是的	是的	不能	是的	是的	是的	是的	不能	不能	是的	是的

优点

提供最佳页面错误数量

缺点

由于需要未来的页面引用知识，因此不适用于实际实现

3. 最近最少使用 (LRU)

LRU 算法会替换最长时间未使用的页面。它通过假设最近使用的页面很可能很快会被再次使用来近似最佳算法。

示例

页面引用序列 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7

帧数 3

页面引用	1	2	3	4	2	1	5	6	2	1	2	3	7
帧 1	1	1	1	4	4	4	4	6	6	6	6	6	6
帧 2	-	2	2	2	2	2	5	5	5	5	5	3	7
帧 3	-	-	3	3	3	1	1	1	2	2	2	3	3
页面错误	是的	是的	是的	是的	不能	是的	是的	是的	是的	不能	不能	是的	是的

实施

LRU 的实现可以通过堆栈或计数器来完成。堆栈实现维护一个页面编号的堆栈，其中最近使用的页面位于顶部。当访问一个页面时，它会从堆栈中移除并推到顶部。位于底部的页面是最近最少使用的。

这是使用 Python 实现 LRU 的简单示例

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.lru = []
    
    def access_page(self, page: int):
        if page in self.cache:
            self.lru.remove(page)
        elif len(self.cache) >= self.capacity:
            lru_page = self.lru.pop(0)
            del self.cache[lru_page]
        self.cache[page] = True
        self.lru.append(page)
    
    def display(self):
        print("Current LRU state:", self.lru)

# Usage
lru_cache = LRUCache(3)
pages = [1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7]
for page in pages:
    lru_cache.access_page(page)
    lru_cache.display()

优点

高效且能很好地近似最佳算法
在实践中表现良好

缺点

比 FIFO 更复杂
需要额外的堆栈或计数器等数据结构

4. 时钟 (第二次机会)

时钟算法是 LRU 的一种近似算法，它使用循环缓冲区（类似于时钟）来跟踪页面引用。每个页面都有一个引用位，当访问页面时会将其设置为 1。当需要替换页面时，算法会扫描循环缓冲区。如果找到引用位为 1 的页面，则会清除该位并继续。如果找到引用位为 0 的页面，则会替换该页面。

示例

页面引用序列 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7

帧数 3

页面引用	1	2	3	4	2	1	5	6	2	1	2	3	7
帧 1	1	1	1	4	4	4	4	6	6	6	6	6	6
帧 2	-	2	2	2	2	2	5	5	5	5	5	5	7
帧 3	-	-	3	3	3	1	1	1	2	2	2	3	3
页面错误	是的	是的	是的	是的	不能	是的	是的	是的	是的	不能	不能	是的	是的

实施

这是在 Python 中实现时钟算法的简单示例

class ClockPageReplacement:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.pages = [-1] * capacity
        self.reference_bits = [0] * capacity
        self.pointer = 0
    
    def access_page(self, page: int):
        if page in self.pages:
            index = self.pages.index(page)
            self.reference_bits[index] = 1
        else:
            while self.reference_bits[self.pointer] == 1:
                self.reference_bits[self.pointer] = 0
                self.pointer = (self.pointer + 1) % self.capacity
            self.pages[self.pointer] = page
            self.reference_bits[self.pointer] = 1
            self.pointer = (self.pointer + 1) % self.capacity
    
    def display(self):
        print("Current Clock state:", self.pages)

# Usage
clock_replacement = ClockPageReplacement(3)
pages = [1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7]
for page in pages:
    clock_replacement.access_page(page)
    clock_replacement.display()

优点

简单高效
LRU 的良好近似

缺点

在某些情况下可能不如 LRU 性能好

5. 最不常使用 (LFU)

LFU 算法替换使用频率最低的页面。它跟踪每个页面的使用频率，并逐出频率最低的那个。

示例

页面引用序列 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7

帧数 3

页面引用	1	2	3	4	2	1	5	6	2	1	2	3	7
帧 1	1	1	1	4	4	4	5	5	5	5	5	5	5
帧 2	-	2	2	2	2	2	2	6	6	6	6	3	3
帧 3	-	-	3	3	3	1	1	1	2	2	2	2	7
页面错误	是的	是的	是的	是的	不能	是的	是的	是的	是的	不能	不能	是的	是的

实施

这是在 Python 中实现 LFU 的简单示例

class LFUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.freq = {}
        self.capacity = capacity
    
    def access_page(self, page: int):
        if page in self.cache:
            self.freq[page] += 1
        else:
            if len(self.cache) >= self.capacity:
                lfu_page = min(self.freq, key=self.freq.get)
                del self.cache[lfu_page]
                del self.freq[lfu_page]
            self.cache[page] = True
            self.freq[page] = 1
    
    def display(self):
        print("Current LFU state:", list(self.cache.keys()))

# Usage
lfu_cache = LFUCache(3)
pages = [1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7]
for page in pages:
    lfu_cache.access_page(page)
    lfu_cache.display()

优点

适用于具有不同访问模式的工作负载

缺点

维护频率计数可能很昂贵
如果所有页面的访问频率相似，则性能可能不佳

6. 最近最少使用 (NRU)

NRU 算法根据页面是否被引用或修改，将页面分为四类。当需要替换页面时，算法会从最不常用的类别中随机选择一个页面。

类别是

未引用，未修改
未引用，已修改
已引用，未修改
已引用，已修改

示例

页面引用序列 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7

帧数 3

页面引用	1	2	3	4	2	1	5	6	2	1	2	3	7
帧 1	1	1	1	4	4	4	5	5	5	5	5	5	7
帧 2	-	2	2	2	2	2	2	6	6	6	6	3	3
帧 3	-	-	3	3	3	1	1	1	2	2	2	2	2
页面错误	是的	是的	是的	是的	不能	是的	是的	是的	是的	不能	不能	是的	是的

实施

这是在 Python 中实现 NRU 的简单示例

import random

class NRUPageReplacement:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.pages = [-1] * capacity
        self.reference_bits = [0] * capacity
        self.modified_bits = [0] * capacity
    
    def access_page(self, page: int, modified: bool):
        if page in self.pages:
            index = self.pages.index(page)
            self.reference_bits[index] = 1
            if modified:
                self.modified_bits[index] = 1
        else:
            class_0 = [i for i in range(self.capacity) if self.reference_bits[i] == 0 and self.modified_bits[i] == 0]
            class_1 = [i for i in range(self.capacity) if self.reference_bits[i] == 0 and self.modified_bits[i] == 1]
            class_2 = [i for i in range(self.capacity) if self.reference_bits[i] == 1 and self.modified_bits[i] == 0]
            class_3 = [i for i in range(self.capacity) if self.reference_bits[i] == 1 and self.modified_bits[i] == 1]
            
            for class_pages in [class_0, class_1, class_2, class_3]:
                if class_pages:
                    replace_index = random.choice(class_pages)
                    break
            
            self.pages[replace_index] = page
            self.reference_bits[replace_index] = 1
            self.modified_bits[replace_index] = 1 if modified else 0
    
    def display(self):
        print("Current NRU state:", self.pages)

# Usage
nru_replacement = NRUPageReplacement(3)
pages = [(1, False), (2, False), (3, False), (4, True), (2, False), (1, True), (5, False), (6, True), (2, False), (1, False), (2, True), (3, False), (7, True)]
for page, modified in pages:
    nru_replacement.access_page(page, modified)
    nru_replacement.display()

优点

简单易于实现

在简单性和性能之间取得平衡

缺点

随机选择可能导致次优性能

需要定期重置引用位

7. Aging (老化)

Aging 算法是 LRU 的一个变体，它使用计数器来跟踪页面引用。每个页面都有一个关联的计数器，当页面被引用时会对其进行增量。定期对计数器进行右移操作以“老化”页面。当需要替换页面时，将逐出计数器最小的页面。

示例

页面引用序列 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7

帧数 3

页面引用	1	2	3	4	2	1	5	6	2	1	2	3	7
帧 1	1	1	1	4	4	4	5	5	5	5	5	5	7
帧 2	-	2	2	2	2	2	2	6	6	6	6	3	3
帧 3	-	-	3	3	3	1	1	1	2	2	2	2	2
页面错误	是的	是的	是的	是的	不能	是的	是的	是的	是的	不能	不能	是的	是的

实施

这是在 Python 中实现 Aging 算法的简单示例

class AgingPageReplacement:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.pages = [-1] * capacity
        self.counters = [0] * capacity
    
    def access_page(self, page: int):
        if page in self.pages:
            index = self.pages.index(page)
            self.counters[index] += 1
        else:
            if -1 in self.pages:
                index = self.pages.index(-1)
            else:
                index = self.counters.index(min(self.counters))
            self.pages[index] = page
            self.counters[index] = 1
    
    def age_pages(self):
        self.counters = [counter >> 1 for counter in self.counters]
    
    def display(self):
        print("Current Aging state:", self.pages)

# Usage
aging_replacement = AgingPageReplacement(3)
pages = [1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7]
for page in pages:
    aging_replacement.access_page(page)
    aging_replacement.age_pages()
    aging_replacement.display()

优点

LRU 的良好近似
简单高效

缺点

需要计数器等额外数据结构
定期老化可能增加开销

结论

页面置换算法在操作系统内存管理的性能中起着至关重要的作用。每种算法都有其优缺点，算法的选择会显着影响系统的平均性能。虽然 FIFO 易于实现，但它可能会遭受 Belady 异常。OPT 在理论上提供最佳性能，但实际应用不可行。LRU 很好地近似了 OPT，并且在实践中表现良好，尽管实现起来可能很复杂。时钟、LFU、NRU 和 Aging 在复杂性和性能之间提供了不同的权衡。

理解这些算法的细微差别并为给定的工作负载选择正确的算法，对于优化系统性能和确保内存利用率至关重要。

下一个主题LRU 和 FIFO 的 Gate 2015 问题

操作系统中的页面置换算法 (OS)

虚拟内存概述

页面置换的必要性

常见的页面置换算法

1. 先进先出 (FIFO)

2. 最佳页面置换 (OPT)

3. 最近最少使用 (LRU)

4. 时钟 (第二次机会)

5. 最不常使用 (LFU)

6. 最近最少使用 (NRU)

7. Aging (老化)

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

操作系统

进程管理

同步

死锁

内存管理

文件管理

其他

选择题

操作系统中的页面置换算法 (OS)

虚拟内存概述

页面置换的必要性

常见的页面置换算法

1. 先进先出 (FIFO)

2. 最佳页面置换 (OPT)

3. 最近最少使用 (LRU)

4. 时钟 (第二次机会)

5. 最不常使用 (LFU)

6. 最近最少使用 (NRU)

7. Aging (老化)

结论

相关帖子

关于最佳适应和首次适应的 GATE 题目

查找最佳页面大小

虚拟内存

请求分页

通过页表映射

OS 中的分段

分段分页

动态分区

动态分区的位图

物理地址与逻辑地址

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器