运行时存储空间的组织和管理.ppt

第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 术语术语过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动活动记录活动记录过程的活动需要可执行代码和存放所需信息的存过程的活动需要可执行代码和存放所需信息的存储空间储空间,后者称为活动记录后者称为活动记录本章内容本章内容讨论一个活动记录中的数据布局讨论一个活动记录中的数据布局程序执行过程中，所有活动记录的组织方式程序执行过程中，所有活动记录的组织方式第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递归当当控控制制从从过过程程的的活活动动返返回回时时，局局部部变变量量的的值值是是否否要保留要保留过程能否访问非局部变量过程能否访问非局部变量过程调用的参数传递方式过程调用的参数传递方式过程能否作为参数被传递过程能否作为参数被传递过程能否作为结果值传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块能否在程序控制下动态地分配存储块是否必须显式地释放存储块是否必须显式地释放6.1 局部存储分配局部存储分配6.1.1过程过程语言概念：语言概念：过程定义、过程定义、过程过程调用、形式参数、实在参调用、形式参数、实在参数、数、活动的活动的生存期生存期6.1 局部存储分配局部存储分配6.1.2名字的作用域和绑定名字的作用域和绑定1、名字的作用域、名字的作用域一个声明起作用的程序部分称为该声明的一个声明起作用的程序部分称为该声明的作作用域用域即使一个名字在程序中只声明一次，该名字即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象在程序运行时也可能表示不同的数据对象6.1 局部存储分配局部存储分配2、环境和状态、环境和状态环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值（即到右值（即名字到值有两步映射名字到值有两步映射）赋值改变状态，但不改变环境赋值改变状态，但不改变环境过程调用改变环境过程调用改变环境如果环境将名字如果环境将名字x映射到存储单元映射到存储单元s，则说则说x被被绑定绑定到到s名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配3、静态概念和动态概念的对应、静态概念和动态概念的对应 静静态态概概念念 动动态态对对应应 过程的定义过程的定义 过程的活动过程的活动 6.1 局部存储分配局部存储分配3、静态概念和动态概念的对应、静态概念和动态概念的对应 静静态态概概念念 动动态态对对应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明名字的绑定名字的绑定6.1 局部存储分配局部存储分配3、静态概念和动态概念的对应、静态概念和动态概念的对应 静静态态概概念念 动动态态对对应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明名字的绑定名字的绑定声明的作用域声明的作用域 绑定的生存期绑定的生存期6.1 局部存储分配局部存储分配6.1.3活动记录活动记录活动记录的常见布局活动记录的常见布局临临时时数数据据参参数数局局部部数数据据机机器器状状态态访访问问链链控控制制链链返返回回值值6.1 局部存储分配局部存储分配6.1.4局部数据的布局局部数据的布局字节是可编址内存的最小单位字节是可编址内存的最小单位变变量量所所需需的的存存储储空空间间可可以以根根据据其其类类型型而而静静态态确定确定一一个个过过程程所所声声明明的的局局部部变变量量，按按这这些些变变量量声声明明时时出出现现的的次次序序，在在局局部部数数据据域域中中依依次次分分配配空间空间局局部部数数据据的的地地址址可可以以用用相相对对于于活活动动记记录录中中某某个位置的地址来表示个位置的地址来表示数据对象的存储布局还有一个对齐问题数据对象的存储布局还有一个对齐问题6.1 局部存储分配局部存储分配例例 在在SPARC/Solaris工工作作站站上上下下面面两两个个结结构构体的体的size分别是分别是24和和16，为什么不一样？，为什么不一样？typedefstruct_atypedefstruct_bcharc1;charc1;longi;charc2;char c2;longi;doublef;doublef;a;b;对齐：对齐：char:1,long:4,double:86.1 局部存储分配局部存储分配例例 在在SPARC/Solaris工工作作站站上上下下面面两两个个结结构构体的体的size分别是分别是24和和16，为什么不一样？，为什么不一样？typedefstruct_atypedefstruct_bcharc1;0charc1;0longi;4charc2;1char c2;8longi;4doublef;16doublef;8a;b;对齐：对齐：char:1,long:4,double:86.1 局部存储分配局部存储分配例例 在在X86/Linux机机器器的的结结果果和和SPARC/Solaris工作站不一样，是工作站不一样，是20和和16。typedefstruct_atypedefstruct_bcharc1;0charc1;0longi;4charc2;1char c2;8longi;4doublef;12doublef;8a;b;对齐：对齐：char:1,long:4,double:46.1 局部存储分配局部存储分配 程序块程序块本身含有局部变量声明的语句本身含有局部变量声明的语句可以嵌套可以嵌套最接近的嵌套最接近的嵌套作用域规则作用域规则并列程序块不会同时活跃并列程序块不会同时活跃并列程序块的变量可以重叠分配并列程序块的变量可以重叠分配6.1 局部存储分配局部存储分配main()/例例/beginofB0/inta=0;intb=0;/beginofB1/intb=1;/beginofB2/inta=2;/endofB2/beginofB3/intb=3;/endofB3/endofB1/endofB0/6.1 局部存储分配局部存储分配main()/例例/beginofB0/inta=0;intb=0;/beginofB1/intb=1;/beginofB2/inta=2;/endofB2/beginofB3/intb=3;/endofB3/endofB1/endofB0/声声明明作作用用域域inta=0;B0 B2intb=0;B0 B1intb=1;B1 B3inta=2;B2intb=3;B3a0b0b1a2,b3重叠分配存储单元重叠分配存储单元6.2 全局栈式存储分配全局栈式存储分配本节介绍本节介绍介介绍绍程程序序运运行行时时所所需需的的各各个个活活动动记记录录在在存存储储空间的分配策略空间的分配策略描描述述过过程程的的目目标标代代码码怎怎样样访访问问绑绑定定到到局局部部名名字的存储单元字的存储单元介绍三种分配策略介绍三种分配策略静态分配策略静态分配策略栈式分配策略栈式分配策略堆式分配策略堆式分配策略6.2 全局栈式存储分配全局栈式存储分配 运行时内存的划分运行时内存的划分代代码码静静态态数数据据堆堆栈栈6.2 全局栈式存储分配全局栈式存储分配1、静态分配、静态分配名名字字在在程程序序被被编编译译时时绑绑定定到到存存储储单单元元，不不需需要运行时的任何支持要运行时的任何支持绑定的生存期是程序的整个运行期间绑定的生存期是程序的整个运行期间6.2 全局栈式存储分配全局栈式存储分配2、静态分配给语言带来限制、静态分配给语言带来限制递归过程不被允许递归过程不被允许数数据据对对象象的的长长度度和和它它在在内内存存中中位位置置的的限限制制，必须是在编译时可以知道的必须是在编译时可以知道的数据结构不能动态建立数据结构不能动态建立6.2 全局栈式存储分配全局栈式存储分配例例 C程程序序的的外外部部变变量量、静静态态局局部部变变量量以以及及程程序中出现的常量都可以静态分配序中出现的常量都可以静态分配声明在函数外面声明在函数外面外部变量外部变量-静态分配静态分配静态外部变量静态外部变量-静态分配静态分配声明在函数里面声明在函数里面静态局部变量静态局部变量-也是静态分配也是静态分配自动变量自动变量-不能静态分配不能静态分配6.2 全局栈式存储分配全局栈式存储分配 活动树和运行栈活动树和运行栈1、活动树、活动树用树来描绘控制进入和离开活动的方式用树来描绘控制进入和离开活动的方式mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2 全局栈式存储分配全局栈式存储分配活动树的特点活动树的特点每个结点代表某过程的一个活动每个结点代表某过程的一个活动根结点代表主程序的活动根结点代表主程序的活动结结点点a是是结结点点b的的父父结结点点，当当且且仅仅当当控控制制流流从从a的的活动进入活动进入b的活动的活动结结点点a处处于于结结点点b的的左左边边，当当且且仅仅当当a的的生生存存期期先先于于b的生存期的生存期mq(1,9)rp(1,9)q(1,3).q(5,9).6.2 全局栈式存储分配全局栈式存储分配当前活跃着的过程活动可以保存在一个栈中当前活跃着的过程活动可以保存在一个栈中例例控制栈的内容：控制栈的内容：m,q(1,9),q(1,3),q(2,3)mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2 全局栈式存储分配全局栈式存储分配2、运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）6.2 全局栈式存储分配全局栈式存储分配2、运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）main栈栈main函数调用关系树函数调用关系树6.2 全局栈式存储分配全局栈式存储分配2、运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mainr函数调用关系树函数调用关系树mainintir()栈栈6.2 全局栈式存储分配全局栈式存储分配2、运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mainq(1,9)r函数调用关系树函数调用关系树mainintiq(1,9)intm,n栈栈6.2 全局栈式存储分配全局栈式存储分配2、运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mainq(1,9)rp(1,9)q(1,3)mainintiq(1,9)intm,nintiq(1,3)intm,n栈栈函数调用关系树函数调用关系树6.2 全局栈式存储分配全局栈式存储分配2、运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mainq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)mainintiq(1,9)intm,nintiq(1,3)intm,nintiq(1,0)intm,n栈栈函数调用关系树函数调用关系树6.2 全局栈式存储分配全局栈式存储分配 调用序列调用序列过过程程调调用用和和过过程程返返回回都都需需要要执执行行一一些些代代码码来来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等过程调用序列过程调用序列过过程程调调用用时时执执行行的的分分配配活活动动记记录录，把把信信息息填填入入它它的的域中，使被调用过程可以开始执行的代码域中，使被调用过程可以开始执行的代码过程返回序列过程返回序列被被调调用用过过程程返返回回时时执执行行的的恢恢复复机机器器状状态态，释释放放被被调调用过程活动记录，使调用过程能够继续执行的代码用过程活动记录，使调用过程能够继续执行的代码调调用用序序列列和和返返回回序序列列常常常常都都分分成成两两部部分分，分分处于调用过程和被调用过程中处于调用过程和被调用过程中6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动动记记录录中中各各域域的的排排放放次次序序，也也会会因因实实现而异现而异设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则以活动记录中间的某个以活动记录中间的某个位置作为基地址位置作为基地址长度能较早确定的域放在长度能较早确定的域放在活动记录的中间活动记录的中间临临时时数数据据参参数数局局部部数数据据机机器器状状态态访访问问链链控控制制链链返返回回值值6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动动记记录录中中各各域域的的排排放放次次序序，也也会会因因实实现而异现而异设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则一般把临时数据域放在一般把临时数据域放在局部数据域的后面局部数据域的后面把参数域和可能有的返回把参数域和可能有的返回值域放在紧靠调用者活动值域放在紧靠调用者活动记录的地方记录的地方临临时时数数据据参参数数局局部部数数据据机机器器状状态态访访问问链链控控制制链链返返回回值值6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动动记记录录中中各各域域的的排排放放次次序序，也也会会因因实实现而异现而异设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则用同样的代码来执行各个用同样的代码来执行各个活动的保存和恢复活动的保存和恢复临临时时数数据据参参数数局局部部数数据据机机器器状状态态访访问问链链控控制制链链返返回回值值6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(1)p计算实参，依计算实参，依次放入栈顶，并在次放入栈顶，并在栈顶留出放返回值栈顶留出放返回值的空间。的空间。top_sp的的值在此过程中被改值在此过程中被改变变返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和参数返回值和参数top_sp 6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(2)p把返回地址和把返回地址和当前当前base_sp的值的值存入存入q的活动记录的活动记录中，建立中，建立q的访问的访问链，增加链，增加base_sp的值的值返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和参数返回值和参数控制链和返回地址控制链和返回地址base_sp top_sp 6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(3)q保存寄存器的保存寄存器的值和其它机器状态值和其它机器状态信息信息返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和参数返回值和参数控制链控制链和保存的机器状态和保存的机器状态6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(4)q根据局部数据根据局部数据域和临时数据域的域和临时数据域的大小增加大小增加top_sp的的值，初始化它的局值，初始化它的局部数据，并开始执部数据，并开始执行过程体行过程体临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配调用者调用者p和被调用者和被调用者q之间的任务划分之间的任务划分被调用者被调用者q的责任的责任调用者调用者p的责任的责任调用者调用者p的的活动记录活动记录被调用者被调用者q的活动记录的活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列临时数据局部数据临时数据局部数据返回值返回值和参数和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 (1)q把返回值置入把返回值置入邻近邻近p的活动记录的活动记录的地方的地方参数个数可变场参数个数可变场合难以确定存放返合难以确定存放返回值的位置，因此回值的位置，因此通常用寄存器传递通常用寄存器传递返回值返回值6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列(2)q对应调用序列对应调用序列的步骤的步骤(4)，减小，减小top_sp的值的值返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和参数返回值和参数控制链控制链和保存的机器状态和保存的机器状态6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列(3)q恢复寄存器恢复寄存器(包包括括base_sp)和机器和机器状态，返回状态，返回p返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和参数返回值和参数6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 (4)p根据参数个数根据参数个数与类型和返回值类与类型和返回值类型调整型调整top_sp，然然后取出返回值后取出返回值6.2 全局栈式存储分配全局栈式存储分配3、过程的参数个数可变的情况、过程的参数个数可变的情况临时数据局部数据临时数据局部数据参参数数参参数数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 (1)函数返回值改函数返回值改成用寄存器传递成用寄存器传递6.2 全局栈式存储分配全局栈式存储分配3、过程的参数个数可变的情况、过程的参数个数可变的情况临时数据局部数据临时数据局部数据参数参数1,参数参数n参数参数1,参数参数m 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 (2)编译器产生将编译器产生将实参表达式逆序计实参表达式逆序计算并将结果进栈的算并将结果进栈的代码代码自上而下依次自上而下依次是参数是参数1,参数参数n6.2 全局栈式存储分配全局栈式存储分配3、过程的参数个数可变的情况、过程的参数个数可变的情况临时数据局部数据临时数据局部数据参数参数1,参数参数n参数参数1,参数参数m 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 (3)被调用函数能被调用函数能准确地知道第一个准确地知道第一个参数的位置参数的位置6.2 全局栈式存储分配全局栈式存储分配3、过程的参数个数可变的情况、过程的参数个数可变的情况临时数据局部数据临时数据局部数据参数参数1,参数参数n参数参数1,参数参数m 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 (4)被调用函数根被调用函数根据第一个参数到栈据第一个参数到栈中取第二、第三个中取第二、第三个参数等等参数等等6.2 全局栈式存储分配全局栈式存储分配3、过程的参数个数可变的情况、过程的参数个数可变的情况临时数据局部数据临时数据局部数据参数参数1,参数参数n参数参数1,参数参数m 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 C语言的语言的printf函函数就是按此方式，数就是按此方式，用用C语言编写的语言编写的下面语句的输出？下面语句的输出？printf(“%d,%d,%dn”);6.2 全局栈式存储分配全局栈式存储分配6.2.4栈上可变长数据栈上可变长数据活动记录的长度在编译时不能确定的情况活动记录的长度在编译时不能确定的情况例例：局局部部数数组组的的大大小小要要等等到到过过程程激激活活时时才才能能确定确定备注：备注：Java语言的实现是将它们分配在堆上语言的实现是将它们分配在堆上6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组控制链控制链数组数组A的指针的指针数组数组B的指针的指针top_sp base_sp.栈栈(1)编译时，编译时，在活动记录中在活动记录中为这样的数组为这样的数组分配存放数组分配存放数组指针的单元指针的单元6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组(2)运行时，运行时，这些指针指向这些指针指向分配在栈顶的分配在栈顶的数组存储空间数组存储空间控制链控制链数组数组A的指针的指针数组数组B的指针的指针top_sp base_sp.栈栈数组数组A数组数组B6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组(3)运行时，运行时，对数组对数组A和和B的访问都要通的访问都要通过相应指针来过相应指针来间接访问间接访问控制链控制链数组数组A的指针的指针数组数组B的指针的指针top_sp base_sp.栈栈数组数组A数组数组B6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组q的数组的数组q的活动记录的活动记录p的数组的数组p的活动记录的活动记录控制链控制链top_sp base_sp 数组数组A的指针的指针数组数组B的指针的指针数组数组A数组数组B控制链控制链.栈栈6.2 全局栈式存储分配全局栈式存储分配6.2.5悬空引用悬空引用悬空引用：悬空引用：引用某个已被释放的存储单元引用某个已被释放的存储单元6.2 全局栈式存储分配全局栈式存储分配6.2.5悬空引用悬空引用悬空引用：悬空引用：引用某个已被释放的存储单元引用某个已被释放的存储单元例：例：main中引用中引用p指向的对象指向的对象main()|int dangle()int q;|intj=20;q=dangle();|return&j;|6.3 非局部名字的访问非局部名字的访问本节介绍本节介绍无过程嵌套的静态作用域（无过程嵌套的静态作用域（C语言）语言）有过程嵌套的静态作用域有过程嵌套的静态作用域（Pascal语言）语言）动态作用域动态作用域（Lisp语言）语言）6.3 非局部名字的访问非局部名字的访问 无过程嵌套的静态作用域无过程嵌套的静态作用域过过程程体体中中的的非非局局部部引引用用可可以以直直接接使使用用静静态态确确定的地址（非局部数据此时就是全局数据）定的地址（非局部数据此时就是全局数据）局局部部变变量量在在栈栈顶顶的的活活动动记记录录中中，可可以以通通过过base_sp指针来访问指针来访问无须深入栈中取数据，无须访问链无须深入栈中取数据，无须访问链过过程程可可以以作作为为参参数数来来传传递递，也也可可以以作作为为结结果果来返回来返回6.3 非局部名字的访问非局部名字的访问 有过程嵌套的静态作用域有过程嵌套的静态作用域sortreadarrayexchangequicksortpartition6.3 非局部名字的访问非局部名字的访问 有过程嵌套的静态作用域有过程嵌套的静态作用域过程过程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度：它的声明所在过程的嵌套变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度深度作为该名字的嵌套深度访问链访问链用来寻找非局部用来寻找非局部名字的存储单元名字的存储单元sa,xq(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链e(1,3)访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链6.3非局部名字的访问非局部名字的访问6.3 非局部名字的访问非局部名字的访问访问非局部名字的存储单元访问非局部名字的存储单元假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度为它引用嵌套深度为na的变量的变量a，na np，如何访问，如何访问a的存储单元的存储单元sort1readarray2exchange2quicksort2partition3sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链6.3 非局部名字的访问非局部名字的访问访问非局部名字的存储单元访问非局部名字的存储单元假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度为它引用嵌套深度为na的变量的变量a，na np，如何访问，如何访问a的存储单元的存储单元从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次次到达到达a的声明所在过程的活动记录的声明所在过程的活动记录访问链的追踪用间接操作就可完成访问链的追踪用间接操作就可完成sort1readarray2exchange2quicksort2partition3sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链访问非局部名字的存储单元访问非局部名字的存储单元 sortreadarrayexchangequicksortpartitionsa,xq(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链e(1,3)访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链6.3非局部名字的访问非局部名字的访问6.3 非局部名字的访问非局部名字的访问过过程程p对对变变量量a访访问问时时，a的的地地址址由由下下面面的的二二元元组表示：组表示：（np na，a在活动记录中的偏移）在活动记录中的偏移）6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假假定定嵌嵌套套深深度度为为np的的过过程程p调调用用嵌嵌套套深深度度为为nx的的过程过程x(1)np nx的情况的情况sort1readarray2exchange2quicksort2partition3这时这时x肯定肯定就声明在就声明在p中中6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假假定定嵌嵌套套深深度度为为np的的过过程程p调调用用嵌嵌套套深深度度为为nx的的过程过程x(1)np nx的情况的情况被被调调用用过过程程的的访访问问链链必必须须指指向向调调用用过过程程的的活活动动记记录的访问链录的访问链访问非局部名字的存储单元访问非局部名字的存储单元 sortreadarrayexchangequicksortpartitionsa,xq(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链e(1,3)访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链6.3非局部名字的访问非局部名字的访问6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假假定定嵌嵌套套深深度度为为np的的过过程程p调调用用嵌嵌套套深深度度为为nx的的过程过程x(2)np nx的情况的情况sort1readarray2exchange2quicksort2partition3这时这时p和和x的的嵌套深度分别嵌套深度分别为为1，2，nx 1的外围过的外围过程肯定相同程肯定相同6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假假定定嵌嵌套套深深度度为为np的的过过程程p调调用用嵌嵌套套深深度度为为nx的的过程过程x(2)np nx的情况的情况追追踪踪访访问问链链np nx+1次次，到到达达了了静静态态包包围围x和和p的且离它们最近的那个过程的最新活动记录的且离它们最近的那个过程的最新活动记录所所到到达达的的活活动动记记录录就就是是x的的活活动动记记录录中中的的访访问问链链应该指向的那个活动记录应该指向的那个活动记录访问非局部名字的存储单元访问非局部名字的存储单元 sortreadarrayexchangequicksortpartitionsa,xq(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链e(1,3)访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链6.3非局部名字的访问非局部名字的访问6.3 非局部名字的访问非局部名字的访问programparam(input,output);（过程作为参数）过程作为参数）procedureb(functionh(n:integer):integer);beginwriteln(h(2)endb;procedurec;varm:integer;functionf(n:integer):integer;beginf:=m+nendf;beginm:=0;b(f)endc;begincend.函数函数f作为参数传递时，怎样在作为参数传递时，怎样在f被激活时建立它的访问链被激活时建立它的访问链6.3 非局部名字的访问非局部名字的访问programparam(input,output);（过程作为参数）过程作为参数）procedureb(functionh(beginwriteln(h(2)end;procedurec;varm:integer;functionf(n:integer)beginf:=m+nendf;beginm:=0;b(f)endc;begincend.从从b的访问链难以建的访问链难以建立立f的访问链的访问链访访问问链链访访问问链链paramcmb6.3 非局部名字的访问非局部名字的访问programparam(input,output);（过程作为参数）过程作为参数）procedureb(functionh(beginwriteln(h(2)end;procedurec;varm:integer;functionf(n:integer)beginf:=m+nendf;beginm:=0;b(f)endc;begincend.f作为参数传递时，作为参数传递时，它的起始地址连同它它的起始地址连同它的访问链一起传递的访问链一起传递访访问问链链访访问问链链paramcmb6.3 非局部名字的访问非局部名字的访问programparam(input,output);（过程作为参数）过程作为参数）procedureb(functionh(beginwriteln(h(2)end;procedurec;varm:integer;functionf(n:integer)beginf:=m+nendf;beginm:=0;b(f)endc;begincend.b调用调用f时，用传递时，用传递过来的访问链来建立过来的访问链来建立f的访问链的访问链访访问问链链访访问问链链paramcmb访访问问链链b6.3 非局部名字的访问非局部名字的访问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.aretbaddm6.3 非局部名字的访问非局部名字的访问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.aretbaddm执行执行addm时，时，a的活动记录已不存的活动记录已不存在，取不到在，取不到m的值的值6.3 非局部名字的访问非局部名字的访问C语语言言的的函函数数声声明明不不能能嵌嵌套套，函函数数不不论论在在什什么么情况下激活，要访问的数据分成两种情况情况下激活，要访问的数据分成两种情况非非静静态态局局部部变变量量（包包括括形形式式参参数数），它它们们分分配配在在活动记录栈顶的那个活动记录中活动记录栈顶的那个活动记录中外外部部变变量量（包包括括定定义义在在其其它它源源文文件件之之中中的