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

分页存储管理方式详解

2023-01-197.7k 阅读

分页存储管理方式的基本概念

在计算机系统中，内存是一个至关重要的资源，操作系统需要有效地管理内存以满足多个进程的需求。分页存储管理方式是现代操作系统广泛采用的一种内存管理技术，它将内存划分为固定大小的块，称为页框（Page Frame），同时将进程的逻辑地址空间也划分为相同大小的块，称为页（Page）。

分页的原理

  1. 页和页框的划分
    • 页框是物理内存中的固定大小的块。例如，常见的页框大小可能为4KB。在32位操作系统中，假设页框大小为4KB（即 (2^{12}) 字节），物理内存大小为4GB（即 (2^{32}) 字节），那么物理内存总共包含 (2^{32} \div 2^{12}=2^{20}) 个页框。
    • 进程的逻辑地址空间同样被划分为页，其大小与页框相同。这样，进程的逻辑地址就可以被表示为页号和页内偏移量的组合。
    • 例如，给定一个逻辑地址 (A)，假设页大小为 (L)，则页号 (p=\lfloor A/L \rfloor)，页内偏移量 (d = A \bmod L)。
  2. 地址映射
    • 当进程访问一个逻辑地址时，操作系统需要将其转换为物理地址。这通过页表（Page Table）来实现。页表是一个数据结构，它存储了每个页号对应的物理页框号。
    • 具体的地址转换过程如下：
      • 首先，从逻辑地址中提取页号 (p) 和页内偏移量 (d)。
      • 然后，根据页号 (p) 在页表中查找对应的物理页框号 (f)。
      • 最后，物理地址 (PA = f \times L + d)，其中 (L) 是页大小。
    • 例如，假设页大小为4KB（(L = 4096)），逻辑地址 (A = 10240)。则页号 (p=\lfloor 10240/4096 \rfloor = 2)，页内偏移量 (d = 10240 \bmod 4096 = 2048)。如果页表中页号2对应的物理页框号为5，则物理地址 (PA = 5 \times 4096+2048 = 22528)。

页表的组织与管理

  1. 页表结构
    • 最简单的页表是一个线性数组，数组的索引是页号，数组元素是对应的物理页框号。例如，在C语言中可以这样定义一个简单的页表示例：
#define PAGE_TABLE_SIZE 1024
typedef struct {
    int frame_number;
    // 其他标志位，如是否在内存中、是否被修改等
    int valid;
    int dirty;
} PageTableEntry;

PageTableEntry page_table[PAGE_TABLE_SIZE];
  • 这种简单的线性页表适用于小型系统，但对于大型系统，随着进程逻辑地址空间的增大，页表可能会变得非常庞大。例如，在64位系统中，如果页大小为4KB，逻辑地址空间为 (2^{64}) 字节，则页表可能需要存储 (2^{64} \div 2^{12}=2^{52}) 个页表项，这将占用大量的内存空间。
  1. 多级页表
    • 为了解决页表过大的问题，引入了多级页表。以二级页表为例：
      • 首先将逻辑地址空间划分为外层页号、内层页号和页内偏移量三部分。
      • 外层页表存储内层页表的物理地址，内层页表存储页框号。
      • 例如，假设逻辑地址为32位，页大小为4KB（(2^{12}) 字节），我们可以将32位地址划分为10位外层页号、10位内层页号和12位页内偏移量。
      • 外层页表最多有 (2^{10}) 个表项，每个表项存储一个内层页表的物理地址。内层页表同样最多有 (2^{10}) 个表项，每个表项存储一个物理页框号。这样，通过两级页表，我们可以有效地管理较大的逻辑地址空间，同时减少了页表占用的内存空间。
    • 在代码实现上，二级页表可以这样表示：
#define OUTER_PAGE_TABLE_SIZE 1024
#define INNER_PAGE_TABLE_SIZE 1024
typedef struct {
    int inner_page_table_address;
} OuterPageTableEntry;

typedef struct {
    int frame_number;
    int valid;
    int dirty;
} InnerPageTableEntry;

