运行时的存储组织

运行时的存储组织知识结构第2页,共43页，2024年2月25日，星期天8.1概述从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配所谓运行时的环境是指目标计算机的寄存器和存储器的结构，以及用来管理存储器并保存执行过程所需要的信息。几乎所有的程序设计语言都使用3种类型的存储环境：完全静态环境、基于栈的存储环境和基于堆的存储环境中的一种或几种。第3页,共43页，2024年2月25日，星期天8.1概述从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的设计和数据空间的分配数据空间包括：用户定义的各种类型的数据对象（变量和常量）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，组织输入/输出所需的缓冲区。第4页,共43页，2024年2月25日，星期天8.1概述存储管理复杂度取决于源语言本身，具体包括：允许的数据类型的多少语言中允许的数据项是静态确定动态确定程序决定名字的作用域的规则和结构段结构过程定义不嵌套，只允许过程递归调用分程序结构分程序嵌套过程定义嵌套第5页,共43页，2024年2月25日，星期天存储区划分成：目标区、静态数据区、栈区、堆区：目标代码区用以存放目标代码，这是固定长度的，即编译时能确定的全程/静态数据区用以存放编译时能确定所占用空间的数据堆/栈区用于可变数据以及管理过程活动的控制信息目标代码区全程/静态数据区栈↑自由空间↓堆8.1运行时存储空间的划分第6页,共43页，2024年2月25日，星期天过程的活动记录过程的活动记录是一段连续的存储区，用来存放过程的一次执行所需要的信息。自变量（参数空间）返回地址用作局部数据的空间用作局部临时变量的空间8.2过程活动记录第7页,共43页，2024年2月25日，星期天编译程序分配目标程序运行时的数据空间的基本依据是程序语言设计时对程序运行中存储空间的使用和管理办法的规定在程序设计语言语义学中，使用environment表示将一个名字映射到一个存储位置的函数，state表示存储位置到值的映射，如图10.2所示：第8页,共43页，2024年2月25日，星期天数据空间的使用和管理方法分成三种：静态存储分配栈式动态存储分配堆式动态存储分配第9页,共43页，2024年2月25日，星期天8.2静态存储分配指在编译时对数据对象分配固定的存储位置，运行时始终不变。即一旦存储空间的某个位置分配给了某个数据名，则在目标程序的整个运行过程中，此位置（地址）就属于该数据名。由静态存储分配产生的数据区称为静态数据区。静态存储分配适用于不允许递归过程或递归调用，不允许可变体积的数据结构的语言静态存储分配的特点：简单、易于实现例：FORTRAN语言，它所有的数据都属于这一类。第10页,共43页，2024年2月25日，星期天8.2静态存储分配例：FORTRAN程序主程序段

ProgramTEST

……ENDSUBROUTINELADD(A,SIZE,QMEAN)COMMONMAXSIZEINTEGERMAXSIZE,SIZEREALA(SIZE),QMEAN,TEMPINTEGERKTEMP0,0DO10K=1,SIZETEMP=TEMP+A(K)10CONTINUEQMEAN=TEMP/SIZERETURNEND

……KQMEAN返回地址TEMP3ASIZEMAXSIZETABLE(1)…(10)TEMP代码区静态数据区附加过程主过程第11页,共43页，2024年2月25日，星期天静态存储分配：在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置8.2静态存储分配第12页,共43页，2024年2月25日，星期天图10.4给出一个FORTRAN77的程序例子：PROGRAMCNSUMECHARACTER*50BUF//程序体所拥有的静态量BUFINTEGERNEXT//程序体所拥有的静态量NEXTCHARACTERC,PRDUCE//程序体所拥有的静态量CDATANEXT/1/,BUF/''/

C=PRDUCE()

BUF(NEXT:NEXT)=C

NEXT=NEXT+1

IF(C.EN.'')GOTO6

WRITE(*,'(A)')BUF(11)END第13页,共43页，2024年2月25日，星期天(12)CHARACTERFUNCTIONPRDUCE()CHARACTER*80BUFFER

INTEGERNEXT

SAVEBUFFER,NEXT//PRDUCE函数体所拥有的静态量BUFFER,NEXT(16)DATANEXT/81/(17)

IF(NEXT.GT.80)THEN(18)

READ(*,'(A)')BUFFER(19)

NEXT=1(20)

ENDIF(21)

PRDUCE=BUFFER(NEXT:NEXT)(22)

NEXT=NEXT+1(23)

END

第14页,共43页，2024年2月25日，星期天图10.5中描述了该程序中局部变量的静态存储位置：第15页,共43页，2024年2月25日，星期天动态存储分配如果一个程序设计语言允许递归过程、可变数组或允许用户自由申请和释放空间，那么，就需要采用动态存储管理技术第16页,共43页，2024年2月25日，星期天栈式动态存储分配这种分配策略是将整个程序的数据空间设计为一个栈第17页,共43页，2024年2月25日，星期天8.3.1简单栈式存储分配对于没有分程序结构，过称规定一不允许嵌套单允许过程递归调用的语言，可以采用一种简单的栈式存储分配策略。C语言满足上述特点。临时工作单元

内情向量简单变量形式单元参数个数返回地址老SP(前一活动记录的地址)TOPSPC语言过程的活动记录第18页,共43页，2024年2月25日，星期天一.简单的栈式存储分配的实现最简单的程序设计语言结构如图10.7所示：

programmain;

