栈式存储分配课件.ppt

1、2023-1-21第第9章章 运行时的存储组织运行时的存储组织 9.1 与存储组织有关的源语言概念与特征与存储组织有关的源语言概念与特征9.2 存储组织存储组织9.3 静态存储分配静态存储分配9.4 栈式存储分配栈式存储分配9.5 栈中非局部数据的访问栈中非局部数据的访问9.6 堆管理堆管理9.7 本章小结本章小结2023-1-229.1 与存储组织有关的源语言概念与特征与存储组织有关的源语言概念与特征n编译程序必须准确地实现包含在源程序中的编译程序必须准确地实现包含在源程序中的各种抽象概念，如各种抽象概念，如名字名字、作用域作用域、数据类型数据类型、操作符操作符、过程过程、参数参数和和控制流

2、结构控制流结构等，这些等，这些概念反映了源语言所具有的一些特征，对它概念反映了源语言所具有的一些特征，对它们的支持往往会影响运行时的存储组织和分们的支持往往会影响运行时的存储组织和分配策略配策略 n给定一个源程序，编译程序必须根据源语言给定一个源程序，编译程序必须根据源语言的特征的特征(规定规定)为源程序中的许多问题做出决策，为源程序中的许多问题做出决策，包括何时、怎样为名字分配内存地址。包括何时、怎样为名字分配内存地址。n静态策略静态策略：在编译时即可做出决定的策略：在编译时即可做出决定的策略n动态策略动态策略：直到程序执行时才能做出决定的策略：直到程序执行时才能做出决定的策略2023-1-

3、239.1.1 名字及其绑定名字及其绑定 n“名字名字”、“变量变量”和和“标识符标识符”的区别与联的区别与联系系n名字和变量分别表示编译时的名字和运行时该名名字和变量分别表示编译时的名字和运行时该名字所代表的内存位置。字所代表的内存位置。n标识符则是一个字符串，用于指示数据对象、过标识符则是一个字符串，用于指示数据对象、过程、类或对象的入口。程、类或对象的入口。n所有标识符都是名字，但并不是所有的名字都是所有标识符都是名字，但并不是所有的名字都是标识符，名字还可以是表达式。例如，名字标识符，名字还可以是表达式。例如，名字x.y可可能表示能表示x所代表结构的域所代表结构的域y。n同一标识符可以

4、被声明多次，但每个声明都引入同一标识符可以被声明多次，但每个声明都引入一个新的变量。即使每个标识符只被声明一次，一个新的变量。即使每个标识符只被声明一次，局部于某个递归过程的标识符在不同的运行时刻局部于某个递归过程的标识符在不同的运行时刻也将指向不同的内存位置。也将指向不同的内存位置。2023-1-24名字的绑名字的绑定定n从名字到值的两步映射从名字到值的两步映射n环境把名字映射到左值，而状态把左值映射到右值环境把名字映射到左值，而状态把左值映射到右值n赋值改变状态，但不改变环境。赋值改变状态，但不改变环境。n如果环境将名字如果环境将名字x映射到存储单元映射到存储单元s，我们就说，我们就说x被

5、被绑定绑定到到s名字名字内存位置内存位置(变量变量)状态状态值值环境环境2023-1-259.1.2 声明的作用域声明的作用域nx的声明的作用域是程序中的这样一段区域，在该区的声明的作用域是程序中的这样一段区域，在该区域中，域中，x的引用均指向的引用均指向x的这一声明。对于某种程序的这一声明。对于某种程序设计语言，如果只通过考察其程序就可以确定某个设计语言，如果只通过考察其程序就可以确定某个声明的作用域，则称该语言使用声明的作用域，则称该语言使用静态作用域静态作用域；否则；否则称该语言使用称该语言使用动态作用域动态作用域。nC+、Java和和C#等还提供了对等还提供了对作用域的显式控制作用域的