OuterPageTableEntry outer_page_table[OUTER_PAGE_TABLE_SIZE];
InnerPageTableEntry inner_page_table[OUTER_PAGE_TABLE_SIZE][INNER_PAGE_TABLE_SIZE];
  1. 快表（TLB）
    • 由于每次地址转换都需要访问页表，而页表通常存储在内存中，这会导致每次内存访问需要两次内存访问（一次访问页表，一次访问实际数据），大大降低了系统性能。为了解决这个问题，引入了快表（Translation Look - aside Buffer，TLB）。
    • TLB是一个高速缓存，它存储了最近经常使用的页表项。当进行地址转换时，首先在TLB中查找，如果找到对应的页表项（命中），则直接使用其中的物理页框号进行地址转换，无需再访问内存中的页表。如果TLB未命中，则再访问内存中的页表，并将新的页表项加入到TLB中（如果TLB已满，可能需要替换其中的一项）。
    • TLB的命中率对系统性能有很大影响。一般来说，TLB的命中率越高，系统的内存访问速度就越快。为了提高TLB命中率，操作系统可以采用合理的替换算法，如最近最少使用（LRU）算法等。

分页存储管理方式的内存分配与回收

在分页存储管理方式下，内存的分配和回收涉及到页框的分配与回收，以及页表的相应操作。

内存分配

  1. 页框分配算法
    • 首次适应算法（First Fit）：从空闲页框链表的头部开始查找，找到第一个能够满足进程页需求的页框块，将其分配给进程。例如，假设空闲页框链表为 ([10, 20, 30, 40, 50])，进程需要分配3个页框。首次适应算法会从链表头部开始，发现从页框10开始的连续3个页框（10, 20, 30）可以满足需求，于是将这3个页框分配给进程。
    • 最佳适应算法（Best Fit）：遍历整个空闲页框链表，找到一个大小最接近且能满足进程页需求的页框块。继续以上面的空闲页框链表为例，如果进程需要分配2个页框，最佳适应算法会选择20和30这两个页框，因为它们的大小之和（20 + 30 = 50）最接近进程所需的2个页框大小，且能满足需求。
    • 最坏适应算法（Worst Fit）：与最佳适应算法相反，它遍历空闲页框链表，找到一个最大的能满足进程页需求的页框块。例如，对于同样的空闲页框链表和需要2个页框的进程，最坏适应算法可能会选择50这个页框块（如果允许分配单个大页框来满足小需求），因为它是最大的能满足需求的块。
  2. 页表更新
    • 当分配页框给进程后，需要更新进程的页表。假设采用简单线性页表，当分配一个页框给进程的第 (n) 页时，将页表中第 (n) 项的物理页框号设置为分配的页框号，并将有效位（valid）设置为1。例如：
// 假设分配的页框号为frame_num，要分配给进程的第n页
page_table[n].frame_number = frame_num;
page_table[n].valid = 1;

内存回收

  1. 页框回收
    • 当进程结束或释放部分内存时，需要回收相应的页框。首先，根据进程的页表，找到要回收的页对应的页框号。然后，将这些页框标记为空闲，并重新加入到空闲页框链表中。例如，假设进程要释放第 (m) 页，其对应的页框号为 (frame_num)：
// 将页表中第m页的有效位设置为0，表示该页已释放
page_table[m].valid = 0;
// 将页框frame_num加入空闲页框链表
// 假设空闲页框链表使用链表结构，定义如下
typedef struct FreeFrame {
    int frame_number;
    struct FreeFrame *next;
} FreeFrame;

FreeFrame *new_frame = (FreeFrame *)malloc(sizeof(FreeFrame));
new_frame->frame_number = frame_num;
new_frame->next = free_frame_list;
free_frame_list = new_frame;
  1. 页表调整
    • 在回收页框后，需要对页表进行相应调整。如果采用多级页表，可能还需要处理内层页表和外层页表的释放等操作。例如，如果一个内层页表中所有页都被释放，那么可以释放该内层页表占用的内存空间，并在外层页表中相应项设置为无效。

分页存储管理方式的优缺点

分页存储管理方式在现代操作系统中得到广泛应用，它具有一些显著的优点，但也存在一定的缺点。

