虚拟内存

虚拟内存的优势

  1. 提供缓存，加速运行
  2. 扩大地址空间，通过内存交换
  3. 每个进程都有自己的虚拟地址空间，互不影响，也不需要关心物理地址

分段（一般不单独使用）

  • 段选择子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
  • 虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。
  • 虚拟地址是通过段表与物理地址进行映射的

缺点：

  • 第一个就是内存碎片的问题。
  • 第二个就是内存交换的效率低的问题。

对于多进程的系统来说，用分段的方式，内存碎片是很容易产生的，产生了内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。所以内存交换的效率也很低

分页（推荐）

分段的好处就是能产生连续的内存空间，但是会出现内存碎片和内存交换的空间太大的问题。要解决这些问题，那么就要想出能少出现一些内存碎片的办法。另外，当需要进行内存交换的时候，让需要交换写入或者从磁盘装载的数据更少一点，这样就可以解决问题了。这个办法，也就是内存分页（Paging）。

  1. 每个进程拥有自己的虚拟地址空间，这个空间被分割成多个页面(page)/虚拟页，页面存放于磁盘中，这些页面通过页表（存于MMU中）被映射到物理内存中的页框/物理页，页面与页框大小一般相等（4KB）
  2. **页表(page table)**负责把操作系统虚拟内存映射为物理内存，页表存放于物理内存中的MMU中，页表中有若干页表项(page table entry)，每个页表项对应虚拟内存的每个页面，页面被分为三种：
    1. 已缓存：磁盘中的页面有对应的页框
    2. 未缓存：磁盘中的页面没有对应的页框
    3. 未分配：磁盘中的页面还没有被页表记录
  3. 页命中：CPU想要读已缓存的页面，翻译成物理地址访问页框，这样非常快
  4. 缺页(page fault)：CPU想要读的页面未缓存或未分配，则产生缺页，从缓存的角度来说是内存缓存不命中，这就需要缺页置换算法（在内存中选择合适的页面换出）

分页相比分段，减少内存碎片，那么释放的内存都是以页为单位释放的，也就不会产生无法给进程使用的小内存。

MMU/TLB

MMU（内存管理单元）位于CPU，将进程的虚拟地址转换为物理地址，输入进程的页表与虚拟地址，输出物理地址。虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址

TLB（快表）存于CPU的L1 Cache，用来缓存已经找到的虚拟地址到物理地址的映射，这样不用去内存去找页表，特别是在多级页表的场景下，加快了虚拟地址到物理地址的映射速度。MMU会先查询TLB再查页表

CPU L1 L2 L3 cache，体现局部性（locality）。L1/L2 Cache通常都是每个CPU核心一个，L3 Cache通常都是各个核心共享的

多级页表

简单分页的缺点：每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表，那页表本身所需的内存空间就很大了

解决办法：二级页表即是对页表本身采用分页式管理，对页表本身增加了一层页表管理。页的大小就是一个页表的大小，一个页表只能装在一个页中。

单级页表：在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万 （2^20） 个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。这 4MB 大小的页表，看起来也不是很大。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。那么，100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存了，更别说 64 位的环境了。

多级页表：我们把这个 100 多万个「页表项」的单级页表再分页，将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。

为什么多级页表更省空间？

  • 当然，如果 4GB 的虚拟地址全部都映射到了物理内上的，二级分页占用空间确实是更大了，但是，我们往往不会为一个进程分配那么多内存。
  • 究其原因，一级页表可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表

为什么单级页表不能省？

  • 保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。假如虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。
  • 所以页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）

多级页表的缺点？

多了一次寻址时间

段页式内存管理

内存分段和内存分页并不是对立的，它们是可以组合起来在同一个系统中使用的，那么组合起来后，通常称为段页式内存管理。

实现的方式：

  • 先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
  • 接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；
  • 这样，地址结构就由段号、段内页号和页内位移三部分组成。