6、显式控制，其方法是使用其方法是使用public、private和和protected这样的关这样的关键字。键字。n声明的作用域是通过符号表进行管理的，详见声明的作用域是通过符号表进行管理的，详见8.4节节的讨论。的讨论。2023-1-261.静态作用域静态作用域n在具有程序块结构的语言中，变量声明的静在具有程序块结构的语言中，变量声明的静态作用域规则如下态作用域规则如下：n如果名字如果名字x的声明的声明D属于程序块属于程序块B，则，则D的作用域的作用域是是B的所有语句，只有满足如下条件的程序块的所有语句，只有满足如下条件的程序块B除外：除外：B嵌套在嵌套在B中中(可以是任意的嵌套深度可以是任意

7、的嵌套深度)，且且B中具有同一名字中具有同一名字x的一个新的声明。的一个新的声明。n令令B1,B2,Bk是包围是包围x的本次引用的所有程序块，的本次引用的所有程序块，Bk-1是是Bk的直接外层程序块，的直接外层程序块，Bk-2是是Bk-1的直接外层的直接外层程序块，如此类推。找到使程序块，如此类推。找到使x的某个声明属于的某个声明属于Bi的的最大最大i，则，则x的本次引用指向的本次引用指向Bi中的这个声明。换中的这个声明。换句话说，句话说，x的本次引用处在的本次引用处在Bi中的这个声明的作用中的这个声明的作用域中。域中。2023-1-271.静态作用域静态作用域表表9.1 图图8.10所示程序

8、中声明的作用域所示程序中声明的作用域2023-1-282.显式访问控制显式访问控制 n类和结构为其成员引入了一种新的作用域类和结构为其成员引入了一种新的作用域n如果如果p是某个带有域是某个带有域(成员成员)x的类的对象，则的类的对象，则p.x中中x的引用将指向该类定义中的域的引用将指向该类定义中的域x。与程序块结构类。与程序块结构类似的是，类似的是，类D中成员中成员x的声明的作用域将会扩展到的声明的作用域将会扩展到D的任何子类的任何子类D，除非，除非D中具有同一名字中具有同一名字x的一个局的一个局部声明。部声明。2023-1-292.显式访问控制显式访问控制 n通过使用像通过使用像public

9、、private和和protected这样的关键这样的关键字，字，C+或或Java类的面向对象语言提供了一种对超类的面向对象语言提供了一种对超类中成员名字的显式访问控制。这些关键字通过限类中成员名字的显式访问控制。这些关键字通过限制访问来支持封装。因此，私有名的作用域只包含制访问来支持封装。因此，私有名的作用域只包含与该类及其友类相关联的方法声明和定义，保护名与该类及其友类相关联的方法声明和定义，保护名只对其子类是可访问的，而公用名从类的外部也是只对其子类是可访问的，而公用名从类的外部也是可以访问的。可以访问的。2023-1-2103.动态作用域动态作用域 n动态作用域规则相对于时间而静态作用

10、域规动态作用域规则相对于时间而静态作用域规则相对于空间则相对于空间n静态作用域规则要求我们找出某个引用所指向的静态作用域规则要求我们找出某个引用所指向的声明，条件是该声明处在包围该引用的声明，条件是该声明处在包围该引用的“空间上空间上最近的最近的”单元单元(程序块程序块)中。中。n动态作用域也是要求我们找出某个引用所指向的动态作用域也是要求我们找出某个引用所指向的声明，但条件是该声明处在包围该引用的声明，但条件是该声明处在包围该引用的“时间时间上最近的上最近的”单元单元(过程活动过程活动)中。中。2023-1-2113.动态作用域动态作用域 n“动态作用域动态作用域”通常是指下面的策略通常是指

11、下面的策略n名字名字x的引用指向带有的引用指向带有x声明的最近被调用的过程声明的最近被调用的过程中中x的这个声明。的这个声明。n例如，过程被当做参数进行传递时例如，过程被当做参数进行传递时 2023-1-2129.1.3 过程及其活动过程及其活动 n将将“过程、函数和方法过程、函数和方法”统称为统称为“过程过程”n过程定义过程定义是一个声明，它的最简单形式是把是一个声明，它的最简单形式是把一个标识符和一个语句联系起来。该标识符一个标识符和一个语句联系起来。该标识符是是过程名过程名，而这个语句是，而这个语句是过程体过程体。n当过程名出现在可执行语句中时，称相应的当过程名出现在可执行语句中时，称相

12、应的过程在该点被调用。过程在该点被调用。过程调用过程调用就是执行被调就是执行被调用过程的过程体。注意，过程调用也可以出用过程的过程体。注意，过程调用也可以出现在表达式中。现在表达式中。2023-1-2139.1.3 过程及其活动过程及其活动 n出现在过程定义中的某些标识符具有特殊的出现在过程定义中的某些标识符具有特殊的意义，称为该过程的形式参数，简称为意义，称为该过程的形式参数，简称为形参形参。调用过程时，表达式作为实在参数调用过程时，表达式作为实在参数(或或实参实参)传传递给被调用的过程，以替换出现在过程体中递给被调用的过程，以替换出现在过程体中的对应形式参数。的对应形式参数。9.1.4节将

