第五章运行环境.

1第五章运行环境源程序最终需要运行，因此需要了解：与源程序等价的目标程序如何在内存中运行，为了程序的正确运行需要什么样的支持。不同的源语言结构，所需的运行环境和支持不同。本章仅以最简单的、基于过程的、顺序执行的程序为前提讨论，即源程序的基本结构是顺序执行的过程，过程与过程之间仅通过子程序调用的方式进行控制流的转移。讨论内容：1.静态的过程运行时具有什么样的动态特性；2.运行时需要什么样的环境支持(存储空间分配)；3.过程之间的调用与返回应如何实现等。25.1过程的动态特性过程与活动1.过程、活动、生存期过程的每一次运行称为一次活动(activation)。活动是一个动态的概念，它有有限的生存期(lifetime)。定义5.1活动的生存期是指从进入活动的第一条指令执行到离开此活动前的最后一条指令执行的这段时间，其中包括调用其它过程时其它活动的生存期。2.活动之间的通信①子程序调用：call/return，有去必有回顺序调用：生存期不交嵌套调用：生存期嵌套，由活动执行轨迹的条件动态确定容易混淆的概念：过程的嵌套与活动的嵌套②消息传递：send/receive，可有去无回35.1过程的动态特性3.顺序执行程序的控制流特点：程序的执行在时间上是顺序的和排他的。即在程序执行的任一瞬间，有且仅有一个活动正在活动。控制流满足：①控制流是连续的；②过程间的控制流可以用树来表示。4.活动树定义5.2描绘控制进入和离开活动方式的树结构被称为活动树①每个结点代表过程的一个活动；②根代表主程序的活动；③结点a是b的父亲，当且仅当控制流从a的活动进入b的活动④结点a处于b的左边，当且仅当a的生存期先于b的生存期。45.1过程的动态特性[例5.1]考虑快排序过程：programsort(input,output);procedurereadarray;functionpartition(y,z:integer):integer;procedurequicksort(m,n:integer);i:=partition(y,z)yizXXXreadarraysortquicksort执行sortsortreadarrayquicksort时间缩为一个点，且翻转55.1过程的动态特性活动树的实质是反映了顺序执行程序的调用和时序关系，它把每个活动的生存期缩小到了一点。[例5.1]快排序程序的一次执行的活动树：srq(1,9)p(1,9)q(1,3)q(5,9)p(1,3)q(1,0)q(2,3)p(5,9)q(5,5)q(7,9)p(2,3)q(2,1)q(3,3)p(7,9)q(7,7)q(9,9)s－sortr－readarrayq－quicksortp－partition1234567893010520865.1过程的动态特性控制栈与活动记录控制流与活动树的关系1.程序控制流：对应活动树从根开始的一次深度优先遍历。2.活动树上各节点之间具有下述关系：①同一层次的活动生存期不交②任一时刻，处在生存期的活动构成一条从根到某节点的路径③路径上各节点生存期是嵌套的(后进先出)3.控制栈与活动记录控制栈：保存所有在生存期的活动(一条后进先出的路径)。活动记录：activationrecord，栈中的每个元素称为一个活动记录，为活动提供的活动场所。75.1过程的动态特性活动记录中至少应该存放两类信息：控制信息：控制活动的正确调用与返回和控制活动记录的正确切换；访问信息：用于为当前活动提供对数据，如本地数据和非本地数据的访问。[例5.2]快排序程序运行时某状态的控制栈控制栈保存了任何时刻所有在生存期活动的活动记录srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)srq(1,9)p(1,9)q(1,3)q(5,9)p(1,3)q(1,0)q(2,3)p(5,9)q(5,5)q(7,9)p(2,3)q(2,1)q(3,3)p(7,9)q(7,7)q(9,9)85.1过程的动态特性名字的绑定1.名字的绑定定义5.3运行时为名字X分配存储空间S，这一过程称为绑定(binding)。换句话说，绑定是名字X与存储空间S的结合。X是一个对象：①既可以是数据对象，如变量，与之结合的是一个存储单元；②也可以是操作对象，如过程，与之结合的是可执行的代码；③我们的讨论仅限于X是一个数据对象。2.静态与动态名字的声明与名字的绑定均需要有对应的存储空间，而存储空间的对应方式，一个是静态的，一个是动态的。95.1过程的动态特性声明时关心的是声明的作用域，即当一个名字被引用时，在不同的作用域中与该名字的不同声明结合；名字和作用域是静态的一对一关系。绑定时关心的是绑定的生存期，即当一个名字在运行时被实际分配的存储单元，名字与存储单元结合的这段时间被称为绑定的生存期，显然此生存期应该和名字的生存期一致。同时，运行时名字与存储单元的结合可以是一对多的关系。静态动态过程的定义过程的活动名字的声明名字的绑定声明的作用域绑定的生存期符号表活动记录10aheaderxreadarrayexchangequicksortsortiheaderreadarrayexchangeheaderquicksortheaderivpartitionheaderijpartition5.1过程的动态特性sortreadarrayexchangequicksortpartition(i)(i)(i)多个活动记录s的活动记录iq(1,9)的活动记录iq(1,3)的活动记录iq(1,0)的活动记录top→简化的符号表srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)115.1过程的动态特性3.变量与值的两步映射名字左值右值环境(绑定)状态(赋值)(a)变量名字的映射名字右值(b)常量名字的映射环境(绑定)xS3.14环境状态(c)x:=3.14的映射pi3.14环境(d)pi=3.14的映射环境改变存储，状态改变值。[例5.3]若有变量声明x:real和常量声明constpi=3.14，则赋值句中变量和常量的映射关系：常量没有左值(存储空间)，所以不能被赋值。125.1过程的动态特性4.环境与状态允许递归调用的情况下，同一作用域中的一个名字，可以同时绑定到多个存储单元，环境是一对多映射。如quicksort。一个存储单元可以存放不同的值，状态也是一对多映射。5.影响存储分配策略的因素编译器怎样对存储空间进行组织，采用什么样的存储分配策略，很大程度上取决于程序设计语言采用的机制，如：过程能否递归过程能否嵌套过程调用时参数如何传递哪些实体可以作为参数和返回值是否允许动态的为对象分配和撤销存储空间存储空间是否必须显式地释放等等135.2运行时数据空间的组织运行时内存的划分与数据空间的存储分配策略可执行代码(静态数据区)[注]静态数据区(staticdata)栈(stack)↓↑堆（heap）[注]当前情况下，源程序代码与可执行代码是一对一的关系，因此可以静态绑定。OOPL允许对代码覆盖(override)，因此代码也存在动态绑定问题。数据区与分配策略：1.静态分配策略：编译时安排所有数据对象的存储，即绑定是静态确定的；2.栈分配策略：按栈方式自动管理运行时的数据存储空间3.堆分配策略：在运行时根据要求从堆数据区动态地分配和释放数据存储空间。145.2运行时数据空间的组织静态与动态分配简介1.静态分配策略特点：绑定是1对1的映射。名字在程序编译时与存储空间结合，每次过程活动时，它的名字映射到同一存储单元。程序运行时不再有对存储空间的分配。↓baseX...↑base1↑base2↑Δx↑base3↑basei限制：①数据对象的大小和它在内存中位置的限制必须在编译时确定，如数组的大小不能是动态的；②不允许程序递归，因为一个过程的所有活动使用同样的名字绑定，即绑定是一对一的；③不能动态生成或撤消数据，因为运行时没有存储分配机制155.2运行时数据空间的组织早期的FORTRAN完全采用静态分配。另外，如果语言允许分别编译的数据定义模块(如全程引用的数据)，也可以采用静态分配，因为它们一般在整个程序运行的期间被共享。srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)2.栈分配策略(重点讨论)特点：按栈的方式自动分配存储空间限制：①活动停止后，局部于活动的名字值不能保持(否则悬空引用)②无法处理需要随时分配或撤销(不满足LIFO)的动态数据③被调用者的活动比调用者的活得更长(活动树不能正确描绘过程间的控制流，如send/receive)iΔisp(base)topq(1,9)q(1,3)q(1,0)165.2运行时数据空间的组织3.堆分配策略特点：可任意分配和撤消数据；对程序设计语言没有限制；静态、栈与堆的关系：①可以静态分配的数据均可以栈分配②可以静态和栈分配的数据均可以堆分配③反之不一定堆分配的基本思想：free1free2free3...freen堆分配的存储空间free1free2free3freen......堆分配的可用存储空间链175.3栈式动态分配控制栈中的活动记录1.活动记录的具体内容(控制信息＋访问信息)①参数与返回值②控制链(可选)③访问链(可选)④保存的机器状态⑤本地(局部)数据⑥临时变量①参数与返回值：存放实参和返回值②控制链(可选)：指向调用者活动记录的指针，用于当调用返回时，将当前栈顶正确切换到调用者的活动记录；③访问链(可选)：用于在可嵌套定义的过程中指示访问非本地数据；④调用时需要保存的机器状态：如程序计数器，寄存器等；⑤过程内部声明的数据：如VARX，Y:INTEGER等；⑥临时变量：源程序中不出现的、由编译程序产生的变量，如表达式x+y+z求值时产生的T1，T2，...；185.3栈式动态分配2.控制栈的两个重要指针(全程量)①top：控制栈的栈顶②sp：每个活动记录中的相对寻址，也代表此活动记录在整个的程序运行过程中，top指示栈顶，sp指示当前栈顶的活动记录。[例5.5]控制栈的变化过程s－r－q(1,9)－q(1,3)－q(1,0)sstopsrsrq(1,9)srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)srtopsq(1,9)topsq(1,9)q(1,3)q(1,0)topsq(1,9)p(1,9)topsrq(1,9)p(1,9)......19上次课总结过程的动态特性过程、活动、生存期、控制流；活动树、控制栈、活动记录；名字的绑定、环境与状态；运行时的存储空间组织内存划分：可执行代码、静态数据区、栈、堆；栈式动态分配控制栈中的活动记录205.3栈式动态分配调用序列与返回序列1.简化的活动记录参数与返回值控制链本地数据临时变量top→top→sp→(过程运行时引用)(调用与返回序列引用)问题：如何使得过程调用和返回时能够实现：①程序控制流正确转移②活动记录正确切换解决方案：在过程运行代码的适当位置，加入实现这些功能的代码，称它们为调用序列和返回序列。任何时刻top和sp都是唯一的，因为只有一个栈215.3栈式动态分配2.调用序列和返回序列的位置调用序列：①、②返回序列：③、④callB①④...i:=i+1...i:=i+1A代码段：调用②③return...j:=j+1...i:=i+1B代码段：返回225.3栈式动态分配3.调用序列和返回序列的内容调用者①传递参数维护访问链(如果必要)保存返回地址和控制链保存机器状态(指令计数器寄存器等)将控制转向被调用者被调用者②设置新的活动记录大小为可变数组分配空间(若有)初始化本地数据（若必要）...（开始可执行代码）被调用者③保留返回值(若为函数)恢复访问链(如果必要)恢复调用时机器状态恢复控制链将控制返回调用者调用者④接收返回值(若有的话)...(继续执行代码)分工原则：尽量将调用序列和返回序列放在被调用者中23①A的调用序列1[top]:=n(n个参数的传递)n+3[top]:=sp(保存旧sp)n+2[top]