运行时存储空间的组织和管理研讨(ppt 112页).ppt

运行时存储空间的组织和管理 运行时的程序 过程的活动过程的一次执行称为过程的一次活动活动记录过程的活动需要可执行代码和存放所需信息的存储空间 后者称为活动记录 本章内容 影响存储分配策略的语言特征活动记录中各种数据域的安排 局部 各种存储分配策略 全局 静态分配 栈式分配 堆式分配非局部数据访问的实现方法各种参数传递方式及其实现符号表管理 影响存储分配策略的语言特征 过程能否递归当控制从过程的活动返回时 局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式过程能否作为参数被传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块是否必须显式地释放 7 1局部存储分配策略 7 1 1过程过程定义过程声明 过程名 过程体过程调用执行被调用过程的过程体形式参数过程定义中用于在主调和被调间传递数据的标识符实在参数过程调用时用于在主调和被调间传递数据的变元活动的生存期程序执行期间的连续的步序列 过程执行的第一到最后一步 名字的作用域和绑定 名字的作用域一个声明起作用的那部分程序称为该声明的作用域 即使一个名字在程序中只声明一次 该名字在程序运行时也可能表示不同的数据对象 即保存值的存储单元 符号表可用来寻找对一个名字的出现起作用的声明 名字的绑定 从名字到值的两步映射 环境把名字映射到左值 而状态把左值映射到右值 赋值改变状态 但不改变环境 如果环境将名字x映射到存储单元s 我们就说x被绑定到s 名字的绑定 静态概念和动态概念的对应 活动记录 过程一次执行所需的信息用一块连续的存储区来管理 称为活动记录 一般的活动记录的布局 指向调用者的活动记录 用来访问存于其它活动记录中的非局部数据 局部数据的安排 字节是可编址内存的最小单位 变量所需的存储空间可以根据其类型而静态确定 一个过程所声明的局部变量 按这些变量声明时出现的次序 在局部数据域中依次分配空间 局部数据的地址可以用相对于某个位置的地址来表示 数据对象的存储安排还有一个对齐问题 整数必须放在内存中特定的位置 如被2 4 8整除的地址 局部数据的安排 在SPARC Solaris工作站上下面两个结构的size分别是24和16 为什么不一样 typedefstruct a typedefstruct b charc1 charc1 longi charc2 charc2 longi doublef doublef a b 局部数据的安排 在SPARC Solaris工作站上下面两个结构的size分别是24和16 为什么不一样 typedefstruct a typedefstruct b charc1 0charc1 0longi 4charc2 1charc2 8longi 4doublef 16doublef 8 a b 局部数据的安排 在X86 Linux机器的结果和SPARC Solaris工作站不一样 是20和16 typedefstruct a typedefstruct b charc1 0charc1 0longi 4charc2 1charc2 8longi 4doublef 12doublef 8 a b 程序块 本身含有局部变量声明的语句可以嵌套最近嵌套作用域规则并列程序块不会同时活跃并列程序块的变量可以重叠分配 程序块 main beginofB0 inta 0 intb 0 beginofB1 intb 1 beginofB2 inta 2 endofB2 beginofB3 intb 3 endofB3 endofB1 endofB0 7 2全局存储分配策略 介绍程序运行时所需的各个活动记录在存储空间的分配策略描述过程的目标代码怎样访问绑定到局部名字的存储单元介绍三种分配策略静态分配策略栈式分配策略堆式分配策略 7 2 1运行时内存的划分 7 2 2静态存储分配策略 名字在程序被编译时绑定到存储单元 不需要运行时的任何支持 绑定的生存期是程序的整个运行时间 控制再次进入该过程时 局部变量的值和控制上一次离开时的一样 每个活动记录的大小是固定的 过程调用时保存信息的地址在编译时也是已知的 例 某分段式程序运行时刻的内存划分 数组区临时工作单元区简单变量区形式单元区寄存器保护区返回地址 某程序段 静态存储分配策略 顺序分配算法 基于调用图 按照程序段出现的先后顺序逐段分配 程序段区域0 2122 3637 5455 7172 9495 104共需要105个存储单元 程序段号 所需数据空间 能用更少的空间么 分层分配算法 允许程序段之间的覆盖 覆盖可能性分析 程序段区域60 950 2240 16323 40217 31141 62共需要63个存储单元 思考 如何设计分配算法 7 80 7 2 2静态存储分配策略 静态分配给语言带来的限制不允许递归过程数据对象的长度和它在内存中位置的限制 必须是在编译时可以知道的数据结构不能动态建立 7 2 2静态存储分配策略 Fortran语言被设计成允许静态存储分配 7 2 2静态存储分配策略 C语言程序的外部变量和程序中出现的常量都可以静态分配 声明在函数外面外部变量静态外部变量声明在函数里面静态局部变量自动变量 7 2 3栈式存储分配策略 如果过程允许递归某一时刻过程A可能已被自己调用了若干次 但只有最近一次处于执行状态 其余各次等待返回被中断的那次调用必须保存每次调用相应的数据区内容 活动记录 引入一个运行栈让过程的每次执行和过程的活动记录相对应 每调用一次过程 就把该过程的活动记录压入栈中 返回时弹出 假设寄存器top标记栈顶 局部名字x的相对地址为dx 则x的地址为top dx怎样刻画控制进入和离开活动的情况 7 2 3栈式存储分配策略 引入活动树活动树 用树来描绘控制进入和离开活动的方式 7 2 3栈式存储分配策略 活动树的特点每个结点代表某过程的一个活动根结点代表主程序的活动结点a是结点b的父结点 当且仅当控制流从a的活动进入b的活动结点a处于结点b的左边 当且仅当a的生存期先于b的生存期 7 2 3栈式全局存储分配策略 当前活跃着的过程活动保存在栈中控制栈的内容 s q 1 9 q 1 3 q 2 3 7 2 3栈式存储分配策略 运行栈 把控制栈中的信息拓广到包括过程活动所需的所有局部信息 即活动记录 7 2 3栈式存储分配策略 运行栈 把控制栈中的信息拓广到包括过程活动所需的所有局部信息 即活动记录 s 7 2 3栈式存储分配策略 运行栈 把控制栈中的信息拓广到包括过程活动所需的所有局部信息 即活动记录 7 2 3栈式存储分配策略 运行栈 把控制栈中的信息拓广到包括过程活动所需的所有局部信息 即活动记录 7 2 3栈式存储分配策略 运行栈 把控制栈中的信息拓广到包括过程活动所需的所有局部信息 即活动记录 7 2 3栈式存储分配策略 过程调用和过程返回都需要执行一些代码来管理活动记录栈 保存或恢复机器状态等过程调用序列过程调用时执行的分配活动记录 把信息填入它的域中的代码过程返回序列过程返回时执行的恢复机器状态 释放活动记录 使调用过程能够继续执行的代码调用序列和返回序列常常都分成两部分 分处于调用过程和被调用过程中 7 2 3栈式存储分配策略 即使是同一种语言 过程调用序列 返回序列和活动记录中各域的排放次序 也会因实现而异设计这些序列和活动记录的一些原则是以活动记录中间的某个位置作为基地址长度能较早确定的域放在活动记录的中间一般把临时数据域放在局部数据域的后面把参数域和可能有的返回值域放在紧靠调用者活动记录的地方用同样的代码来执行各个活动的保存和恢复 7 2 3栈式存储分配策略 调用者和被调用者之间的任务划分 7 2 3栈式存储分配策略 过程p调用过程q的调用序列p在栈上留出放返回值的空间 并计算实参 依次放入栈顶 同时改变top sp的值p把返回地址和当前base sp的值存入q的活动记录中 建立q的访问链 增加base sp的值q保存寄存器的值和其它机器状态信息q根据局部数据域和临时数据域的大小增加top sp的值 初始化它的局部数据 并开始执行过程体 7 2 3栈式存储分配策略 过程p调用过程q的返回序列q把返回值置入邻近p的活动记录的地方q对应调用序列的步骤 4 减小top sp的值q恢复寄存器 包括base sp 和机器状态 返回pp根据参数个数与类型和返回值类型调整top sp 然后取出返回值 7 2 3栈式存储分配策略 过程的参数个数可变的情况函数返回值改成用寄存器传递编译器产生将这些参数逆序进栈的代码被调用函数能准确地知道第一个参数的位置被调用函数根据第一个参数到栈中取第二 第三个参数等等如C语言的printf 7 2 3栈式存储分配策略 活动记录的长度在编译时不能确定的情况局部数组的大小要等到过程激活时才能确定在活动记录中为这样的数组分别存放数组指针的单元运行时 这些指针指向分配在栈顶的存储空间 7 2 3栈式存储分配策略 悬空引用 悬空引用 引用某个已被释放的存储单元main int dangle int p inti 23 p dangle return 7 2 4堆式存储分配策略 栈式分配策略在下列情况下行不通 过程活动停止后 局部名字的值还必须维持被调用者的活动比调用者的活动的生存期更长 此时活动树不能正确描绘程序的控制流不遵守栈式规则的有Pascal语言和C语言的动态变量Java禁止程序员自己释放空间 7 3非局部名字的访问 本节内容无过程嵌套的静态作用域 C语言 有过程嵌套的静态作用域 Pascal语言 动态作用域 Lisp语言 7 3 1无过程嵌套的静态作用域 过程体中的非局部引用可以直接使用静态确定的地址局部变量在栈顶的活动记录中 可以通过base sp指针来访问无须深入栈中取数据 无须访问链过程可以作为参数来传递 也可以作为结果来返回 7 3 2有过程嵌套的静态作用域 sortreadarrayexchangequicksortpartition 7 3 2有过程嵌套的静态作用域 过程嵌套深度sort1readarray2exchange2quicksort2partition3 7 3 2有过程嵌套的静态作用域 过程嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度 它的声明所在过程的嵌套深度作为该名字的嵌套深度 7 3 2有过程嵌套的静态作用域 寻找非局部名字存储单元的访问链 s a x q 1 9 k v 访问链 s a x q 1 3 k v 访问链 q 1 9 k v 访问链 s a x q 1 3 k v 访问链 q 1 9 k v 访问链 p 1 3 i j 访问链 e 1 3 访问链 s a x q 1 3 k v 访问链 q 1 9 k v 访问链 p 1 3 i j 访问链 7 3 2有过程嵌套的静态作用域 假定过程p的嵌套深度为np 它引用嵌套深度为na的变量a na np 如何访问a的存储单元 从栈顶的活动记录开始 追踪访问链np na次 到达a的声明所在过程的活动记录 访问链的追踪用间接操作就可完成 7 3 2有过程嵌套的静态作用域 过程p对变量a访问时 a的地址由下面的二元组表示 np na a在活动记录中的偏移 7 3 2有过程嵌套的静态作用域 建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp nx的情况x肯定就声明在p中被调用过程的访问链必须指向调用过程的活动记录的访问链 7 3 2有过程嵌套的静态作用域 建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程xnp nx的情况p和x的嵌套深度分别为1 2 nx 1的外围过程肯定相同追踪访问链np nx 1次 到达了静态包围x和p的且离它们最近的那个过程的最新活动记录所到达的访问链就是x的活动记录中的访问链应该指向的那个访问链 7 3 2有过程嵌套的静态作用域 programparam input output 过程作为参数 procedureb functionh n integer integer beginwriteln h 2 end b procedurec varm integer functionf n integer integer beginf m nend f beginm 0 b f end c begincend 过程作为参数传递时 怎样在该过程被激活时建立它的访问链从b的访问链难以建立f的访问链 7 3 2有过程嵌套的静态作用域 programparam input output 过程作为参数 procedureb functionh beginwriteln h 2 end procedurec varm integer functionf n integer beginf m nend f beginm 0 b f end c begincend 7 3 2有过程嵌套的静态作用域 programret input output 过程作为返回值 varf function integer integer functiona function integer integer varm integer functionaddm n integer integer beginreturnm nend beginm 0 returnaddmend procedureb g function integer integer beginwriteln g 2 end beginf a b f end 7 3 2有过程嵌套的静态作用域 C语言的函数声明不能嵌套 函数不论在什么情况下激活 要访问的数据分成两种情况 非静态局部变量 包括形式参数 它们分配在活动记录栈顶的那个活动记录中外部变量 包括定义在其它源文件中的外部变量 和静态的局部变量 它们都分配在静态数据区 通过使用Display表 SPnSPn 1 SP1SP0 SP SPn为第n层过程数据区首址 7 3 2有过程嵌套的静态作用域 7 3 3动态作用域 被调用过程的非局部名字a和它在调用过程中引用的是同样的存储单元 新的绑定仅为被调用过程的局部名字建立 这些名字在被调用过程的活动记录中占用存储单元 7 3 3动态作用域 programdynamic input output varr real procedureshow beginwrite r 5 3 end proceduresmall varr real beginr 0 125 showend begin静态作用域r 0 25 0 2500 250show small writeln 0 2500 250show small writelnend 7 3 3动态作用域 programdynamic input output varr real procedureshow beginwrite r 5 3 end proceduresmall varr real beginr 0 125 showend begin动态作用域r 0 25 0 2500 125show small writeln 0 2500 125show small writelnend 7 3 3动态作用域 实现动态作用域的方法深访问用控制链搜索运行栈 寻找包含该非局部名字的第一个活动记录浅访问为每个名字在静态分配的存储空间中保存它的当前值当过程p的新活动出现时 p的局部名字n使用在静态数据区分配给n的存储单元 n的先前值可以保存在p的活动记录中 当p的活动结束时再恢复 7 4参数传递 本节内容形参和实参相关联的几种方法传值调用引用调用复制 恢复传名调用 7 4 1传值调用 实参的右值传给被调用过程值调用可以如下实现把形参当作所在过程的局部名看待 形参的存储单元在该过程的活动记录中 调用过程计算实参 并把右值放入形参的存储单元中 7 4 2引用调用 实参的左值传给被调用过程引用调用可以如下实现 把实参的左值放入形参的存储单元 在被调用过程的目标代码中 任何对形参的引用都是通过传给该过程的指针来间接引用实参的 7 4 3复制 恢复调用 值调用和引用调用的混合复制 恢复调用可以如下实现 实参的右值和左值同时传给被调用过程 在被调用过程中 像值调用那样使用实参的右值 当控制返回调用过程时 根据传递来的实参的左值 将形参当前的值复写到实参存储单元 7 4 4换名调用 用实参表达式对形参进行正文替换 procedureswap varx y integer vartemp integer begin调用swap i a i temp x temp i x y i a i y tempa i tempend 子程序P X Y Z Y Y 1 Z Z X 传值调用 2 传地址 X T 5 Y Z A 2A A 1 2 1A A T 3 58 换名A A 1 3A A A B 3 3 39 主程序A 2 B 3 P A B A A PrintA 临时单元 T A B 5 符号表管理 符号表的内容编译过程中需要不断地汇集和反复查证出现在源程序中各种名字的属性 特征 值等有关信息 他们通常被记录在一个或几个符号表中 变量类型 种属 长度 地址 形参标识 数组的内情向量过程外部过程 函数及类型 声明处理 形实结合信息 入口地址常数类型 地址 值 符号表管理 组织方式与查填技术 组织方式分类符号表 变量表 过程表 常数表 统一符号表 一般形式 符号表管理 组织方式与查填技术 查填表的主要方式线性表对半查与二叉树Hash法对符号的名字或内码 key 进行简单的算术或逻辑运算后得到入口 要求均匀散列 带嵌套程序 过程 的符号表管理 如果允许过程的嵌套 对符号表有何特殊要求 程序具有如下性质标识符必须先定义后引用遵循最小作用域原则同一程序块 无嵌套 中 标识符不允许重名 带嵌套程序 过程 的符号表管理 对符号表的要求属于哪一个层次的符号表当前处理的层次是什么外层符号表的内容对内层程序的处理有效内层符号表的内容对外层程序的处理无用定义以最内层优先能识别重定义 无定义和重说明 无说明问题 带嵌套程序 过程 的符号表管理 层次划分的标志分程序 begin end过程 过程名后首字符 end循环语句 for end 带嵌套程序 过程 的符号表管理 标识符的基本处理方法 1 当在某一层的说明中识别出一个标识符 id的定义性出现 以此标识符查相应于本层的符号表 If查到then出重复说明错else在符号表中加入新登记项 将标识符及有关信息填入 2 当在语句部分扫视到标识符时 id的应用性出现 首先在该层符号表中查找该id if找不到then到直接外层符号表中去查 如此等等 一旦找到 则在表中取出有关信息并作相应处理If查遍所有外层符号表均未找到该id 则表明该id未经说明 出错 带嵌套程序 过程 的符号表管理 实现 1 分层组织符号表登记项每层符号表的登记项连续地排列在一起 2 建立一个层次表 记录每层的信息扫视嵌套结构的源程序时 总是按先进后出的顺序为使每层符号表登记项连续地排列在一起 设置一个临时工作栈 按先进后出预构造符号表于栈中 造好后移入正式表算法基本步骤自左向右扫描源程序 遇到层开始 在层次表中加一项 记下临时工作栈栈顶遇到id定义 在栈顶添一项 并将层次表本层登记项数加1遇到层结束 将栈中内容正式记录入符号表 记下pointer 过程说明语句的翻译 分析参数的类型 分配地址统计参数和返回值的空间需求与调用语句配合完成形 实参数的结合符号表处理完成过程名的属性登记 说明语句 Procedureid X1 X2 Xn 过程说明语句代码结构 说明语句 Procedureid X1 X2 Xn 代码结构X1 code按参数传递要求实现参数X1的传递 或者完成传递准备 X2 code按参数传递要求实现参数X2的传递 或者完成传递准备 Xn code按参数传递要求实现参数Xn的传递 或者完成传递准备 完成动态存储分配相关的工作 进入过程体 过程调用语句的代码结构 过程调用语句id E1 E2 En 代码结构E1 codea1 E1 place En codean En place动态存储分配相关工作gotopc n 1parama1 paramancallid place n 需要一个队列存放a1 a2 an 以生成 过程调用的实现 1 在过程f中调用过程p时a f对实在参数求值 将结果存入p的活动记录参数域b 在p的活动记录中存放返回地址和当前栈顶指针c 按照活动记录的大小 上移栈顶指针d 控制转到p的入口 过程体 e p存放寄存器值和其它状态信息f 执行过程体2 从过程p返回 对应return语句a p在返回值域中保存返回值b 恢复原栈顶指针和其它寄存器c 按返回地址返回调用者 代码结构E1 codea1 E1 place En codean En place动态存储分配相关工作gotopc n 1parama1 paramancallid place n 过程调用语句的制导翻译定义 产生式语义规则S callid Elist S code Elist code gen goto pc Elist num 1 for队列q中的每一项tdogen param t gen call id place Elist num Elist E Elist num 1 Elist code E code t newtemp gen t E place 建立队列q 并将t放入q Elist Elist1 E Elist num Elist1 num 1 Elist code Elist1 code E code t newtemp gen t E place 将t放入队列q 3 a 6 生成的目标代码t1 3 agotopc 3paramt1param6callf 2 函数调用f 3 a 6 的翻译 函数调用f b c 1 x y x y 的翻译 t1 b ct2 t1 1t3 x ygotopc 5paramt2paramt3paramxparamycallf 4 赋值语句x a b f b c 1 x y x y 的翻译 t1 a bt2 b ct3 t1 1t4 x ygotopc 5 paramt3paramt4paramxparamycallf place 4t5 t1 f valx t5 本章要点 影响存储分配策略的语言特征各种存储分配策略 主要了解静态分配和动态栈式分配活动记录中各种数据域的作用和安排非局部数据访问的实现方法各种参数传递方式及其实现符号表管理 例题1 一个C语言程序及其在X86 Linux操作系统上的编译结果如下 根据所生成的汇编程序来解释程序中四个变量的存储分配 作用域 生存期和置初值方式等方面的区别 staticlongaa 10 shortbb 20 func staticlongcc 30 shortdd 40 例题1 data align4 align4 typecc 2 object typeaa object sizecc 2 4 sizeaa 4 cc 2 aa long30 long10 text globlbb align4 align2 globlfunc typebb object func sizebb 2 bb movw 40 2 ebp value20 例题2 main char cp1 cp2 cp1 12345 cp2 abcdefghij strcpy cp1 cp2 printf cp1 s ncp2 s n cp1 cp2 某些C编译器 如X86LinuxC 的运行结果是 cp1 abcdefghijcp2 ghij为什么cp2所指的串被修改了 例题2 因为常量串 12345 和 abcdefghij 连续分配在常数区执行前 12345 0abcdefghij 0 cp1cp2执行后 abcdefghij 0fghij 0 cp1cp2现在的编译器大都把程序中的串常量单独存放在一个只读的数据段中 例题3 下面的程序运行时输出3个整数 试从运行环境和printf的实现来分析 为什么此程序会有3个整数输出 main printf d d d n 例题4 func i func longi pushl ebp老的基地址指针压栈 movl esp ebp修改基地址指针longj subl 4 esp为j分配空间j i 1 movl8 ebp edx取i到寄存器func j decl edxi 1 movl edx 4 ebp i 1 jmovl 4 ebp eaxpushl eax把实参j的值压栈callfunc函数调用addl 4 esp恢复栈顶指针L1 leave恢复基地址指针 栈顶指针ret返回调用者 例题4 func i func longi pushl ebp老的基地址指针压栈 movl esp ebp修改基地址指针longj subl 4 esp为j分配空间j i 1 movl8 ebp edx取i到寄存器func j decl edxi 1 movl edx 4 ebp i 1 jmovl 4 ebp eaxpushl eax把实参j的值压栈callfunc函数调用addl 4 esp恢复栈顶指针L1 leave恢复基地址指针 栈顶指针ret返回调用者 例题4 func i func longi pushl ebp老的基地址指针压栈 movl esp ebp修改基地址指针longj subl 4 esp为j分配空间j i 1 movl8 ebp edx取i到寄存器func j decl edxi 1 movl edx 4 ebp i 1 jmovl 4 ebp eaxpushl eax把实参j的值压栈callfunc函数调用addl 4 esp恢复栈顶指针L1 leave恢复基地址指针 栈顶指针ret返回调用者 调用序列返回序列 例题5 func i j f e shorti j floatf e shorti1 j1 floatf1 e1 printf Addressofi j f e 36 42 44 54 八进制数 Addressofi1 j1 f1 e1 26 24 20 14 例题5 func i j f e Sizesofshort int long float shorti j floatf e double 2 4 4 4 8 shorti1 j1 floatf1 e1 printf Addressofi j f e 36 42 44 54 八进制数 Addresso