第9章运行时存储空间组织

1、第九章运行时存储空间组织第九章运行时存储空间组织在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。程序中使用的存储单元都由标识符来表示。标识符对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。第九章运行时存储空间组织第九章运行时存储空间组织9.1 目标程序运行时的活动9.2 运行时存储器的划分9.3 静态存储分配9.4 简单的栈式存储分配9.5 嵌套过程语言的栈式实现9.6 堆式动态存储分配 1、过程的活动 P2409.1 目标程序运行时的活动 2、参数传递 （1） 传值 （2）传地址 （3）传名 （4）得结果9.1 目标程序运行时的活动例：proce

2、dure swap(n,m:real); var j:real;begin j:=n; n:=m; m:=j;end;若存在调用：swap(i,k(i)（1）传值（2）传地址（3）传名： j:=i; i:=K(i) ; k(i):=j;例：procedure swap(n,m:real); var j:real;begin j:=n; n:=m; m:=j;end;若存在调用：swap(i,k(i)(4) 得结果 swap(m,n)addr(i), i addr(k(i),K(i)9.2运行时存储器的划分一、运行时存储器的划分 1、编译器需要在存储区保护的对象、编译器需要在存储区保护的对象（1

3、）目标代码目标代码编译是可确定，故可放在一个静态确编译是可确定，故可放在一个静态确 定的区域定的区域（2）数据对象数据对象部分数据对象的大小在编译时可确部分数据对象的大小在编译时可确 定，故也可放在一个静态确定的区域定，故也可放在一个静态确定的区域（3）跟踪过程活动的控制栈跟踪过程活动的控制栈目标代码目标代码静态数据静态数据栈栈堆堆9.2运行时存储器的划分2、栈和堆、栈和堆 A、栈栈：用扩充的栈来管理过程的活动，当发生过程：用扩充的栈来管理过程的活动，当发生过程调用时，中断当前活动的执行，激活新被调调用时，中断当前活动的执行，激活新被调用过程的活动，并把包含在这个活动生存期用过程的活动，并把包

4、含在这个活动生存期中的数据对象以及该活动有关的其它信息存中的数据对象以及该活动有关的其它信息存入栈中。当控制从调用返回时，将所占存储入栈中。当控制从调用返回时，将所占存储空间弹出栈顶。同时，被中断的活动恢复执行。空间弹出栈顶。同时，被中断的活动恢复执行。B、堆（堆（heap）存放动态数据，大小可随程序的运存放动态数据，大小可随程序的运行而改变。行而改变。9.2运行时存储器的划分二、活动记录1、活动记录：、活动记录：为了管理过程在一次执行中所需要为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，该连的信息，使用一个连续的存储块，该连续的存储块叫活动记录。续的存储块叫活动记录。当过程调用

5、时当过程调用时，产生一个过程的新的活动，用一，产生一个过程的新的活动，用一个活动记录表示该活动的相关信息，并将个活动记录表示该活动的相关信息，并将其压入栈。其压入栈。当过程返回时当过程返回时，将该活动记录从栈中弹出。，将该活动记录从栈中弹出。Pascal C9.2运行时存储器的划分2、活动记录的内容、活动记录的内容（1）连接数据）连接数据 SP指向现行过程的活动记录在栈里的起始位置。指向现行过程的活动记录在栈里的起始位置。返回地址返回地址动态链动态链 指向调用该过程前的最新活动记录地址指向调用该过程前的最新活动记录地址的指针。运行时，使运行栈上各数据全动态建的指针。运行时，使运行栈上各数据全动

6、态建立的次序结成链。链头为栈顶起始位置。立的次序结成链。链头为栈顶起始位置。静态链静态链指向静态直接外层最新活动记录地址的指向静态直接外层最新活动记录地址的指针，用来访问非局部数据指针，用来访问非局部数据（2）形式单元）形式单元存放相应的实在参数的地址或值存放相应的实在参数的地址或值（3）局部数据区）局部数据区 局部变量局部变量简单变量简单变量内情向量内情向量局部数据的内情向量，即数组元素局部数据的内情向量，即数组元素临时工作单元临时工作单元存放对表达式求值的结果存放对表达式求值的结果9.2运行时存储器的划分三、存储分配策略 1、静态存储分配策略、静态存储分配策略 在编译时对所有数据对象分配固

7、定的存储单元，且在编译时对所有数据对象分配固定的存储单元，且 在运行时始终保持不变。在运行时始终保持不变。 2、栈式动态分配策略、栈式动态分配策略 在运行时把存储器作为一个栈进行管理，运行时，在运行时把存储器作为一个栈进行管理，运行时， 每当调用一个过程，它所需要的存储空间就动态地分配每当调用一个过程，它所需要的存储空间就动态地分配 于栈顶，一旦退出，它所占空间就予以释放。于栈顶，一旦退出，它所占空间就予以释放。 3、堆式动态分配策略、堆式动态分配策略 在运行时把存储器组织成堆结构，以便用户关于存在运行时把存储器组织成堆结构，以便用户关于存 储空间的申请与归还（回收），凡申请者从堆中分储空间的

8、申请与归还（回收），凡申请者从堆中分 给一块，凡释放者退回给堆给一块，凡释放者退回给堆9.3 静态存储分配P2469.4简单的栈式存储分配1、前提：、前提：假设程序语言无分程序结构，过程定义不允假设程序语言无分程序结构，过程定义不允 许嵌套，但允许过程的递归调用。许嵌套，但允许过程的递归调用。例如：例如：C 语言语言2、过程：运行时、过程：运行时每当进入一个过程每当进入一个过程即一个过程的活动开始，就把其即一个过程的活动开始，就把其它活动记录压入栈（置于栈顶），从而它活动记录压入栈（置于栈顶），从而形成过程工作时的数据区形成过程工作时的数据区当活动结束当活动结束即过程退出时，再把其活动记录弹出

9、即过程退出时，再把其活动记录弹出栈，这样，它在栈顶上的数据区在随即栈，这样，它在栈顶上的数据区在随即不复存在不复存在9.4简单的栈式存储分配3、举例、举例 （1）主程序调用过程）主程序调用过程Q，而，而Q又调用又调用R，在，在R进进入运行后的存储结构入运行后的存储结构 （2）主程序调用过程）主程序调用过程Q，Q递归调用自己，在递归调用自己，在Q过程第二次进入运行后的存储结构过程第二次进入运行后的存储结构 （3）主程序先调用过程）主程序先调用过程Q，然后主程序调用，然后主程序调用R，且过程且过程Q不调用不调用Q和和RQ和和R进入运行后的存储结构如图所示：进入运行后的存储结构如图所示：R的活动记录

10、Q的活动记录Main的活动记录全局数据SPTOP静态分配9.4简单的栈式存储分配4、指示器指示器SP总是指向现行过程活动记录的总是指向现行过程活动记录的起点，用于访问局部数据起点，用于访问局部数据 指示器指示器TOP始终指向（已占用）栈顶单元始终指向（已占用）栈顶单元9.4简单的栈式存储分配一、C的活动记录 1、C的活动记录的项目的活动记录的项目 （1）连接数据连接数据A、老、老SP值值: 即前一活动记录的地址即前一活动记录的地址 B、返回地址、返回地址 （2）参数个数参数个数 （3）形式单元形式单元存放实在参数的值或地址存放实在参数的值或地址 （4）过程的局部变量过程的局部变量临时工作单元临

11、时工作单元内情向量内情向量简单变量简单变量形式单元形式单元参数个数参数个数返回地址返回地址老老SPSPTOPSP9.4简单的栈式存储分配2、（1）不允许过程嵌套）不允许过程嵌套非局部量仅能出现在源程非局部量仅能出现在源程 序头，可采用静态存储分配，编译时可确定其地址序头，可采用静态存储分配，编译时可确定其地址 （2）局部变量或形参在活动记录中的位置确定）局部变量或形参在活动记录中的位置确定其地址是相对于活动记录的基地址其地址是相对于活动记录的基地址SP的的绝对地址绝对地址=活动记录基地址活动记录基地址+相对地址相对地址 变址访问变址访问XSPX代表相对数，即相对于活动记代表相对数，即相对于活动

12、记录起点的地址，编译时可完全确定下来录起点的地址，编译时可完全确定下来9.4简单的栈式存储分配二、C的过程调用，过程进入、数组空间分配和过程返回已知过程调用的四元式序列为：par T1 par Tn call P,nC语言过程调用与返回Par Ti(i+3)TOP := Ti （传值） 或(i+3)TOP := addr(Ti)（传地址）Call P,n1TOP := SP3 TOP := nJSR P (转P)SP := TOP+11SP := 返回地址TOP := TOP + 活动单元数Return(E)TOP := SP1SP := 0SPX := 2TOPUJ 0 x /* UJ:无条

13、件转移*/9.5嵌套过程语言的栈式实现前提：前提：假定允许过程定义嵌套，如Pascal语言， 但去掉Pascal中的“文件”类型程序举例：程序举例：课本P258 图9.159.5嵌套过程语言的栈式实现一、非局部名字的访问的实现 说明非局部名字的访问 1、静态链和活动记录、静态链和活动记录 A、静态链静态链活动记录的一个域，从一个过程的当前活 动记录指向其静态直接外层的最新活动记录。 动态链动态链活动记录一个域，从一个过程的当前活动 记录指向调用该过程前正在运行的过程的最新 的活动记录的基地址。B、活动记录结构活动记录结构P259 图9.16形式单元形式单元参数个数参数个数静态链静态链动态链（老

14、动态链（老SPSP）返回地址返回地址简单变量简单变量内情向量内情向量临时工作单元临时工作单元SPTOPprogram P; var a,x:integer; proc Q(b:integer); var i:integer; proc R(u:integer,var v:integer); var c,d:integer; begin end; begin end; proc S; var c,i:integer; begin end;begin c P; proc Q; proc R; begin R(.,.); end; begin R(,) end; proc S; beg

15、in Q() end;begin S; end. 01234567890返回地址0ax0返回地址00（形参个数）csptopi10sptopC、程序运行时栈的变化过程程序运行时栈的变化过程举例：ib(形参)1(形参个数)0返回地址5ic00返回地址0 xa0返回地址0ic0(形参个数)0返回地址0 xa0返回地址0过程过程P中调中调用用S时时161514131211109876543210SPTOPTOPSP109876543210过程过程S中中调用调用Q时时dcv(形参)u(形参)2(形参个数)11返回地址11ib(形参)1(形参个数)0返回地址5ic00返回地址0 xa0返回地址0TOPS

16、P1211109876543210242322212019181716151413过程过程Q中调用中调用R时时dcvu211返回地址17dcv(形参)u(形参)2(形参个数)11返回地址11ib(形参)1(形参个数)0返回地址5ic00返回地址0 xa0返回地址032313029282726252423222120191817161514131211109876543210SPTOP过程过程R中递归调用中递归调用R9.5嵌套过程语言的栈式实现D、含义：、含义：静态链：静态链：通过其值可以找到当前过程/活动可以引用的“非局部变量”的过程的活动记录的基址，从而找到要引用的“非局部变量”动态链：动态

17、链：通过其值可以找到当前过程/活动结束后，需要返回的上一层活动记录的基址SP9.5嵌套过程语言的栈式实现2、嵌套层次显示表（、嵌套层次显示表（display）和活动记录）和活动记录 A、嵌套层次显示表：、嵌套层次显示表：每进入一个过程后，在建立它的活动区的同时建立该表 B、表的内容：、表的内容：假定现进行的过程的层数为i，则其display含有i+1个单元。该表本身是一个小栈，自顶向下每个单元依次存放现行层，直接外层,直到最外层（0层主程序层）等每一层过程的最新活动记录的基地址。举例：举例：令过程令过程R的外层为的外层为Q，Q的外层为的外层为P，则，则R运行时运行时display表为表为2 2

18、R R的现行活动记录地址（的现行活动记录地址（SPSP的现行值）的现行值）1 1Q Q的最新活动记录的地址的最新活动记录的地址0 0P P的活动记里的地址的活动记里的地址9.5嵌套过程语言的栈式实现C、“非局部量非局部量”地址的确定：地址的确定：绝对地址绝对地址= display静态层数静态层数+相对地址相对地址D、活动记录结构：、活动记录结构：TOPa321SP 0临时单元临时单元内情向量内情向量简单变量简单变量display形参单元形参单元参数个数参数个数全局全局DisplayDisplay返回地址返回地址老老SP(SP(动态链动态链) )p1 调用 P2 的两种不同嵌套：P1P2P0P2

19、P1k-1kk-1kkp1 调用 P2 的两种不同嵌套：P1P2k-1kDisplayK项P1P2P1的display k项p2的sptopsptopspp1 调用 P2 的两种不同嵌套：P0P2P1k-1kkDisplayK+1项P1P2P1的display 前k项p2的sptopsptopsp00返回地址10（display)2a3x405返回地址62(全局display)70(形参个数)809510C11i12sptoptopspdisplayF、静态链方法与显示表方法的比较：、静态链方法与显示表方法的比较：通过向示表访问非局部量要比沿着静态链访问非局部量的速度快。原因：原因：因为通过显

20、示表的一个域，可以确定任意 外层活动记录的指针，再沿着这个指针便可 以找到处于外层活动记录的非局部量。9.5嵌套过程语言的栈式实现二、参数传递的实现 1、par TT为数组为数组（1）或者传递数组T的首地址（2）或者传递数组T的内情向量地址 2、Par TT为过程为过程假设：过程P把过程T作为实在参数传递过程Q，随后，Q又通过引用相应的形式参数调用T。 3、Par T 为标号为标号在进入在进入T T之后，为了建立之后，为了建立T T自己的自己的display display ，T T必须知道它直接外层的必须知道它直接外层的displaydisplay。又又P P的的displaydisplay

21、或者正好就是这个外层的或者正好就是这个外层的displaydisplay， 或者包含了这个外层或者包含了这个外层displaydisplay而由于而由于T T的层数是已知的的层数是已知的只要知道只要知道P P的的displaydisplay，T T就可以用它来建立自己的就可以用它来建立自己的displaydisplay，即假定，即假定T T的层数为的层数为1 1，则，则T T的的displaydisplay乃是由乃是由P P的的displaydisplay的前的前1 1个单元的内容和个单元的内容和SPSP的的现行值所组成。现行值所组成。为为了使得了使得过过程程T T工作工作时时能能够够知道知道

22、过过程程P P的的displaydisplay，必，必须须在在P P把把T T作作为为使使参传递给参传递给Q Q的的时时候把候把P P自身的自身的displaydisplay地址地址也也传过传过去去即：即：过过程程P P中的中的par T par T 的作用可刻的作用可刻画为画为建立如下所示的建立如下所示的两个两个相相继临时单继临时单元：元：第一第一个临时单个临时单元元B1B1：过过程程T T的入口地址的入口地址第二第二个临时单个临时单元元B2B2：过过程程T T的的displaydisplay地址。；地址。； 然后然后执执行（行（i+1i+1）TOP:=addr(B1)TOP:=addr(B

23、1)把第一把第一临时单临时单元元B1B1的地址的地址传给传给Q Q假定过程假定过程Q现在执行到调用语句现在执行到调用语句call Z,mZ形式参数，形式单元形式参数，形式单元Z中已含有上述中已含有上述B1的地址的地址故故B1的内容将用来作为转子指令的目的地址的内容将用来作为转子指令的目的地址（即转进过程（即转进过程T） B2的内容将作为的内容将作为“全局全局display地址地址”（第三项连接数据）传送给（第三项连接数据）传送给T9.6堆式动态存储分配1、堆式动态存储分配使用的情况、堆式动态存储分配使用的情况（1）允许用户自由地申请数据空间和退还空间（2）不仅有过程而且有进程的程序结构即空间的使用未必服从即空间的使用未必服从“先请后还，后请先还先请后还，后请先还”的原则的原则例如：例如：pascal语言中的标准过程语言中的标准过程new-dispose2、该种分配方法必须考虑的几个主要问题、该种分配方法必须考虑的几个主要问题（1）当运行程