# 前言

之前的几本书，都是 全都读完 之后，再将笔记从语雀转移到自己的 Hexo 博客上，但是想想一本书有多少？笔记就算记得再少也少不到哪里去。

这就导致一个问题：文字太多，自己都...em...

于是这次想转变一下思路和做法，感觉可以单独先『移记』一下的，那就先在整理到博客上。

# 第一章 基本概念

# 术语

位 (bit)：小写字母 b 指代位
字节 (byte)：使用大写字母 B 表示
随机存取存储器 (RAM)：允许不管访问的存储器区域如何，都能在相同的访问时间内读取数据
非均匀访问存储器：与 RAM 相反，访问存储器所需时间取决于其在物理存储器上的位置（在访问之前必须将存储介质放置，例如旋转到正确位置）
地址 (address)：表示整个存储区中的特定位置
算数逻辑单元 (ALU)：负责执行加法和减法运算，计算机核心。现代计算机包括多个 ALU，可实现计算并行化
控制单元 (control unit)：解码从内存中读取的程序指令 (操作码)。根据内部指令的描述，执行哪些算数或逻辑运算以及要对哪些数据进行运算

• 控制单元存储一个称为指令指针 (IP) 或程序计数器 (PC) 的附加寄存器，以指向当前执行的指令。正常程序执行非常简单，只需要将存储在 PC 中的地址递增到后续指令即可，循环或跳出之类就像将指令指针的值更改为另一个地址和指定要移动程序执行的位置一样简单。
• 注：严格说，操作码只是指令的一部分，指令包括操作码和地址码

寄存器 (register)：通常包含在内存中的可以直接从 ALU 和 / 或控制单元 (可以统称为执行单元) 快速访问的内存位置，速度极快，没有地方比它更接近执行单元的了
字 (word)：特定计算机设计中使用的固定大小的基本数据单位。反映在许多设计领域，如大多数寄存器大小、最大地址或在单个操作中传输的最大数块。常用位表示，称为字长。如 32 位或 64 位长寄存器。

# 静态分配

在编译期间，甚至在执行程序之前，就必须知道所需内存的数量和确切位置

# 寄存器机

使用寄存器 (或特殊情况下的累加器) 在算数逻辑单元 (ALU) 上操作的机器。
构成这种设计的机器称为寄存器机：因为在这样的机器上执行程序时，实际上是在寄存器上进行计算。如果要进行加法、除法或其它操作时，必须先将对应的数据从内存加载到对应的寄存器中，然后调用特定指令对其执行对应操作，然后调用另一个指令将其中一个寄存器的结果存储到内存中。

# 堆栈 (Stack)

概念上，堆栈是一种数据结构，可以简单地描述为 后进先出 (LIFO) 列表
堆栈一开始就与计算机编程有着内在联系，主要是因为子例程的概念
堆栈帧 (stack frame)：为特定目的保存在堆栈上的任何结构化数据

• 嵌套调用子例程只需要重复这个模式，即可为每个调用添加一个活动帧
• 子例程调用的嵌套越多，堆栈上的活动帧就越多（这也使得无限嵌套调用成为不可能）

如图所示，堆栈指针 (SP) 保留一个指示堆栈当前边界的地址。程序计数器 (PC) 指向执行函数内部某个位置
现代计算机中的堆栈既有硬件层面 (通过为堆栈指针提供专用寄存器) 的支持，也有软件层面 (通过操作系统对线程及其指定为堆栈的内存部分的抽象) 的支持

• 堆栈可以存储在 cpu 内部专用内存块或专用芯片上
• 也可以直接重用普通计算机内存（大多数现代架构中情况）

# 堆栈机

与寄存器不同，在堆栈机中，所有指令都在专用表达式堆栈 (或求值堆栈) 上操作。

• 注：此处堆栈机与前文讨论的堆栈不必相同

在这样的计算机中，默认情况下，指令从表达式堆栈顶部获取参数，结果也存储在堆栈顶部，这种情况下它们被称为纯堆栈计算机

• 与不纯的实现相对应 (当操作不仅可以从堆栈顶部访问值，而且还可以访问更深的值时，称为不纯的实现)

