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

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

在程序的执行过程中，程序中数据的存取是通过与之对应的存储单元来进行的。

程序中使用的存储单元都由标识符来表示。 标识符对应的内存地址都是由编译程序在编译时或由其生成的目标程序运行时进行分配。第九章运行时存储空间组织9.1目标程序运行时的活动9.2运行时存储器的划分9.3静态存储分配9.4简单的栈式存储分配9.5嵌套过程语言的栈式实现9.6堆式动态存储分配1、过程的活动

P2409.1目标程序运行时的活动2、参数传递（1）传值（2）传地址（3）传名（4）得结果9.1目标程序运行时的活动例：procedureswap(n,m:real);varj:real;beginj:=n;n:=m;m:=j;end;若存在调用：swap(i,k(i))（1）传值（2）传地址（3）传名：

j:=i;i:=K(i);k(i):=j;例：procedureswap(n,m:real);varj:real;beginj:=n;n:=m;m:=j;end;若存在调用：swap(i,k(i))(4)得结果

swap(m,n)addr(i),iaddr(k(i)),K(i)9.2运行时存储器的划分一、运行时存储器的划分

1、编译器需要在存储区保护的对象 （1）目标代码编译是可确定，故可放在一个静态确 定的区域 （2）数据对象部分数据对象的大小在编译时可确 定，故也可放在一个静态确定的区域 （3）跟踪过程活动的控制栈目标代码静态数据栈↓↑堆9.2运行时存储器的划分2、栈和堆

A、栈：用扩充的栈来管理过程的活动，当发生过程 调用时，中断当前活动的执行，激活新被调 用过程的活动，并把包含在这个活动生存期 中的数据对象以及该活动有关的其它信息存 入栈中。当控制从调用返回时，将所占存储 空间弹出栈顶。同时，被中断的活动恢复执行。B、堆（heap）——存放动态数据，大小可随程序的运 行而改变。9.2运行时存储器的划分二、活动记录

1、活动记录：为了管理过程在一次执行中所需要 的信息，使用一个连续的存储块，该连 续的存储块叫活动记录。

当过程调用时，产生一个过程的新的活动，用一 个活动记录表示该活动的相关信息，并将 其压入栈。

当过程返回时，将该活动记录从栈中弹出。PascalC9.2运行时存储器的划分2、活动记录的内容（1）连接数据

SP指向现行过程的活动记录在栈里的起始位置。

返回地址

动态链——

指向调用该过程前的最新活动记录地址 的指针。运行时，使运行栈上各数据全动态建 立的次序结成链。链头为栈顶起始位置。

静态链——指向静态直接外层最新活动记录地址的 指针，用来访问非局部数据（2）形式单元——存放相应的实在参数的地址或值（3）局部数据区

局部变量——简单变量

内情向量——局部数据的内情向量，即数组元素

临时工作单元——存放对表达式求值的结果9.2运行时存储器的划分三、存储分配策略

1、静态存储分配策略 在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。

2、栈式动态分配策略 在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。

3、堆式动态分配策略 在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，凡释放者退回给堆9.3静态存储分配P2469.4简单的栈式存储分配1、前提：假设程序语言无分程序结构，过程定义不允 许嵌套，但允许过程的递归调用。

例如：C语言2、过程：运行时

每当进入一个过程——即一个过程的活动开始，就把其 它活动记录压入栈（置于栈顶），从而 形成过程工作时的数据区

当活动结束——即过程退出时，再把其活动记录弹出 栈，这样，它在栈顶上的数据区在随即 不复存在9.4简单的栈式存储分配3、举例（1）主程序调用过程Q，而Q又调用R，在R进 入运行后的存储结构（2）主程序调用过程Q，Q递归调用自己，在Q

过程第二次进入运行后的存储结构（3）主程序先调用过程Q，然后主程序调用R， 且过程Q不调用Q和R⇒Q和R进入运行后的存储结构如图所示：R的活动记录Q的活动记录Main的活动记录全局数据SPTOP静态分配9.4简单的栈式存储分配4、指示器SP——总是指向现行过程活动记录的 起点，用于访问局部数据

指示器TOP——始终指向（已占用）栈顶单元9.4简单的栈式存储分配一、C的活动记录

1、C的活动记录的项目（1）连接数据——A、老SP值:

即前一活动记录的地址

B、返回地址（2）参数个数（3）形式单元——存放实在参数的值或地址（4）过程的局部变量临时工作单元内情向量简单变量形式单元参数个数返回地址老SPTOPSP9.4简单的栈式存储分配2、（1）不允许过程嵌套——非局部量仅能出现在源程 序头，可采用静态存储分配，编译时可确定其地址

（2）局部变量或形参在活动记录中的位置确定 其地址是相对于活动记录的基地址SP的

绝对地址=活动记录基地址+相对地址

变址访问X[SP]X——代表相对数，即相对于活动记 录起点的地址，编译时可完全确定下来9.4简单的栈式存储分配二、C的过程调用，过程进入、数组空间分配和过程返回已知过程调用的四元式序列为：parT1

… parTn callP,nC语言过程调用与返回ParTi(i+3)[TOP]:=Ti（传值）或(i+3)[TOP]:=addr(Ti)（传地址）CallP,n1[TOP]:=SP3[TOP]:=nJSRP(转P)SP:=TOP+11[SP]:=返回地址TOP:=TOP+活动单元数Return(E)TOP:=SP－1SP:=0[SP]X:=2[TOP]UJ0[x]/*UJ:无条件转移*/9.5嵌套过程语言的栈式实现前提：假定允许过程定义嵌套，如Pascal语言，但去掉Pascal中的“文件”类型

程序举例：——课本P258图9.159.5嵌套过程语言的栈式实现一、非局部名字的访问的实现说明——非局部名字的访问