13、讨论实参和形参节将讨论实参和形参的结合方法。的结合方法。n过程体的每次执行叫做该过程的一个过程体的每次执行叫做该过程的一个活动活动。过程过程p的一个活动的生存期是从过程体执行的的一个活动的生存期是从过程体执行的第一步到最后一步，包括执行被第一步到最后一步，包括执行被p调用的过程调用的过程的时间，以及再由这样的过程调用其它过程的时间，以及再由这样的过程调用其它过程所花的时间，等等。所花的时间，等等。2023-1-2149.1.3 过程及其活动过程及其活动 n如果如果a和和b是过程的活动，那么它们的生存期是过程的活动，那么它们的生存期或者不交迭，或者嵌套。也就是说，如果在或者不交迭，或者嵌套。也就

14、是说，如果在a结束之前结束之前b就开始了，那么就开始了，那么b必须在必须在a结束之前结束之前结束。结束。n如果同一个过程的一次新的活动可以在前一如果同一个过程的一次新的活动可以在前一次活动结束前开始，则称这样的过程是次活动结束前开始，则称这样的过程是递归递归的的。递归过程。递归过程p也可以间接地调用自己。也可以间接地调用自己。n如果某个过程是递归的，则在某一时刻可能如果某个过程是递归的，则在某一时刻可能有它的几个活动同时活跃，这时必须合理组有它的几个活动同时活跃，这时必须合理组织这些同时活跃着的活动的内存空间。织这些同时活跃着的活动的内存空间。2023-1-2159.1.4 参数传递方式参数传

15、递方式 n当一个过程调用另一个过程时，它们之间交当一个过程调用另一个过程时，它们之间交换信息的方法通常是通过非局部名字和被调换信息的方法通常是通过非局部名字和被调用过程的参数来实现的。用过程的参数来实现的。n传值传值n传地址传地址n传值结果传值结果n传名传名n其主要区别在于实参所代表的究竟是左值、其主要区别在于实参所代表的究竟是左值、右值还是实参的正文本身右值还是实参的正文本身 2023-1-2161.传值传值n计算实参并将其右值传递给被调用过程计算实参并将其右值传递给被调用过程 n传值方式可以如下实现：传值方式可以如下实现：n被调用过程为每个形参开辟一个称为形式单元的被调用过程为每个形参开辟

16、一个称为形式单元的存储单元，用于存放相应实参的值。存储单元，用于存放相应实参的值。n调用过程计算实参，并把右值放入相应的形式单调用过程计算实参，并把右值放入相应的形式单元中。元中。调用者调用者被调用者被调用者直接使用直接使用A实际参数实际参数A形式参数形式参数XA的值的值单向传值单向传值2023-1-2172.传地址传地址n调用过程将实参的地址传递给被调用过程调用过程将实参的地址传递给被调用过程 n传地址方式可以如下实现：传地址方式可以如下实现：n如果实参是一个具有左值的名字或表达式，则传递如果实参是一个具有左值的名字或表达式，则传递该左值本身该左值本身 n如果实参是如果实参是a+b或或2这样

17、的没有左值的表达式，则调这样的没有左值的表达式，则调用过程首先计算实参的值并将其存入一个新的存储用过程首先计算实参的值并将其存入一个新的存储单元，然后将这个新单元的地址传递给被调用过程单元，然后将这个新单元的地址传递给被调用过程 调用者调用者被调用者间址访问被调用者间址访问A实际参数实际参数A形式参数形式参数XA的地址的地址传地址传地址2023-1-2183.传值结果传值结果n传值结果就是将传值和传地址这两种方式结合起来传值结果就是将传值和传地址这两种方式结合起来n传值结果方式可以如下实现：传值结果方式可以如下实现：n实参的右值和左值同时传给被调用过程。实参的右值和左值同时传给被调用过程。n在