表达式堆栈操作：

• 例如，假想的乘法指令，将从求值堆栈顶部弹出两个值，将其相乘，然后将结果放回求值堆栈

堆栈机概念带来了非常清晰和易于理解的代码

• 与如何以及在何处存储临时值无关，不管是在寄存器、堆栈还是在主内存。
  • 从概念上将，比试图以最佳方式管理所有这些可能的目标更容易，因此简化了实现。
• 由于存在许多无操作数或单操作数指令，因此在所需内存方面操作码可以更短
  • 这允许对指令进行高效的二进制编码，从而产生高密度的二进制代码。因此即使指令数量可能比基于寄存器机的方法要多 (由于更多的加载 / 存储操作)，但仍然是受益的

尽管堆栈机有其优点，但它很少在硬件上实现。但这种架构是设计独立于平台的虚拟机或执行引擎的好方法。（如 java 虚拟机和 .net 运行时就是堆栈机的完美示例，它们实现了堆栈机逻辑，并由 x86 或 ARM 寄存器机执行）
虚拟堆栈机 (不是由真正的硬件堆栈机执行的堆栈机) 可以在生成高性能代码的同时提供良好的平台独立性。
堆栈机代码的层次更高，可以更好地从实际底层硬件抽象出来，其概念非常简单、优雅和高效。

• 另一方面，基于寄存器的虚拟机设计更接近其实际运行的真实硬件设计，对可能的优化更有用（所解释的代码与机器代码相似越多，效果越好）

目前 .Net 执行引擎是作为一个堆栈机实现的，不过并不是完全纯的，例如会将求值堆栈映射到包含寄存器和内存的底层硬件上。
注：并非所有虚拟机和执行引擎都是堆栈机

# 指针

将位置地址存储在内存中的变量，允许通过地址引用内存中的其它位置。
指针大小与字长有关，由计算机架构决定，如今我们通常处理 32 位或 64 位宽的指针。由于只是内存的一小部分，因此也可以将其放置在堆栈中 (例如作为局部变量或函数参数) 或 cpu 寄存器上。
指针还可以提供指针算数，可以加上或减去内存的相对引用部分。

• 例如增量运算符将指针的值加上指向的对象大小的值，而不是单个字节。

悬空指针：释放后没有置为 null

# 堆 (Heap)

堆 (也称为自由存储区) 是一个用于动态分配对象的内存区域。

• 自由存储区：没有体现任何内部结构，而只体现了一个目的。
• 与有序的堆栈空间相反，堆传统英语含义：混乱的地方
• 注：堆数据结构与堆没有关系

堆是一种内存机制，能够提供具有指定大小的连续内存块。该操作被称为动态内存分配。

• 由于内存的位置在编译时是不知道的，因此动态分配的内存必须要由指针来引用，因此指针与堆本质上是相关的。
• 指针可以存放在堆栈中、堆本身或其它任何地方。

堆碎片：尽管堆上有足够可用空间，但是并不连续。

# 自动内存管理

最初在 lisp 语言中诞生，自动内存管理和垃圾回收名称可以互换使用。
可以将其定义为一种机制，该机制一旦创建对象，便会在不再需要时自动销毁 (并且恢复它们的内存)，从而使程序员无需承担手动内存管理的责任。
但，即使内存管理是完全自动化的，也会产生问题。

# Mutator

内存管理最基本也是最重要的概念，称为 mutator 的抽象。
最简单来看，可以将 mutator 定义为负责执行应用程序代码的实体，或者说所有可能修改内存的东西，无论是通过修改现有对象还是通过创建新对象。

• 是应用程序中有关内存的所有更改的驱动器。

为了完全可操作，mutator 需要为运行的应用程序提供以下三种操作：

• new (amount)：分配给定数量内存，然后由新创建对象使用（这种抽象级别上，不考虑对象的类型信息，只是提供所需分配的内存大小）
• write (address,value)：在给定地址下写入指定值
• read (address)：从指定地址读取一个值

