运行时的存储组织.ppt

1、第八章哈尔滨工业大学软件学院运行时存储组织，重点介绍了符号表的内容和组织、过程调用的实现以及静态存储分配和动态存储分配的基本方法。难点：参数传递、过程描述语句的代码结构、过程调用语句的代码结构、过程调用语句的语法指导定义、堆栈存储分配。2020/7/30，2，第8章，运行时的存储组织，8.1与存储组织相关的源语言概念和功能，8.2存储组织，8.3静态存储分配，8.4堆栈存储分配，8.5对堆栈中非本地数据的访问，8.6堆管理，8.7本章概述，2020/7/30，3，8.1与存储组织相关的源语言概念和功能，编译器必须准确实现源程序中包含的各种抽象概念，如名称、范围、数据类型、运算符、过程、参数这些

2、概念反映了源语言的一些特征，它们的支持经常影响运行时的存储组织和分配策略。给定一个源程序，编译器必须根据源语言的特性(规则)来决定源程序中的许多问题，包括何时以及如何为名字分配内存地址。静态策略：可以在编译时决定的策略；动态策略：在程序执行之前无法决定的策略；2020/7/30，4，8.1.1名称及其绑定，以及“名称”、“变量”和“标识符”之间的区别和联系。名称和变量表示编译时的名称以及运行时由名称表示的内存位置。标识符是指示数据对象、过程、类或对象的条目的字符串。所有标识符都是名称，但不是所有的名称都是标识符。名字也可以是表达。例如，名称x.y可以表示由x表示的结构的域y。同一个标识符可以声

3、明多次，但是每次声明都会引入一个新的变量。即使每个标识符只声明一次，递归进程本地的标识符将在不同的运行时指向不同的内存位置。2020/7/30，5，名称绑定，从名称到值的两步映射环境将名称映射到左值，而状态将左值映射到右值。分配改变状态，但不改变环境。如果环境将名字X映射到存储单元S，我们说X绑定到由S声明的范围，名字，存储位置(变量)，状态，值，环境，2020/7/30，6，8.1.2，并且由X声明的范围是程序中的这样一个区域，其中X的所有引用都指向X的这个声明。对于某个编程语言，如果一个声明的范围只能通过检查其程序来确定，则说该语言使用静态范围；否则，据说语言使用动态范围。C、Java和C

4、#还通过使用公共、私有和受保护等关键字来提供对范围的显式控制。声明的范围通过符号表进行管理，详见第8.4节。2020/7/30，7，1。静态范围。在具有块结构的语言中，变量声明的静态范围规则如下：如果名字X的声明D属于块B，那么D的范围就是B的所有语句，除了块B满足以下条件：B嵌套在B中(它可以嵌套在任何深度)，B有一个新的同名声明X.假设B1、B2、Bk是围绕X的所有参考块，Bk-1是Bk的直接外块，Bk-2是Bk-1的直接外块，依此类推。找到最大的一个属于毕的“我”，那么这个“我”指的就是毕的这个说法。换句话说，对X的这种引用在毕的这种声明的范围之内。2020/7/30，8，1。静态范围，

5、表8.1图8.10所示程序中声明的范围，2020/7/30，9，2。显式访问控制、类和结构为其成员引入了新的范围。如果P是具有域(成员)X的类的对象，那么P.X。类似于块结构，类D中成员X的声明范围将扩展到D的任何子类D，除非D具有与X同名的局部声明，2020/7/30，10，2。显式访问控制。通过使用诸如公共、私有和受保护等关键字，面向对象的C语言或Java类提供了对超类中成员名称的显式访问控制。这些关键字通过限制访问来支持封装。因此，私有名称的范围只包含与类及其友元相关联的方法声明和定义，保护名称只对其子类可访问，公共名称也可从类外访问。2020/7/30，11，3。动态范围、相对于时间的