18、被调用过程中，像传值方式那样使用实参的右值。在被调用过程中，像传值方式那样使用实参的右值。n当控制返回调用过程时，根据传递来的实参的左值，当控制返回调用过程时，根据传递来的实参的左值，将形参当前的值复制到实参存储单元。将形参当前的值复制到实参存储单元。调用者调用者被调用者被调用者A实际参数实际参数A形式参数形式参数XA的值的值传值传值/传地址传地址A的地址的地址2023-1-2194.传名传名n用实参表达式对形参进行文字替换。用实参表达式对形参进行文字替换。n传名方式可以如下实现：传名方式可以如下实现：n在调用过程中设置计算实参左值或右值的形实转在调用过程中设置计算实参左值或右值的形实转换子程

19、序。换子程序。n被调用过程为每个形参开辟一个存储单元，用于被调用过程为每个形参开辟一个存储单元，用于存放该实参的形实转换子程序的入口地址。被调存放该实参的形实转换子程序的入口地址。被调过程执行时，每当要向形参赋值或取该形参的值过程执行时，每当要向形参赋值或取该形参的值时，就调用相应于该形参的形实转换子程序，以时，就调用相应于该形参的形实转换子程序，以获得相应的实参地址或值。注意，形实转换子程获得相应的实参地址或值。注意，形实转换子程序的运行环境是调用程序。形实转换子程序又称序的运行环境是调用程序。形实转换子程序又称为换名子程序为换名子程序thunk。2023-1-220例例procedure

20、swap(var x,y:integer);var temp:integer;begin 调用调用swap(i,ai)temp:=x;temp:=i;x:=y;i:=ai;y:=tempai:=temp end2023-1-221子程序子程序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传值结果：传值结果：X=T=5,Y=Z=A=2Y:=Y+1=3Z:=Z+X=5+2=7Y A=3Z A=77传名传名A:=A+1=3A:=A+A+B=3+3+39主程序主程序A:=2;B:=3;P(A+B,A,A);

21、print A临时单元临时单元:T:A+B=52023-1-222编译程序组织存储空间时必须考虑的问编译程序组织存储空间时必须考虑的问题题n过程能否递归？过程能否递归？n当控制从过程的活动返回时，局部变量的值是否要当控制从过程的活动返回时，局部变量的值是否要保留？保留？n过程能否访问非局部变量？过程能否访问非局部变量？n过程调用的参数传递方式？过程调用的参数传递方式？n过程能否作为参数被传递？过程能否作为参数被传递？n过程能否作为结果值传递？过程能否作为结果值传递？n存储块能否在程序控制下动态地分配？存储块能否在程序控制下动态地分配？n存储块是否必须显式地释放？存储块是否必须显式地释放？202

22、3-1-2239.2 存储组织存储组织n9.2.1 运行时内存的划分运行时内存的划分n9.2.2 活动记录活动记录n9.2.3 局部数据的组织局部数据的组织n9.2.4 全局存储分配策略全局存储分配策略2023-1-2249.2.1 运行时内存的划分运行时内存的划分目标代码目标代码静态数据静态数据栈栈堆堆空闲空闲 空间空间2023-1-225n过程的每个活动所需要的信息用一块连续的存储过程的每个活动所需要的信息用一块连续的存储区来管理，这块存储区叫做区来管理，这块存储区叫做活动记录活动记录 n假定语言的特点为假定语言的特点为:允许过程递归调用、允许过程允许过程递归调用、允许过程含有可变数组，含

23、有可变数组，过程定义过程定义允许允许/不允许嵌套。不允许嵌套。n采用栈式存储分配机制采用栈式存储分配机制n活动记录：运行时，每当进入一个过程就有一个活动记录：运行时，每当进入一个过程就有一个相应的活动记录相应的活动记录压入压入栈顶栈顶。活动活动记录记录一般含有连一般含有连接数据接数据、形式单元、局部变量、局部数组的内情形式单元、局部变量、局部数组的内情向量和临时工作单元等向量和临时工作单元等。9.2.2 活动记录活动记录2023-1-226对任何局部变量对任何局部变量X的引的引用可表示为变址访问用可表示为变址访问:dxSPdx:变量变量X相对于活动记相对于活动记录起点的地址，在编译录起点的地址

24、，在编译时可确定。时可确定。参数个数参数个数返回地址返回地址形式单元形式单元临时变量临时变量数组内情向量数组内情向量简单变量简单变量SP 012旧旧SPTOP 每个过程的活动记录内容每个过程的活动记录内容 非嵌套语言非嵌套语言(如如C)2023-1-227l 连接数据连接数据l 返回地址返回地址l 动态链：指向调用该动态链：指向调用该过程前的最新活动记过程前的最新活动记录地址的指针。录地址的指针。l 静态链：指向静态直接静态链：指向静态直接外层最新活动记录地址的外层最新活动记录地址的指针，用来访问非局部数指针，用来访问非局部数据。据。静态链静态链动态链动态链形式单元形式单元临时变量临时变量数组

