CSAPP:第9章虚拟内存

谁践踏了优雅 2022-10-29 11:27 335阅读 0赞

### CSAPP:第9章 虚拟内存 ###

### 文章目录 ###

*   *   *  CSAPP:第9章 虚拟内存
         *   *  9.1 物理和虚拟寻址
             *  9.2 地址空间
             *  9.3 虚拟内存作为缓存的工具
             *   *  9.3.1 DRAM缓存的组织结构
                 *  9.3.2 页表
                 *  9.3.3 页命中
                 *  9.3.4 缺页
                 *  9.3.5 分配页面
                 *  9.3.6 又是局部性解救了我们
             *  9.4 虚拟内存作为缓存管理的工具
             *  9.5 虚拟内存作为内存保护的工具
             *  9.6 地址翻译
             *   *  9.6.1 结合高速缓存和虚拟缓存
                 *  9.6.2 利用TLB加速地址翻译
                 *  9.6.3 多级页表
                 *  9.6.4 总和：端到端的地址翻译
             *  9.7 案例研究：Intel Core i7/Linux内存系统
             *   *  9.7.1 Core i7 地址翻译
                 *  9.7.2 Linux 虚拟内存系统
             *  9.8 内存映射
             *   *  9.8.1 再看共享对象
                 *  9.8.2 再看fork函数
                 *  9.8.3 再看execve函数
                 *  9.8.4 使用mmap函数的用户级映射
             *  9.9 动态内存分配
             *   *  9.9.1 malloc 和 free 函数
                 *  9.9.2 为什么要使用动态内存分配
                 *  9.9.3 分配器的要求和目标
                 *  9.9.4 碎片
                 *  9.9.5 实现问题
                 *  9.9.6 隐式空闲链表
                 *  9.9.7 放置已分配的块
                 *  9.9.8 分割空闲块
                 *  9.9.9 获取额外的堆内存
                 *  9.9.10 合并空闲块
                 *  9.9.11 带边界标记的合并
                 *  9.9.12 综合：实现一个简单的分配器
                 *  9.9.13 显式空闲链表
                 *  9.9.14 分离的空闲链表
             *  9.10 垃圾收集
             *   *  9.10.1 垃圾收集器的基本知识
                 *  9.10.2 Mark&Sweep 垃圾收集器
                 *  9.10.3 C 程序的保守 Mark&Sweep
             *  9.11 C程序中常见的与内存有关的错误
             *   *  9.11.1 间接引用坏指针
                 *  9.11.2 读未初始化的内存
                 *  9.11.3 允许栈缓冲区溢出
                 *  9.11.4 假设指针和它们指向的对象是相同大小的
                 *  9.11.5 造成错位错误
                 *  9.11.6 引用指针，而不是它所指向的对象
                 *  9.11.7 误解指针运算
                 *  9.11.8 引用不存在的变量
                 *  9.11.9 引用空闲堆块中的数据
                 *  9.11.10 引起内存泄漏

#### 9.1 物理和虚拟寻址 ####

*  ![image-20210211110251714][] \- 所谓物理寻址即CPU直接用物理地址寻址
 *  ![image-20210211110332797][] \- 所谓虚拟寻址，即相较于物理多一个把虚拟地址转换成物理地址的过程（MMU，地址转换机构），在进行物理寻址。

#### 9.2 地址空间 ####

*  地址空间（address space )是 非负整数地址的有序集合：\{ 0，1，2，…\}
 *  虚拟地址空间 ( virtual address space):\{0，1，2 ,…，N — 1\}
    
     *  CPU 从一个有 N=2"个地址的地址空间中生成虚拟地址。
 *  物理地址空间（physical address space):\{0，1，2 ,…，M — 1\}
    
     *  DRAM的大小为M。

#### 9.3 虚拟内存作为缓存的工具 ####

##### 9.3.1 DRAM缓存的组织结构 #####

*  使用术语 SRAM 缓存来表示位于 CPU 和主存之间的 Ll、L2 和 L3 高速缓存。
 *  使用用术语 DRAM 缓存来表示虚拟内存系统的缓存，它在主存中缓存虚拟页。

##### 9.3.2 页表 #####

*  一个存放在物理内存中的数据结构——叫做页表（page table )，用于
 *  ![image-20210211112710058][] \- 有效位表明了该虚拟页当前是否被缓存在 DRAM 中。如果设置了有效位，那么地址字段就表示 DRAM 中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。

##### 9.3.3 页命中 #####

*  ![image-20210211113813545][] \- 通过虚拟地址找到PTE的某一行+该行有效位为1=》页命中=表内地址为该页的物理首地址

##### 9.3.4 缺页 #####

*  DRAM 缓存不命中称为缺页（page fault)。
 *  ![image-20210211114003264][] \- 通过虚拟地址找到PTE的某一行+该行有效位为0=》页未命中 - 接下来，内核从磁盘复制 VP 3 到内存中的 PP 3, 更 新 PTE 3, 随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发送到地址翻译硬件。但是现在，VP 3 已经缓存在主存中了，那么页命中也能由地址翻译硬件正常处理了。如下所示 - ![image-20210211114311746][]

##### 9.3.5 分配页面 #####

*  展示了当操作系统分配一个新的虚拟内存页时对我们示例页表的影响，例如，调用 malloc 的结果。在这个示例中，VP5 的分配过程是在磁盘上创建空间并更新 PTE 5 , 使它指向磁盘上这个新创建的页面。
 *  ![image-20210211144345669][]

##### 9.3.6 又是局部性解救了我们 #####

