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

第九章运行时存储空间的组织和管理一、数据的存储单元编译程序必须为目标程序的运行分配数据的存储单元。如：变量、常量单元，临时工作单元，返回地址若无存放数据信息的单元，则目标程序将无法运行。二、存储单元分配策略1、静态存储分配在编译时就可以完全为数据项目分配存储单元，称为静态存储分配。注：若一个程序设计语言不允许递归调用，而且不含有可变数组，则可使用静态存储分配策略。2、动态存储分配在运行时才能进行数据存储单元分配，称为动态存储分配。注：1)若某程序设计语言允许过程递归调用，而且允许使用可变数组，那么在编译时就不可能完全为其数据项目分配存储单元，必须采取动态存储分配策略。2)动态分配数据单元时一般使用：栈式存储分配堆式存储分配2、动态存储分配（1）栈式存储分配运行时，每进入一个过程，就在栈顶为该过程分配一块数据区，一旦退出该过程，它所占的空间也退还给系统。（2）堆式存储分配有些语言允许用户随时动态地申请和释放存储空间，但申请和释放之间不遵守先申请后释放或后申请先释放原则，故不能使用栈式存储分配，而是更复杂的动态分配策略。这种策略是：让运行程序持有一个大的存区（堆），在申请时从堆中取一块，释放时将一块存储区退还给堆。栈式存储管理一、允许过程(函数)递归调用的数据存储管理1、语言特点允许过程（函数）的递归调用，但不允许定义嵌套的过程（函数），也不许使用可变数组。如C语言。2、栈式存储分配：每进入一个过程，就有相应的数据区建立在栈顶。当程序开始运行前，用于建造数据区的栈是空栈。当开始进入主程序执行语句前，便在栈中建立全局变量和主程序数据区。在主程序中若有调用过程的语句时，便在栈顶累筑该过程的活动记录。在进入过程后执行过程的可执行语句前再把局部数组累筑于栈顶，若还有调用过程的语句就重复上述过程。例如有如下程序：MAIN(){……callQ();}P(){……}Q(){……callP();}当P过程进入运行后，栈顶数据区有两个指针：SP指向现行过程数据区起点；TOP指向顶点注：从数据区中引出指向主程序数据区的箭头表示外部变量引用关系。3、活动记录：包含连接数据、形式单元、局部变量、内情向量和临时工作单元等。注：1)活动记录的建立是按照调用次序而累筑，而非排列次序；2)栈顶活动记录数据区有两个指针SP和TOP，SP指向现行数据区起点，TOP指向顶点；3)从数据区中引出指向主程序数据区的箭头表示外部变量引用关系；4)C语言的活动记录所含区段是：连接数据(包含老SP值(即前一活动记录的首地址；或称施调过程的数据区首地址)和返回地址(即调用语句的下一条指令的地址))、参数(形参)个数、形式单元(存放实参值或地址)、过程的局部变量(简单变量)、数组内情变量和临时工作单元。5)过程中的局部变量(简单变量)在内存地址可表示为变址形式x[SP]，其中SP为当前数据区首地址，用作变址值，x称为相对位移量。连接数据：老SP值：前一活动记录的首地址（施调过程的数据区首址）；返回地址；简单变量X在数据区内相对地址设为x，则，x的内存地址表示为变址形式x[SP],SP为当前数据区首址，x为相对位移量。4、C语言的数据区建立与撤销1)过程调用段：Call语句翻译成中间代码后所作操作有两个：将参数传递到过程或函数的数据区的形参单元中；跳转到过程或函数。例如：callQ(T1,T2,…,Tn)语句的中间代码为：ParT1…ParTnJsrn,Q注：C语言的数据区是由过程调用引起2)过程进入段工作：定义新活动记录的SP，保护返回地址和定义这个活动记录的TOP,即：SP:=TOP+11[SP]:=返回地址TOP:=TOP+L/*L是过程Q的活动记录所需单元数*/3)过程返回段（1）假定此时E的值已经计算出来并已放在某临时单元T中，那么就将T值传送到某个特定的寄存器中，以备调用段获取(调用段将从此寄存器获得被调用过程的结果值)；（2）恢复SP和TOP，以便回到调用段的数据区。TOP:=SP-1；SP:=0[SP](3)按返回地址回到调用语句的下一语句去继续运行。X:=2[TOP]；Jmp0[X]注：若是过程调用，则不必回送结果，其他相同。二、嵌套过程语言的栈式存储管理1、语言特点既允许过程嵌套，也允许过程递归调用。2、存储管理方式1)根据嵌套过程语言的规定，由变量的最小作用域原则，一个过程可以引用包围它的任意外层过程所定义的变量和数组。所以，运行时过程必须知道它所有直系外层过程的最新活动记录的地址。2)由于允许递归，过程活动记录的位置是动态变化的。因此，每个活动记录中必须设法记住直系外层的最新活动记录的位置，以处理递归。3、解决方案使用层次显示表display1）内容：每进入一个过程，在建立其活动记录区的同时，为它建立一张层次显示表，以登记它所有直系外层最新活动记录的首址和本过程活动记录的首址注：(1)直系外层是指从0层开始直到当前过程，即当前过程的所有直系祖先；(2)可将本过程display表放在其活动记录中的形式单元之上(3)也可将全局display地址存储在本过程的活动记录中(在返回地址之上)。(4)因为当前过程的层数是确定的，所以它的display表也是确定的。(5)由于每个过程的形参单元的数目在编译时是完全确定的,所以display表的相对地址d在编译时也是完全确定的。2)Pascal语言的活动记录4、直系外层中变量的引用假定现行过程中引用了某一直系外层(k)的变量X，则可以用下面两条变址指令获得X的值，送到R2寄存器。LDR1,(d+k)[SP];LDR2,x[R1];注：第一句作用是从display表中取出k层过程的最新活动记录首址送给R1；x是变量X在第k层活动记录的相对地址。5、层次显示表display的建立例如：若当前处于P1过程，它的display表包含：P0活动记录首地址和P1过程最新活动记录首址。当执行CallP2后，应进入过程P2，在建立P2活动记录的同时应建立P2的display表。此表的内容为：P0活动记录首地址和P1过程最新活动记录首址，及P2活动记录首址。例如：同层调用若当前处于P1过程，当执行CallP2后，应进入过程P2，P2的display表包含两项：P0活动记录首地址和P2的SP。P0活动记录首地址在P2的display表中有过，可从其中抄得。故：当进入第i层过程时，其display表可从施调过程得display表中抄录i项，i代表当前数据区的静态层次，然后加上自身活动记录首址SP组成。注：要完成上面的过程，将施调过程的display表首址作为连接数据送到被调用过程的全局display单元。不允许隔层调用，是因为造不出被调过程的display表。总之，要构造某被调过程的display表，就从施调过程的display表中抄若干项，然后再加上本身的SP组成。此时，连接数据要变为三项：老SP、返回地址和全局display地址。6、Pascal语言的数据区建立和撤销1）过程调用段（1）传递简单变量（包括临时变量和常量）ParTi解释为:(i+4)[TOP]:=Ti/*传值*/或：(i+4)[TOP]:=addr(Ti)/*传地址*/（2）传递数组：一般传递内情向量表首址。(i+4)[TOP]:=Ti的内情向量表首地址2)过程进入段SP=TOP+1;1[SP]=返回地址TOP=TOP+L构造display表，,即按全局display指出位置抄I项并加上本身的SP,其中i为该过程的静态层次号LN若有数组说明，根据内情向量表，建立数组存储区，并修改栈顶指针TOP3)过程返回段TOP=SP-1;SP=0[SP];X=2[TOP];JMP0[X];若return语句含有返回值或Q是函数，则需先把返回值送到某特定寄存器。例如：对下面求阶乘的程序，第二次调用F函数后，给出栈式数据区的内容。假定每个过程有存储函数F的结果单元。ProgramM;varA,B:integerfunctionF(N:integer):integer;ifN=2thenteturn(N)elsereturn(N*F(N-1));beginread(A);/*设A=5*/B:=F(A);write(B);end.堆式存储管理对象：在高级语言中有些数据存储空间的请求与释放不再遵循后进先出的原则，而且是全局性的。对策：让运行程序持有一块专用的全局存储空间来满足这些数据的存储要求。这种存储空间就叫“堆”(heap)。堆通常是一片连续的足够大的存储区，当需要时，就从堆中分配一小块存储区；用完就及时退还给堆。一、堆式存储管理技术1、固定长块管理方法：把堆空间分成许多固定长的块，每块的第一个字用作指示器，将所有未用块链接起来，形成一张可利用表。当堆管理程序收到请求分配空间时，就查询该表，并将一块空白块的首指示器送给申请者，然后修改此表。2、可变长块管理申请分配空间时，堆管理程序从可利用表中查到一个未用块，若该块大于所需空间，就将它分成两部分，等于申请空间的一部分和剩余部分；这样下去留在可利用表中的块越来越小，最后形成无法用的碎片。若查到的块只比申请空间大一点，就不再分开，整个给申请者使用，此块中用不到的那部分也无法给别人用，就是内部碎片。注：这两种碎片很多时，碎片的总和大于申请空间，但无法分配给申请者。故可变长块管理主要考虑如何减少碎片的影响。可变长块管理分配策略(1)首次匹配式堆管理策略给表中每块首字中加入块大小的信息，分配时沿可利用表顺序查找，选择第一个大于所需空间的未用块，此块划出所需空间后剩余的部分必须大于某规定长度。注：改进算法，可采用循环链表，释放存储区时合并相邻未用块。(2)最优匹配式堆管理策略分配时对可利用表从头查到尾，找到一个容量正好等于或稍大于申请空间的未用块。注：此方法看似合理，但太花时间。(3)最差匹配式堆管理策略分配时找到一个容量大于申请空间且是可利用表中最大的的未用块，把它分开划给申请者，剩余部分留在表中。注：为了节省查找最大未用块的时间，可以将可利用表的未用块从大到小排好。这样分配的剩余部分要插到表的适当位置上。3、按块长不同分为若干集合方法：把整个堆空间分为若干集合，每个集合中块长是相等的，并把它们链接在一起。当申请m个长度为n的块时，就到块长为n或稍大于n的集合中去查找可利用块。若该集合中由m个这样的块，则满足申请；若没有m个，则从块长较大的集合中取一块或多块，把它们分成相等的两块然后再分配。注：优点：减少搜索时间，容易实现块合并；缺点：会使内部碎片增加。二、堆空间的释放与无用单元收集1、堆空间的释放对应语句:Dispose(P);free(p);处理方法：将释放块作为新块插入到可利用表的链首位置。由于这样做一段时间后，可利用表中将有大量小块，影响分配程序的操作；此时可改进一下:将地址连续的小块合并成一大块。注：这样做可利用表必须按块的地址顺序组织。2、无用单元的收集1）执行时机：在堆的可利用空间几乎耗尽，以至于不能满足用户申请要求，或发现可利用空间已降至某个危险点时执行。2）收集过程：标记阶段：查看已分配的块近期有无访问，访问过就做一标记；收集阶段：把所有没有加标记的存储块加入可利用表中，然后消除标记。注：最好在可利用空间降到某个数值时就调用收集程序，以避免收集时间过长。执行收集程序必须中断用户程序的执行，所以选择执行收集程序的时刻必须合理。PASCAL语言运行时的数据区存储管理将栈和堆安排在存区两端，各自无关的向中间靠拢。当碰到一起时存储空间用完。此时调用无用单元收集程序。数据区是否够用时无法估计的，堆和栈碰头也是难免的，所以设置堆管理是很重要的。小结1)C语言程序的数据存储管理允许递归调用使用活动记录2)PASCAL语言程序的数据存储管理允许递归调用和过程嵌套定义使用带有DISPLAY表的活动记录，全局DISPLAY表首地址是调用过程的DISPLAY表首地址