25、内情向量数组内情向量局部变量局部变量SP012返回地址返回地址TOP 每个过程的活动记录内容每个过程的活动记录内容 嵌套语言嵌套语言(如如Pascal)2023-1-228l形式单元：存放相形式单元：存放相应的实在参数的地应的实在参数的地址或值。址或值。l局部数据区：局部局部数据区：局部变量、内情向量、变量、内情向量、临时工作单元临时工作单元(如存如存放对表达式求值的放对表达式求值的结果结果)。静态链静态链动态链动态链形式单元形式单元临时变量临时变量数组内情向量数组内情向量局部变量局部变量SP 012返回地址返回地址TOP 每个过程的活动记录内容每个过程的活动记录内容2023-1-2299.2

26、.3 局部数据的组织局部数据的组织n字节是可编址内存的最小单位。字节是可编址内存的最小单位。n变量所需的存储空间可以根据其类型而静态确定。变量所需的存储空间可以根据其类型而静态确定。n一个过程所声明的局部变量，按这些变量声明时出一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间。现的次序，在局部数据域中依次分配空间。n局部数据的地址可以用相对于某个位置的地址来表局部数据的地址可以用相对于某个位置的地址来表示。示。n数据对象的存储安排还有对齐的问题。数据对象的存储安排还有对齐的问题。n整数必须放在内存中特定的位置，如被整数必须放在内存中特定的位置，如被2、4、8整除

27、整除的地址的地址2023-1-2309.2.3 局部数据的组织局部数据的组织在在SPARC/Solaris工作站上下面两个结构的工作站上下面两个结构的size分别是分别是24和和16，为什么不一样？，为什么不一样？typedef struct _atypedef struct _bchar c1;char c1;long i;char c2;char c2;long i;double f;double f;a;b;2023-1-2319.2.3 局部数据的组织局部数据的组织在在SPARC/Solaris工作站上下面两个结构的工作站上下面两个结构的size分别是分别是24和和16，为什么不一样？

28、，为什么不一样？typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2;1char c2;8 long i;4double f;16 double f;8a;b;2023-1-2329.2.3 局部数据的组织局部数据的组织在在X86/Linux机器的结果和机器的结果和SPARC/Solaris工作工作站不一样，是站不一样，是20和和16。typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2;1char c2;8 long i;

29、4double f;12 double f;8a;b;2023-1-233n静态存储分配策略静态存储分配策略(FORTRAN)如果在编译时能确定数据空间的大小，则可采用如果在编译时能确定数据空间的大小，则可采用静态分配方法：在编译时刻为每个数据项目确定静态分配方法：在编译时刻为每个数据项目确定出在运行时刻的存储空间中的位置。出在运行时刻的存储空间中的位置。n动态存储分配策略动态存储分配策略(PASCAL)如果在编译时不能确定运行时数据空间的大小，如果在编译时不能确定运行时数据空间的大小，则必须采用动态分配方法。允许递归过程及动态则必须采用动态分配方法。允许递归过程及动态申请、释放内存。申请、释

30、放内存。n栈式动态存储分配栈式动态存储分配n堆式动态存储分配堆式动态存储分配9.2.4 全局存储分配策略全局存储分配策略 2023-1-2349.3 静态存储分配策略静态存储分配策略n如果在编译时就能确定一个程序在运行时所需如果在编译时就能确定一个程序在运行时所需要的存储空间的大小，则在编译时就能安排好要的存储空间的大小，则在编译时就能安排好目标程序运行时的全部数据空间，并能确定每目标程序运行时的全部数据空间，并能确定每个数据项的地址，存储空间的这种分配方法称个数据项的地址，存储空间的这种分配方法称为静态存储分配。必须满足如下条件：为静态存储分配。必须满足如下条件：n数据对象的长度和它在内存中