Linux 内存主要采用的是页式内存管理，但同时也不可避免地涉及了段机制（因为intel处理器的历史缘故）。

Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间（32 位环境下），也就是所有的段的起始地址都是一样的。这意味着，Linux 系统中的代码，包括操作系统本身的代码和应用程序代码，所面对的地址空间都是线性地址空间（虚拟地址），这种做法相当于屏蔽了处理器中的逻辑地址概念，段只被用于访问控制和内存保护。

Linux的虚拟地址空间

在 Linux 操作系统中，虚拟地址空间的内部又被分为内核空间和用户空间两部分，不同位数的系统，地址空间的范围也不同。比如最常见的 32 位和 64 位系统，32 位系统的内核空间占用 1G，位于最高处，剩下的 3G 是用户空间；64 位系统的内核空间和用户空间都是 128T，分别占据整个内存空间的最高和最低处，剩下的中间部分是未定义的（一般很少有进程需要那么大的内存）。

虽然每个进程都各自有独立的虚拟内存，但是每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。这样，进程切换到内核态后，就可以很方便地访问内核空间内存。

用户空间内存，从低到高分别是 7 种不同的内存段：

  • 程序文件段，包括二进制可执行代码；
  • 已初始化数据段，包括静态常量；
  • 未初始化数据段，包括未初始化的静态变量；
  • 堆段，包括动态分配的内存，从低地址开始向上增长，使用 C 标准库的 malloc()在这里动态分配
  • 文件映射段，包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关），使用系统调用mmap()在这里动态分配
  • 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 8 MB。当然系统也提供了参数，以便我们自定义大小；

缺页中断

缺页中断指的是当进程试图访问已映射在虚拟地址空间，但并未被加载在物理内存中的一个分页时，由CPU所触发的中断。

缺页中断会使进程陷入内核，然后执行以下操作：

  1. 检查要访问的虚拟地址是否合法
  2. 查找/分配一个物理页
  3. 填充物理页内容（读取磁盘，或者直接置0，或者啥也不干）
  4. 建立映射关系（虚拟地址到物理地址）

与普通的中断的区别在于：

  1. 在指令执行期间产生和处理缺页中断信号
  2. 一条指令在执行期间，可能产生多次缺页中断
  3. 缺页中断返回时，执行产生中断的那一条指令，而一般的中断返回时，执行下一条指令

页面置换算法

页面置换算法

如果发生缺页中断，为了能够把所缺的页面装入内存，系统必须从内存中选择一页将其换出，选择哪个页面调出就取决于页面置换算法。如果一个被频繁使用地页面被置换出内存，那么它很快又要被调入内存，这就造成了不必要的开销，所以一个好的页面置换算法至关重要。最常用的是LRU算法。

PS：如果要换出的页面在驻留内存期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本，如果该页面没有被修改过，那么就不需要写回磁盘，

  1. 最佳/最优置换（Optimal）：被置换的页面以后不再被访问，或者在将来最迟才回被访问的页面，缺页中断率最低，但这种算法无法实现，但仍可以作为衡量其他页面置换算法的标准
  2. 最近未使用（NRU）：在一个时钟内（约 20 ms）淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好，LRU的很粗糙的近似，主要优点是易于理解并且能够有效的实现
  3. 先进先出置换（FIFO）：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面，一般按照进入内存的先后次序排列成队列，但是该算法会淘汰经常访问的页面，不适合进程实际运行规律，很少使用纯粹的FIFO置换算法
  4. 第二次机会(second chance)：解决FIFO可能会把经常使用的页面换出的问题，当需要出队列时，检查最老页面的R位，如果是0，则该页是最老的且没有被使用，直接换出；如果是1，则清除此位，把该页放在链表尾部，修改它的装入时间就好像它刚放进来一样
  5. 时钟页面置换算法（clock）：解决第二次机会经常要在链表中移动页面从而降低效率的问题，把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面
  6. 最近最少使用置换（Least Recently Used, LRU）：置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。LRU置换算法效率不粗破，适用于各种类型的程序，但是系统要时时刻刻对各页的访问历史情况加以记录和更新，开销太大，因此LRU置换算法必须要有硬件的支持
  7. 最近最不常用页面置换算法(Least Frequently Used)，也就是淘汰一定时期内被访问次数最少的页
  8. 最不经常使用（NFU）：LRU的相对粗略近似
  9. 老化算法：非常近似LRU的有效算法，很好的选择
  10. 工作集算法：开销很大
  11. 工作集时钟算法：好的有效算法。

