9运行时存储空间组织.pptx

1第九章 运行时的存储空间组织关于源程序的一些问题v我们编写的源程序实际上是静态的程序文本；v它们的目的是要在计算机上正确的运行；v在运行过程中，这些静态程序文本必须与程序运行时的活动状态联系在一起，才能实现程序的目的；v程序运行时，源程序文本中的标识符对应运行时的不同数据对象；v数据对象的空间分配和释放需要管理策略，这些策略由运行的支撑程序包运行管理。v这就是编译程序要完成的运行环境和存贮管理。关于源程序的一些问题v源程序可以由不同的过程组成；v在执行过程中，过程过程的每次执行称为过程的一个活动活动。v如果这个过程设计为递归调用过程，那么，则会在某一个时刻可能有它的几个活动都活跃着；v过程的每一次调用，都会引起一个活动，这个活动就会调用编译软件的存贮管理的软件包给活动的数据对象分配相应的数据空间；关于源程序的一些问题v过程过程过程定义过程定义是一个声明，它的最简单形式是把一个标识符和一个语句联系起来；标识符是过程名；语句是过程体；过程调用过程调用表现为过程名出现在执行语句中；如果过程调用出现在表达式表达式中，则这个过程就是函数，这个调用就是函数调用函数调用；v函数函数是特殊的过程，它是具有一个返回值的过程；v其实一个完整的程序程序就是一个过程；v过程参数形式参数形式参数：过程定义中表明的标识符；实在参数实在参数：过程调用中表明的标识符；在过程调用中，实在参数要取代形式参数；v这需要编译程序的运行环境存贮空间管理；这需要编译程序的运行环境存贮空间管理；关于源程序的一些问题v活动树活动树每次过程的调用都会产生一个活动；过程的调用可能会嵌套或者递归，这时可能会有多个活动同时活跃，活动树产生了！v控制流控制流程序执行时过程的调用是按照一定的步骤和顺序实施的，这就是所谓的控制流；控制流是连续的。程序的执行由一些连续的步骤组成的，在任何一步，控制都处于程序中的某点；过程的每次执行都从过程体的起点开始，最后控制返回到直接跟随本次调用点的位置；v过程间控制流的特点为活动树产生和应用提供了条件；关于源程序的一些问题v活动的生存期：活动的生存期：是过程执行的第一步和最后一步之间的步序列，包括消耗在执行被这个过程所调用的其他过程所用的时间，以及再由那些被调用过程又调用别的过程所用的时间，以此类推。v不同过程的活动生存期可能重叠，这时就出现了所谓的递归和嵌套等。关于源程序的一些问题v递归递归如果一个过程的前一个活动结束前，它的一个新的活动又开始，则这样的过程是递归的；递归过程不必直接调用自己，过程p可以调用另一个过程q，然后q通过一系列过程调用之后再调用了p，这也是递归调用；v活动树活动树描述控制进入和离开活动的方式可以用一棵树的方式，这就是活动树；活动树的每一个结点代表了过程的一个活动；根结点代表主程序的活动；结点a是结点b的父结点，当且仅当控制流从a的活动进入b；a结点处于b结点的左边，当且仅当a的生存期先于b的生存期；结点和活动是一一对应的，所以控制结点就是控制活动。读入整数并排序的Pascal程序vProgram sort(input,output);Program sort(input,output);var a:array0.10 of var a:array0.10 of integer;integer;Procedure readarray;Procedure readarray;vVar i:integer;Var i:integer;vBeginBeginFor i:=1 to 9 do For i:=1 to 9 do read(ai)read(ai)vEnd;End;Function Function partition(y,z:integer):intpartition(y,z:integer):integer;eger;vvar i,j,x,v:integer;var i,j,x,v:integer;vBeginBeginvEnd;End;见书P240Procedure quicksort(m,n:integer);Var i:integer;Begin If(nm)then begin i:=partition(m,n);Quicksort(m,i-1);Quicksort(i+1,n);end;End;Begin a0:=-9999;a10:=9999;readarray;quicksort(1,9)End.关于源程序的一些问题srq(1,9)q(5,9)p(1,9)q(1,3)q(2,3)P(1,3)q(1,0)q(3,3)P(2,3)q(2,1)q(7,9)p(5,9)q(5,5)q(9,9)q(7,7)p(7,9)活动树活动树1010.0概述v在代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配。v编译程序需要一定的存贮空间以使目标程序在其上运行，该存贮空间需容纳生成的目标代码和目标代码运行时的数据空间。v数据空间包括数据空间包括：用户定义的各种类型的数据对象（变量和常量）所需的存贮空间；作为保留中间结果和传递参数的临时工作单元；调用过程时所需的连接单元；组织输入/输出所需的缓冲区。v编译过程中，有些数据对象所占用的空间可可以确定以确定，有些数据对象具有可变体积和待编译性质，无法在编译时确定无法在编译时确定存贮空间的位置。v作为运行时存贮分配的一个原则是尽可能对数据对象进行静态分配。1210.0概述存贮空间常常划分为：目标代码区、静态数据区、栈区、堆区。目标代码区用以存放目标代码，是固定长度，编译时能够确定。静态数据区用以存放编译时能确定所占用空间的数据。堆栈区用于可变数据以及管理过程活动的控制信息。存贮组织要解决的问题是把静态的源程序与该程序的目标程序运行时的动态活动联系起来，即要搞清楚运行中的程序信息是如何进行存贮和访问的。codeStatic datastack(可变区域)heap所谓数据空间分分配配，本质上看，是将程序中的每个名字与一个存贮位置关联起来，该存贮位置用以容纳名字的值。源语言的结构特点、源语言的数据类型、源语言中决定名字作用域的规则等因素影响存贮空间的管理和组织的复杂程度，决定数据空间分配的基本策略。名字（标识符）存贮位置值环境状态1410.1 10.1 数据空间的三种不同使用方法和管理方法数据空间的三种不同使用方法和管理方法数据空间的使用和管理方法从大类分为两种：静态和动态静态和动态。而动态又分为：栈式和堆式两栈式和堆式两种种。静态存贮分配策略静态存贮分配策略：如果在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存贮位置。动态存贮分配策略动态存贮分配策略：目标程序在运行时所需要的数据空间，在编译时无法知道，它所需要的数据空间的大小要待程序运行是动态地确定。有两种存贮分配方式：栈式栈式和堆式堆式。栈式存贮栈式存贮：1、将整个程序的数据空间设计为一个栈；2、每当调用一个过程时，它所需的数据空间就分配在栈顶，每当过程工作结束时就释放这部分空间；3、过程所需数据空间包括两部分：一部分是本次调用中的数据对象；另一部分是用以管理过程活动的记录信息；4、当控制从调用返回时，便根据栈中记录的信息恢复机器状态，使该过程的活动继续进行。堆式存贮堆式存贮：1、自由地申请数据空间和退还数据空间；2、数据空间的利用不服从“先申请后释放，后申请先释放”的原则；3、这种存贮方式空间的利用率可能受到限制。容易产生碎片。1610.2 10.2 栈式存贮分配的实现栈式存贮分配的实现栈式存贮分配的基本策略是调用一个过程时在栈顶分配所需数据空间，返回时，在栈顶释放数据空间。过程的活动记录过程的活动记录是一段连续的存贮区，用以存放过程的一次执行所需要的信息。信息包括：1.1.临时工作单元临时工作单元：计算表达式过程中需要存放中间结果用的临时值单元；2.2.局部变量局部变量：一个过程的局部变量；3.3.保存机器状态保存机器状态：容纳该过程执行前关于机器状态的信息，如程序计数器、寄存器的值等；4.4.存取链存取链：用以存取非局部变量，这些变量存放于其他过程活动记录中。（所谓链，实际上是链接，包所谓链，实际上是链接，包含指针含指针）；5.5.控制链控制链：指向调用该过程的那个过程的活动记录；6.6.实参实参：形式单元。由调用过程向该被调用过程提供实参的值；7.7.返回地址返回地址：保存该被调用过程返回后的地址。临时工作单元局部变量机器状态信息存取链控制链实参返回地址1710.2.1 简单的栈式存贮分配的实现简单的特征是：没有分程序结构，过程定义不嵌套，允许过程递归调用。存贮空间的分配策略存贮空间的分配策略：运行时，每当进入一个过程时，则为该过程分配一段存贮空间，当一个过程工作完毕后返回时，它所占用的存贮区则释放。程序在运行时，存贮空间（栈）中在某一个时刻可能会包含不同过程的几个活动记录；可能会包含某个过程的几个活动记录（递归调用）。同一个存贮位置，不同的运行时刻分配给不同的数据对象。在栈的最顶端数据区有两个指针：SP总是指向现行过程活动记录的起点；TOP总是指向占用的栈顶单元。Program main;全局变量或数组的说明；proc R;end(R);proc Qend(Q)主程序执行语句end.(main)1810.2.1 简单的栈式存贮分配的实现R的活动记录Q的活动记录主程序全局数据区R的活动记录Q的活动记录主程序全局数据区Q的活动记录主程序全局数据区主程序全局数据区TOPSP控制链（老SP）返回地址参数个数实参（形式单元）局部简单变量局部数组的内情向量临时工作单元TOPSP主程序全局数据区Q的活动记录R的活动记录R的数组区TOPSPR的活动记录（）19ib(形参)1(形参个数)0返回地址5ic00返回地址0 xa0返回地址0ic0(形参个数)0返回地址0 xa0返回地址0过程过程S中调中调用用Q时时161514131211109876543210SPTOPTOPSP109876543210过程过程P中中调用调用S时时（）20dcv(形参)u(形参)2(形参个数)11返回地址11ib(形参)1(形参个数)0返回地址5ic00返回地址0 xa0返回地址0TOPSP1211109876543210242322212019181716151413过程过程Q中调用中调用R时时（）21dcvu211返回地址17dcv(形参)u(形参)2(形参个数)11返回地址11ib(形参)1(形参个数)0返回地址5ic00返回地址0 xa0返回地址032313029282726252423222120191817161514131211109876543210SPTOP过程过程R中递归调用中递归调用R22主要特点主要特点：（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）；（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据；必须设法跟踪每个外层过程的最新活动记录的位置。关键技术关键技术：嵌套过程主要解决对非局部变量的引用问题嵌套过程主要解决对非局部变量的引用问题。跟踪的办法有两种跟踪的办法有两种：一种是在过程活动记录中增设存取链，指向包含该过程的直接外层过程的最新活动记录的起始位置；另一种是每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表display。存取链和控制链分别是存取非局部变量和指定直接外部过程。嵌套层次嵌套层次：指过程定义的层数。Display是一个数组，也可以看作为一个小栈。自顶向下每个单元依次存放着现行层、直接外层、最外层等每一层过程的最新活动记录地址。10.2.2嵌套过程语言的栈式实现嵌套过程语言的栈式实现23举例举例程序中过程定义的嵌套情况Sort看成整个程序的最外层。过程readarray、exchange、quicksort是次外层。过程partition是最内层。在过程readarray、exchange和partition中引用的a均不是它们的局部变量，而是过程sort的局部变量。这就遇到了一个非局部变量的存取问题。必须设法跟踪每个外层过程的最新活动记录的位置。Sort readarray exchange quicksort partition24举例举例过程sort调用过程quicksort。动态栈的存贮情形如下图Quicksort过程活动记录中斜线描述的存贮单元用以记录过程quicksort 引用过程sort中的变量a和x。如何引用呢？通过指针！在这个单元中设置存取链，指向包含该过程的直接外层过程的最新活动记录的其始地址。局部变量k,v 局部变量a,x 可以引用的过程sort的局部变量过程quicksort的活动记录过程sort的活动记录局部变量.存取链控制链TOPSP25sort quicksort quicksort partition exchangesort quicksort quicksort partition exchange变量a,x控制链存取链局部变量k,v控制链存取链局部变量k,v控制链存取链局部变量y,z控制链存取链局部变量i,jExchangeExchange的活动记录的活动记录partitionpartition的活动记录的活动记录quicksortquicksort的活动记录的活动记录quicksortquicksort的活动记录的活动记录sortsort的活动记录的活动记录存取链指向直接外层存取链指向直接外层控制链指向调用过程控制链指向调用过程26Display表每进入一个过程时，在建立它的活动记录的同时建立一张嵌套层次显示表display。嵌套层次就是过程定义的层数。层数作为过程的属性登记在过程的符号表中。display是一个指针数组，也可以看作是栈。从顶往下每个单元依次存放着现行层、直接外层、直到最外层（0层，即主程序层）等每层过程的最新活动记录的地址。嵌套层次i的过程的局部变量局部变量a是由display元素i所指的那个活动记录中存放的。嵌套层次i+1过程中的非局部变量非局部变量可能在i，i-1，.，0层，对它的存取是通过display元素的di,di-1,.,d0而获得的。27Qicksort的活动记录Sort的活动记录TOPSPd1d0displayQicksort的活动记录（现行）Qicksort的活动记录(第一次)Sort的活动记录TOPSPd1d0displaysortquicksort.调用过程sortquicksortquicksort.调用过程动态运行栈和 Display非局部变量跟踪28动态运行栈和 Display非局部变量跟踪Partition的活动记录Qicksort的活动记录（现行）Qicksort的活动记录(第一次)Sort的活动记录TOPSPd2d1d0displayExchange的活动记录Partition的活动记录Qicksort的活动记录（现行）Qicksort的活动记录(第一次)Sort的活动记录TOPSPd2d1d0displaysortquicksortquicksortpartition exchange.调用过程sortquicksortquicksortpartition.调用过程29Display表vDisplay本身的体积在编译时可确定。vDisplay本身作为单独的表分配存贮。vDisplay本身作为活动记录的一部分。3010.3 基于堆的动态存贮分配如果程序设计语言允许用户动态地申请和释放存贮空间，而且申请和释放之间不是遵循“后申请先释放，先申请后释放”的原则，即可以在任何时间以任意的顺序来进行，则采用堆式动态存贮分配。基本思想是基本思想是：假设程序运行时有一个大的空闲存贮区，称之为堆。每当程序提出申请时，就按照某种分配原则在堆中可使用区寻找一块能满足需求的存贮空间分配给它。对于释放操作，则将程序不再占用的存贮空间归还给堆，使之变为空闲区。堆式存贮管理实现方法是堆式存贮管理实现方法是：首先将堆的存贮空间划分为若干个存贮块，块可以等长，也可以是不等长。当用户程序运行时，随机地根据活动的开始和完成，分别对堆申请或释放一个或多个存贮块。当程序运行一段时间后，堆中的存贮块会动态地分成两组，一组是被占用的存贮块，另一组是未被分配的存贮块。在C语言中链表、树等数据结构通常采用堆式动态存贮分配。3110.3 基于堆的动态存贮分配如果设当前堆中空闲块总长度为M，程序需要申请的存贮空间为n。则堆式存贮管理步骤如下：1.若当前有若干空闲块的长度均大于或等于n，则直接按照下列策略之一进行存贮分配：从 free所指的首节点开始，查找出一个其长度m满足m=n的空闲块，并将该空闲块长度为n的子块分配给用户程序，而将长度为m-n的剩余部分仍然放在自由链中，修改链指针和长度信息。在链中查找一个长度满足需要的最大空闲块进行分配。在链中查找一个长度满足需要，且其长度最接近n的空闲块进行分配。2.若链中所有空闲块的长度均小于n，但是这些空闲块的总长度M满足M=n，此时可将空闲块在堆中进行汇集或重组，以便形成一个长度满足需求的新的空闲块进行分配。3.当nM时，不能满足需求。3210.3 基于堆的动态存贮分配对于释放一个存贮块，只要将它作为新的自由块重新插入自由链中，并删除使用块信息表中的记录。因为申请和释放是交错进行，因此，使用块和空闲块会交错分布。要对使用情况进行记录，通过管理方法使得空闲块汇集，提高使用效率，避免碎片出现。free使用块信息3310.4 参数传递v当一个过程调用其他过程时，调用过程和被调用过程之间的通信经由非局部量或经由参数传递。v过程调用，实际上是形式参数按照什么方式与实在参数关联过程调用，实际上是形式参数按照什么方式与实在参数关联。v形实参对应的方法常有：值调用、地址调用、名字调用以及宏扩展等。也就是说传值、传地址、传名等。v形实参对应实际上就类似于赋值语句，“=”左边为为存贮位置，右边为存贮位置中存放的值。v参数传递方法的不同主要基于实在参数是表达式是一个右值、一个左值，还是实在参数本身的文字（名）。3410.4.1 传值传值：也称值调用。即将实参计算出它的值，然后把它传给传值：也称值调用。即将实参计算出它的值，然后把它传给被调用过程被调用过程。1.形式参数当作过程的局部变量处理，即在被调用过程的活动记录中开辟了形式参数的存贮空间。2.调用过程计算实参的值，并将它们的右值放在形式单元开辟的空间中。3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。传值的重要特点是对形式参数的任何运算不影响调用过程的活动记录中实参的值。3510.4.2 传地址v传地址：当参数通过引用传递时，也称做传地址，或引用调用。传地址：当参数通过引用传递时，也称做传地址，或引用调用。v调用过程传递给被调用过程的是指针，指向实参存贮位置的指针。如实参是一个名字或是具有左值的表达式，则左值本身传递过去。如实参是一个表达式，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去。被调用过程中对形式参数的任何引用和赋值都通过传递到被调用过程的指针被处理成间接访问。