31、的位置在编译时必须数据对象的长度和它在内存中的位置在编译时必须是已知的；是已知的；n不允许过程的递归调用，因为一个过程的所有活动不允许过程的递归调用，因为一个过程的所有活动都是用同样的局部名字绑定的；都是用同样的局部名字绑定的；n数据结构不能动态建立，因为没有运行时的存储分数据结构不能动态建立，因为没有运行时的存储分配机制。配机制。2023-1-235某分段式程序运行时的内存划分某分段式程序运行时的内存划分2023-1-236n每个数据区有一个编号，地址分配时，在符号表每个数据区有一个编号，地址分配时，在符号表中，对每个数据名登记其所属数据区编号及在该中，对每个数据名登记其所属数据区编号及在该

32、区中的相对位置。区中的相对位置。n考虑子程序段：考虑子程序段：SUBROUTINE SWAP(A,B)T=AA=BB=TRETURNEND寄存器保护区寄存器保护区返回地址返回地址ATB01a2023-1-237静态存储分配策略静态存储分配策略n顺序分配算法（基于调用图）顺序分配算法（基于调用图）n按照程序段出现的先后顺序逐段分配按照程序段出现的先后顺序逐段分配1/222/153/184/176/105/23程序段程序段 区域区域1 0212 22363 37544 55715 72946 95104共需要共需要105个存储单元个存储单元程序段号程序段号/所需数据空间所需数据空间能用更少的空间么

33、？能用更少的空间么？2023-1-238分层分配算法分层分配算法n允许程序段之间的覆盖（覆盖可能性分析）允许程序段之间的覆盖（覆盖可能性分析）程序段程序段 区域区域6095022 4016323402173114162共需要共需要63个存储单元个存储单元1/222/153/184/176/105/23思考：如何设计分配算法？思考：如何设计分配算法？2023-1-2399.4 栈式存储分配策略栈式存储分配策略n如果过程允许递归如果过程允许递归n某一时刻过程某一时刻过程A可能已被自己调用了若干次，但只可能已被自己调用了若干次，但只有最近一次处于执行状态。其余各次等待返回被中有最近一次处于执行状态。

34、其余各次等待返回被中断的那次调用断的那次调用n必须保存每次调用相应的数据区内容（活动记录）必须保存每次调用相应的数据区内容（活动记录）n引入一个运行栈引入一个运行栈n让过程的每次执行和过程的活动记录相对应。让过程的每次执行和过程的活动记录相对应。n每调用一次过程，就把该过程的活动记录压入栈中，每调用一次过程，就把该过程的活动记录压入栈中，返回时弹出。返回时弹出。n假设寄存器假设寄存器top标记栈顶，局部名字标记栈顶，局部名字x的相对地址为的相对地址为dx，则，则x的地址为的地址为top+dx 或或 dxtop2023-1-2409.4.1 调用序列和返回序列调用序列和返回序列 n过程调用和过程

35、返回都需要执行一些代码来过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等n过程调用和返回是通过在目标代码中生成调过程调用和返回是通过在目标代码中生成调用序列和返回序列来实现的用序列和返回序列来实现的 n调用序列负责分配活动记录，并将相关信息填入调用序列负责分配活动记录，并将相关信息填入活动记录中活动记录中 n返回序列负责恢复机器状态，使调用过程能够继返回序列负责恢复机器状态，使调用过程能够继续执行续执行 n调用序列和返回序列常常都分成两部分，分调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中处于调用过程和被调用过程中

36、2023-1-2419.4.1 调用序列和返回序列调用序列和返回序列n即使是同一种语言，过程调用序列、返回序列和活即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异动记录中各域的排放次序，也会因实现而异n设计这些序列和活动记录的一些原则：设计这些序列和活动记录的一些原则：n以活动记录中间的某个位置作为基地址；以活动记录中间的某个位置作为基地址；n长度能较早确定的域放在活动记录的中间；长度能较早确定的域放在活动记录的中间；n一般把临时数据域放在局部数据域的后面，以便其一般把临时数据域放在局部数据域的后面，以便其长度的改变不会影响数据对象相对于中间那些域的长度的改变

37、不会影响数据对象相对于中间那些域的位置；位置；n用同样的代码来执行各个活动的状态保存和恢复；用同样的代码来执行各个活动的状态保存和恢复；n把参数域和可能有的返回值域放在紧靠调用者活动把参数域和可能有的返回值域放在紧靠调用者活动记录的地方。记录的地方。2023-1-2429.4.1 调用序列和返回序列调用序列和返回序列调用者和被调用者之间的任务划分调用者和被调用者之间的任务划分2023-1-2439.4.1 调用序列和返回序列调用序列和返回序列一种可能的调用序列：一种可能的调用序列：n调用者计算实参调用者计算实参n调用者把返回地址和调用者把返回地址和sp的旧值存入被调用者的旧值存入被调用者的活动

