运行时的存储组织和分配.ppt

第7章目标程序运行时的存储组织,存储组织 运行时的分配策略,从逻辑上看，在代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配。一般来讲，假如编译程序从操作系统中得到一块存储区以使目标程序在其上运行，该存储区需容纳生成的目标代码和目标代码运行时的数据空间。,概述,数据空间应包括：用户定义的各种类型的数据对象（变量和常数）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，以及组织输入输出所需的缓冲区。目标代码所占用空间的大小，在编译时能确定，有些数据对象所占用的空间也能在编译时确定，其地址可以编译进目标代码中。但有些数据对象具有可变体积和待编译性质，而无法在编译时确定存储空间的位置。,因此运行时的存储区常常划分成：目标区、静态数据区、栈区和堆区。,1.存储组织,编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定。,所谓数据空间的分配，本质上看，是将程序中的每个名字与一个存储位置关联起来，该存储位置用以容纳名字的值。我们知道，即便有些名字在程序中只声明了一次，但该名字可能对应运行时不同的运行空间位置以容纳每次执行时的值。,因此，源语言的结构特点、源语言数据类型、源语言中决定名字作用域的规则等因素影响存储空间的管理和组织的复杂程序，决定数据空间分配的基本策略。,2.数据空间的使用和管理方法分成三种：,静态存储分配 栈式动态存储分配 堆式动态存储分配 存储分配方案策略 静态存储分配 动态存储分配栈式、堆式,术语,静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。 动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。 可变（动态）数组：若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变（动态）数组。,如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置，那么则称这种分配策略为静态存储分配。,如像FORTRAN这样的语言， 其程序是段结构的，即由主程序段和若干子程序段组成。各程序段中定义的名字一般是彼此独立的（除公共块和等价语句说明的名字以外），也即各段的数据对象名的作用域在各段中，同一个名字在不同的程序段表示不同的存储单元，不会在不同段间互相引用、赋值。,另外它的每个数据名所需的存储空间大小都是常量（即不许含可变体积的数据，如可变数组），且所有数据名的性质是完全确定的。这样，整个程序所需数据空间的总量在编译时完全确定，从而每个数据名的地址就可静态进行分配。,栈式动态存储分配：,这种分配策略是将整个程序的数据空间设计为一个栈。它适用于PASCAL，C，ALGOL之类语言的实现，每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间。,过程所需的数据空间包括两部分，一部分是生存期在本过程这次活动中的数据对象，如局部变量、参数单元、临时变量等等；另一部分则是用以管理过程活动的记录信息，即当一次过程调用出现时，调用该过程的那个过程的活动即被中断，当前机器的状态信息，诸如程序计数器（返地址）、寄存器的值等，也都必须保留在栈中。,当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动重新开始。,堆式动态存储分配:,如果一个程序语言提供用户自由地申请数据空间和退还数据空间的机制（如C+中的new，delete， PASCAL的new，便是这种机制）或者不仅有过程而且有进程的程序结构，即空间的使用未必服从“先申请后释放，后申请先释放”的原则，那么栈式的状态分配方案就不适用了。,这种情况下通常使用一种称为堆式的动态存储分配方案。假设程序运行时有一个大的存储空间，每当需要时就从这片空间中借用一块，不用时再退还。,栈式存储分配的实现,前面提到，使用栈式存储分析策略意味着，运行时每当进入一个过程，就在栈顶为该过程分配所需的数据空间，当一个过程工作完毕返回时，它的栈顶的数据空间也即释放。下面讨论栈式存储分配的实现。,术语过程的活动记录AR（Activation Record）,过程的活动记录是一段连续的存储区，用以存放过程的一次执行所需要的信息为说明方便，假定程序是由过程组成，过程区分为源文本，运行时称作过程的激活。 一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区（块）叫做一个活动记录。,1、临时工作单元，比如计算表达式过程中需存放中间结果用的临时值单元。,2、局部变量，一个过程的局部变量。 3、保存机器状态，容纳该过程执行前关于机器状态的信息，诸如程序计数器 、寄存器的值，这些值都需要在控制从该过程返回时给予恢复。 4、存取链，用以存取非局部变量，这些变量存放于其它过程活动记录中。并不是所有 语言需要该信息。,5、控制链，指向调用该过程的那个过程的活动记录，这也不是所有语言都需要的。,6、实参，也称形式单元，由调用过程向该被调过程提供实参的值（或地址）。当然在实际编译程序中，也常常使用机器寄存器传递实参。 7、返回地址，保存该被调过程返回后的地址。,如果一个程序设计语言允许递归过程，可变数组或可变数据结构，那么，就需要采用动态存储管理技术。,简单的栈式分配方案,一种最简单的程序设计语言结构：没有分程序结构，过程定义不嵌套，但允许过程递归调用。,Program main； 全局变量的说明； proc R； end R； proc Q； end Q； 主程序执行语句 end.（main）,采用栈式动态分配策略，即运行时，每当进入一个过程，则为该过程分配一段存储区，当一个过程工作完毕返回时，它所占用的存储区则可释放。程序运行时的存储空间，（栈）中在某一时刻可能会包含某个过程的几个活动记录（某个过程递归调用的情况）；另外，同样一个存储位置，可能不同运行时刻分配给不同的数据对象。,参数传递,当一个过程调用其它过程时，调用过程和被调过程之间的通信经由非局部量或者经由参数传递。,（1）procedureexchangel（i，j:integer）； （2）varx:integer； （3）begin； （4）x:=ai；ai:=aj；a j:=x （5）end； 带有非局部变量和形参的PASCAL过程，非局变量ai和aj的值进行交换，i，j为形参（在这里是传值）。,语句exchangel（m，n）；表示了对过程exchangel的一次调用，其中m，n为实在参数，简称实参。我们所讨论的问题是，为执行exchangel（m，n），形参i，j应按何种方式同实参m，n相联，换句话说，如何把实在参数传递给相应的形式参数呢？,有几种形实参对应的方法，分别称作值调用，地址（引用）调用，名字调用以及宏扩展。也就是说，参数传递的几种不同途径是传值，传地址，传名及宏扩展等。,在一个赋值语句ai:=aj中，表达式aj表示一个值，而ai表示一个存储位置，用于存放aj的值。通常术语左值（value）指 表达式代表的存储，右值（value）指该 存储位置中含有的值。“左”和“右”来自赋值语句的“左”端和“右”端。参数传递方法的不同主要基于实在参数是表达一个右值，一个左值，还是实在参数本身的文本。,传值：,现在讨论传值的实现。传值，即call-by-value，也称值调用。这是最简单的参数传递方法。即将实参计算出它的值，然后把它传给被调过程。具体来讲是这样的：,1、形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的实参或形式单元。,2、调用过程计算实参的值，并将它们的右值（r-value）放在形式单元开辟的空间中。,传值或值调用的重要特点是对形式参数 的任何运算来不影响调用过程的活动记录中实参的值。,3、被调用过程执行时，就像使用局部变量一样使用这些形式单元。,传地址：,例如：过程swap（var x，y:integer）；swap（a，b）；（a，b为调用时的实参）调用结果a，b的值被改变。 传值（值调用）：特点是对形式参数的任何运算不影响实参的值。 例如：过程swap（x，y:integer）；swap（a，b）；其结果：a，b调用前的值不改变。,传地址的实现,把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参： 1、实在参数是一个名字，或具有左值的表达式传递左值。 2、实在参数是无左值的表达式计算值，放入一存储单元，传此存储单元地址。 3、目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用。,Pragram main（input，output）； Procedure p（x，y，z）； begin y:=y+1； z=z+1； end； begin a:=2；b:=3；p（a+b，a，a）； print a end. 问：a的输出分别为多少 传值2 传地址8,第五章: 编译程序的数据结构和符号表,5.1 分配型数据结构 5.2 查找型数据结构,概述,在编译过程中需要建立并保持一批表格符号表。 从提高编译程序 的工作效率上考虑，有关的数据结构的设计就显得非常重要。 从使用角度上看可以分为：查找型数据结构和分配型数据结构。 查找型数据结构在编译过程中用于构造不同的信息表，保存源程序中不同实体的属性信息。特点是每个实体的项只创建一次，但可以查询多次，所以查询效率很重要。 分配型数据结构主要用于处理嵌套结构的程序。其特点是分配给实体的内存地址对实体用户是可知的。因此不会对其进行查询操作，但分配和回收的速度和内存的使用效率却是十分重要的。,5.2.1 查找型数据结构,(1)什么是符号表? 在编译过程中，编译程序用于记录源程序中各种名字的特性信息， 所以也称为名字特性表。 名字： 程序名、过程名、函数名、用户定义类型、变量名、符号名字。 特性信息：名字种类、类型、维数、参数个数及目标地址（存储单元地址）等。,(2) 建表和查表的必要性 (符号表在编译过程中的作用),源程序中变量要先声明，然后才能引用。 用户通过声明语句，声明各种名字，以及给出它们的类型维数等信息，编译程序在出来这些声明语句时，因将声明中的名字以及信息登录到符号表中，同时编译还要给变量分配存储单元，而存储单元地址也必须登录在符号表中。 当编译程序编译到引用所声明的变量时（赋值或引用其值）要进行语法语义正确性检查 类型是否符合要求和生成相应的目标程序，这就需要查符号表来取得相关信息。,1.语法分析和语义分析 说明语句赋值语句的语法规则 上下文有关分析；是否声明； 类型一致性检查 2. 生成目标代码 LOAD a 的地址 ADD b 的地址 STO x 的地址,例: int x,a,b; L: x:=a+b; ,建表 分配存贮,符号表,数据区,(3) 有关符号表的操作：填表和查表,填表:当分析到程序中的说明或定义语句时应将说明或定义的名字以及与之有关的信息填入符号表中 例：Procedure P() 查表: (1) 填表前查表检查在程序的同一作用域内名字是否重复定义 (2) 检查名字的种类是否与说明一致 (3)对于强类型语言要检查表达式中各变量的类型是否一致 (4) 生成目标指令时要取得所需要的地址,5.2.2 符号表的组织与内容,(1)符号表的结构与内容 符号表的基本结构如下 名字 特性(信息) “名字”域:存放名字。一般为标识符的符号串，也可为指向标识符字符串串指针,“特性”域：可包括多个子域，分别表示标识符的有 关信息。如： 名字（标识符）的种类：变量、函数、过程、数组、标号、参数等 类型：如整型、浮点型、字符型、指针等 性质：变量形参、值形参等 名字：常量名 地址：变量所分配单元的首址或地址位移 大小：所占的字节数,名字 特性(信息),作用域的嵌套层次,对于数组：维数、上下界值、计算下标量地址所用的信息以及数组元素类型等 对于记录（结构、联合）：域的个数、每个域名、地址位移、类型等 对于过程或函数：形参个数、所在层次、函数返回值类型、局部变量所占空间大小等 对于指针：所指对象类型等,(2) 组织方式,1.统一符号表:无论什么名字都填入统一格式的符号表中 符号表表项应按信息量最大的名字设计 填表 查表比较方便 结构简单 但是浪费大量空间 2.对于不同种类的名字分别建立各种符号表 节省空间 但是填表和查表不方便 3.折中办法: 大部分共同信息组成统一格式的符号表。 特殊信息另设附表,两者用指针连接.,例：begin array B1.100end,补充 指针连接,