MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

分页内存管理方式的运行机制

2022-01-072.7k 阅读

分页内存管理方式的基础概念

内存管理的重要性

在现代计算机系统中，内存是一种极其关键的资源。程序的运行需要将其指令和数据加载到内存中，CPU 才能对其进行处理。随着计算机技术的发展，程序规模越来越大，功能越来越复杂，如何高效地管理内存，为众多程序合理分配内存空间，成为了操作系统设计中的核心问题之一。良好的内存管理不仅能提高内存利用率，还能提升系统的整体性能和稳定性。

分页内存管理的提出背景

早期的内存管理方式，如分区管理，存在着诸多弊端。例如，固定分区管理虽然简单，但会造成内存空间的浪费，因为程序大小很难刚好与分区大小匹配；可变分区管理虽然在一定程度上解决了固定分区的问题，但随着内存的不断分配和回收，会产生大量的外部碎片，导致内存无法有效利用。分页内存管理方式就是为了解决这些问题而提出的。它将内存空间和程序地址空间都进行划分，通过一种映射机制来实现程序在内存中的存储和访问，大大提高了内存的利用率和管理效率。

分页的基本概念

分页内存管理把内存空间划分为大小相等的块，这些块称为页框（Page Frame）或物理页。同样，把程序的逻辑地址空间也划分为与页框大小相同的块，称为页（Page）或逻辑页。通常，页框和页的大小是固定的，常见的页大小有 4KB、8KB 等。这种划分方式使得程序可以离散地存储在内存的不同页框中，而不再需要连续的内存空间。每个页都有一个唯一的页号，每个页框也有一个唯一的页框号。

分页内存管理方式的运行机制

地址结构

在分页系统中，逻辑地址由页号（Page Number）和页内偏移（Page Offset）两部分组成。假设页大小为 (2^n) 字节，那么页内偏移需要 (n) 位来表示。例如，若页大小为 4KB（即 (2^{12}) 字节），则页内偏移需要 12 位。而逻辑地址中的剩余部分则表示页号。

以一个 32 位的逻辑地址为例，如果页大小为 4KB，那么低 12 位表示页内偏移，高 20 位表示页号。通过这种地址结构，操作系统可以很方便地从逻辑地址中提取出页号和页内偏移，从而进行地址转换。

页表

为了实现从逻辑页到物理页框的映射，操作系统引入了页表（Page Table）的概念。页表是一个数据结构，它记录了每个逻辑页对应的物理页框号。每个进程都有自己独立的页表，操作系统通过维护这些页表来管理进程的内存映射。

页表通常存储在内存中，其结构一般包含页号和对应的页框号两列。当进程访问某个逻辑地址时，操作系统首先根据该逻辑地址中的页号在页表中查找对应的页框号，然后将页框号与逻辑地址中的页内偏移组合，形成物理地址，从而实现对内存的访问。

地址转换过程

  1. 逻辑地址解析：当 CPU 执行一条指令，需要访问内存中的数据或指令时，会生成一个逻辑地址。操作系统接收到这个逻辑地址后，首先根据预先设定的页大小，将逻辑地址拆分为页号和页内偏移。
  2. 页表查找：通过页号在进程的页表中查找对应的页框号。如果页表项存在且有效，说明该逻辑页已经被加载到内存中，操作系统可以获取到对应的页框号。
  3. 物理地址生成：将获取到的页框号与逻辑地址中的页内偏移组合，形成物理地址。这个物理地址就是数据或指令在内存中的实际存储地址，CPU 可以根据这个物理地址访问内存。

下面通过一个简单的代码示例来说明地址转换的过程（假设使用 C 语言和简单的模拟环境）：

#include <stdio.h>

// 假设页大小为 4KB (2^12)
#define PAGE_SIZE 4096  
// 假设逻辑地址空间为 32 位
#define ADDRESS_BITS 32  
// 页内偏移位数
#define OFFSET_BITS 12  
// 页号位数
#define PAGE_NUMBER_BITS (ADDRESS_BITS - OFFSET_BITS)  

// 模拟页表结构
typedef struct {
    int pageFrameNumber;
    int valid;
} PageTableEntry;

// 假设进程的页表有 1024 个页表项
PageTableEntry pageTable[1024];

// 初始化页表
void initPageTable() {
    for (int i = 0; i < 1024; i++) {
        pageTable[i].valid = 0;
    }
}

// 模拟将一个逻辑页加载到内存中的操作
void loadPageToMemory(int pageNumber, int pageFrameNumber) {
    pageTable[pageNumber].pageFrameNumber = pageFrameNumber;
    pageTable[pageNumber].valid = 1;
}

// 地址转换函数
int translateAddress(int logicalAddress) {
    // 提取页号
    int pageNumber = (logicalAddress >> OFFSET_BITS) & ((1 << PAGE_NUMBER_BITS) - 1);
    // 提取页内偏移
    int offset = logicalAddress & ((1 << OFFSET_BITS) - 1);

    if (!pageTable[pageNumber].valid) {
        printf("Page fault! Page %d not in memory.\n", pageNumber);
        return -1;
    }

    int pageFrameNumber = pageTable[pageNumber].pageFrameNumber;
    // 生成物理地址
    int physicalAddress = (pageFrameNumber << OFFSET_BITS) | offset;
    return physicalAddress;
}