*  局部性(locality)原理导致这个机制的命中率比较高
    
     *  局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动瓦面 (active page)集合上工作，这个集合叫做**工作集**(working set)或者**常驻集合**(resident set)。
 *  如果工作集的大小超出了物理内存的大小，那么程序将产生一种不幸的状态，叫做抖动（thrashmg)，这时页面将不断地换进换出。

#### 9.4 虚拟内存作为缓存管理的工具 ####

*  当虚拟内存比物理内存更小，虚拟内存任然可以大大地简化内存管理，并提供一种自然的保护内存的方法。
 *  操作系统为每个进程提供了一个独立的页表
 *  简化链接
    
     *  独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。
 *  简化加载
    
     *  虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。要把目标文件中.text 和.data 节加载到一个新创建的进程中，Linux 加载器为代码和数据段分配虚拟页，把它们标记为无效的（即未被缓存的），将页表条目指向目标文件中适当的位置。
     *  加载器从不从磁盘到内存实际复制任何数据。虚拟内存系统会按照需要自动地调人数据页。
 *  简化共享
    
     *  独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。
     *  对于需要共享的代码和数据，只需要在页表中指向共享代码和数据的物理地址即可（首地址）
 *  简化内存分配

#### 9.5 虚拟内存作为内存保护的工具 ####

*  现代任何系统：
    
     *  不应该允许一个用户进程修改它的只读代码段
     *  不允许它读或修改任何内核中的代码和数据结构
     *  不应该允许它读或者写其他进程的私有内存
     *  不允许它修改任何与其他进程共享的虚拟页面
     *  除非所有的共享者都显式地允许它这么做（通过调用明确的进程间通信系统调用）
 *  大致思想就是添加标志位（就像有效位那个一样）
    
     *  ![image-20210211150842334][]

#### 9.6 地址翻译 ####

*  符号说明：
    
     *  ![image-20210211151336747][]
 *  形式上来说，地址翻译是一个 iV 元素的虚拟地址空间（VAS)中的元素和一个 M 元素的物理地址空间（PAS)中元素之间的映射，
    
     *  ![image-20210211152025378][]
 *  下图解释了转换过程：
    
     *  1、读PTBR得到首地址，和虚拟页号一起计算页号所在地址（数组index的计算方法）
 *  2、check有效位，若1则得到PPN，再和VPO一起得到物理地址。若0则缺页中断。
    
     *  ![image-20210211152136809][]
     *  当页面命中时，CPU 硬件执行的步骤：
        
         *  第 1 步 ：处理器生成一个虚拟地址，并把它传送给 MMU。
     *  第 2 步 ：MMU 生成 PTE 地址，并从高速缓存/主存请求得到它。
        
         *  第 3 步 ：高速缓存/主存向 MMU 返回 PTE。
         *  第 4 步 ：MMU 构造物理地址，并把它传送给高速缓存/主存。
         *  第 5 步 ：高速缓存/主存返回所请求的数据字给处理器。
         *  ![image-20210211155320081][]
     *  页面命中完全是由硬件来处理的，与之不同的是，处理缺页要求硬件和操作系统内核协作完成
        
         *  第 1 步 到 第 3 步 相同。
         *  第 4 步 ：PTE 中的有效位是零，所以 MMU 触发了一次异常，传递 CPU 中的控制到操作系统内核中的缺页异常处理程序
         *  第 5 步 ：缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘。
         *  第 6 步 ：缺页处理程序页面调人新的页面，并更新内存中的 PTE。
         *  第 7 步 ： 缺页处理程序返回到原来的进程，再次执行导致缺页的指令。CPU 将引起缺页的虚拟地址重新发送给 MMU。因为虚拟页面现在缓存在物理内存中，所以就会命中，在 MMU 执行了图 9-13b 中的步骤之后，主存就会将所请求字返回给处理器。
         *  ![image-20210211155640132][]

##### 9.6.1 结合高速缓存和虚拟缓存 #####

*  ![image-20210212113508461][]
 *  Cache速度更快，MMU在转换的时候首先去匹配L1，命中则直接返回，不命中才去内存访问。

##### 9.6.2 利用TLB加速地址翻译 #####

*  翻译后备缓冲器（Translation Lookaside Buffer, TLB)。个人理解成页表的cache（记录页表）。
 *  一行：
    
     *  ![image-20210212113846974][]
 *  步骤：
    
     *  第 1 步 ：CPU 产生一个虚拟地址。
     *  第 2 步 和 第 3 步：MMU 从 TLB 中取出相应的 PTE。
     *  第 4 步 ：MMU 将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存。
    
     *  第 5 步 ：高速缓存/主存将所请求的数据字返回给 CPU。
 *  下图展示TLB命中与不命中的情况：
    
     *  ![image-20210212114659218][]
     *  当 TLB 不命中时，MMU 必须从 L1 缓存中取出相应的 PTE。新取出的 PTE 存放在 TLB 中，可能会覆盖一个已经存在的条目。

##### 9.6.3 多级页表 #####

*  ![image-20210212115215372][]
 *  个人理解是：多级页表可以减少内存汇总页表的驻留数量（减少内存占用）；可以减少页表查找次数（类似于线性查找和走树的方式查找，当然，一个节点又多个PTE）
 *  书上的解释：
    
     *  用来压缩页表的常用方法是使用层次结构的页表。
        
         *  第一，如果一级页表中的一个 PTE 是空的，那么相应的二级页表就根本不会存在。这代表着一种巨大的潜在节约，因为对于一个典型的程序，4GB 的虚拟地址空间的大部分都会是未分配的。
         *  第二，只有一级页表才需要总是在主存中；虚拟内存系统可以在需要时创建、页面调入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中。

##### 9.6.4 总和：端到端的地址翻译 #####