1、静态链和活动记录

A、静态链——活动记录的一个域，从一个过程的当前活 动记录指向其静态直接外层的最新活动记录。

动态链——活动记录一个域，从一个过程的当前活动 记录指向调用该过程前正在运行的过程的最新 的活动记录的基地址。B、活动记录结构——P259图9.16形式单元参数个数静态链动态链（老SP）返回地址简单变量内情向量临时工作单元SPTOPprogramP;vara,x:integer;

procQ(b:integer);vari:integer;

procR(u:integer,varv:integer);varc,d:integer;begin…end;begin…end;

procS;varc,i:integer;begin…end;begin…cP;

procQ;procR;begin…R(..,..);…end;

begin…R(…,…)…end;

procS;

begin…

Q(…)

…end;begin…

S;…end.

01234567890返回地址0ax0返回地址00（形参个数）csptopi10sptopC、程序运行时栈的变化过程——举例：ib(形参)1(形参个数)0返回地址5ic00返回地址0xa0返回地址0ic0(形参个数)0返回地址0xa0返回地址0过程P中调用S时161514131211109876543210SPTOPTOPSP109876543210过程S中调用Q时dcv(形参)u(形参)2(形参个数)11返回地址11ib(形参)1(形参个数)0返回地址5ic00返回地址0xa0返回地址0TOPSP1211109876543210242322212019181716151413过程Q中调用R时dcvu211返回地址17dcv(形参)u(形参)2(形参个数)11返回地址11ib(形参)1(形参个数)0返回地址5ic00返回地址0xa0返回地址032313029282726252423222120191817161514131211109876543210SPTOP过程R中递归调用R9.5嵌套过程语言的栈式实现D、含义：

静态链：通过其值可以找到当前过程/活动可以引用的“非局部变量”的过程的活动记录的基址，从而找到要引用的“非局部变量”

动态链：通过其值可以找到当前过程/活动结束后，需要返回的上一层活动记录的基址SP9.5嵌套过程语言的栈式实现2、嵌套层次显示表（display）和活动记录

A、嵌套层次显示表：每进入一个过程后，在建立它的活动区的同时建立该表

B、表的内容：假定现进行的过程的层数为i，则其display

含有i+1个单元。该表本身是一个小栈，自顶向 下每个单元依次存放现行层，直接外层……,直 到最外层（0层主程序层）等每一层过程的最新 活动记录的基地址。举例：令过程R的外层为Q，Q的外层为P，则R运行时display表为2R的现行活动记录地址（SP的现行值）1Q的最新活动记录的地址0P的活动记里的地址9.5嵌套过程语言的栈式实现C、“非局部量”地址的确定：

绝对地址=display[静态层数]+相对地址D、活动记录结构：TOPa321SP0临时单元内情向量简单变量display形参单元参数个数全局Display返回地址老SP(动态链)p1调用P2的两种不同嵌套：P1P2P0P2P1k-1kk-1kkp1调用P2的两种不同嵌套：P1P2k-1k…DisplayK项………P1P2P1的displayk项p2的sptopsptopspp1调用P2的两种不同嵌套：P0P2P1k-1kk…DisplayK+1项………P1P2P1的display前k项p2的sptopsptopsp00返回地址10（display)2a3x405返回地址62(全局display)70(形参个数)809510C11i12sptoptopspdisplayF、静态链方法与显示表方法的比较： 通过向示表访问非局部量要比沿着静态链访问非局部量的速度快。

原因：——因为通过显示表的一个域，可以确定任意 外层活动记录的指针，再沿着这个指针便可 以找到处于外层活动记录的非局部量。9.5嵌套过程语言的栈式实现二、参数传递的实现

1、parT T——为数组 （1）或者传递数组T的首地址 （2）或者传递数组T的内情向量地址

2、ParT T——为过程 假设：过程P把过程T作为实在参数传递过程Q，随 后，Q又通过引用相应的形式参数调用T。

3、Par T——为标号⇒在进入T之后，为了建立T自己的display，T必须知道它直接外层的display。又P的display或者正好就是这个外层的display， 或者包含了这个外层display而由于T的层数是已知的⇒只要知道P的display，T就可以用它来建立自己的display，即假定T的层数为1，则T的display乃是由P的display的前1个单元的内容和SP的现行值所组成。⇒为了使得过程T工作时能够知道过程P的display，必须在P把T作为使 参传递给Q的时候把P自身的display地址也传过去即：过程P中的parT的作用可刻画为建立如下所示的两个相继临时单元：

第一个临时单元B1：过程T的入口地址

第二个临时单元B2：过程T的display地址。；然后执行（i+1）[TOP]:=addr(B1)把第一临时单元B1的地址传给Q假定过程Q现在执行到调用语句callZ,mZ——形式参数，形式单元Z中已含有上述B1的地址⇒故B1的内容将用来作为转子指令的目的地址 （即转进过程T）

B2的内容将作为“全局display地址” （第三项连接数据）传送给T9.6堆式动态存储分配1、堆式动态存储分配使用的情况（1）允许用户自由地申请数据空间和退还空间（2）不仅有过程而且有进程的程序结构 即空间的使用未必服从“先请后还，后请先还”的原则

例如：pascal语言中的标准过程new-dispose2、该种分配方法必须考虑的几个主要问题（1）当运行程序要求一块体积为N的空间时，我的应该分配那一块给它？（2）如果运行程序要求一块体积为N的空间，但所有空闲 块的总和也不够N，那该怎么办？9.6堆式动态存储分配一、堆式动态存储分配的实现

1、定长块管理

（1）实现方法：

（2）优点：

2、变长块管理

（1）实现方法

（2）实现的分配策略 首次满足法