在考虑标识符和绑定(bindings)的时候, 关键在于区分标识符和它们所引用的对象, 以及以下事件:
- 对象的创建
- 绑定的创建
- 所有使用绑定的情况, 诸如引用变量, 子程序, 类型等
- 停用和重用那些暂时没有用的绑定
- 绑定的析构(destruction)
- 对象的析构
绑定的生命周期指的是这个绑定从创建到析构的整个过程, 类似的可以定义对象的生命周期. 通常情况下, 一个对象的生命周期可能会大于对应的绑定的生命周期, 即当
标识符不再引用该对象时, 该对象依然存在(例如在子程序中传入某个对象的引用, 如C++中的&参数). 当然, 一个绑定的生命周期也有可能大于对应对象的生命周期,
虽然这通常被认为是一个BUG.
对象的生命周期通常与以下内存分配(storage allocation)机制有关:
- 静态(static)对象会在程序的整个运行过程中被分配一个绝对地址.
- 栈(stack)对象随着子程序的调用和返回而被创建以及按照LIFO的顺序析构.
- 堆(heap)对象可以在任何时候创建和析构, 其额外要求更加通用和昂贵的内存分配算法.
静态分配(static allocation)
静态分配最明显的例子就是全局对象, 当然全局对象不是唯一的例子. 构成程序机器语言翻译的指令也可以认为是静态分配的变量; 数字和字符串的常量当然也是静态分配 的; 另外很多编译器会产生一系列的表用于支持运行时的debug, 动态类型检查, 垃圾回收, 异常处理等, 这些表也都是静态分配的. 静态分配的对象通常希望它们的值 不在变化, 因此经常被分配在被保护的只读的内存中以方便在试图修改其值产生中断并抛出运行时错误.
在很多语言中,一个具名常量通常要求有一个能够在编译期确定的初始值. 通常这些初始值都被限制在那些已知的常量以及内置的函数. 这些具名常量加上字面常量通常被
叫做表现常量(manifest constants)或者编译期常量(compile-time constants). 在某些语言中(C, Ada), 常量仅仅只是那些无法在elaboration
time之后改变的值, 这些值可能依赖与其他在运行时才能确定的值. 这些elaboration-time的常量在作为递归函数的局部变量时必须要分配在栈上. C#显示提供了
声明两种常量的方法, 即const和readonly关键字.
另外编译器通常对于子程序的某些值采用特定的分配策略:
- 参数和返回值, 编译器通常会尽可能的将这些值存在寄存器中.
- 临时变量, 通常是那些复杂计算过程的中间值, 一个优秀的编译器也会将它们保存在寄存器内.
- bookkeeping information, 这些通常包含子程序的返回地址.
基于栈的分配(stack-based allocation)
一门语言如果想要支持递归, 那么在局部变量上采用静态分配的策略将不再适用(Fortran90之前不支持递归), 因为需要变量的个数是未知的. 所幸的是递归天然地适用 于栈结构的分配策略. 每一个子程序在运行时都有一个栈帧(frame, 或者称为活动记录, activation record), 包含了传入参数, 局部变量, 临时变量, 以及 bookkeeping信息. 通常传入参数位于帧的顶部, 方便被调用者定位参数, 而其他的布局则依赖于实现. 栈的维护是子程序调用序列的责任, 即调用者在调用前(序言, prologue)和调用后(尾声, epilogue)执行的代码. 通常有一个帧指针(frame pointer)来保存当前帧的地址, 在大多数语言的实现中, 栈都是往地址减 小的方向增长的. 在这样的实现方式下, 局部变量, 临时变量, bookkeeping信息对于帧指针有一个负的偏移, 而传入参数和返回对于帧指针则有一个正的偏移, 因为 这些都保存在调用者的帧上.
即时没有递归的语言也可以从基于栈的分配中获益, 因为大多数语言的子程序都无法在同一个时间内运行, 如果采用静态分配意味着需要预先分配所有局部变量(运行的与 不运行的), 而基于栈的分配则可以节省很大的空间开销.
基于堆的分配(heap-based allocation)
堆上的子块(subblock)可以在任何时候分配和释放. 堆对于那些链式数据结构, 以及在运行时会改变大小的对象, 诸如列表, 集合, 通用的字符串等是必须的. 堆上的空间管理策略众多, 主要的原则是在速度和空间上进行权衡. 空间上又可以细分为内部错误(internal fragmentation)与外部错误(external fragmentation), 内部错误发生在一个内存分配算法分配的块比实际对象需要的空间更大, 而外部错误发生在未被使用的空间过于碎片化, 虽然有空间但无法满足实际 对象的需要. 许多内存管理算法都管理一个单链表, 即有堆内未被使用的块组成的可用链表(free list), 初始状态下这个链表只包含一个块即整个堆. first fit 算法会选择满足要求的第一个块, best fit 算法则会遍历整个链表寻找最小的且满足要求的块. 无论采用哪种策略, 如果被选择的块大小比实际需要的更大, 会将块分 成两部分, 返回满足要求的部分而将剩下的部分放回可用链表(如果剩余部分比最小的限制更小的话, 则会产生一个内部错误即不放回而返回一个更大的块). 当某个块 被释放而返回可用链表时, 将检查地址上与其相邻的一边或两边是否也有空闲的块, 如果有的话则将其合并. 直观上来讲, 希望能够有一个的 best fit 的算法能够 尽可能的将更大的块分给更大的对象. 与此同时, 该算法将花费更多的时间, 因为其必须遍历以寻找最合适的块. 并且该算法更倾向于产生更多的碎片. first fit 与 best fit 哪一种能够产生更少的外部错误取决于要求分配大小的分布.
在管理单个链表的内存算法中, 分配空间所花费的时间与可用块的数量成正比. 为了将这个开销降到常数级, 一些内存管理算法管理包含不同大小的多条链表, 每一个分 配请求都会选择一个合适的标准大小的链表. 实际上, 堆被划分为许多池(pools), 每一个对应一个标准大小, 且划分可以是静态的也可以是动态的. 两种广泛使用 的动态池调整机制包括伙伴系统(buddy system)和斐波那契堆(Fibonacci heap). 在伙伴系统中, 标准大小是2的幂次方序列, 如果请求一个大小为 $2^k$ 的块但不满足时会将一个大小为 $2^{k+1}$的块平分, 其中一个返回而将剩下的放入第k条链表中(标准大小为$2^k$). 当块被释放时, 其将于其可用的"伙伴"(平分 时出现的另一半)合并. 类似的, 斐波那契堆将标准大小序列分成斐波那契数列, 该算法产生内部错误比伙伴系统更少, 因为斐波那契数列增长比2的指数序列更为缓慢.
外部错误出现的问题在于堆的分配能力总是随着时间下降的. 总存在一个分配序列使得总大小小于堆的大小而堆无法完成所有分配, 为了减少外部错误, 必须要压紧(compact) 堆.
垃圾回收(garbage collection)
使用堆分配的对象, 在某些语言中(C, C++, Pascal)可以显示释放, 而更多的语言则规定分配的对象将在不再被使用时隐式地释放. 对于这种语言的运行时库(run-time library)必须要提供垃圾回收(garbage collection)机制来识别和回收不可达的对象. 许多函数式语言和脚本语言以及最近的命令式(imprerative, 指广泛意义上的)语言, 如Java, Modula-3和C#都提供了垃圾回收. 支持显示释放的传统观点包括实现更简单以及执行更高效, 即使是一个简单(naive)的自动垃圾 收集对于一个类型系统丰富的语言来说也会增加不小的复杂度, 另外即时是一个复杂的(sophisticated)的垃圾收集器也需要一个非常数的开销. 因此, 如果程序员 能够正确的界定一个对象的生命周期, 那么就不需要额外的运行时负担且能达到更高的效率. 而支持自动垃圾收集的观点则更为引人注目(compelling): 人为的释放 错误在现实世界中广泛存在并常常导致BUG, 如果一个对象释放的太早则会导致一个悬挂引用(dangling reference), 访问一个被另外对象所使用的空间; 相反 如果释放的过迟则可能会导致内存泄露问题, 最终甚至耗尽堆内存. 臭名昭著的释放内存错误难以定位和修复, 随着前沿程序的复杂性以及体积与日俱增, 能够从自动垃圾 收集中收获更大的益处.