*  这里口述一下：
    
     *  ![image-20210212120427069][]
     *  上图TLB是四路组相连，所以MMU一开始分析虚拟地址的时候会将低两位（TLBI）作为组索引（图中的6、7两位，有点偏），得到是TLB中的哪一行，再遍历这行的四项，对比标记位（TLBT）看看是否匹配，若是（且有效位为1），则直接得到物理地址，若不是，则继续访问缓存。
     *  ![image-20210212120912024][]
     *  ![image-20210212121055776][]
     *  若缓存可以，则类似上面得到物理地址，若不是，则访问页表，这时候只需要根据VPN对比有效位即可，有就得到物理地址，没有就得磁盘IO了

#### 9.7 案例研究：Intel Core i7/Linux内存系统 ####

##### 9.7.1 Core i7 地址翻译 #####

*  CPU封装：
    
     *  ![image-20210212130434596][] \- 我的关注点是：每个核都有两级cache、TLB，而L3在核外，被所有核共享。
     *  ![image-20210212131053869][] \- 上图标出顺序，两个1是因为我认为（可能i7不是这样）MMU是快慢表同时访问的机制。
     *  四级页表条目
        
         *  ![image-20210212140103326][] \- 上图（前三级页表中条目的格式）应当按照红线分两部分对照看，可以对照下表字段注释分析得到条目的格式
         *  ![image-20210212140805764][] \- 而第四级的条目只需要注意6、7两位的变化， - 对于7只对第一层定义故为0 - 而6则是修改位（由MMU在读和写时设置，由软件清除）
     *  将四级地址换连起来，就可以得到如下顺序
        
         *  ![image-20210212141125228][]

##### 9.7.2 Linux 虚拟内存系统 #####

*  1 .Linux 虚拟内存区域
    
     *  Linux 将虚拟内存组织成一些区域（也叫做段）的集合。一个区域（area)就是已经存在着的（已分配的）虚拟内存的连续片（chunk), 这些页是以某种方式相关联的。
     *  ![image-20210212151909551][]
     *  task\_struct:[进程描述符][Link 1]
     *  mm\_struct:(内存描述符)(https://blog.csdn.net/qq\_26768741/article/details/54375524)
     *  ![image-20210212152021901][]
 *  2、Linux 缺页异常处理
    
     *  1、\*\*判断虚拟地址A是否合法：\*\*虚拟地址是否合法（即判断地址越界），主要看它是否存在某个段中。处理程序会将虚拟地址A与链表中的所有节点中的`vm_start`和`vm_end`进行比较，判断虚拟地址A所处的段，如果不存在任一段中，则会触发段错误，终止进程。
     *  2、\*\*判断对虚拟地址A的访问是否合法：（判断读写权限）\*\*当虚拟地址A处在某个段中时，可以通过`vm_prot`确定该段的读写许可，然后与我们所需要的操作进行对比，如果操作违背了许可，则会触发保护异常，终止进程，Linux也将其报告为段错误。
     *  3、如果以上两个步骤都是合法的，则执行正常的缺页处理。处理程序会选择一个物理牺牲页（替换页），如果牺牲页被修改了，则进行写回，然后将虚拟地址A对应的虚拟页写入对应的物理页中，修改对应的页表，然后从处理程序返回。
     *  以上三种情况对应下图中的1、2、3
        
         *  ![image-20210212153757451][]

#### 9.8 内存映射 ####

*  Linux的一个虚拟内存区域与一个磁盘上的对象关联起来，对象如下：
    
     *  1、Linux文件系统中的普通文件
        
         *  一个区域可以映射到一个普通文件的连续部分
     *  2、匿名文件
        
         *  一个区域可以映射到匿名文件，所谓匿名文件，是由内核创建，包含的全部是二进制零
 *  一旦初始化了，就在swap（交换空间，在安装系统时，如果选择自定义分配盘区，会有一项swap分配，一般为内存一到两倍比较合适）中换来换去（与内存）

##### 9.8.1 再看共享对象 #####

*  ![image-20210212155205599][]
 *  有了映射机制，对于共享对象，自然而然想到在虚拟内存页表中把物理地址指向共享对象首地址即可。
    
     *  因为每个对象都有一个唯一的文件名，内核可以迅速地判定进程 1 已经映射了这个对象，而且可以使进程 2 中的页表条目指向相应的物理页面。关键点在于即使对象被映射到了多个共享区域，物理内存中也只需要存放共享对象的一个副本。
 *  而对于私有对象，有一个技术叫做：写时复制（copy-on-write)将其映射到虚拟内存中
    
     *  即不写的时候和共享对象一样——一份副本
     *  只要有一个进程试图写私有区域内的某个页面，那么这个写操作就会触发一个保护故障。当故障处理程序注意到保护异常是由于进程试图写私有的写时复制区域中的一个页面而引起的，它就会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复这个页面的可写权限。
     *  ![image-20210212155658973][]

##### 9.8.2 再看fork函数 #####

*  当 fork 函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的 PID。
    
     *  为了给这个新进程创建虚拟内存，它创建了当前进程的 mm\_struct、区域结\_区域结构都标记为私有的写时复制。当 fork 在新进程中返回时，新进程现在的虚拟内存刚好和调用 fork 时存在的虚拟内存相同。
     *  当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

##### 9.8.3 再看execve函数 #####