页回写

读缓存可以通过cache实现，写缓存主要有三种策略：

  • 不缓存nowrite，也就是说高速缓存不去缓存任何写操作。当对一个缓存中的数据片进行写时，将直接跳过缓存，写到磁盘，同时也使缓存中的数据失效。几乎不用
  • 写透缓存(write-through cache），写操作将自动更新内存缓存，同时也更新磁盘文件。这种策略对一致性有好处，缓存与磁盘时刻保持同步，实现也最简单
  • 回写（write-back），程序执行写操作直接写到缓存中，后端存储不会立刻直接更新，而是将页高速缓存中被写入的页面标记成“脏”，并且被加入到脏页链表中。然后由一个进程（回写进程）周期行将脏页链表中的页写回到磁盘，从而让磁盘中的数据和内存中最终一致。最后清理“脏”页标识。注意这里“脏页”这个词可能引起混淆，因为实际上脏的并非页高速缓存中的数据（它们是干干净净的），而是磁盘中的数据（它们已过时了）。也许更好的描述应该是“未同步”吧。实现比较复杂，但是Linux就是使用的这种

缓存回收，Linux实现的是一个修改过的LRU，也称为双链策略，Linux维护两个链表：活跃链表和非活跃链表。处于活跃链表上的页面被认为是“热”的且不会被换出，而在非活跃链表上的页面则是可以被换出的。在活跃链表中的页面必须在其被访问时就处于非活跃链表中。两个链表都被伪LRU规则维护：页面从尾部加入，从头部移除，如同队列。两个链表需要维持平衡——如果活跃链表变得过多而超过了非活跃链表，那么活跃链表的头页面将被重新移回到非活跃链表中，以便能再被回收。双链表策略解决了传统LRU算法中对仅一次访问的窘境。而且也更加简单的实现了伪LRU语义。这种双链表方式也称作LRU/2。更普遍的是n个链表，故称LRU/n。

内存描述符

内核使用内存描述符结构体表示进程的地址空间，该结构包含了和进程地址空间有关的全部信息。内存描述符由mm_struct结构体表示，定义在文件<linux/sched.h>中。

所有的mm_struct结构体都通过自身的mmlist域连接在一个双向链表中

虚拟内存区域

内存区域由vm_area_struct结构体描述，定义在文件<linux/mm_types.h>中。内存区域在Linux内核中也经常称作虚拟内存区域（virtual memoryAreas，VMAs）。

vm_area_struct 结构体描述了指定地址空间内连续区间上的一个独立内存范围。内核将每个内存区域作为一个单独的内存对象管理，每个内存区域都拥有一致的属性，比如访问权限等，另外，相应的操作也都一致。按照这样的方式，每一个VMA就可以代表不同类型的内存区域（比如内存映射文件或者进程用户空间栈），这种管理方式类似于使用VFS层的面向对象方法（请看

mmap和unmmap

内核使用do_mmap()函数创建一个新的线性地址区间，会将一个地址区间加入到进程的地址空间中——无论是扩展已存在的内存区域还是创建一个新的区域。

在用户空间可以通过mmap()系统调用获取内核函数do_mmap()的功能。

do_mummap()函数从特定的进程地址空间中删除指定地址区间

在用户空间可以通过munmap()系统调用获取内核函数do_mummap()的功能

内存分配算法：伙伴(buddy)/slab

进程申请内存大小是任意的，如果malloc用法不对，会产生内存碎片，它们小而且不连续，不满足malloc申请连续内存的要求

内存碎片存在的方式有两种：a. 内部碎片  b. 外部碎片

  • 内部碎片的产生：因为所有的内存分配需要满足字节对齐，所以通常会多分配一点不需要的多余内存空间，造成内部碎片。如：申请43Byte，因为没有合适大小的内存，会分配44Byte或48Byte，就会存在1Byte或3Byte的多余空间。
  • 外部碎片的产生：频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间，从而产生外部碎片。比如有一块共有100个单位的连续空闲内存空间，范围为099，如果从中申请了一块10 个单位的内存块，那么分配出来的就是09。这时再继续申请一块 5个单位的内存块，这样分配出来的就是 1014。如果将第一块释放，此时整个内存块只占用了 1014区间共 5个单位的内存块。然后再申请20个单位的内存块，此时只能从 15开始，分配1524区间的内存块，如果以后申请的内存块都大于10个单位，那么 09 区间的内存块将不会被使用，变成外部碎片。

伙伴算法就是将内存分成若干块，然后尽可能以最适合的方式满足程序内存需求的一种内存管理算法，内存释放后，检查与该内存相邻的内存是否是同样大小并且同样处于空闲的状态，如果是，则将这两块内存合并，然后程序递归进行同样的检查。

  • 伙伴算法的优点是能够完全避免外部碎片的产生。
  • 申请时，伙伴算法会给程序分配一个较大的内存空间，即保证所有大块内存都能得到满足。
  • 伙伴算法的缺点是会产生内部碎片，当分配比需求还大的内存空间，就会产生内部碎片。

slab allocation的基本原理：将分配的内存分割成各种尺寸的块，并把相同尺寸的块分成组。当要释放已分配到的内存时，只会回收、不会释放，返回到对应的组重复利用。下次分配对象时，会使用最近释放的对象的内存块，因此其驻留在cpu高速缓存中的概率会大大提高。

  • 对从Buddy拿到的内存进行二次管理，以更小的单位进行分配和回收(注意，是回收而不是释放)，防止了空间的浪费。
  • 让频繁使用的对象尽量分配在同一块内存区间并保留基本数据结构，提高程序效率。

最佳实践：如果你要创建和撤销很多大的数据结构，那么考虑建立slab高速缓存。slab层会给每个处理器维持一个对象高速缓存（空闲链表），这种高速缓存会极大地提高对象分配和回收的性能。slab层不是频繁地分配和释放内存，而是为你把事先分配好的对象存放到高速缓存中。当你需要一块新的内存来存放数据结构时，slab层一般无须另外去分配内存，而只需要从高速缓存中得到一个对象就可以了。

伙伴算法与slab算法的关系：

  • slab与Buddy都是内存分配器。
  • slab的内存来自Buddy
  • slab与Buddy在算法上级别对等。Buddy把内存条 当作一个池子来管理，slab是把从Buddy拿到的内存当作一个池子来管理的。

kmalloc()函数与用户空间的malloc()一族函数非常类似，只不过它多了一个gfp_t类型的flags参数。flags参数指定了内存分配器的行为。与kmalloc对应的就是kfree。

vmalloc()函数类似kmalloc，只是vmalloc分配的内存虚拟地址是连续的，而物理地址则无须连续。尽管在某些情况下才需要物理上连续的内存块，但是出于性能考虑，很多内核代码都用kmalloc()来获得内存，而不是vmalloc()。而且vmalloc需要一个个映射不连续的物理页，导致更大的TLB抖动

每个进程的内核栈大小既依赖体系结构，也与编译时的选项有关。历史上，每个进程都有两页的内核栈。因为32位和64位体系结构的页面大小分别是4KB和8KB，所以通常它们的内核栈的大小分别是8KB和16KB。

真棒！ 20 张图揭开内存管理的迷雾，瞬间豁然开朗 by 小林coding