优点

  1. 内存利用率高
    • 分页方式将内存划分为固定大小的页框，进程的逻辑地址空间划分为同样大小的页，这使得内存分配更加灵活。相比于分区存储管理方式，分页可以有效地减少内存碎片。例如，在分区存储管理中，如果一个进程需要10KB内存，而系统中只有一个16KB的空闲分区和一个8KB的空闲分区，16KB的分区分配给该进程会产生6KB的内部碎片，而8KB的分区无法满足需求。而在分页存储管理中，假设页大小为4KB，该进程需要3个页框（10KB (\div) 4KB (\approx) 3），系统可以从不同的空闲页框中分配3个页框给该进程，不会产生内部碎片（页内碎片相对较小且是固定的）。
  2. 支持虚拟内存
    • 分页存储管理是实现虚拟内存的基础。通过页表和缺页中断机制，操作系统可以将进程暂时不用的页存放在外存（如磁盘）上，当进程需要访问这些页时，再将其调入内存。这使得系统可以运行比实际物理内存大得多的进程。例如，一个系统物理内存为4GB，但通过分页和虚拟内存技术，可以运行多个总大小超过4GB的进程。
  3. 地址转换效率较高
    • 借助快表（TLB），大部分内存访问的地址转换可以在高速缓存中快速完成。虽然每次内存访问理论上需要两次内存访问（一次访问页表，一次访问实际数据），但由于TLB的高命中率，实际的内存访问速度得到了很大提升。例如，当TLB命中率达到90%以上时，大部分内存访问只需要一次物理内存访问（TLB命中时），大大提高了系统性能。

缺点

  1. 页表开销
    • 页表本身需要占用一定的内存空间。对于大型系统，随着进程逻辑地址空间的增大，页表可能会变得非常庞大。例如，在64位系统中，如果采用简单线性页表，其占用的内存空间可能会达到无法接受的程度。虽然多级页表可以在一定程度上减少页表占用的内存，但仍然会带来一定的开销。此外，页表的维护（如更新、查找等）也需要一定的时间和资源。
  2. 页内碎片
    • 由于页大小是固定的，进程的最后一页往往不能被充分利用，从而产生页内碎片。例如，假设页大小为4KB，一个进程大小为10001字节，它需要3个页框，前两个页框被完全利用，而第三个页框只使用了10001 - 2 (\times) 4096 = 1809字节，剩余 (4096 - 1809 = 2287) 字节的空间被浪费，这就是页内碎片。虽然页内碎片相对较小，但在大量进程运行时，其总和也可能不可忽视。

分页存储管理方式在不同操作系统中的应用

不同的操作系统在实现分页存储管理方式时，会根据自身的特点和需求进行一些优化和调整。

Linux操作系统

  1. 页表结构
    • Linux采用多级页表结构。在32位系统中，通常采用三级页表：页全局目录（Page Global Directory，PGD）、页中间目录（Page Middle Directory，PMD，在某些情况下可能被省略）和页表（Page Table，PT）。64位系统则采用四级页表结构，增加了页上级目录（Page Upper Directory，PUD）。
    • 这种多级页表结构使得Linux能够有效地管理不同大小的物理内存和进程逻辑地址空间。例如，在64位系统中，通过四级页表可以灵活地映射庞大的逻辑地址空间，同时减少页表占用的内存。
  2. 内存分配与回收
    • Linux的内存分配器采用伙伴系统（Buddy System）来管理页框。伙伴系统将内存按照不同的大小块进行组织，当需要分配内存时，从合适大小的空闲块中分配。如果没有合适大小的块，则将较大的块分裂成两个相等的“伙伴”块，直到找到合适大小的块。当回收内存时，会检查相邻的空闲块是否为“伙伴”，如果是，则将它们合并成一个更大的块。
    • 例如，假设系统中有一个大小为 (2^n) 的空闲块，当需要分配一个大小为 (2^m)（(m \leq n)）的块时，会将 (2^n) 的块不断分裂，直到得到大小为 (2^m) 的块。当释放一个大小为 (2^m) 的块时，如果其“伙伴”（地址相邻且大小相同）也是空闲的，则将它们合并成一个大小为 (2^{m + 1}) 的块。
  3. 虚拟内存管理
    • Linux通过分页机制实现虚拟内存。当进程访问一个不在内存中的页时，会触发缺页中断。内核在处理缺页中断时，会根据页表中的信息，将所需的页从外存（如磁盘）调入内存。同时，Linux采用了写时复制（Copy - on - Write，COW）技术，对于一些共享的内存区域，只有当某个进程试图对其进行写操作时，才会为该进程复制一份独立的副本，从而节省内存空间。例如，多个进程共享一个可执行文件的代码段，在进程运行过程中，如果没有进程对代码段进行写操作，它们可以共享同一份物理内存中的代码页，只有当某个进程试图修改代码段时，才会复制一份代码页给该进程。