*  当我们运行`execve("a.out", NULL, NULL)`执行可执行目标文件`a.out`时，包含以下步骤：
    
     *  \*\*删除用户段：\*\*将进程的虚拟地址空间中的用户段删除，即删除`vm_area_struct`和页表。
     *  \*\*映射私有段：\*\*首先为可执行目标文件中的不同数据节创建对应的段，即在`vm_area_struct`中新建节点，并设置对应的段起始虚拟地址、段终止虚拟地址，设置这些段为私有写回复制的。然后将这些段通过内存映射与`a.out`中的内容关联起来。（对私有对象的读写参考2.2）
     *   *  对于需要初始化为0的段，可将其与匿名文件进行关联。
     *  \*\*映射共享段：\*\*对于共享库的内容，会将其映射到共享库的内存映射段中，即在`vm_area_struct`中创建一个共享段，然后将其与共享库的内容关联起来，这样就能在多个进程中共享相同的共享库。（对共享对象的读写参考2.1）
     *   *  如果共享库有维护状态的静态变量，比如随机生成器在调用时会维持状态，且不同的进程的状态不同，对于这种要修改静态数据的函数，应该将该段标记为私有写时复制的，这样就能在不同进程中维护自己独立的状态。
         *  ![image-20210212162527823][]
     *  设置PC——程序入口
 *  \*\*总结：\*\*当程序运行时，我们并没有加载任何内容到内存中，所做的只是设置内存映射，在内核中创建数据结构，由此创建了虚拟地址空间和这些对象之间的映射关系，而实际的拷贝工作会由缺页异常按需完成。

##### 9.8.4 使用mmap函数的用户级映射 #####

*  Linux 进程可以使用mmap 函数来创建新的虚拟内存区域，并将对象映射到这些区域中。
 *  ![image-20210212162811364][]
 *  mmap 函数要求内核创建一个新的虚拟内存区域
    
     *  **最好**是从地址 start 开始的一个区域，并将文件描述符 fd 指定的对象的一个连续的片(chunk)映射到这个新的区域。连续的对象片大小为 length 字节，从距文件开始处偏移量为 offset 字节的地方开始。
     *  start地址仅仅是一个暗示，通常被定义为 NULL。
     *  ![image-20210212163023463][]
     *  参数 prot 包含描述新映射的虚拟内存区域的访问权限位（即在相应区域结构中的 vm\_prot 位）。
        
         *  PROT\_EXEC：这个区域内的页面由可以被 CPU 执行的指令组成。
         *  PROT\_READ：这个区域内的页面可读。
         *  PROT\_WRITE：这个区域内的页面可写。
         *  PROT\_NONE： 这个区域内的页面不能被访问。
 *  munmap 函数删除虚拟内存的区域：
    
     *  ![image-20210212163228914][]
     *  munmap 函数删除从虚拟地址 start 开始的，由接下来 length 字节组成的区域。接下来对已删除区域的引用会导致段错误。

#### 9.9 动态内存分配 ####

*  用动态内存分配器（dynamic memory allocator)更方便，也有更好的可移植性。
 *  动态内存分配器维护着一个进程的虚拟内存区域，称为堆（heap)
    
     *  ![image-20210212164502619][]
     *  对于每个进程，内核维护着一个变量 brk(读做 “break”），它指向堆的顶部。
     *  分配器将堆视作大小不同的块（block）的集合来维护，每个块就是一个连续的虚拟内存片（chunk）。
     *  分配器有两种基本风格：
        
         *  **显式分配器（explicit allocator)**, 要求应用显式地释放任何已分配的块。
            
             *  C 程序通过调用 malloc 函数来分配一个块，并通过调用 free 函数来释放一个块。
             *  C+ + 中 的 new 和 delete 操作符与 C 中的 malloc 和 free 相当。
         *  **隐式分配器（impUcit allocator)**, 另一方面，要求分配器检测一个已分配块何时不再被程序所使用，那么就释放这个块。
            
             *  隐式分配器也叫做垃圾收集器（garbage collector)，而自动释放未使用的已分配的块的过程叫做垃圾收集（garbage collection)。
             *  例如，诸如 Lisp、 ML 以及 Java 之类的高级语言就依赖垃圾收集来释放已分配的块。

##### 9.9.1 malloc 和 free 函数 #####

*  malloc：
    
     *  ![image-20210212205112406][]
     *  malloc 函数返回一个指针，指向大小为至少 size 字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。
     *  在实际应用中，我们通常会指定malloc返回指针的类型。如：`char* b = (char*)malloc(300000*sizeof(char));`
     *  如果 malloc 遇到问题(例如，程序要求的内存块比可用的虚拟内存还要大），那么它就返回 NULL，并设置 errno。
     *  **malloc 不初始化它返回的内存**。那些想要已初始化的动态内存的应用程序可以使用 calloc
        
         *  calloc 是一个基于 malloc 的瘦包装函数，仓将分配的内存初始化为零。
     *  想要改变一个以前已分配块的大小，可以使用 realloc 函数。
     *  malloc是在堆中分配空间（上文红圈）。
 *  sbrk：
    
     *  ![image-20210212205642062][]
     *  sbrk 函数通过将内核的 brk 指针增加 incr 来扩展和收缩堆。
     *  如果成功，它就返回brk 的旧值，否则，它就返回一1，并将 errno 设置为 ENOMEM。
     *  如果 incr 为零，那么sbrk 就返回 brk 的当前值。
     *  用一个为负的 incr 来调用 sbrk 是合法的，而且很巧妙，因为返回值（brk 的旧值）指向距新堆顶向上 abs(incr)字节处。
 *  free：
    
     *  程序是通过调用 free 函数来释放已分配的堆块。
     *  ![image-20210212205933563][] \- ptr 参数必须指向一个从 malloc、calloc 或者 realloc 获得的已分配块的起始位置。如果不是，那么 free 的行为就是未定义的。更糟的是，既然它什么都不返回，\*\*free就不会告诉应用出现了错误\*\*。
 *  示例：
    
     *  ![image-20210212210328483][]
     *  这里说明了两点：
        
         *  1、malloc边界双字对齐。
         *  2、free之后指针还在，只不过空间不是给这个指针分配的了。

##### 9.9.2 为什么要使用动态内存分配 #####

*  更灵活——数组大小的最大值就只由可用的虚拟内存数量来限制。
    
     *  但是malloc的堆有时候会爆掉（百万级数据），而new不会。

##### 9.9.3 分配器的要求和目标 #####

*  显示分配器要求：
    
     *  处理任意请求序列
     *  立即响应请求
        
         *  不允许分配器为了提高性能重新排列或者缓冲请求。
     *  只使用堆
        
         *  为了使分配器是可扩展的，分配器使用的任何非标量数据结构都必须保存在堆里。
     *  对齐块（求其要求）
     *  不修改已分配的块
        
         *  一旦块被分配了就不允许修改或者移动它
 *  目标：
    
     *  最大化吞吐率
     *  最大化空间利用率：![image-20210213144644766][]
        
         *  聚集有效载荷（aggregate payload)表示为 P(为当前已分配的块的有效载荷之和)，上式分子表示最大的P（前k条指令中最大的P）
         *  而Hk表示堆的当前的（单调非递减的）大小。

