第10章 存储组织

1第十章存储组织10.1概述10.2数据空间的管理10.3栈式动态存储分配的实现10.4参数传递10.5跟过程相关的语义分析210.1概述•操作系统分配给目标程序运行所需的内存空间•此内存空间的具体使用由编译程序在语义分析阶段确定•此内存空间分为两大部分：代码段、数据段•数据段包括（P231）代代码码段段静静态态数数据据段段运运行行栈栈堆堆310.2数据空间的使用方法存储分配策略：静态存储分配栈式动态存储分配堆式动态存储分配4静态存储分配•特点–编译时刻确定存储位置–访问效率高•主要用途–子程序的目标代码段–全局数据目标（全局变量）10.2数据空间的使用方法5栈式存储分配•把程序看作由多个过程（子程序、函数等）组成•每进入一个过程，在栈顶为它分配所需的数据空间；•当一个过程工作完毕之后，相应的数据空间将被释放。主程序AR活动记录活动记录活动记录运行栈图示10.2数据空间的使用方法过程1过程2过程3过程06堆式存储分配•用于动态数据结构–存储空间的动态分配和释放•实现方法：–将内存空间分为若干块，根据用户要求分配–无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配10.2数据空间的使用方法7对过程的语义处理•过程说明的翻译–计算实在参数、返回值的空间•过程体的翻译–计算局部变量、临时变量的空间10.3栈式动态存储分配的实现过程的活动记录AR（ActivationRecord）•一段连续的存储区，用以存放过程的一次执行所需的信息。8程序由过程组成，当过程被激活时，在运行栈的栈顶设置相应的AR：临时值：例如计算表达式时的中间工作单元。局部变量（数据）保存运行过程前的状态（程序计数器，寄存器值……）存取链（可选）：对于非局部量的引用。控制链(老SP)（可选）：指向调用者的AR。实参（形式单元）返回值（对函数），有时可使用寄存器存放返回值返回地址：保存该被调过程返回后的地址9简单语言的分配方案语言的结构特点：过程可递归调用不允许嵌套定义没有分程序结构允许可变数组(P234图10.7；见右例)例:main全局变量的说明procR……endR;procQ……endQ;主程序执行语句endmain10.3栈式动态存储分配的实现10MainQRMainQQR的活动记录Q的活动记录主程序全局数据区TOPSPSPSPTOPQ的活动记录SPQ的活动记录主程序全局数据区SPSP10.3栈式动态存储分配的实现Q之AR全局数据区TOPSPR之AR全局数据区MainQR退出ＱMain11R的活动记录Q的活动记录主程序全局数据区TOPSPR的数组区10.3栈式动态存储分配的实现临时工作单元局部简单变量局部数组的内情向量调用前的状态实参和参数个数控制链（老SP）TOPSP返回地址老SP：指向调用者的AR起始位置R的活动记录假如R含有可变数组12例（P236图10.11）sortvara;readarray;…a…;exchange;quicksort;partition;…a…;exchange;quicksort;……嵌套过程语言的分配方案语言主要特点：一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。10.3栈式动态存储分配的实现过程012问题：如何引用非局部标识符？实现方法：一个过程可以引用它的任一外层过程的最新AR中的某些数据。13关键技术：解决对非局部变量的引用(存取)也就是说，设法跟踪每个外层过程的最新活动记录AR的位置。跟踪办法：1.存取链。2.DISPLAY表。10.3栈式动态存储分配的实现14－－－指向定义该过程的直接外层过程（或主程序）运行时最新活动记录的基地址。（例如：PL/0）注意与控制链（又名动态链SP）相区别：－－－控制链指向调用者的AR，存取链指向定义者的AR。－－两链的指向位置有可能相同，也可能不同。10.3栈式动态存储分配的实现存取链（SL），又名：静态链(PL/0)P237图10.13、图10.14、图10.1515嵌套层次显示表（Display表）display是一个指针数组d，自顶向下，每个单元依次存放现行层、直接外层……直至最外层（0层）的每一层过程的最新活动记录的基地址。10.3栈式动态存储分配的实现d[0]存第0层d[1]1d[2]2……d[n]nSP0SP1SP2d[0]d[1]d[2]display160老SP1返回地址2全局DISPLAY地址3参数个数4形式单元...ddisplay...简单变量数组内情向量临时变量当过程的层次为n，它的display为n+1个值。一个过程被调用时，从调用过程的display表中自下向上抄录n个SP值，再加上本层的SP值。全局display地址10.3栈式动态存储分配的实现各个过程的display存放在自己的AR中17例：programmain(i,0);程序结构图……procR(c,d);……Rend/*R*/procP(a);主……procQ(b);……PQcallRR(x,y);end/*Q*/callQ……Q(z);callPend/*P*/……callRP（W）；……R（U，V）；……end/*main*/10.3栈式动态存储分配的实现18用Display表的方案(1)主程序---(2)P---(3)Q---(4)R主程序的活动记录d[0]spdisplaytop（1）P的活动记录主程序的活动记录d[1]d[0]displaysptop（2）10.3栈式动态存储分配的实现19用Display表的方案主程序---(2)P---(3)Q---(4)RR的活动记录Q的活动记录P的活动记录主程序的活动记录d[1]d[0]displaytopsp（3）（4）Q的活动记录P的活动记录主程序的活动记录displayd[2]d[1]d[0]sptop10.3栈式动态存储分配的实现20分程序结构ProcedureA(m,n);integerm,n;B1:beginrealz;arrayB[m:n];B2:beginreald,e;L3:end;B4:beginarrayC[1:m];B5:beginreale;L6:end;end;L8:end;10.3栈式动态存储分配的实现21分程序结构的存储分配方案方法之一：把分程序看成“无名无参过程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但极为低效：1）每逢进入一个分程序，就照样建立连接数据和DISPLAY表,这是不必要的。2）对于多层嵌套的分程序，当从内层分程序向外层转移时，可能要同时结束若干层分程序。10.3栈式动态存储分配的实现22按照过程处理办法，意味着必须一层一层地通过“返回”来恢复所要到达的那个分程序的数据区，但不能直接到达。例如：如果有一个从第5层分程序转出到达第1层分程序的标号L，虽然在第5层分程序工作时知道L所属的层数，我们极易从display中获得第1层分程序的活动记录基址（SP），但是怎么知道第1层分程序进入时的TOP呢？唯一的办法是从5,4,3和2各层顺序退出。但这种办法是很浪费时间的。10.3栈式动态存储分配的实现23为了解决上述问题，可采取两种措施：第一，对每个过程或分程序都建立有自己的栈顶指示器TOP，代替原来仅有过程的栈顶指示器,每个TOP的值保存在各自活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作“无参过程”，每个分程序享用包围它的那个最近过程的display。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。10.3栈式动态存储分配的实现24：每个过程被当作是0层分程序。而过程体分程序（假定是一个分程序）当作是它所管辖的第1层分程序。这样，每个过程的活动记录所含的内容有：1.过程的TOP值，它指向过程活动记录的栈顶位置。2.连接数据，共四项：(1)老SP值；(2)返回地址；(3)全局display地址；(4)调用时的栈顶单元地址，老TOP。10.3栈式动态存储分配的实现253.参数个数和形式单元4.display表。5.过程所辖的各分程序的局部数据单元，对于每个分程序来说，它们包括：（1）分程序的TOP值。当进入分程序时它含现行栈顶地址，以后，用来定义栈的新高度（分程序的TOP值）；（2）分程序的局部变量，数组内情向量和临时工作单元。10.3栈式动态存储分配的实现26变量eB5的TOP数组C的内情向量变量e和dB4的TOPB2的TOP数组B的内情向量变量zKB1的TOPDDISPLAY6形式单元m,n5参数个数：24调用时的栈顶地址（老TOP）3全局DISPLAY地址2返回地址1老SP0过程的TOP，指向活动记录之顶27B的内情向量ZB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(a)(b)(a)到达标号B1处;(b)进入分程序B1;28数组B数组BedB2的TOPB的内情向量B的内情向量zzB1的TOPB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(c)(d)(c)数组B分配之后；（d）进入分程序29数组C数组C数组B数组BC的向量内情eB5的TOPC的内情向量B4的TOPB4的TOPB的内情向量B的内情向量zZB1的TOPB1的TOPDISPLAYDISPLAY形式单元m,n2形式单元m,n2连接数据连接数据A的TOPA的TOP∶∶∶∶(e)(f)(e)进入分程序B4分配数组C之后；(f)进入分程序B5。3010.4过程调用的参数传递(1)procedureexchangel(i,j:integer);(2)varx:integer;(3)begin;(4)x:=a[i];a[i]:=a[j];a[j]:=x(5)end;带有非局部变量和形参的PASCAL过程非局变量a[i]和a[j]的值进行交换，i,j为形参（在这里是传值）31(1)programreference(input,output);(2)vara,b:integer;(3)procedureswap({var}x,y:integer);(4)vartemp:integer;(5)begin(6)temp:=x;(7)x:=y;(8)y:=temp(9)end;(10)begin/*reference*/(11)a:=1;b:=2;(12)swap(a,b);(13)writeln(‘a=‘,a);writeln(‘b=‘,b)(14)end./*swap*/10.4过程调用的参数传递过程参数以传地址方式被调用的PASCAL程序32•传地址（变量参数）例如：过程swap(varx,y:integer);swap(a,b）；（a,b为调用时的实参）调用结果a,b的值被改变。•传值（值调用）例如：过程swap(x,y:integer);特点是对形式参数的任何运算不影响实参的值。swap(a,b）；其结果：a,b调用前的值不改变。10.4过程调用的参数传递33传值的实现1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。2.调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。10.4过程调用的参数传递34procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；调用swap(a,b)过程将不会影响a和b的值。其结果等价于执行下列运算：x:=a；y:=b；temp:=x；x:=y；y:=temp10.4过程调用的参数传递35传地址的实现把实参的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参：1、实参是一个名字，或具有左值的表达式——传递左值2、实在参数是