【OS】Heap & Stack

操作系统概念的堆、栈不同于数据结构的堆、栈。

C 语言中，一切指针占 4 字节，这意味着指针指向 RAM 中的地址可以有 2³² 个，最小的地址是 0，最大的地址是 2³¹ - 1。

（一）堆：

堆空间在内存中是一个字节的沙盒。

malloc()、free()、realloc() 是程序员使用软件，通过特定的启发式策略管理内存的。malloc() 不仅返回一块内存的基地址，它还留出额外的头部空间记录了分配出去的内存块的实际大小。

经过一些分配释放后，堆中的内存碎片化了，形成有大有小的空闲块。因此使用一个内存块的链表（存储下个空闲内存块的地址）来记录空闲的内存块，这个链表称为空闲表，方便 malloc() 等函数继续管理内存。

（二）栈：

当进行函数调用时，函数调用会强制地为局部变量申请空间，这些局部变量的内存就在 RAM 中被称为“栈”（stack segment）的子集中。

调用 main() 函数时会得到它的局部变量，它们 alive & active，当 main() 调用一个子函数时，main() 的变量就暂时被屏蔽掉了，无法访问；当继续调用子函数的子函数时，这一系列变量都被分配好空间，但只有在最底部的函数中的局部变量才是 alive 的，并可以通过变量名访问。

每当函数调用时，系统都会为其创建活动记录。

如调用以下 void fun(int para1, int para2) 函数，

void fun(int para1, int *para2) {
    char a[4];
    short *b;
    // 以下略
    ...
}

系统会形成这样的布局。

注意：

（1）函数形参从左到右，分别存放在内存的低地址到高地址，通俗地讲，第二个参数在第一个参数之上。

（2）位于函数形参和局部变量中间的部分，存储着调用函数的某些信息，告诉我们“哪块代码”调用了 fun()，这里称为 saved PC。

另一个递归调用阶乘函数的例子：

int fact(int n) {
    if (n == 0)    return 1;
    return n * fact(n - 1);
}

我们用模拟汇编指令的方法写该 <fact> 函数：

 1 R1 = M[SP + 4];    // 将 n 的值存放到寄存器 R1 中
 2 BNE R1, 0, PC + 12;    // Branch分支指令，R1 和 0 Not Equal 时，跳转
 3 RV = 1;
 4 RET;    // RV 存放返回值 1，调用 RET 返回
 5 R1 = M[SP + 4];
 6 R1 = R1 - 1;    // R1 = n - 1
 7 SP = SP - 4;
 8 M[SP] = R1;
 9 CALL <fact>;    // 继续调用 <fact>，此时RV已经存放了 <fact> 返回的有意义的值
10 SP = SP + 4;
11 R1 = M[SP + 4];
12 RV = RV * R1;
13 RET;