Re：Linux系统篇（四十九）线程篇 · 二：为什么现代操作系统选择分页式存储？分页如何解决物理内存碎片？分页结构如何演化到页表、页目录、MMU？
概要&序論
Hello,大家好，我是此方。上一篇我们讲了线程的基本概念（说实话那篇有点水），本文将从物理内存碎片问题开始，逐步介绍分页式存储布局的产生背景、Linux内核中的物理页管理方式，以及页表、页目录、多级页表和MMU地址转换流程。好，我们开始吧。
一、物理内存碎片化——分页式存储急需解决的问题
1.1虚拟地址空间与页表的产生
1.1.1为什么会有物理内存碎片化问题
思考一下，如果在没有虚拟内存和分页机制的情况下，每一个用户程序在物理内存上所对应的空间必须是连续的，如下图：
因为每一个程序的代码、数据长度都是不一样的，按照这样的映射方式，物理内存将会被分割成各种离散的、大小不同的块。经过一段运行时间之后，有些程序会退出，那么它们占据的物理内存空间可以被回收，导致这些物理内存都是以很多碎片的形式存在。
1.1.2解决虚拟连续物理不连续的需求
怎么办呢？我们希望操作系统提供给用户的空间必须是连续的，但是物理内存最好不要连续。 此时虚拟内存和分页便出现了，如下图所示：
把物理内存按照一个固定的长度的页框进行分割，有时叫做物理页。每个页框包含一个物理页（page）。一个页的大小等于页框（页帧）的大小。
我们以前讲的哪些问题牵扯到了？
- 子进程写时拷贝一次申请4KB
- 共享内存一次申请4KB的整数倍
- section要合并成一个个4KB的segment
大多数 32位 体系结构支持 4KB 的页，而 64位 体系结构一般会支持 8KB 的页。区分一页和一个页框是很重要的：
- 页框是一个存储区域；
- 而页是一个数据块，可以存放在任何页框或磁盘中；
- 权限管理以页框为单位，写时拷贝也是。
有了这种机制，CPU 便并非是直接访问物理内存地址，而是通过虚拟地址空间来间接的访问物理内存地址。所谓的虚拟地址空间，是操作系统为每一个正在执行的进程分配的一个逻辑地址，在32位机上，其范围从0 ~ 4GB-1。
操作系统通过将虚拟地址空间和物理内存地址之间建立映射关系，也就是页表，这张表上记录了每一对页和页框的映射关系，能让CPU间接的访问物理内存地址。
1.1.3总结
总结一下，其思想是将虚拟内存下的逻辑地址空间分为若干页，将物理内存空间分为若干页框，通过页表便能把连续的虚拟内存，映射到若干个不连续的物理内存页。这样就解决了使用连续的物理内存造成的碎片问题。
二、物理内存如何被管理
假设一个可用的物理内存有 4GB 的空间。按照一个页框的大小 4KB 进行划分，4GB 的空间就是 4GB/4KB = 1048576 个页框。有这么多的物理页，操作系统肯定是要将其管理起来的，操作系统需要知道哪些页正在被使用，哪些页空闲等等。
2.1 struct page源码
内核用 struct page 结构表示系统中的每个物理页，出于节省内存的考虑，struct page 中使用了大量的联合体 union。
/* include/linux/mm_types.h */
struct page {
/* 原子标志，有些情况下会异步更新 */
unsigned long flags;
union {
struct {
/* 换出页列表，例如由zone->lru_lock保护的active_list */
struct list_head lru;
/* 如果最低位为0，则指向inode
* address_space，或为NULL
* 如果页映射为匿名内存，最低位置位
* 而且该指针指向anon_vma对象
*/
struct address_space* mapping;
/* 在映射内的偏移量 */
pgoff_t index;
/*
* 由映射私有，不透明数据
* 如果设置了PagePrivate，通常用于buffer_heads
* 如果设置了PageSwapCache，则用于swp_entry_t
* 如果设置了PG_buddy，则用于表示伙伴系统中的阶
*/
unsigned long private;
};
struct { /* slab, slob and slub */
union {
struct list_head slab_list; /* uses lru */
struct { /* Partial pages */
struct page* next;
#ifdef CONFIG_64BIT
int pages; /* Nr of pages left */
int pobjects; /* Approximate count */
#else
short int pages;
short int pobjects;
#endif
};
};
struct kmem_cache* slab_cache; /* not slob */
/* Double-word boundary */
void* freelist; /* first free object */
union {
void* s_mem; /* slab: first object */
unsigned long counters; /* SLUB */
struct { /* SLUB */
unsigned inuse : 16; /* 用于SLUB分配器：对象的数目 */
unsigned objects : 15;
unsigned frozen : 1;
};
};
};
...
};
union {
/* 内存管理子系统中映射的页表项计数，用于表示页是否已经映射，还用于限制逆向映射
搜索*/
atomic_t _mapcount;
unsigned int page_type;
unsigned int active; /* SLAB */
int units; /* SLOB */
};
...
#if defined(WANT_PAGE_VIRTUAL)
/* 内核虚拟地址（如果没有映射则为NULL，即高端内存） */
void* virtual;
#endif /* WANT_PAGE_VIRTUAL */
...
}
2.2 其中比较重要的几个参数
2.2.1 flags：用来存放页的状态
flags：用来存放页的状态。这些状态包括页是不是脏的，是不是被锁定在内存中等。
flag 的每一位单独表示一种状态，所以它至少可以同时表示出32种不同的状态。这些标志定义在<linux/page-flags.h>中。
其中一些比特位非常重要，如PG_locked用于指定页是否锁定，PG_uptodate用于表示页的数据已经从块设备读取并且没有出现错误。
#define PG_locked 0 /* Page is locked. Don't touch. */
#define PG_error 1
#define PG_referenced 2
#define PG_uptodate 3
#define PG_dirty 4
#define PG_lru 5
#define PG_active 6
#define PG_slab 7 /* slab debug (Suparna wants this) */
#define PG_checked 8 /* kill me in 2.5.<early>. */
#define PG_arch_1 9
#define PG_reserved 10
#define PG_private 11 /* Has something at ->private */
#define PG_writeback 12 /* Page is under writeback */
#define PG_nosave 13 /* Used for system suspend/resume */
#define PG_compound 14 /* Part of a compound page */
#define PG_swapcache 15 /* Swap page: swp_entry_t in private */
#define PG_mappedtodisk 16 /* Has blocks allocated on-disk */
#define PG_reclaim 17 /* To be reclaimed asap */
#define PG_nosave_free 18 /* Free, should not be written */
#define PG_buddy 19 /* Page is free, on buddy lists */
PG_locked：该页已被锁定（通常在进行磁盘 I/O 时）。PG_active/PG_referenced：用于内存回收的 LRU 算法，表示该页是否活跃。PG_dirty：脏页标记，表示该页的内容已被修改，需要写回磁盘。PG_lru：说明该页是否在内存回收的 LRU 链表中（正好对应你图中蓝框里的lru结构）。
2.2.2 _mapcount表示在页表中有多少项指向该页
_mapcount：表示在页表中有多少项指向该页，也就是这一页被引用了多少次。当计数值变为-1时，就说明当前内核并没有引用这一页，于是新的分配中就可以使用它。
2.2.3 virtual就是页的虚拟地址
virtual：是页的虚拟地址。通常情况下，它就是页在虚拟内存中的地址。有些内存（即所谓的高端内存）并不永久地映射到内核地址空间上。在这种情况下，这个域的值为NULL，需要的时候，必须动态地映射这些页。
总结：我们申请物理内存，是在做什么？查数组，改page!建立内核数据结构的对应关系。
2.3页的内存占用有多大
要注意的是 struct page 与物理页相关，而并非与虚拟页相关。而系统中的每个物理页都要分配一个这样的结构体，让我们来算算对所有这些页都这么做，到底要消耗掉多少内存。
算 struct page 占40个字节的内存吧（一般在32-40个字节左右），假定系统的物理页为 4KB 大小，系统有 4GB 物理内存。那么系统中共有页面 1048576 个（1兆个），所以描述这么多的page结构体消耗的内存只不过 40MB，相对系统 4GB 内存而言，仅是很小的一部分罢了。因此，要管理系统中这么多物理页面，这个代价并不算太大。
要知道的是，页的大小对于内存利用和系统开销来说非常重要，页太大，页内必然会剩余较大不能利用的空间（页内碎片）。页太小，虽然可以减小页内碎片的大小，但是页太多，会使得页表太长而占用内存，同时系统频繁地进行页转化，加重系统开销。因此，页的大小应该适中，通常为 512B - 8KB，windows/Linux系统的页框大小为4KB。
2.4struct page如何锁定物理地址
为什么struct page里面没有物理地址这个字段？
因为内核将所有物理页的管理转化为对 struct page mem[…] 数组的操作，每个 struct page 在数组中都有固定的下标，通过 下标 * 4KB 即可天然计算出对应的起始物理地址，再结合页内偏移就能得到具体的物理地址，因此无需在结构体中额外保存物理页地址。
2.5 struct page 的其他维护方式
我们上面讲的全局page数组是一种最基础的存储方式，但不是唯一的存储方式，它可以被容纳到哈希表中，可以被容纳到redixtree中，可以被容纳到lru链表中。
老登啊，什么是redixtree？redixtree中文名基序树。是一种树形数据结构。
每个文件在内核中都对应一个 address_space 结构体，其中包含一棵基数树 struct radix_tree_root page_tree，用来管理该文件映射在内存中的所有物理页（Page Cache）。
基数树的节点 radix_tree_node 中包含一个槽位数组 void *slots[…]，其指针直接指向内存页的描述符 struct page。
基数树是一种基于偏移量（文件内的逻辑页索引，如 pgoff_t）构建的多叉树。内核根据文件的页偏移量二进制位，顺着树层级快速查找，最终在叶子节点的 slots 中找到对应的 struct page。
三、页表——详细介绍
3.1一共有多少个页表项
页表中的每一个表项，指向一个物理页的开始地址。在 32 位系统中，虚拟内存的最大空间是 4GB，这是每一个用户程序都拥有的虚拟内存空间。既然需要让 4GB 的虚拟内存全部可用，那么页表中就需要能够表示这所有的 4GB 空间，那么就一共需要 4GB/4KB = 1048576 个表项。如下图所示：
3.2虚拟物理映射关系
虚拟内存看上去被虚线“分割”成一个个单元，其实并不是真的分割，虚拟内存仍然是连续的。这个虚线的单元仅仅表示它与页表中每一个表项的映射关系，并最终映射到相同大小的一个物理内存页上。
页表中的物理地址，与物理内存之间，是随机的映射关系，哪里可用就指向哪里(物理页)。虽然最终使用的物理内存是离散的，但是与虚拟内存对应的线性地址是连续的。 处理器在访问数据、获取指令时，使用的都是线性地址，只要它是连续的就可以了，最终都能够通过页表找到实际的物理地址。
3.3页表本身的消耗
假设，在 32 位系统中，地址的长度是 4 个字节，那么页表中的每一个表项就是占用 4 个字节。所以页表占据的总空间大小就是：1048576*4 = 4MB 的大小。也就是说映射表自己本身，就要占用 4MB / 4KB = 1024 个物理页。这会存在哪些问题呢？
- 回想一下，当初为什么使用页表，就是要将进程划分为一个个页可以不用连续的存放在物理内存中，但是此时页表就需要1024个连续的页框，似乎和当时的目标有点背道而驰了……
- 此外，根据局部性原理可知，很多时候进程在一段时间内只需要访问某几个页就可以正常运行了。因此也没有必要一次让所有的物理页都常驻内存。
3.4解决页表容量过大的问题
解决需要大容量页表的最好方法是：对页表再分页，由此形成多级页表的思想。
为了解决这个问题，可以把这个单一页表拆分成 1024 个体积更小的映射表。如下图所示。这样一来，1024(每个表中的表项个数) * 1024(表的个数)，仍然可以覆盖 4GB 的物理内存空间。
这里的每一个表，就是真正的页表，所以一共有 1024 个页表。一个页表自身占用 4KB，那么 1024 个页表一共就占用了 4MB 的物理内存空间，和之前没差别啊？
从总数上看是这样，但是一个应用程序是不可能完全使用全部的 4GB 空间的，也许只要几十个页表就可以了。例如：一个用户代码的代码段、数据段、栈段，一共就需要 10 MB 的空间，那么使用 3 个页表就足够了。
计算过程：
每一个页表项指向一个 4KB 的物理页，那么一个页表中 1024 个页表项，一共能覆盖 4MB 的物理内存；
那么 10MB 的程序，向上对齐取整之后(4MB 的倍数，就是 12 MB)，就需要 3 个页表就可以了。
四、页目录结构
4.1 什么是页目录结构
到目前为止，每一个页框都被一个页表中的一个表项来指向了，那么这 1024 个页表也需要被管理起来。管理页表的表称之为页目录表，形成二级页表。如下图所示：
- 所有页表的物理地址被页目录表项指向.
- 页目录的物理地址被
CR3 寄存器指向（教材里严谨得说叫做：“指向当前硬件上下文”，因为页目录跟着进程走，进程切换，CR3指向的页目录页跟着切换。），这个寄存器中，保存了当前正在执行任务的页目录地址。
所以操作系统在加载用户程序的时候，不仅仅需要为程序内容来分配物理内存，还需要为用来保存程序的页目录和页表分配物理内存。
4.2 两级页表的地址转换与MMU工作流程
4.2.1两级页表地址转化原理
下面以一个逻辑地址为例。将逻辑地址（ 0000000000‘0000000001’111111111111 ）转换为物理地址的过程：
- 在32位处理器中，采用4KB的页大小，则虚拟地址中低12位为页偏移，剩下高20位给页表，分成两级，每个级别占10个bit（10+10）。
CR3 寄存器读取页目录起始地址，再根据一级页号查页目录表，找到下一级页表在物理内存中存放位置。- 根据二级页号查表，找到最终想要访问的内存块号。
- 结合页内偏移量得到物理地址。
- 一个物理页的地址一定是
4KB对齐的(最后的12位全部为0)，所以其实只需要记录物理页地址的高 20 位即可。
4.2.2 MMU 的工作流程
以上其实就是 MMU 的工作流程。MMU是被集成在CPU上面的，MMU(Memory Manage Unit)是一种硬件电路，其速度很快，拿着虚拟地址，拿着CR3里面的这个页目录地址，去做上面这件事情转化得到我们的物理地址。
MMU主要工作是进行内存管理，地址转换只是它承接的业务之一。
到这里其实还有个问题，MMU要先进行两次页表查询确定物理地址，在确认了权限等问题后，MMU再将这个物理地址发送到总线，内存收到之后开始读取对应地址的数据并返回。那么当页表变为N级时，就变成了N次检索+1次读写。可见，页表级数越多查询的步骤越多，对于CPU来说等待时间越长，效率越低。
4.2.3块表——解决多级页表效率问题
让我们现在总结一下：单级页表对连续内存要求高，于是引入了多级页表，但是多级页表也是一把双刃剑，在减少连续存储要求且减少存储空间的同时降低了查询效率。
有没有提升效率的办法呢？计算机科学中的所有问题，都可以通过添加一个中间层来解决。 MMU 引入了新武器，江湖人称快表的 TLB （其实，就是缓存，Translation Lookaside Buffer，学名转译后备缓冲区）
当 CPU 给 MMU 传新虚拟地址之后， MMU 先去问 TLB 那边有没有，如果有就直接拿到物理地址发送到总线给内存，齐活。但 TLB 容量比较小，难免发生 Cache Miss ，这时候 MMU 还有保底的老武器页表，在页表中找到之后 MMU 除了把地址发送到总线传输内存，还把这条映射关系给定TLB，让它记录一下刷新缓存。
4.3再谈页目录结构的细节
4.3.1聚集效应
我们的低12位是用来**区分页内的偏移量的，**所以高 20位就是用来区分页的，高20位相同的，会在同一个页中，然后通过低12位获取偏移量。有这种聚集效应后，我们访问某一个地址，就有可能访问附近的地址，于是每次申请一个页，就可以优化效率。
4.3.2其他细节
细节 1：物理内存分配的流程
申请内存 → \rightarrow → 查找数组 → \rightarrow → 找到没有被使用的 page → \rightarrow → page index → \rightarrow → 物理页框地址。
细节 2：页表重建场景
写时拷贝、缺页中断、内存申请等操作，背后可能都需要重新建立新的页表和映射关系。
细节 3：进程映射体系
进程通过一张页目录 + n n n 张页表构建映射体系。虚拟地址是索引，物理地址页框是目标。物理地址计算： 虚拟地址 (低 12 位) + 页框地址 = 物理地址。
细节 4：为什么是低 12 位？
页框大小是 4KB，其字节偏移范围是 [ 0 , 4095 ] [0, 4095] [0,4095]，对应二进制的 2 12 2^{12} 212，即需要低 12 位作为页内偏移量。ELF 文件/代码段在内存中属于同一个 4KB 页框，并且是有序化排列的。
虚拟地址的某一位作为页表的下标。页表的内容是页框的物理地址
4.3.3由物理地址逆推虚拟地址
假设32位物理地址00000000000000011111111111110000，划分为前20位和后12位。
- 物理页框号:00000000000000011111
- 页内偏移:111111110000
说明这个物理地址在第31号物理页框中的第4080个字节。操作系统需要反查：
-
找二级页号：看这个物理页框号在哪项页表里、是第几项（第几行）。行号转化成二进制（10位），就是虚拟地址的中间段（二级页号）。（对应图中：在页表中找到它在第 1022 行，变二进制就是 1111111110 ）
-
找一级页号：看这个页表的基地址，在左边的“页目录表”里是第几项（第几行）。行号转化成二进制（10位），就是虚拟地址的最高段（一级页号）。（对应图中：该页表地址在页目录表第 0 行，变二进制就是 0000000000 ）
最后把： 一级页号（10位） + 二级页号（10位） + 偏移量（12位） 顺着顺序列成一排，就是你要的虚拟地址！
五、 最后一个话题：缺页异常
设想，CPU 给 MMU 的虚拟地址，在 TLB 和页表都没有找到对应的物理页，该怎么办呢？其实这就是缺页异常 Page Fault ，它是一个由硬件中断触发的可由软件逻辑纠正的错误。
假如目标内存页在物理内存中没有对应的物理页或者存在但无对应权限，CPU 就无法获取数据，这种情况 CPU 就会报告一个缺页错误。
由于 CPU 没有数据就无法进行计算，CPU 罢工了用户进程也就出现了缺页中断，进程会从用户态切换到内核态，并将缺页中断交给内核的 Page Fault Handler 处理。
缺页中断会交给 PageFaultHandler 处理，其根据缺页中断的不同类型会进行不同的处理：
*
Hard Page Fault也被称为Major Page Fault，翻译为硬缺页错误/主要缺页错误，这时物理内存中没有对应的物理页，需要 CPU 打开磁盘设备读取到物理内存中，再让 MMU 建立虚拟地址和物理地址的映射。（比如动态库的加载就是）
*Soft Page Fault也被称为Minor Page Fault，翻译为软缺页错误/次要缺页错误，这时物理内存中是存在对应物理页的，只不过可能是其他进程调入的，发出缺页异常的进程不知道而已，此时 MMU 只需要建立映射即可，无需从磁盘读取写入内存，一般出现在多进程共享内存区域。
*Invalid Page Fault翻译为无效缺页错误，比如进程访问的内存地址越界访问，又比如对空指针解引用内核就会报segment fault错误中断进程直接挂掉。
最后大总结：执行流看到的资源本质是：在合法的情况下，你拥有多少虚拟地址，虚拟地址是资源的代表。虚拟地址空间 mm_struct + vm_area_struct 本质：进行资源的统计数据和整体数据。
页表是一张虚拟到物理地图
- 资源划分：本质就是地址空间划分
- 资源共享：本质就是虚拟地址的共享！
六、和内存申请有关的其他话题
6.1关于mmap申请内存
mmap是基于文件的空间申请方案。
new和malloc第底层brk实际上做的是修改mm_struct中标识指针位置的指针值，修改堆空间的大小，而不申请物理内存。
物理内存的申请自访问该虚拟地址空间时发生缺页中断开始。——延迟申请，这样原本给你的内存就可以给别人用了，变相的提升内存使用的充分度。
6.2new，malloc，brk三者之间的关系
new，malloc，brk三者之间的关系。
6.3一个问题，越界了一定会报错吗？
先说结论，不一定，你的越界，有时候操作系统都不知道。
页号合法性检查：操作系统在处理中断或异常时，首先检查触发事件的虚拟地址的页号是否合法。如果页号合法但页面不在内存中，则为缺页中断；如果页号非法，则为越界访问。
内存映射检查：操作系统还可以检查触发事件的虚拟地址是否在当前进程的内存映射范围内。如果地址在映射范围内但页面不在内存中，则为缺页中断；如果地址不在映射范围内，则为越界访问。
越界但是越界后的内存依然合法那么就不会崩溃。
越界后内存不合法，就会崩溃。
举一个越界不崩溃的例子，死循环。
由于 int i 先于 int array[10] 声明，变量 i 会被存放在比 array 数组更高地址的栈空间中，且紧挨着数组的末尾 array[9]。
数组访问 array[i] 本质上是通过基地址进行偏移计算：当 i 增加到 10 时，恰好指向了变量 i 所占用的那 4 个字节的空间。
执行 array[10] = 0 时，CPU 将数据 0 写入了该计算出来的内存地址，将变量 i 原有的值（10）强行改写为了， 触发死循环。
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
31
0- 0
已为社区贡献12条内容
所有评论(0)