课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一部分回顾Lecture 18至Lecture 20，包含虚拟内存以及内存分配。

备注：图片和总结内容均来自于课件。

说明：

大部分内容已经整理过，这部分参考之前的笔记：

https://doraemonzzz.com/2021/09/16/2021-9-16-%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F-%E7%AC%AC9%E7%AB%A0-%E7%AC%94%E8%AE%B0%E6%95%B4%E7%90%86-p1/

https://doraemonzzz.com/2021/09/16/2021-9-16-%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F-%E7%AC%AC9%E7%AB%A0-%E7%AC%94%E8%AE%B0%E6%95%B4%E7%90%86-p2/

这里仅仅进行补充。

Lecture 18

略过。

Lecture 19

隐式空闲链表

隐式空闲链表：查找空闲块

  • 首次适配：

    • 从头开始搜索列表，选择第一个适合的空闲块：

      p = start;
while ((p < end) &&    \\ not passed end
	   ((*p & 1) ||    \\ already allocated
       (*p <= len)))   \\ too small
    p = p + (*p & -2); \\ goto next block (word addressed)

    • 时间复杂度关于块总数（已分配和空闲）为线性；

    • 在实际中，它可能会导致链表开头的“碎片”；

  • 下一次适配：

    • 像首次适配，但从前一次搜索结束的地方开始搜索；
    • 比首次适配更快：避免重新扫描无用的块；
    • 一些研究表明碎片更糟；

  • 最佳适配：

    • 搜索链表表，选择最佳空闲块：匹配，并且剩余的比特数最少；
    • 保持碎片小；
    • 通常会比首次适配慢；

隐式空闲链表：小结

  • 实现：非常简单；
  • 分配成本：
    • 最坏情形下为线性；
  • 释放成本：
    • 最坏情形下为常数；
    • 即使有合并；
  • 内存使用：
    • 将取决于安置策略；
    • 首次适配，下一次适配，最佳适配；
  • 在实际中中不用于malloc/free，因为线性的分配时间复杂度；
    • 用于许多特殊用途的应用程序；
  • 但是，拆分和边界标签，合并的概念适用于所有的分配器；

Lecture 20

显式空闲链表

逻辑上：

物理上：块可以按照任意顺序

显式空闲链表分配

显式空闲链表释放

LIFO策略

情形1

将释放的块插入列表的根部：

情形2

合并后继块，合并两个内存块并将新块插入到链表的根部：

情形3

合并前驱块，合并两个内存块，在链表根部插入新块：

情形4

合并前驱和后继块，合并所有3个内存块并将新块插入列表的根部：

分离空闲链表

每个大小类别的块都有自己的空闲列表：

处理内存错误

  • 调试器：gdb
    • 有利于发现错误的指针间接引用；
    • 难以检测其他内存错误；
  • 数据结构一致性检查器
    • 默默运行，仅在出错时打印消息；
  • 二进制翻译器：valgrind
    • 强大的调试分析技术；
    • 重写可执行目标文件的text部分；
    • 在运行时检查每个单独的引用；
      • 坏指针、覆盖、超出已分配块的引用；
  • glibc malloc 包含检查代码
    • setenv MALLOC_CHECK_ 3