int main() {
    initPageTable();
    // 模拟将逻辑页 10 加载到页框 20
    loadPageToMemory(10, 20);

    int logicalAddress = 10 * PAGE_SIZE + 100; // 逻辑地址，假设在逻辑页 10 内偏移 100 的位置
    int physicalAddress = translateAddress(logicalAddress);

    if (physicalAddress != -1) {
        printf("Logical address %d translated to physical address %d.\n", logicalAddress, physicalAddress);
    }

    return 0;
}

在上述代码中，首先定义了页大小、地址位数等相关常量，然后创建了一个简单的页表结构 PageTableEntry。initPageTable 函数用于初始化页表，loadPageToMemory 函数模拟将逻辑页加载到内存的操作，translateAddress 函数实现了从逻辑地址到物理地址的转换。在 main 函数中，进行了页表初始化、加载逻辑页到内存以及地址转换的操作。

快表（TLB）

虽然页表解决了逻辑地址到物理地址的映射问题，但由于页表存储在内存中，每次地址转换都需要访问内存两次（一次访问页表获取页框号，一次根据物理地址访问数据），这大大增加了内存访问的时间开销。为了提高地址转换的速度，操作系统引入了快表（Translation Lookaside Buffer，TLB），也称为联想寄存器。

快表是一种高速缓存，它存储了最近经常访问的页表项。当进行地址转换时，操作系统首先在快表中查找，如果找到对应的页表项，就可以直接获取页框号，而无需访问内存中的页表，从而大大提高了地址转换的速度。只有当快表中未命中时，才会去内存中的页表查找，并将查找到的页表项存入快表中，以便后续使用。

快表的命中率是衡量其性能的重要指标。命中率越高，地址转换的速度就越快，系统性能也就越好。为了提高快表命中率，操作系统通常采用一些替换算法，如最近最少使用（LRU）算法，当快表已满且需要插入新的页表项时，将最近最少使用的页表项替换出去。

页分配与回收

  1. 页分配：当一个进程启动或需要扩展内存时，操作系统需要为其分配页框。操作系统维护一个空闲页框链表，记录所有空闲的页框。当需要分配页框时，从空闲页框链表中选取一个或多个空闲页框分配给进程，并更新进程的页表，将新分配的页框号与相应的逻辑页号建立映射关系。
  2. 页回收：当进程结束或释放部分内存时，操作系统需要回收这些页框。操作系统首先检查进程的页表，将不再使用的页表项标记为无效，并将对应的页框归还给空闲页框链表，以便重新分配给其他进程使用。

页面置换算法

在分页内存管理中，由于内存空间有限，当进程所需的页框数超过系统可用的页框数时，就需要将一些暂时不用的页从内存中置换出去，为新的页腾出空间。这就涉及到页面置换算法的选择。一个好的页面置换算法应该尽量减少页面置换的次数，从而降低系统的开销，提高系统性能。常见的页面置换算法有以下几种：

  1. 最佳置换算法（Optimal，OPT）：这是一种理论上的最优算法，它选择在未来最长时间内不会被访问的页进行置换。然而，由于操作系统无法预知未来的访问情况，该算法实际上无法实现，但它可以作为衡量其他页面置换算法性能的标准。
  2. 先进先出算法（First In First Out，FIFO）：FIFO 算法按照页面进入内存的先后顺序进行置换，即最早进入内存的页最先被置换出去。这种算法实现简单，但性能较差，因为它没有考虑页面的使用情况，可能会把一些经常使用的页置换出去。
  3. 最近最少使用算法（Least Recently Used，LRU）：LRU 算法选择最近一段时间内使用次数最少的页进行置换。它基于一个假设，即如果一个页在过去很长时间内没有被使用，那么在未来它被使用的可能性也较小。LRU 算法性能较好，但实现起来相对复杂，需要记录每个页面的使用时间。
  4. 时钟算法（Clock）：时钟算法是一种简单有效的页面置换算法，它结合了 FIFO 和 LRU 的优点。操作系统为每个页设置一个访问位，当页被访问时，访问位被置为 1。时钟算法维护一个类似时钟的循环链表，当需要置换页时，从当前指针位置开始扫描链表，寻找访问位为 0 的页进行置换，如果扫描过程中遇到访问位为 1 的页，则将其访问位清零并继续扫描。

下面通过一段简单的 Python 代码来模拟 FIFO 和 LRU 页面置换算法：

class FIFOPageReplacement:
    def __init__(self, frame_count):
        self.frame_count = frame_count
        self.frames = []
        self.page_faults = 0

    def access_page(self, page):
        if page not in self.frames:
            if len(self.frames) == self.frame_count:
                self.frames.pop(0)
            self.frames.append(page)
            self.page_faults += 1