Windows操作系统

  1. 页表结构
    • Windows同样采用多级页表结构来管理内存。在32位系统中，使用两级页表，即页目录表（Page Directory Table）和页表（Page Table）。64位系统则采用四级页表结构，分别为页全局目录（Page Global Directory，PGD）、第一级页表（First - level Page Table，PML4）、第二级页表（Second - level Page Table，PDPT）和第三级页表（Third - level Page Table，PT）。
    • 这种页表结构设计使得Windows能够有效地支持不同规模的物理内存和进程逻辑地址空间，并且在地址转换过程中能够保证较高的效率。
  2. 内存分配与回收
    • Windows的内存管理器使用一种称为段页式管理的方式（本质上还是基于分页）。它将进程的地址空间划分为多个段，每个段再进一步划分为页。在内存分配方面，Windows采用了多种策略，包括快速分配（对于小内存请求）和常规分配（对于大内存请求）。快速分配通常使用内存池（Memory Pool）技术，预先分配一些固定大小的内存块，当有小内存请求时，可以快速从内存池中分配，提高分配效率。
    • 在回收内存时，Windows会将释放的页框标记为空闲，并根据需要进行合并等操作，以便后续重新分配。例如，当一个进程结束时，其占用的所有页框会被释放，内存管理器会将这些页框纳入空闲页框集合，并检查是否有相邻的空闲页框可以合并成更大的块。
  3. 虚拟内存管理
    • Windows通过分页实现虚拟内存。它使用页面文件（Page File）来存储不在内存中的页。当系统内存不足时，会将一些不常用的页写入页面文件，腾出物理内存给更需要的进程。Windows还提供了用户可配置的虚拟内存设置，用户可以根据系统的实际情况调整页面文件的大小等参数。例如，用户可以根据自己计算机的物理内存大小和运行的应用程序特点，适当增大或减小页面文件的大小，以优化系统性能。

分页存储管理方式的发展与展望

随着计算机硬件技术的不断发展，如处理器性能的提升、内存容量的增加以及存储设备速度的加快，分页存储管理方式也在不断演进和优化。

与硬件技术结合的优化

  1. 硬件加速的地址转换
    • 现代处理器越来越多地支持硬件加速的地址转换技术，如Intel的扩展页表（Extended Page Tables，EPT）和AMD的嵌套页表（Nested Page Tables，NPT）。这些技术通过在硬件层面实现更高效的地址转换，减少了软件层面页表遍历的开销。例如，EPT技术允许处理器直接在硬件中进行从客户机虚拟地址到物理地址的转换，而无需操作系统频繁地进行页表切换等操作，大大提高了虚拟化环境下的内存访问效率。
  2. 更大页大小的支持
    • 为了进一步提高内存访问效率，减少页表开销，一些操作系统和硬件开始支持更大的页大小。例如，除了传统的4KB页大小，现代系统还支持2MB甚至1GB的大页（Huge Page）。对于一些大数据量的应用程序，如数据库系统，使用大页可以减少页表项的数量，降低页表占用的内存空间，同时减少地址转换的开销。例如，一个数据库进程如果使用4KB页大小，可能需要大量的页表项来映射其庞大的内存空间，而使用2MB大页时，所需的页表项数量将大大减少。

适应新应用场景的改进

  1. 云计算与虚拟化环境
    • 在云计算和虚拟化环境中，多个虚拟机共享物理内存。分页存储管理方式需要进一步优化以提高内存利用率和性能。例如，通过内存超分（Memory Overcommitment）技术，系统可以分配比实际物理内存更多的虚拟内存给虚拟机，提高资源利用率。同时，在虚拟机之间进行内存分配和回收时，需要更精细的管理策略，以保证各个虚拟机的性能和稳定性。例如，当一个虚拟机内存使用量突然增加时，系统需要能够动态地调整其他虚拟机的内存分配，以满足需求。
  2. 大数据与人工智能应用
    • 大数据和人工智能应用通常需要处理大量的数据，对内存管理提出了新的挑战。分页存储管理方式可能需要与数据局部性原理更好地结合，以提高内存访问效率。例如，对于深度学习模型，其数据访问模式具有一定的局部性，操作系统可以根据这种局部性特点，优化页的分配和调度，将经常访问的数据页集中存放在物理内存的相邻区域，减少页表查找和内存访问的开销。同时，对于一些需要频繁读写磁盘数据的大数据应用，分页机制可以与磁盘I/O优化相结合，提高数据加载和存储的速度。

总之，分页存储管理方式作为现代操作系统内存管理的核心技术之一，将随着计算机技术的发展不断演进和完善，以适应日益复杂和多样化的应用需求。