6、动态范围规则和相对于空间静态范围规则的静态范围规则要求我们找出引用所指向的声明，前提是声明位于引用周围的“空间最近”单元(程序块)中。动态范围还要求我们找出引用所指向的声明，但前提是声明位于引用周围的“最近时间”单位(流程活动)。2020/7/30，12，3。动态范围，“动态范围”通常指以下策略名称X的引用，该引用指向最近调用的带有X声明的进程中的X声明。例如，当流程作为参数传递时，2020/7/30，13，8.1.3流程及其活动(将“流程、函数和方法”称为“流程”)是一个声明，其最简单的形式是将标识符与语句相关联。这个标识符是过程名，这个语句是过程体。当一个过程名出现在可执行语句中时，相应的

7、过程将在该点被调用。过程调用是执行被调用过程的过程体。请注意，过程调用也可以出现在表达式中。2020/7/30，14，8.1.3流程及其活动。过程定义中出现的一些标识符具有特殊的含义，它们被称为过程的形式参数，简称为形式参数。调用过程时，表达式作为实参数(或实参)传递给被调用的过程，以替换过程体中出现的相应形式参数。第8.1.4节将讨论实际参数和形式参数的组合方法。流程主体的每次执行都被称为流程的一个活动。进程p的活动的生命周期是从进程体执行的第一步到最后一步，包括执行由p调用的进程的时间，以及由这样的进程调用其他进程所花费的时间，等等。2020/7/30，15，8.1.3流程及其活动。如果A

8、和B是进程的活动，它们的生命周期不是重叠就是嵌套。也就是说，如果b在a结束之前开始，那么b必须在a结束之前结束。如果同一个流程的新活动可以在前一个活动结束之前开始，则称该流程是递归的。递归过程p也可以间接调用自己。如果一个过程是递归的，它的几个活动可能在某个时刻同时活动，所以这些活动的存储空间必须合理地组织。2020/7/30，16，8.1.4。当一个过程调用另一个过程时，它们之间交换信息的方法通常通过被调用过程的非本地名称和参数来实现。逐值逐地址逐值逐名称传递。主要区别在于参数是代表左值还是右值，还是文本本身。2020/7/30，17，1。传递值、计算参数以及将其正确值传递给被调用过程的方式

9、可以实现如下：被调用过程为每个形式参数打开一个称为形式单元的存储单元，以存储相应参数的值。调用过程计算实际参数，并将正确的值放入相应的形式单元。，由调用者和被调用者直接使用，a，实际参数a，形式参数x，a的值，单向值传递，2020/7/30，18，2。地址传递，调用进程将实际参数的地址传递给被调用进程。地址传递的方式可以实现如下：如果实际参数是带有左值的名称或表达式，那么如果实际参数是b，则左值本身被传递。然后调用进程首先计算实际参数的值并将其存储在新的存储单元中，然后将该新单元的地址发送给被调用进程、用于地址访问的调用方和被调用方，a、实际参数a、形式参数x、a、2020/7/30、19、3

10、的地址。在被调用的过程中，参数的正确值被用作传递值的方式。当控制返回到调用过程时，根据传递的参数的左值，将参数的当前值复制到参数存储单元。调用者，被调用者，a，实际参数a，形式参数x，a的值，值/地址，a的地址，2020/7/30，20，4。传递名称，并用实际参数表达式对形式参数进行文字替换。名称传递的方法可以实现如下：在调用过程中，设置一个形实转换子程序来计算参数的左值或右值。被调用的进程为每个参数打开一个存储单元，用于存储参数的转换子例程的入口地址。当传输的进程被执行时，每当一个参数被赋值或取用时，对应于该参数的形式-实转换子程序被调用以获得该参数的相应地址或值。注意，转换子程序的运行环境

11、是调用程序。形式到现实的转换子程序也称为重命名子程序thunk。2020/7/30，21，例如，程序交换(var x，y:整数)；var temp:整数；开始呼叫交换(I，ai)温度：=x；温度：=i。x :=y；i :=ai:=温度：=温度结束，2020/7/30，22，子程序P(X，Y，Z)；Y :=Y 1；Z:=Z X，传输值：2，传输地址：X=T=5，Y=Z=A=2 A :=A 1=21 A :=A T=358，传输名称A :=A 1=3 A 3360=A AB=3339 b :=3；(甲乙丙丁)；打印A，临时单元： T:A B=5，2020/7/30，23，编译器组织存储空间时必须考