class LRUPageReplacement:
    def __init__(self, frame_count):
        self.frame_count = frame_count
        self.frames = []
        self.page_faults = 0
        self.access_order = []

    def access_page(self, page):
        if page not in self.frames:
            if len(self.frames) == self.frame_count:
                lru_page = self.access_order.pop(0)
                self.frames.remove(lru_page)
            self.frames.append(page)
            self.page_faults += 1
        else:
            self.access_order.remove(page)
        self.access_order.append(page)

# 测试代码
page_sequence = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
frame_count = 3

fifo = FIFOPageReplacement(frame_count)
for page in page_sequence:
    fifo.access_page(page)
print("FIFO 页面置换算法的缺页次数:", fifo.page_faults)

lru = LRUPageReplacement(frame_count)
for page in page_sequence:
    lru.access_page(page)
print("LRU 页面置换算法的缺页次数:", lru.page_faults)

在上述 Python 代码中，分别定义了 FIFOPageReplacement 和 LRUPageReplacement 类来实现 FIFO 和 LRU 页面置换算法。每个类都有一个 access_page 方法，用于模拟页面访问操作，并统计缺页次数。在测试部分，定义了一个页面访问序列和页框数，分别使用 FIFO 和 LRU 算法进行模拟，并输出缺页次数。

分页内存管理方式的优点与不足

优点

  1. 提高内存利用率：分页内存管理允许程序离散地存储在内存中，有效地解决了外部碎片问题，提高了内存的利用率。即使内存中存在大量不连续的空闲页框，也可以满足程序的内存需求。
  2. 便于内存管理：通过页表和地址转换机制，操作系统可以方便地管理进程的内存空间，实现内存的分配、回收和保护等功能。每个进程都有自己独立的页表，相互之间不会干扰，提高了系统的稳定性和安全性。
  3. 支持虚拟内存：分页内存管理是实现虚拟内存的基础。通过将部分暂时不用的页存储在磁盘上，当需要时再调入内存，使得系统可以运行比实际内存更大的程序，提高了系统的并发处理能力。

不足

  1. 页表开销：每个进程都需要维护一个页表，随着进程数量的增加和程序规模的扩大，页表占用的内存空间也会相应增加。此外，为了提高地址转换速度而引入的快表，虽然在一定程度上缓解了页表访问的开销，但快表本身也需要占用一定的硬件资源。
  2. 页面置换开销：当发生页面置换时，需要将磁盘上的页调入内存，并将内存中的页调出到磁盘，这涉及到磁盘 I/O 操作，而磁盘 I/O 操作的速度相对较慢，会导致系统性能下降。此外，选择不合适的页面置换算法也会增加页面置换的次数，进一步降低系统性能。
  3. 程序局部性问题：虽然分页内存管理在一定程度上提高了内存利用率，但如果程序的局部性较差，即程序在执行过程中频繁地访问不同的页，会导致大量的页面置换，降低系统性能。因此，在编写程序时，需要尽量考虑程序的局部性，以提高分页内存管理的效率。

分页内存管理方式的改进与扩展

多级页表

为了减少页表占用的内存空间，操作系统引入了多级页表的概念。多级页表将页表进行分级，例如二级页表。在二级页表中，第一级页表称为页目录（Page Directory），它的每个表项指向一个第二级页表，第二级页表才真正记录逻辑页到物理页框的映射关系。

当进行地址转换时，首先根据逻辑地址中的页目录号在页目录中查找对应的第二级页表地址，然后根据逻辑地址中的页号在第二级页表中查找对应的页框号。这样，只有当进程实际使用到某些页时，才会为这些页分配第二级页表，从而大大减少了页表占用的内存空间。

反置页表

传统的页表是基于进程的，每个进程都有自己独立的页表，这在进程数量较多时会占用大量的内存空间。反置页表（Inverted Page Table）则是基于物理页框的，系统中只有一个反置页表，它记录了每个物理页框当前被哪个进程的哪个逻辑页占用。

当进行地址转换时，需要遍历反置页表来查找对应的物理页框号。虽然反置页表可以大大减少页表占用的内存空间，但地址转换的时间开销相对较大，需要采用一些优化措施，如使用哈希表等数据结构来加快查找速度。

分页与分段的结合

分页内存管理解决了内存的离散存储和外部碎片问题，而分段内存管理则更符合程序的逻辑结构，它将程序按照逻辑功能划分为不同的段，如代码段、数据段、栈段等。将分页与分段结合起来，可以充分发挥两者的优点。

在这种方式下，程序的地址空间首先被划分为多个段，每个段再进行分页。逻辑地址由段号、段内页号和页内偏移三部分组成。地址转换时，首先根据段号找到对应的段表，从段表中获取该段的页表起始地址，然后根据段内页号在页表中查找对应的页框号，最后与页内偏移组合形成物理地址。这种方式既满足了程序的逻辑结构需求，又提高了内存的利用率。

综上所述，分页内存管理方式作为现代操作系统内存管理的重要组成部分，通过合理的地址结构、页表机制、地址转换过程以及页面置换算法等，有效地提高了内存的利用率和系统的性能。虽然它存在一些不足之处，但通过不断的改进和扩展，如多级页表、反置页表以及与分段的结合等，使其在复杂的计算机系统环境中仍然发挥着重要的作用。