##### 9.9.4 碎片 #####

*  造成堆利用率很低的主要原因是一种称为碎片（fragmentation )的现象——当虽然有未使用的内存但不能用来满足分配请求时
    
     *  分为：
        
         *  内部碎片(internal fragmentation)
            
             *  是已分配块大小和它们的有效载荷大小之差的和。
             *  在任意时刻，内部碎片的数量只取决于以前请求的模式和分配器的实现方式。
         *  外部碎片（external fragmentation)。
            
             *  是当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的
             *  外部碎片难以量化且不可能预测——它不仅取决于以前请求的模式和分配器的实现方式，还取决于将来请求的模式
 *  分配器通常采用启发式策略来试图维持少量的大空闲块，而不是维持大量的小空闲块。
    
     *  这里查了下启发式策略的定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个[可行解][Link 2]，该可行解与最优解的偏离程度一般不能被预计。（[或者这个回答也比较清楚][Link 3]）

##### 9.9.5 实现问题 #####

*  一个实际的分配器要在吞吐率和利用率之间把握好平衡，就必须考虑以下几个问题：
    
     *  空闲块组织：我们如何记录空闲块？
     *  放置 ：我们如何选择一个合适的空闲块来放置一个新分配的块？
     *  分割：在将一个新分配的块放置到某个空闲块之后，我们如何处理这个空闲块中的剩余部分？
     *  合并：我们如何处理一个刚刚被释放的块？

##### 9.9.6 隐式空闲链表 #####

*  任何实际的分配器都需要一些数据结构，允许它来区别块边界，以及区别已分配块和空闲块。
    
     *  ![image-20210213150552954][]
     *  一个块是由一个字的头部、有效载荷，以及可能的一些额外的填充组成的。
     *  由于双字的对齐约束条件的存在，块大小就总是 8 的倍数，且块大小的最低 3 位总是零——我们只需要内存大小的 29 个高位，释放剩余的 3 位来编码其他信息。即图中头部012位
 *  特点：
    
     *  简单
     *  显著的缺点是任何操作的开销
        
         *  类似单链表的结构（因为大小不固定，所以只有读头部才知道下一块的在哪），所以该搜索所需时间与堆中已分配块和空闲块总数呈线性关系。
     *  最小双字的限制（即使是一个char，也要申请两字）

##### 9.9.7 放置已分配的块 #####

*  放置策略（placement policy)
    
     *  常见的策略是首次适配（first fit)、下一次适配（next fit)和最佳适配（best fit)。

##### 9.9.8 分割空闲块 #####

*  一旦分配器找到一个匹配的空闲块，它就必须做另一个策略决定，那就是分配这个空闲块中多少空间。一个选择是用整个空闲块。虽然这种方式简单而快捷，但是主要的缺点就是它会造成内部碎片。

##### 9.9.9 获取额外的堆内存 #####

*  如果分配器不能为请求块找到合适的空闲块：
    
     *  1、通过合并那些在内存中物理上相邻的空闲块来创建一些更大的空闲块。
     *  2、合并了也找不到——sbrk函数向内核请求额外的堆内存。
        
         *  分配器将额外的内存转化成一个大的空闲块,将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

##### 9.9.10 合并空闲块 #####

*  假碎片（fault fragmentation)——相邻两块都是空闲的
    
     *  为了解决假碎片问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并（coalescing)。
        
         *  **立即合并**（immediate coalescing)，也就是在每次一个块被释放时，就合并所有的相邻块。
         *  **推迟合并**（deferred coalescing), 也就是等到某个稍晚的时候再合并空闲块。

##### 9.9.11 带边界标记的合并 #####

*  边界标记( boundary tag), 允许在常数时间内进行对前面块的合并。
 *  如下所示：再块末尾复制一份头部（称为脚部，这个脚部总是在距当前块开始位置一个字的距离，因此比较好访问）那么分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态。
    
     *  ![image-20210213152504036][]
 *  下图为前后块的四种情况，一般来说是符合直觉的合并方式：
    
     *  ![image-20210213152753759][]

##### 9.9.12 综合：实现一个简单的分配器 #####

*  坑位——过段时间做实验

##### 9.9.13 显式空闲链表 #####