//主程序头全局变量或数组的说明；procR;

//过程R的头…

//过程R的体end(R);

//过程R的尾procQ;

//过程Q的头…

//过程Q的体end(Q);

//过程Q的尾主程序执行语句

//主程序体end.(main)

//主程序尾第19页,共43页，2024年2月25日，星期天例如，图10.7的程序结构中，若主程序调用了过程Q，Q又调用了R,在R进入运行后的存储结构如图10.8(a)所示：若主程序调用了过程Q，Q递归调用自己，在Q过程第2次进入运行后的存储结构如图10.8(b)所示：若主程序先调用过程Q，然后主程序接着调用R，且Q过程没有调用Q和R，这时Q和R进入运行后的存储结构分别如图10.8(c)和10.8(d)所示：第20页,共43页，2024年2月25日，星期天第21页,共43页，2024年2月25日，星期天常常使用两个指针指示栈最顶端的数据区：SP：总是指向现行过程活动记录的起点TOP：始终指向已占用的栈顶单元第22页,共43页，2024年2月25日，星期天这种语言若含有可变数组，则其过程活动记录的内容如图10.9所示：第23页,共43页，2024年2月25日，星期天图10.10表明分配数组区之后的运行栈情况，可以与图

10.8（a）对照：第24页,共43页，2024年2月25日，星期天二.嵌套过程语言的栈式实现Pascal语言程序结构的特点是允许过程嵌套定义，如图

8.11所示：第25页,共43页，2024年2月25日，星期天第26页,共43页，2024年2月25日，星期天图8.11的Pascal程序中过程定义的嵌套情况如下：sortreadarrayexchangequicksortpartition第27页,共43页，2024年2月25日，星期天假如过程sort激活（调用）了过程quicksort，这时存储栈中的情形如图8.12所示，其中在quicksort过程活动记录中有一存储单元（用斜线描绘）用以记录过程quicksort可以引用sort中定义的变量a和x。也就是说，为了解决对非局部变量的存取问题，必须设法跟踪每个外层过程的最新活动记录的位置第28页,共43页，2024年2月25日，星期天第29页,共43页，2024年2月25日，星期天一种跟踪方法是：在过程活动记录中增设存取链,指向包含该过程的直接外层过程的最新活动记录的起始位置。过程活动记录的内容如图8.13（a）所示。图10.12所提到的情况可用图8.13（b）所示：第30页,共43页，2024年2月25日，星期天因为PL/O的过程是无参过程，PL/O也无动态数组，所以它的过程活动记录的内容如图10.14所示：第31页,共43页，2024年2月25日，星期天再回到图10.11例子，如果该程序的某次执行顺序为：sort

quicksort

quicksort

partition

exchange…图10.15给出了进入过程exchange之后运行栈的示意，仅标明存取链和控制链的值第32页,共43页，2024年2月25日，星期天第33页,共43页，2024年2月25日，星期天另一种跟踪方法是：每进入一个过程后，在建立它的活动记录的同时建立一张嵌套层次显示表display嵌套层次：指过程定义的层数，始终假定主程序的层数为0，因此主程序称为0层过程第34页,共43页，2024年2月25日，星期天计数过程的层数用一个计数器Level，初值为0，每遇到过程说明则增1，过程说明结束则减1display是一个指针数组d，也可看做是一个小栈，自顶向下每个单元依次存放着现行层，直接外层，……直至最外层（0层，主程序层）等每一层过程的最新活动记录的地址第35页,共43页，2024年2月25日，星期天图10.11的程序，假定有如下四种调用情况：（a）sortquicksort…（b）sortquicksortquicksort…（c）sortquicksortquicksortpartition…（d）sort

quicksortquicksortpartitionexchange…图10.16(a)-(d)分别说明上述四种情形的运行栈和display第36页,共43页，2024年2月25日，星期天第37页,共43页，2024年2月25日，星期天display本身的体积在编译时可确定，它作为单独的表分配存储还是作为活动记录的一部分，比如置于实参的上端（如图10.17所示），则取决于编译程序的设计者第38页,共43页，2024年2月25日，星期天8.4堆式存储分配假设程序运行时有一个大的存储空间，每当需要时就从这片空间中借用一块，不用时再退还，由于借还的时间先后不一，即不空间的使用不一定按照“先申请后释放”的原则，经一段运行之后，程序运行空间将被划分成许多块，有些占用，有些空闲。那么当运行程序要求一块体积为N的空间时，需要决定应该从哪个空闲块得到这个空间。理论上讲,应该从比N稍大一些的空闲块中取出N个单元，以便使大的空闲块派更大的用场，但实现难度很大第39页,共43页，2024年2月25日，星期天堆式存储分配方法的基本思想是：先一个程序开始只想时有很大一块存储空间，运行期间如果需要就从里面申请一块存储空间，使用完毕归还。系统必须记录所有使用情况，尤其是要记录所有的空闲区以备后用，尽量把相连空闲区汇集成一个比较大的空闲区以免存储区被分割为许多难以使用的碎片。堆式存储分配方法的实现方法是：按定长进行分配。初始化时将堆存储空间分成若干个长度相等的快，按邻块的顺序吧这些块练成一个链表，每次申请空间从链表最前面的未使用节点开始分配，归还时把节点插入链表，尽量保证第一个未使用的节点之后没有已分配的块。3种分配策略：（1）首次匹配法（2）最优匹配法（3）最差匹配法第40页,共43页，2024年2月