mutator 抽象最常见的一个实现是基于线程。不过就操作系统线程而言，不必将 mutator 实现为线程，例如 erlangVM、fiber

# 分配器 (Allocator)

分配器是一个负责管理动态内存分配和解除分配的实体。
分配器必须提供两个主要操作：

• Allocator.Allocate (amount)：分配指定数量内存
  • 如果类型信息可用于分配器，则可以通过能够为特定类型的对象分配内存的方法来扩展此方法，如被 Mutator.New 操作内部使用
• Allocator.Deallocate (address)：释放给定地址下的内存以供将来分配。
  • 在自动内存管理情况下，此方法为内部方法，不会暴露给 Mutotor (用户不可显式调用)

两种最流行的分配器：顺序和自由列表

# 回收器 (Collector)

当我们将 mutator 定义为负责执行应用程序代码的实体时，也可以将回收器定义为运行垃圾回收 (自动回收内存) 代码实体。
可达性并不意味着对象的存活性，而只是我们拥有的最佳近似值。

• 如果某个对象无法从任何 mutator 到达，则可以安全回收。
• 但它的反面显然不是事实，可到达对象可以永远保持可到达状态 (由于一些复杂的引用图来保持)，但由于执行条件可能永远无法访问，因此实际上已经死了。（大多托管内存泄露都存活性和可到达性之间）

mutator 在可达性方面的起点称为根，确切内容取决于特定 mutator 实现。不过大多情况，当 mutator 是一个线程时，可以是：

• 局部变量和子例程参数，放置在堆栈或寄存器中
• 静态分配的对象，放置于堆上
• 存储在回收器自身内部的其它内部数据结构

# 引用计数

自动内存管理的两种最流行的方法之一。
优点

• 确定性释放时刻，我们知道只要引用计数降为零即会发生释放。
• 更少内存限制，内存回收与不再使用对象速度一样快，等待回收的对象不会占用任何内存开销
• 不需要运行时支持即可实现
  • 可以作为外部库的某些特定类型的附加机制来实现。(如 c++ 智能指针)

缺点

• 增加大量开销 (简单在运行时引入)
• 多线程同步问题处理开销
• 降低 cpu 缓存使用效率
• 循环引用

C++ 的智能指针是基于标准库之上，而不是语言本身。直接在设计中就引入智能指针的语言：

• rust
• swift

# 跟踪回收器 (Tracking Collector)

查找对象可达性很困难，因为它是对象的全局属性，而释放对象的简单显式调用是非常局部的，在该局部上下文中，我们并不了解全局上下文 —— 现在是否还有其它对象在使用该对象？

• 引用计数试图通过只查看该局部上下文以及一些附加信息 (对象的引用计数) 来克服这一问题。会导致循环引用出现问题及一些其它缺点。

跟踪垃圾回收器是基于对象生存期的全局上下文的了解，从而可以更好地决定是否是删除对象 (回收内存) 的最佳时机。

• 这是一种非常流行的方法，当人们谈到垃圾回收器时，可能指的就是跟踪垃圾回收器。
• 核心思路是，跟踪垃圾回收器通过从 mutator 的根开始并递归地跟踪程序的整个对象图，来发现对象的真正可到达性。

跟踪垃圾回收器最典型方法包括以下两个主要步骤：

• 标记：回收器通过找到它们的可达性来确定内存中哪些对象可以被回收
• 回收：回收器将回收那些所发现的不再可到达的对象的内存

例如 .net 中：标记 - 计划 - 清除 - 压缩

# 标记阶段

从 mutator 根开始，回收器遍历整个对象图并标记访问过的对象。在标记阶段结束时那些未标记对象将是不可达的。由于对象标记，将不再存在循环引用问题。
由于程序正常执行图会不断变化，遍历这样的图会很困难，因此在某些垃圾回收器实现中，所有 mutator 都在标记阶段的时间内停止。

• 一旦线程恢复运行，回收器基于对象图所掌握的知识就会过时，但对于不可达对象来说不是问题：如果它以前不可达，那么将再也无法到达

# 保守垃圾回收器（conservation garbage collector）

这种类型的回收器可以被看成一个保底的解决方案。

