环境管理_编译原理之运行时刻环境

第七章 运行时刻环境,湖南大学计算机与通信学院（软件学院）,编译器的一些问题,变量的存储位置如何分配？ 名字的作用域如何实现？ 过程调用如何实现？ 参数传递如何实现？ 这些问题需要依靠运行时环境来辅助解决。,运行时刻环境,运行时刻环境 为数据分配安排存储位置 确定访问变量时使用的机制 过程之间的连接 参数传递 和操作系统、输入输出设备相关的其它接口 主题 存储管理：栈分配、堆管理、垃圾回收 对变量、数据的访问,存储分配的典型方式,目标程序的代码放置在代码区，通常位于存储的低端 静态区、堆区、栈区分别放置不同类型生命期的数据值,实践中栈向较低地址方向增长堆向较高方向增长。,图7-1,编译的结果,全局/静态变量,共享,*从现在开始要注意， 为使我们能在所有的例子中方便地使用正的偏移量,栈向较高地址方向增长，即顶是在最下端。,0X00H,0XFFFFH,. . .,静态和动态存储分配,静态分配 编译器在编译时刻就可以做出存储分配决定，不需要考虑程序运行时刻的情形，如：静态变量（语言中static变量） 全局变量 动态分配 栈式存储：过程的局部名字采用栈式存储 和过程的调用/返回同步进行分配和回收，值的生命期和过程生命期相同 堆heap存储：有些数据生命期比相应过程调用的生命期更长，常分配在一个可重用存储的“堆”中。,堆和垃圾回收,堆是虚拟内存的一个区域，它允许对象或其他数据元素在被创建时获得存储空间，并在数据变得无效时释放该存储空间 垃圾回收：检测出堆中无用的数据元素，释放它们的空间 手工进行回收（程序员） 垃圾回收机制，如：,栈式分配,内容： 活动树 活动记录 调用(代码)序列 栈中的变长数据,活动树,过程调用（过程活动）在时间上总是嵌套的： 后调用的先返回(LIFO) 因此可以用栈式分配来处理过程活动所需要的内存空间。 程序运行的所有过程活动可以用树表示 每个结点对应于一个过程活动 根结点对应于main过程的活动 过程p的某次活动对应的结点的子结点对应于此次活动调用的各个过程活动（从左向右，表示调用的先后顺序）,活动树的例子快速排序（1）,活动树的例子快速排序（）,程序：P260，图7-2 过程调用（返回）序列和活动树的前序（后序）遍历对应 假定当前活动对应结点N，那么所有尚未结束的结点对应于N及其祖先结点。,活动记录,过程调用和返回由控制栈进行管理 过程活动记录：当调用过程或函数时，为其局部数据动态分配的存储区 活动记录按照活动的开始时间，从栈底到栈顶排列,图活动记录框架,计算中间结果,局部变量,活动记录,控制链：指向调用者的活动记录（固定长度部分） 访问链：活动记录中指向上一级活动记录(包含嵌套的环境定义的活动记录)的指针 保存的机器状态：此次调用前的机器状态信息，如：返回地址及一些寄存器的值,运行时刻栈的例子,例：快速排序 a11为全局变量 main没有局部变量 r有局部变量i q的局部变量i，和参数m,n。,Main的活动记录,调用序列,调用序列(calling sequence)为活动记录分配空间，填写记录中的信息； 返回序列(return sequence)恢复机器状态，使调用者继续运行。 调用序列会分割到调用者和被调用者中。 根据源语言、目标机器、操作系统的限制，可以有不同的分割方案 把代码尽可能放在被调用者中。,调用/返回序列的要求,数据方面 能够把参数正确地传递给被调用者 能够把返回值传递给调用者 控制方面 能够正确转到被调用者的代码的开始位置 能够正确转回调用者的调用位置（的下一条指令） 调用序列和活动记录的布局相关,活动记录的布局原则,调用者和被调用者之间传递的值放在被调用者记录的开始位置 固定长度的项放在中间位置 控制链、访问链、机器状态字段 早期不知道大小的项在活动记录尾部（干脆将固定长度的局部变量也放入该段） 栈顶指针通常指向固定长度字段的末端top_sp,调用代码序列的例子,Calling sequence（调用序列） 调用者计算实在参数的值 将返回地址和原top_sp（控制链）存放到被调用者的活动记录中。调用者增加top_sp的值（越过了调用者的局部数据、临时变量、被调用者的参数、机器状态字段） 被调用者保存寄存器值和其他状态字段 被调用者初始化局部数据、开始运行。 Return sequence （返回序列） 被调用者将返回值放到和参数相邻的位置 恢复top_sp和寄存器，跳转到返回地址。,栈中的变长数据,如果数据对象的生命期局限于过程活动的生命期，就可以分配在运行时刻栈中。 top指向实际的栈顶 top_sp用于寻找顶层记录的定长字段（框架指针）,例 利用Euclid算法的简单递归算法， 计算两个非负整数的最大公约数。,程序清单 C代码 #include int x, y; int gcd(int u, int v) if (v=0) return u; else return gcd(v, u%v); main() scanf(“%d%d”, ,若输入为，（）试画出运行的活动树 （）试画出运行时栈变化过程,main(),gcd(15,10),gcd(10,5),gcd(5,0),第3个调用时的环境如图7-2所示。,x:15 y:10,u:15 v:10 控制链 返回地址 局部变量,u:10 v:5 控制链 返回地址 局部变量,u:5 v:0 控制链 返回地址 局部变量,自由空间,Top_sp,top,全局静态区域,main的活动记录,第一次调用gcd时的活动记录,第二次调用gcd时的活动记录,第三次调用gcd时的活动记录,栈的生长方向,基于栈的环境,返回值为,基于栈的运行时环境,注意： 同一个过程的不同活动对应的活动记录的大小完全相同； 新的活动记录总是在栈顶加入； 其控制链总是指向先前的活动记录的控制链； top_sp指向当前活动记录的控制链； 调用返回时，将按顺序从栈中删去每个活动记录； 当在main中执行printf语句时，环境中只保留了main的活动记录和全局/静态区域。,7.3 栈中非局部数据的访问7.3.1无嵌套过程时的数据访问,无嵌套过程时的数据访问 例：语言 不允许嵌套过程声明，变量要么在函数内定义，要么全局地定义 C语言中函数对变量的访问 局部变量：在当前活动记录内，可通过top_sp指针加上相对地址来访问 全局/静态变量：在静态区，地址在编译时可知 C语言允许函数参数 参数中只需要包括函数代码的起始地址。 在函数中访问变量的模式很简单，不需要考虑过程是如何激活的。,C语言中活动记录中无需访问链,7.3 基于栈的运行时环境,1) 对名称的访问 在基于栈的环境中，要访问参数和局部变量，可用当前框架指针(top_sp)的偏移量实现。 在大多数的语言中，每个局部声明的偏移量可由编译程序静态地计算出来。因为过程的声明在编译时是固定的，而且为每个声明分配的存储器大小也根据其数据类型而固定。,例 考虑C过程 void f(int x, char c) int a10; double y; . . . ,对f调用的活动记录,x偏移量,top_sp,c偏移量,a偏移量,y偏移量,*此处在返回地址下 省略了被保存的状态等信息,整型4个字节、地址4个字节、字符1个字节、双精度浮点数8个字节，则偏移量为： 名称 偏移量 x -9 c -8 a +0 y +40 ai的地址为：0+4*i+ top_sp。 在基于栈的环境中，非局部的和静态的名字的地址都是固定的静态地址，可以直接访问。,*注意在本章内，栈是往下面大端生长的。,非局部数据的访问（嵌套过程）,PASCAL语言允许过程嵌套定义，且遵循静态作用域规则 代码运行时，对变量的访问应指向运行栈中最上层的同名变量。 问题：变量不一定在当前活动记录中，如何确定其位置？ 思考：符号表中存储了变量的偏移量，因此只需要确定的活动记录。 子问题：用嵌套层次可以完全解决这个问题吗？,非局部数据的访问（嵌套过程）,问题：用调用层次可以完全解决这个问题吗？,不能！A,B的层次差是，但B的控制链并没有直接指向A,解决方法：引入访问链 指向过程的定义环境,7.3.3 一个支持嵌套过程声明的语言,最新的支持嵌套过程的典型语言之一：ML ML是一种函数式语言，变量一旦声明并初始化就不会再改变 有少数例外，如：数组元素可通过特殊的函数调用改变 变量定义并初始化为不可更改的值的语句形式： = 函数定义的语法： Fun ()= 函数体(body)定义的语法： Let in end,嵌套深度,嵌套深度是正文概念，可根据源程序静态地确定 不内嵌于任何其他过程中的过程，嵌套深度为1 嵌套在深度为i的过程中的过程，深度为i+1.,深度为1 sort 深度为2 readArray，exchange， quicksort 深度为3 partition,图7-10 一个使用嵌套函数声明的ML风格的quicksort,访问链,显式表 显式表,访问链,引入访问链的目的：访问非局部数据 如果过程p在声明时嵌套在过程q的声明中，那么p的活动记录中的访问链指向最上层（最新）的q的活动记录。 从栈顶活动记录开始，访问链形成了一个链路，嵌套深度逐一递减。 设深度为np的过程p访问变量x，而变量x在深度为nq的过程中声明，那么 从当前活动记录出发，沿访问链前进np-nq次找到活动记录（其中的x就是要找的变量位置） x相对于该活动记录的偏移量在编译时刻已知 np和-nq在编译时刻已知；,访问链的例子P270,图7-11 用来查找非局部数据的访问链,访问链的处理 （明确调用过程与声明嵌套深度的关系）,当过程q调用过程p时，P访问链如何设置？把p的声明嵌套深度np与nq的关系分为大于，等于，小于三种情况考虑 p的声明嵌套深度大于q，p必然在q中直接定义，否则不满足作用域规则，那么p的访问链指向当前活动记录(即父亲直接调用孩子) 递归调用：p=q 。p的活动记录的访问链等于q当前记录的访问链(即自身等于自身) p的声明嵌套深度小于q的深度：此时必然有过程r，p直接在r中定义，而q嵌套在r中。此时应让p的访问链指向r的活动记录。(即q是p的侄子系的，r是p的父亲),7.3.6 过程型参数的访问链,有些语言允许过程作为参数，如：语言 例：tiny编译器中语义分析程序analyze.c的transverse函数声明如下： static void traverse( TreeNode * t, void (* preProc) (TreeNode *), void (* postProc) (TreeNode *) ) 构建符号表前序遍历语法树traverse(syntaxTree,insertNode,nullProc); 类型检查时后序遍历语法树traverse(syntaxTree,nullProc,checkNode);,7.3.6 过程型参数的访问链,当一个过程作为参数传递给另一个过程，并且随后调用了这个参数，有可能并不知道在程序中出现的上下文 后果：不知道如何设置的访问链 解决办法： 在传递过程指针参数时，过程型参数中不仅包含过程的代码指针(IP)，还包括正确的访问链（AL)。,7.3.6 过程型参数的访问链,图-12 使用函数参数的ML程序的概要,f是一个函数参数,对的引用,d被用作函数参数,7.3.6 过程型参数的访问链,因为d在c中定义,7.3.8 显示表（display),用访问链访问数据时，如果嵌套深度大，则访问的效率差。 显示表：使用数组d为每个嵌套深度保留一个指针 指针di指向栈中最高的对应于嵌套深度为i的的活动记录。 如果程序p中访问嵌套深度为i的过程q中变量x，那么di直接指向相应的q活动记录； 显示表的维护 调用过程p时，在p的活动记录中保留原dnp的值，并将dnp设置为p的该次活动记录。 从p返回时，恢复dnp的值。,显示表举例（）,q(1,9)调用q(1,3)时，q的深度为2,例： ML风格的quicksort,显示表举例（）,q(1,3)调用p，p的深度为3,q调用e，e的深度为2,例： ML风格的quicksort,嵌套层次结构分析,伪代码,Display,(1)main-(2)P-(3)Q-(4)R,主程序的 活动记录,d1,display,栈顶,（1）,主程序的 活动记录 P 的 活动记录,d1 d2,display,栈顶,（2）,栈,栈,主程序-P-Q-R,主程序的 活动记录P 的 活动记录 Q 的 活动记录 R 的 活动记录,主程序的 活动记录 P 的 活动记录 Q 的 活动记录,display,d1 d2 d3,d1 d2 d3,display,（3）,（4）,栈顶,栈,栈,栈顶,堆管理,堆空间 用于存放生命周期不确定、或者生存到被显式删除为止的数据对象，例： new生成的对象可以生存到被delete为止 Malloc申请的空间生存到被free为止 存储管理器 分配/回收堆区空间的子系统 根据语言而定 C、C+需要手动回收空间 Java可以自动回收空间（垃圾收集）,存储管理器的基本功能,分配：为每个内存请求分配一段连续的、适当大小的堆空间。 首先从空闲堆空间分配； 若没有可分配的堆空间，则从操作系统中获得连续的虚拟内存来增加堆空间； 如空间已用完，则将空间耗尽的消息反馈给应用程序 回收：把被回收的空间返回空闲空间缓冲池，以满足以后的分配请求。,期望的存储管理器特性,空间效率 使程序所需堆空间最小 实现手段：最小化存储碎片 程序效率 充分利用存储子系统，提高程序运行效率 在存储子系统中，不同的层次访问速度不一样 尽可能多的利用高访问速度的存储器件，可大幅度提高效率 低开销 最小化分配/收回内存的开销 即花费在分配和回收上的执行时间在总运行时间中所占的比例 注：分配的开销由小型请求决定，管理大型对象的开销相对不重要,一次内存访问中，机器首先在最低层的存储中寻找数据，如果数据不在那里则到上一层中寻找。,程序的局部性,大部分程序呈现高度的局部性 即程序的大部分运行时间花费在相对较小的一部分代码 时间局部性 若一个程序访问的存储位置很可能将在一个很短的时间段内被再次访问，称其具有时间局部性 空间局部性 若被访问的存储位置的邻近位置很可能将在一个很短的时间段内被再次访问，称其具有空间局部性,程序的局部性,程序把90的时间用于执行10的代码，原因如下： 程序常包含许多从不被执行的指令 如：使用组件和库构建的程序只使用了它们提供的一小部分功能 随需求变化和程序演化，遗留系统中常常包含许多不再被使用的指令 有大量容错和调试代码在正常运行时不执行 执行最内层循环和最紧凑递归环花费了程序执行的大部分时间,堆空间的碎片问题,程序运行前，堆是一个连续的自由空间 随着程序分配/回收内存，堆区逐渐被分割成空闲存储块（窗口，hole）和已用存储块 分配内存时，通常是把一个窗口的一部分分配出去，其余部分成为更小的块。 回收时，被释放的存储块被放回缓冲池。通常会把连续的窗口接合成为更大的窗口。,堆空间分配方法,Best-Fit（最佳适应优先） 在满足请求的最小窗口中分配内存 优点：可将大窗口保留下来以应对更大的请求 First-Fit（最先适应优先） 在第一个满足请求的窗口中分配内存 优点：快，常具有较好数据局部性（同一段时间内的对象分配连续空间） 缺点：总体性能较差,使用容器的管理方法,设定不同大小的空闲块，并将同样大小的块放在容器中。 较小的（较常用的）尺寸设置较多的容器。 比如GNU的C编译器gcc使用存储管理器lea将所有存储块对齐到8字节边界。 空闲块的尺寸大小： 16,24,32,40,512（相邻间相差8） 大于512的按照对数值划分(每个容器的最小尺寸是前一个容器的最小尺寸的两倍。) 荒野块：可以扩展的内存块 分配方法： 对于小尺寸的请求，直接在相应容器中找。 大尺寸的请求，在适当的容器中寻找适当的空闲块。可能需要分割内存块。 可能需要从荒野块中分割更多的块。,管理和接合空闲空间,当回收一个块时，可能可以把这个块和相邻的块接合起来，构成更大的块。 有些管理方法，比如说Lea中，不一定需要进行接合。(小于512的) 支持相邻块接合的数据结构需要如下两点 边界标记：在每一块存储块的两端，分别设置一个free/used位(兼当边界)；相邻的位置上存放字节总数。 双重链接的、嵌入式的空闲块列表：列表的指针存放在空闲块中、用双向指针的方式记录了有哪些空闲块。,例子,相邻的存储块A、B、C 当回收B时，通过对free/used位的查询，可