存储分配

Stack allocation, deallocation

最简单的存储模式就是栈。

如果我们申请x bytes，我们主要做法就是：

1 2	sp += x; return sp-x;

上述与实际上的函数调用都是同理。

当我们free x bytes的时候：

sp -= x;

并且所有在sp之后的东西，都可以被认为是空闲的。

上述代码实际上一般要去检查栈溢出，但是一般编译器不这样做，因为如果有溢出，就是bug，你得处理它。

然而，栈的使用是有局限性的，也就是说，我们不会track中间的部分，但是栈很快！（实际上，栈是向下增长的，也就是说从高地址到低地址，这里方便理解才这样说）

Heap

由于栈有缺陷，这里就有了堆，堆是一种动态分配的内存，我们可以在程序运行时动态的分配内存。同时，这里的堆与数据结构与算法、C++里面的堆是不同的。

C语言提供了malloc和free函数来分配和释放内存。C++提供了new和delete来分配和释放内存。不像Java和Python，这些语言有自己的垃圾回收机制，所以不需要手动释放内存。堆存储一旦被分配，就必须手动释放，否则会造成内存泄漏。同时我们需要注意悬空指针以及双重释放（多次释放，会导致未定义的行为）的问题。

Fix size allocation（固定的大小heap分配）

固定内存大小分配，每一块内存都有相同的大小，没有被使用的内存用空闲链表来管理。（把页面分成固定大小的blocks）

当我们去做分配的时候，我们代码是这样的：

1
2
3

x = free;
free = free->next;
return x;

这里都是指针，其中free指向的是第一个空闲的内存块，free->next指向的是下一个空闲的内存块。很容易理解，就是个链表嘛，其实我们需要注意第二条语句，free != NULL，这个是必须的，否则会出现未定义的行为。

当我们释放内存的时候：

1 2	x->next = free; free = x;

实际上可以理解成在首部添加一个节点。

我们使用free list的优缺点如下：

优点：
- 分配和释放内存都是O(1)的时间复杂度
- 有着很好的时间局部性，最近释放的将是要分配的
缺点：
- 空间局部性很差，因为有外部碎片的存在，即页面有剩余的blocks，但是不是连续的，无法继续给进程分配内存，同时由于这些blocks是分散的，当内存块（blocks）分配得很分散时，意味着同一个程序的数据被存储在物理内存的许多不同位置。这就需要在页表中为这些不同的位置建立映射关系，导致页表的大小增加。换句话说，如果一个程序的数据被连续地存储在内存中，那么页表就可以通过一个连续的地址范围来表示这些数据。但是，如果数据被分散地存储在内存中，那么页表就需要为每一个数据块单独建立映射关系，这就会使页表的大小增加。
- 同时对于TLB影响也很大！如果页表变大，那么TLB的命中率就会降低，因为TLB的大小是有限的，如果页表变大，那么TLB就会有更多的缺失，这样就会导致更多的内存访问，这样就会影响性能。

消除外部碎片的一个方法

为每个磁盘页面都维护一个空闲链表，当我们想要分配内存的时候，我们从最满页面的空闲链表中分配内存，这样就可以减少外部碎片的存在。也就是这样的思想：90-10 is better than 50-50.

我们可以看到，两次随机访问，能够hit同一个页面的概率左边要比右边大！这也就是优化邻域里面所说的，做更多的倾斜。

动态大小堆分配(binned free list)

为了利用好空闲链表的效率，我们使用binned free list，接受有限数量的内部碎片。

我们可以看到，我们这里有一堆bins，每个bin都有一个固定的大小，bin k里面的blocks就是有 $2^k$ 的大小的内存。我们来看具体是怎么做的：

我们先确定分配x bytes的k是多少，然后，我们找一个非空的对应的bin，返回一个block就行。如果我们没找到，那么我们就找一个大一点的bin，然后把它分成pieces，如果是多级的，就一层一层分，反正这样的分也是二进制分法。如下所示：

同时，如果没有更大的blocks，那么我们就需要去找操作系统去请求更多的内存。

程序在虚拟内存中的分布

好的，现在有一个问题，既然我们的计算机现在是64位的，理论上虚拟内存非常大，那么我们为什么不一直分配而不去做释放呢？

其实问题在于外部碎片的问题，如果我们一直分配，那么就会有很多外部碎片，这样我们就没法继续分配内存了。
物理内存会耗尽

因此我们在分配上面有一个目标：

Use as little virtual memory as possible, and tryto keep the used portions relatively compact.

关于BFL的理论分析

如果我们有最大的堆内存是M，那么理论上我们拥有的bin数量上界限为log2(M)。而且我们知道，如果我们的block size是 $2^k$ ，那么我们的上界是2M，这样我们把两项相乘得到的是 $M* log_2(M)$ ，这就是虚拟内存的堆存储分配数量级。

GC算法(Garbage collection)

早些年在华科实习，学习SSD，就有接触过GC，还好自己在这方面有点基础认识，否则这节课听起来云里雾里

术语回顾：

Roots指的是可以直接被程序访问的对象，比如全局变量，栈等等
Live objects指的是可以从root沿着指针访问到的对象
Dead objects指的是不能从root沿着指针访问到的对象，并且这些对象能够被回收

我们可以知道，C语言里面没有GC，因为要实现GC，首先要严格的定义指针，并且指针不能去做一些奇怪的操作，比如指针运算导致内存地址找不到，这样才能保证GC的正确性。

Reference counting（垃圾回收的简单形式）

我们对于每一个对象，都有一个引用计数，当引用计数为0的时候，我们就可以回收这个对象。这样的方法有一个问题，就是循环引用，比如A引用B，B引用A，这样的话，引用计数永远不会为0，这样就会导致内存泄漏。（其实这种循环引用的方法，我们可以通过定义强指针，弱指针来解决，弱指针的话，其引用就是0），当然，C没有这种强弱指针机制，因此我们需要另一个方法。