• 当运行时或编译器无法通过提供确切的类型信息 (对象在内存中布局) 从而不能直接支持回收时，并且在使用指针进行操作时回收器不能获得 mutator 支持时可以使用的解决方案。

如果保守回收器想要找出什么对象是可达的，就要扫描整个堆栈、静态数据区和寄存器

• 由于没有任何帮助，它不知道什么是指针，只能试图去猜测 (即前面说的保底的意思)
• 通过检查一些东西来做到，最重要的一个检查是：将给定字解释为地址 (指针) 是否是指向由分配器堆区域管理的有效地址。
• 如果结果肯定，回收器将保守地假定它确实是一个指针，并把它当做一个引用来遵循。
• 显然猜测时可能犯错，随机会使有些位看起来像是具有正确地址的有效指针 (实际并不是)，将导致在垃圾回收中依旧保留对应内存不做回收。

保守垃圾回收主要优点是可以在没有运行时支持的情况下工作，它仅扫描内存，因此不需要运行时支持 (引用跟踪)
不过，保守回收器需要分配器的支持才能解决未知对象的内存布局问题。
优点

• 对于不支持从头开始进行垃圾回收的环境 (如早期运行时阶段或非托管语言) 而言，更容易使用

缺点

• 不精确：随机会导致看起来像一个指针的所有内容都会阻止内存被回收 (尽管并不常见)

在简单方法中，对象不能移动 (压缩)，因为回收器不确定哪些是指针 (而且它不能仅仅更新一个仅假定为指针的值)

# 精确垃圾回收器（precise garbage collector）

与保守垃圾回收器相比，精确垃圾回收器则简单许多，因为编译器或运行时为回收器提供了有关对象的内存布局的全部信息。还可以支持堆栈爬网 (枚举堆栈上所有对象的根)。
从定义明确的根开始，只需要逐个对象来扫描内存。

# 回收阶段

跟踪垃圾回收器找到了可到达对象之后，就可以从所有其它死对象中回收内存。回收器的回收阶段可以有多种不同的方式进行设计。

# 清除（sweep）

在这种方法中，死对象被简单地标记为可用空间，以便以后重用。这可能是一个非常快速的操作，因为仅需更改存储块的单个单位标记。
另外还有不简单的实现，可能需要通过构建数据结构来存储有关可用内存块的信息，以便更快地检索，通常采用空闲列表的形式，而且这些空闲列表必须足够智能，以合并相邻的可用内存块。
虽然清除速度很快，但最终会导致内存碎片变大或变小：可能会导致尽管总体上有足够的空闲内存，但是没有单个连续的空闲空间来用于新对象。

# 压缩（compact）

消除碎片会降低性能，因为它需要在内存中的对象之间移动。
主要有两种方式：

• 复制所有存活对象，会带来更大内存开销：因此一般只用于特定的小内存区域（而不是整个进程内存）
• 就地压缩：将对象移向彼此，以消除间隙。主要问题是：如何在不相互覆盖且不使用任何临时缓冲区的情况下相对于彼此来移动对象（如 .net）

# 比较

保守垃圾回收器实现了清除回收，精确垃圾回收器实现了压缩回收。
跟踪垃圾回收器优缺点：

• 优点
  • 从开发人员角度看，完全透明，内存被抽象为无限，开发人员无需考虑如何释放不再需要的对象内存
  • 不存在循环引用问题
  • 在 mutator 上没有太大开销
• 缺点
  • 更复杂的实现
  • 非确定地释放对象
  • 停止标记阶段程序线程
  • 更大的内存约束 —— 由于在不需要对象时无法快速回收对象，因此可能会引入更大的内存压力

主要是因为第一个优点，因此跟踪垃圾回收器在不同的运行时间和环境中非常流行。

# 总结

应该始终致力于扩展知识，以努力成为一名专业人士 —— 知识是不会自动跑到大脑里的，需要跳出舒适区。
如果不能理解原理，止步于用 .net、jvm 框架之类的，会像星期天的司机一样，只能从方向盘和踏板的角度来看待我们的车。