12、虑的问题，该过程可以递归吗？当控制从流程活动中返回时，您是否希望保留局部变量的值？一个过程可以访问非局部变量吗？如何传递过程调用的参数？过程可以作为参数传递吗？过程可以作为结果值传递吗？内存块可以在程序控制下动态分配吗？内存块必须被显式释放吗？2020/7/30，24，8.2存储组织，8.2.1运行时内存分区8.2.2活动记录8.2.3本地数据组织8.2.4全局存储分配策略，2020/7/30，25，7.2.1运行时内存分区和目标流程的每个活动所需的信息由一个连续的存储区域管理，该区域称为活动记录。假设语言特性：允许过程的递归调用，允许过程的变量数组，并且允许/不允许过程定义的嵌套。活动记录采

13、用堆栈式存储分配机制：在运行时，每次进入一个进程，相应的活动记录就被推到堆栈的顶部。活动记录通常包含连接数据、正式单元、局部变量、局部数组的内部向量、临时工作单元等等。8.2.2活动记录，2020年7月30日，对任何局部变量X的引用可以表示为索引访问：DXSP DX3360变量X相对于活动记录起始点的地址，该地址可以在编译时确定。参数号，返回地址，形式单元，临时变量，数组上下文向量，简单变量，SP 0，1，2，旧SP，TOP，每个进程的活动记录内容不是嵌套语言(如C)，2020/7/30，28，连接数据返回地址动态链：调用进程前指向最新活动记录地址的指针。静态链：指向静态直接外层中最新活动记录

14、地址的指针，用于访问非本地数据。，静态链，动态链，形式单元，临时变量，数组上下文向量，局部变量，SP0，1，2，返回地址，TOP，活动记录内容每个进程的嵌套语言(如Pascal)，2020年7月30日，29，形式单元：对应实参数的地址或值。局部数据区：局部变量、内部信息向量和临时工作单元(如存储表达式的评估结果)。静态链，动态链，形式单元，临时变量，数组内部向量，局部变量，SP 0，1，2，返回地址，TOP，每个进程的活动记录内容，组织局部数据2020年7月30日，8.2.3，字节是可寻址内存的最小单元。变量所需的存储空间可以根据其类型静态确定。由进程声明的局部变量在局部数据字段中按照声明时出

15、现的顺序分配空间。本地数据的地址可以用相对于某个位置的地址来表示。数据对象的存储安排也有对齐的问题。整数必须放在内存中的特定位置，例如可被2、4和8整除的地址，以及2020/7/30、31和8.2.3中的本地数据组织。在SPARC/Solaris工作站上，以下两种结构的大小分别为24和16。它们为什么不同？typedef struct _ atypedef struct _ b char C1；char c1长I；char c2charc2长I；双倍f。双倍f。a .b .2020/7/30，32，8.2.3本地数据的组织。在SPARC/Solaris工作站上，以下两种结构的大小分别为24和1

16、6。它们为什么不同？typedef struct _ atypedef struct _ b char C1；0 char c10长I；4 char c21 charc28长I；4双f；16双f；8a；b .2020/7/30，33，8.2.3本地数据的组织，X86/Linux机器上的结果不同于SPARC/Solaris工作站，它们是20和16。typedef struct _ atypedef struct _ b char C1；0 char c10长I；4 char c21 charc28长I；4双f；12双f；8a；b .2020/7/30，34，静态存储分配策略(FORTRAN)如果可以在编译时确定数据空间的大小，则可以采用静态分配方法：在编译时运行时确定每个数据项在存储空间中的位置。动态存储分配策略(PASCAL)如果运行时的数据空间大小不能在编译时确定，则必须采用动态分配方法。允许递归过程和动态应用以及内存释放。堆栈动态存储分配堆栈动态存储分配，8.2.4全局存储分配策略，以及2020/7/30、35和8.3静态存储分配策略。如果您可以确定程序运行时所需的存储空间大小，那么您可以在目标程序运行时安排其所有数据空间