*  ![image-20210213153912402][]
 *  使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。
 *  释放一个块的时间可以是线性的，也可能是个常数，这取决于我们所选择的空闲链表中块的排序策略。
 *  排序策略：
    
     *  后进先出（LIFO)（类似与栈）：
        
         *  使用 LIFO 的顺序和首次适配的放置策略，分配器会最先检査最近使用过的块。
         *  在这种情况下，释放一个块可以在常数时间内完成。如果使用了边界标记，那么合并也可以在常数时间内完成。
     *  地址顺序：
        
         *  地址排序的首次适配比 LIFO 排序的首次适配有更高的内存利用率，接近最佳适配的利用率。
 *  显式链表的**缺点**是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，也潜在地提高了内部碎片的程度。

##### 9.9.14 分离的空闲链表 #####

*  减少分配时间的方法——分离存储（segregated storage), 就是维护多个空闲链表，其中每个链表中的块有大致相等的大小。
    
     *  一般的思路是将所有可能的块大小分成一些等价类，也叫做大小类（size class)。
 *  简单分离存储（simple segregated storage)：
    
     *  使用简单分离存储，每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小。
     *  如果链表非空，我们简单地分配其中第一块的全部。空闲块是不会分割以满足分配请求的——要分配就整块分配
     *  要释放一个块，分配器只要简单地将这个块插人到相应的空闲链表的前部——头插法
     *  特点：
        
         *  分配和释放块都是很快的常数时间操作。
         *  不分割，不合并，这意味着每个块只有很少的内存开销。
         *  一个已分配块的大小就可以从它的地址中推断出来。
         *  已分配块不需要头部，也不需要脚部。
         *  简单分离存储很容易造成内部和外部碎片。
            
             *  因为空闲块是不会被分割的，所以可能会造成内部碎片。更糟的是，因为不会合并空闲块，所以某些引用模式会引起极多的外部碎片。
 *  分离适配（segregated fit)：
    
     *  分配器维护着一个空闲链表的数组。每个空闲链表是和一个大小类相关联的，并且被组织成某种类型的显式或隐式链表。每个链表包含潜在的大小不同的块，这些块的大小是大小类的成员。
     *  为了分配一个块，必须确定请求的大小类，并且对适当的空闲链表做**首次适配**，査找一个合适的块。
        
         *  如果找到了一个，那么就(可选地)分割它，并将剩余的部分插入到适当的空闲链表中。
         *  如果找不到合适的块，那么就搜索下一个更大的大小类的空闲链表。如此重复，直到找到一个合适的块。
         *  如果空闲链表中没有合适的块，那么就向操作系统请求额外的堆内存，从这个新的堆内存中分配出一个块，将剩余部分放置在适当的大小类中。
     *  要释放一个块，执行合并，并将结果放置到相应的空闲链表中。
        
         *  这里有一个问题，是有脚部？所以可以快速释放？
 *  伙伴系统：
    
     *  伙伴系统（buddy system)是分离适配的一种特例，其中每个大小类都是 2 的幂。
     *  分配一块的时候，寻找合适的快大小直接分配，找不到则找大一号的块对半分，一般分配，一半插入合适（大小为一半）的链表
     *  特点：
        
         *  伙伴系统分配器的主要优点是它的快速搜索和快速合并。
         *  主要缺点是要求块大小为 2的幂可能导致显著的内部碎片。
         *  因此，伙伴系统分配器不适合通用目的的工作负载。
         *  然而，对于某些特定应用的工作负载，其中块大小预先知道是 2 的幂，伙伴系统分配器就很有吸引力了。

#### 9.10 垃圾收集 ####

*  垃圾收集器（garbage collector)是一种动态内存分配器，它自动释放程序不再需要的已分配块。
 *  自动回收堆存储的过程叫做垃圾收集（garbage collection)。

##### 9.10.1 垃圾收集器的基本知识 #####

*  垃圾收集器将内存视为一张有向可达图（reachability graph)
 *  该图的节点被分成一组根节点（root node ) 和一组堆节点（heap node)。
    
     *  ![image-20210213160802337][]
     *  当存在一条从任意根节点出发并到达f的有向路径时，我们说节点是可达的(reachable)。在任何时刻，不可达节点对应于垃圾，是不能被应用再次使用的。
     *  垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点且将它们返回给空闲链表，来定期地回收它们。
 *  对于C系的垃圾收集器来说，不能维持可达图的精确表示。这样的收集器也叫做保守的垃圾收集器（conservative garbage collector)——每个可达块都被正确地标记为可达了，而一些不可达节点却可能被错误地标记为可达。
    
     *  ![image-20210213161103503][]

##### 9.10.2 Mark&Sweep 垃圾收集器 #####

*  Mark&Sweep 垃圾收集器由标记（mark)阶段和清除（sweep)阶段组成，
    
     *  标记阶段标记出根节点的所有可达的和已分配的后继。块头部中空闲的低位中的一位通常用来表示这个块是否被标记了。
     *  清除阶段释放每个未被标记的已分配块。
 *  函数说明：
    
     *  ![image-20210213162145210][]
 *  伪代码：
    
     *  ![image-20210213161932918][]
     *  标记阶段为每个根节点都调用一次`mark`函数，首先会判断输入`p`是否为指针，如果是则返回`p`指向的堆节点`b`，然后判断`b`是否被标记，如果没有，则对其进行标记，并返回`b`中不包含头部的以字为单位的长度，这样就能依次遍历`b`中每个字是否指向其他堆节点，再递归地进行标记。这是对图进行DFS。
 *  示例：
    
     *  ![image-20210213162342585][]
     *  上图堆由六个已分配块组成，其中每个块都是未分配的。第 3块包含一个指向第 1 块的指针。第 4 块包含指向第 3 块和第 6 块的指针。根指向第 4 块。在标记阶段之后，第 1 块、第 3 块、第 4 块和第 6 块被做了标记，因为它们是从根节点可达的。第 2 块和第 5 块是未标记的，因为它们是不可达的。在清除阶段之后，这两个不可达块被回收到空闲链表。

