编译原理ch6 (2).ppt

第六章运行时的存储组织与管理注意：
这只是一个逻辑示意图，实际的方案与具体的语言及开发者的习惯而有不同，如FORTRAN语言没有动态区，但却有公用区。
保留区是只读区，其中的存储单元是为目标计算机体系结构特殊使用所保留的。如与寄存器、操作数栈相关的数据等。
栈区存放那些局部于过程的数据实体，它们随过程调用而分配、过程返回而消亡。由于遵循“先调用后返回”的原则，所以采用栈式管理。
堆区存放动态申请存储空间的动态变量及不遵守栈式规则的过程中的数据，如ADA的“task”。二、变量的存储分配静态变量(StaticVariable)
所需的存储区大小固定、在编译时可确定大小、编译时分配空间、运行时绑定于一个存储区，不会随所在的程序单元（过程、子程序）调用/返回而改变存储位置。这类变量称为静态变量。
半静态变量(SemistaticVariable)
所需的存储区大小固定、在编译时可确定大小、编译时分配空间，但随所在的程序单元调用而被绑定，返回而失去空间，并可能会在存储空间留有多个副本。在运行时可知（动态可确定），称为半静态变量。
例如：在允许递归语言中的递归过程中的变量。半动态变量(SemidynamicVariable)
主要指数组。所需存储区大小未知，但维数编译时已知，因此信息向量表的大小确定，是半静态的，数组元素的实际存储区则在运行时分配、绑定。例如：数组元素将被分配在二级存储区中。
动态变量(DynamicVariable)
存储区大小不能确定、且可能变化。即使到所在程序单元被激活（被调用）仍然未知，或者对数组而言信息向量表的大小未知，只有到使用时才能确定并被绑定。称为动态变量。
一般而言，1)存放在静态区，2)3)在栈区，4)在堆区§2. 存储管理特点：每个程序单元可以独立编译，对应于（绑定于）一个数据区。通过数据区首址和位移量为每个静态实体编址，位移在编译时确定，数据区在连接和执行时可以不同。
说明：
在FORTRAN语言中有二类特殊的语句说明数据实体。
COMMON语句与COMMON区。在COMMON区中存放的是COMMON语句所定义的变量，功能上相当于全局变量。
等价语句(EQUIVALENCE)。为降低空间开销，使用的一种覆盖技术，但覆盖会导致出现难以理解的错误。静态分配也适用于许多语言中的静态变量。如全局变量。
在Modula-2中一个模块的局部量
Ada语言中最高层模块（包）(Top-levelpackages)中定义的变量
C语言中的外部变量、静态变量
二、堆（heap）存储管理模式最优满足法（best-fitmethod)：寻找一块剩余最少的自由块。效率较差：引起小（无用）碎片增多。
首次满足法（first-fit)：选择第一个找到的足够大的自由块。
循环首次满足法（Circularfirstfit)：类似b)，但不同的是开始搜索不总是起点，而是当前的搜索点。
释放策略
不释放（ignore)：空间用完了就停止或从头分配。并不很差，尤其对空间较大的环境。
显式：通过执行释放命令来释放无用空间，由程序员完成。如C语言中的free(..）。
缺点是引起如“悬摆指针”这样的致命错误。隐式：即自动回收无用的堆空间，由系统完成，称为“无用单元收集”（garbageCollection)
常用方法：
单引用：不允许同一存区由多于一个引用存在，一旦引用改变指向，就释放该存区。此方法简单，但只适用简单数据类型，而不适合复杂的数据类型，如图、网等。
引用计数：对每个存区设立一个引用计数，当计数为零时释放,如COM。
废区自动收集：跟随所有得到的存区的指针，不断地标识所有可存取的堆目标，定时地检查存区是废区就回收。将消耗大量的时/空资源。§3.栈式分配被调用过程非局部变量存储区的首地址（静态链、Display表）
调用过程的AR首址（动态链，oldSP)
调用点的机器状态
形实参数通讯区
返回值
被调用过程的局部量和临时变量存储区程序单元一般可以以过程或分程序为单位，主要讨论以过程为单位。一旦知道过程的静态嵌套层号，AR所需的存储空间的大小是确定的。
AR的管理方法为：
建立一个运行栈
过程的每一次执行（被调用)与一个该过程的AR相对应。即每调用一次就将其AR下推入栈，过程返回该AR弹出。
例1：对如下的程序框架，当过程Q调用自己时，运行栈的情形如何？main
p
Q
callQ

callQ

callp
为保证SP总指向当前AR首址，要求：
调用发生时，在新建立的AR中保存当时的SP（称为oldSP)。
改变SP的当时值，使其指向新的AR。
过程执行结束时，取出oldSP，恢复为当前的SP。二、静态/半静态变量的访问例2：假定以unit为单位进行存储分配，即一个unit对应一个AR。
进入unitD时运行栈