38、记录中，然后将的活动记录中，然后将sp移过调用者的局部移过调用者的局部数据域和临时变量域，以及被调用者的参数数据域和临时变量域，以及被调用者的参数域和状态域域和状态域n被调用者保存寄存器值和其它机器状态信息被调用者保存寄存器值和其它机器状态信息n被调用者初始化其局部数据，并开始执行。被调用者初始化其局部数据，并开始执行。2023-1-2449.4.1 调用序列和返回序列调用序列和返回序列一种可能的返回序列：一种可能的返回序列：n被调用者将返回值放入临近调用者的活动被调用者将返回值放入临近调用者的活动记录的地方。记录的地方。n利用状态域中的信息，被调用者恢复利用状态域中的信息，被调用者恢复sp和

39、和其它寄存器，并且按调用者代码中的返回其它寄存器，并且按调用者代码中的返回地址返回。地址返回。n尽管尽管sp的值减小了，调用者仍然可以将返的值减小了，调用者仍然可以将返回值复制到自己的活动记录中，并用它来回值复制到自己的活动记录中，并用它来计算一个表达式。计算一个表达式。2023-1-2459.4.1 调用序列和返回序列调用序列和返回序列过程的参数个数可变的情况过程的参数个数可变的情况n函数返回值改成用寄存器传递函数返回值改成用寄存器传递n编译器产生将这些参数逆序进栈的代码编译器产生将这些参数逆序进栈的代码n被调用函数能准确地知道第一个参数的位置被调用函数能准确地知道第一个参数的位置n被调用函

40、数根据第一个参数到栈中取第二、被调用函数根据第一个参数到栈中取第二、第三个参数等等第三个参数等等n如如C语言的语言的printf2023-1-246n过程调用的过程调用的三地址码三地址码:param x1param x2 param xncall p，n9.4.2 C语言的过程调用和返回语言的过程调用和返回 2023-1-2471)每个每个param xi(i=1,2,n)可直接翻译成如下指令可直接翻译成如下指令:(i+3)top:=xi (传值传值)(i+3)top:=addr(xi)(传地址传地址)2)call p，n 被翻译成被翻译成如下指令如下指令:1top:=sp (保护现行保护现行

41、sp)3top:=n (传递参数个数传递参数个数)JSR p (转子指令转子指令)参数个数参数个数返回地址返回地址内情向量内情向量局部变量局部变量老老sp临时单元临时单元对于对于par和和call产生的目标代码产生的目标代码top sp 调用过程的活动记录调用过程的活动记录老老sp参数个数参数个数形式单元形式单元形式单元形式单元2023-1-2483)进进入过程入过程p后，首先应执行下述指令后，首先应执行下述指令:sp:=top+1 (定义新的定义新的sp)1sp:=返回地址返回地址 (保护返回地址保护返回地址)top:=top+L (新新top)L：过程过程P的活动记录所需单元数，的活动记录

42、所需单元数，在编译时可确定。在编译时可确定。参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老sp临时单元临时单元TOP 调用过程的活动记录调用过程的活动记录返回地址返回地址topsp2023-1-2494)过程返回时，应执行下列指令过程返回时，应执行下列指令:top:=sp-1 (恢复调用前恢复调用前top)sp:=0sp (恢复调用前恢复调用前SP)X:=2top (把返回地址把返回地址取到取到X中中)UJ 0X (按按X返回返回)UJ为无条件转移指令，为无条件转移指令，即按即按X中的返回地址实行变址转移中的返回地址实行变址转移参数个数参数个数返回地址返回

43、地址形式单元形式单元内情向量内情向量局部变量局部变量老老sp临时单元临时单元调用过程的活动记录调用过程的活动记录topspsptop2023-1-2509.4.3 栈中的可变长数据栈中的可变长数据活动记录的长度在编译时不能确定的情况活动记录的长度在编译时不能确定的情况n局部数组的大小要等到过程激活时才能确定局部数组的大小要等到过程激活时才能确定n在活动记录中为这样的数组分别存放数组指在活动记录中为这样的数组分别存放数组指针的单元针的单元n运行时，这些指针指向分配在栈顶的存储空运行时，这些指针指向分配在栈顶的存储空间间2023-1-2519.4.3 栈中的可变长数据栈中的可变长数据图图9.13