##### 9.10.3 C 程序的保守 Mark&Sweep #####

*  C程序想要使用Mark&Sweep垃圾收集器，在实现`isPtr`函数时**具有两个困难：**
    
     *  第一，C不会用任何类型信息来标记内存位置。因此，对 isPtr 没有一种明显的方式来判断它的输人参数 P 是不是一个指针。
     *  第二，即使我们知道 P 是一个指针，对 isPtr 也没有明显的方式来判断 P 是否指向一个已分配块的有效载荷中的某个位置。
        
         *  解决方法是将已分配块集合维护成一棵平衡二叉树，这棵树保持着这样一个属性：左子树中的所有块都放在较小的地址处，而右子树中的所有块都放在较大的地址处。
         *  ![image-20210213162926060][]
         *  isPtr(PtrP>函数用树来执行对已分配块的二分查找。在每一步中，它依赖于块头部中的大小字段来判断 P是否落在这个块的范围之内。
         *  但是它仍然可能不正确地标记实际上不可达的块，因此它可能不会释放某些垃圾。虽然这并不影响应用程序的正确性，但是这可能导致不必要的外部碎片。

#### 9.11 C程序中常见的与内存有关的错误 ####

##### 9.11.1 间接引用坏指针 #####

scanf("%d", &val);
    //错写成，
    scanf("%d", val);

*  在这种情况下，scanf 将把 val 的内容解释为一个地址，并试图将一个字写到这个位置。
 *  当val 的内容对应于虚拟内存的某个合法的读/写区域，于是我们就覆盖了这块内存，这通常会在相当长的一段时间以后造成灾难性的、令人困惑的后果。

##### 9.11.2 读未初始化的内存 #####

*  ![image-20210213163753161][]
 *  malloc并不会初始化y数组中的值（可能是0可能是其他任意值），但是下方双循环中却错误地假设已经全部被初始化了。

##### 9.11.3 允许栈缓冲区溢出 #####

*  ![image-20210213164037323][]
 *  下面的函数就有缓冲区溢出错误，因为 gets 函数复制一个任意长度的串到缓冲区。
    
     *  因此我们必须使用 fgets 函数，这个函数限制了输人串的大小

##### 9.11.4 假设指针和它们指向的对象是相同大小的 #####

*  一种常见的错误是假设指向对象的指针和它们所指向的对象是相同大小的：
 *  ![image-20210213205139035][] \- 因为程序员在第 5 行将 sizeof(int \* )写成了 sizeof(int ) , 代码实际上创建的是一个 int 的数组。 - 这段代码只有在 int 和指向 int 的指针大小相同的机器上运行良好。但对于某些指针大于int那么最终分配空间可能大于需要预测分配的空间。

##### 9.11.5 造成错位错误 #####

*  错位（off-by-one)错误是另一种很常见的造成覆盖错误的来源：
 *  ![image-20210213205718194][]

##### 9.11.6 引用指针，而不是它所指向的对象 #####

*  ![image-20210213205828046][] \- 在第 6 行，目的是减少 size 指针指向的整数的值。然而，因为一元运算符--和 \*的优先级相同，从右向左结合，所以第 6 行中的代码实际减少的是指针自己的值，而不是它所指向的整数的值。

##### 9.11.7 误解指针运算 #####

*  ![image-20210213205955077][] \- 然而，因为每次循环时，第 4 行都把指针加了 4(一个整数的字节数），函数就不正确地扫描数组中每 4 个整数。 - p指向下一个整数只需要p++即可

##### 9.11.8 引用不存在的变量 #####

*  ![image-20210213210346688][] \- 在return后，尽管 &val 仍然指向一个合法的内存地址，但是它已经不再指向一个合法的变量了。当以后在程序中调用其他函数时，内存将重用它们的栈帧。\*\*即指针存在，但是被标为未分配。\*\*

##### 9.11.9 引用空闲堆块中的数据 #####

*  一个相似的错误是引用已经被释放了的堆块中的数据。
    
     *  ![image-20210213210732445][]
     *  这个跟malloc和free的机制有关，free虽然把空间表为未分配，但是并没有删除x指针，故x还是指向原来的数组地址。

##### 9.11.10 引起内存泄漏 #####

*  之前学过：C系采用的是保守的垃圾收集机制，对于下列leak函数，x并不会被回收，久而久之则会导致内存泄漏。
    
     *  ![image-20210213211421646][]
     *  如果经常调用 leak，那么渐渐地，堆里就会充满了垃圾，最糟糕的情况下，会占用整个虚拟地址空间。
     *  对于像守护进程和服务器这样的程序来说，内存泄漏是特别严重的，根据定义这些程序是不会终止的。

[image-20210211110251714]: /images/20221024/18bb0bd39084491aa74adf5f3f564d7a.png
[image-20210211110332797]: /images/20221024/feb5b9188419400aba210b0ebedc7b68.png
[image-20210211112710058]: /images/20221024/5d78801820c445c6957eaff8944f8dc9.png
[image-20210211113813545]: /images/20221024/6bdf87d08642432f847235ed3584b8e2.png
[image-20210211114003264]: http://docker.aliyouth.cn/img/image-20210211114003264.png
[image-20210211114311746]: /images/20221024/59e010c9d6764b0a893072dca7f40a43.png
[image-20210211144345669]: /images/20221024/ca6854b7e18f4d7c8738c0e70629911d.png
[image-20210211150842334]: /images/20221024/ca774002102340a588ce65cdd1a674c7.png
[image-20210211151336747]: /images/20221024/5fd3c4848c124e72a4002f3c91b3ba7c.png
[image-20210211152025378]: /images/20221024/4ffeeaacb9d343c995a31fa5baad4ebc.png
[image-20210211152136809]: /images/20221024/5f6e039bbf7945f5a8e404080465c628.png
[image-20210211155320081]: /images/20221024/ce7bb281c7df4db8b98329ae7e3468e2.png
[image-20210211155640132]: /images/20221024/0976a73904614a2ebccd91cb7c06e0ea.png
[image-20210212113508461]: /images/20221024/6fc056bc95d64377b12640a05d283c56.png
[image-20210212113846974]: /images/20221024/03646e86594345c59d6828e5384a58dc.png
[image-20210212114659218]: /images/20221024/10d5f6e8ff0f430485a6bdfb4136c7dc.png
[image-20210212115215372]: /images/20221024/f7b6ef1614444b608fcbeca0a7815881.png
[image-20210212120427069]: /images/20221024/5e3b8e6250e540ebab3c72a168f7fe23.png
[image-20210212120912024]: /images/20221024/8f519ab6f0e34f05b435cf0787c3808b.png
[image-20210212121055776]: /images/20221024/55c6fcf82d2a4c2893a96a7ac37382d9.png
[image-20210212130434596]: /images/20221024/3730768508b74807aaedee2ac0ef9715.png
[image-20210212131053869]: /images/20221024/308229a0253a40c3aba92e25f3d012c1.png
[image-20210212140103326]: /images/20221024/83e56c67c99d489eb0ab5dc2bc514b46.png
[image-20210212140805764]: /images/20221024/57da497cba2743488b608dc6474d74cc.png
[image-20210212141125228]: /images/20221024/bdca4e1dab114855bac24dde79f5bd12.png
[image-20210212151909551]: /images/20221024/50337b137d6743b4be4dabfafb58e298.png
[Link 1]: https://blog.csdn.net/qq_26768741/article/details/54348586
[image-20210212152021901]: /images/20221024/c69fc8f17522452b8c5e730bd9d185ac.png
[image-20210212153757451]: /images/20221024/f1911de12ba64098b4e5121e55228174.png
[image-20210212155205599]: /images/20221024/c8c7ab899120435eb57836d60b24f40d.png
[image-20210212155658973]: /images/20221024/602f2b8717f24d9998512e050581892e.png
[image-20210212162527823]: /images/20221024/55a3b5ae3add497da5adecc9fa626611.png
[image-20210212162811364]: /images/20221024/7b9b34e9a18c4d2eb0010caade075a78.png
[image-20210212163023463]: /images/20221024/d93a056c92fa4fef855935f90610c27c.png
[image-20210212163228914]: /images/20221024/288dbb3e745943838c25939c6bda9fc9.png
[image-20210212164502619]: /images/20221024/93a9d43ff21a42868f9abf851aa20a0a.png
[image-20210212205112406]: /images/20221024/23969555340c4d04a1d38c5294ac8a6a.png
[image-20210212205642062]: /images/20221024/1b7e8f2cf18b4713b511a594f322d923.png
[image-20210212205933563]: /images/20221024/74dd54da5814465c9bb3d479636dcdc9.png
[image-20210212210328483]: /images/20221024/08d9854b3cac409dadf47bd5268bbed0.png
[image-20210213144644766]: /images/20221024/9527ce86f6724c408efbd8f8ec166da7.png
[Link 2]: https://baike.baidu.com/item/%E5%8F%AF%E8%A1%8C%E8%A7%A3/962143
[Link 3]: https://zhidao.baidu.com/question/295385586.html
[image-20210213150552954]: /images/20221024/efffe0f89a424b6eba15028eaea170f8.png
[image-20210213152504036]: /images/20221024/3c80783e31304f5eaed133d582fc8c69.png
[image-20210213152753759]: /images/20221024/6783382913684365a192cbdc400ae867.png
[image-20210213153912402]: /images/20221024/97155229e5eb465aa9f314189215895a.png
[image-20210213160802337]: /images/20221024/04a78b819cd6449db781f333a7f608b6.png
[image-20210213161103503]: /images/20221024/41b5edcc31b441b486cd6cea8c8df11d.png
[image-20210213162145210]: 
[image-20210213161932918]: /images/20221024/3c4cebab068c428892f5887d7eb0a63f.png
[image-20210213162342585]: /images/20221024/b2cb353f405c4b1bb6a0ea9266d55e04.png
[image-20210213162926060]: /images/20221024/0df216af32c944fea91e8956c15e40a5.png
[image-20210213163753161]: /images/20221024/8c5f438b72324a5c8466f30d117332ae.png
[image-20210213164037323]: /images/20221024/4f3acf1dc731428bb6f1a714e78702be.png
[image-20210213205139035]: /images/20221024/f940445c6c7342638b11930fd281136a.png
[image-20210213205718194]: /images/20221024/9fd9c4deb0d04f949966df7c59c8a73b.png
[image-20210213205828046]: /images/20221024/bf14a849a7d34cd38828131ee66753d3.png
[image-20210213205955077]: /images/20221024/3560ece5085c426782e9a7c3fcd63e02.png
[image-20210213210346688]: /images/20221024/9cff1dc5dbb74286afeb54303acef451.png
[image-20210213210732445]: /images/20221024/5e261587230942f79cefb325aef1b1a5.png
[image-20210213211421646]: /images/20221024/7cf9eb9b18cb4f79a630f29f839641b6.png