44、访问动态分配的数组访问动态分配的数组2023-1-252栈式存储分配策略的局限栈式存储分配策略的局限栈式分配策略在下列情况下行不通：栈式分配策略在下列情况下行不通：n过程活动停止后，局部名字的值还必须维持过程活动停止后，局部名字的值还必须维持n被调用者的活动比调用者的活动的生存期更被调用者的活动比调用者的活动的生存期更长，此时活动树不能正确描绘程序的控制流长，此时活动树不能正确描绘程序的控制流n不遵守栈式规则的有不遵守栈式规则的有Pascal语言和语言和C语言的动语言的动态变量态变量nJava禁止程序员自己释放空间禁止程序员自己释放空间 2023-1-2539.5 栈中非局部数据的访问栈中非局

45、部数据的访问本节内容本节内容n无嵌套过程的静态作用域的实现（无嵌套过程的静态作用域的实现（C语言）语言）n包含嵌套过程的静态作用域的实现（包含嵌套过程的静态作用域的实现（Pascal语言）语言）n动态作用域的实现（动态作用域的实现（Lisp语言）语言）2023-1-2549.5.1 无过程嵌套的静态作用域无过程嵌套的静态作用域n假定假定:允许过程递归调用、允许过程含有可变数允许过程递归调用、允许过程含有可变数组，但过程定义不允许嵌套，如组，但过程定义不允许嵌套，如C语言语言。n过程体中的非局部引用可以直接使用静态确定过程体中的非局部引用可以直接使用静态确定的地址的地址n局部变量在栈顶的活动记录

46、中，可以通过局部变量在栈顶的活动记录中，可以通过sp指指针来访问针来访问n无须深入栈中取数据，无须访问链无须深入栈中取数据，无须访问链n过程可以作为参数来传递，也可以作为结果来过程可以作为参数来传递，也可以作为结果来返回返回C语言的函数声明不能嵌套，函数不论在什语言的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况么情况下激活，要访问的数据分成两种情况:n非静态局部变量（包括形式参数），它们分非静态局部变量（包括形式参数），它们分配在活动记录栈顶的那个活动记录中配在活动记录栈顶的那个活动记录中n外部变量（包括定义在其它源文件中的外部外部变量（包括定义在其它源文件中的外部变量

47、）和静态的局部变量，它们都分配在静变量）和静态的局部变量，它们都分配在静态数据区态数据区 9.5.1 无过程嵌套的静态作用域无过程嵌套的静态作用域2023-1-2552023-1-256 全局数据说明全局数据说明main()main中的数据说明中的数据说明 void R()R中的数据说明中的数据说明void Q()Q中的数据说明中的数据说明n主程序主程序过程过程Q 过程过程RQ的活动记录的活动记录主程序主程序活动记录活动记录TOPR的活动记录的活动记录SP参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元全局数据区全局数据区2023-1-2

48、579.5.2 有过程嵌套的静态作用域有过程嵌套的静态作用域假定语言不仅允许过程的递归调用假定语言不仅允许过程的递归调用(和可变数和可变数组组)，而且允许过程定义的嵌套，如，而且允许过程定义的嵌套，如PASCAL，PL语言。语言。sortreadarrayexchangequicksortpartition2023-1-258n(1)program sort(input,output);n(2)var a:array0.10 of integer;n(3)x:integer;n(4)procedure readarray;n(5)var i:integer;n(6)begin a end re

49、adarray;n(7)procedure exchange(i,j:integer);n(8)begin n(9)x:=ai;ai:=aj;aj:=x;n(10)end exchange;program sort procedure readarray procedure exchange procedure quicksort function partition 2023-1-259n(11)procedure quicksort(m,n:integer);n(12)var k,v:integer;n(13)function partition(y,z:integer):integer;

50、n(14)var i,j:integer;n(15)begin an(16)vn(17)exchange(i,j);n(18)end partition;n(19)begin end quicksort;n(20)begin end sort.program sort procedure readarray procedure exchange procedure quicksort function partition 2023-1-2609.5.2 有过程嵌套的静态作用域有过程嵌套的静态作用域引入概念：引入概念：过程嵌套深度过程嵌套深度sort1readarray2exchange2qui