ch07--运行环境

LIWensheng,SCST,BUPT第7章运行环境知识点：活动记录、控制栈栈式存储分配非局部名字的访问参数传递方式WenshengLiBUPT@20082/71运行环境程序运行时刻的环境，即运行中程序的信息是怎样存储和访问的。执行过程中，程序中数据的存取是通过对应的存储单元来进行的。存储组织与管理–早期的计算机上，存储管理工作是由程序员自己来完成–有了高级语言之后，程序中使用的存储单元都由标识符来表示，它们对应的内存地址由编译程序在编译时或由其生成的目标程序在运行时进行分配。存储的组织及管理是编译程序要完成的一个复杂而又十分重要的工作。WenshengLiBUPT@20083/71运行环境7.1程序运行时的存储组织7.2存储分配策略7.3访问非局部名字7.4参数传递机制小结WenshengLiBUPT@20084/717.1程序运行时的存储组织概念：过程与活动一、程序运行空间的划分二、控制栈与活动记录三、作用域及名字绑定WenshengLiBUPT@20085/71概念：过程与活动过程的定义–一个声明语句–把一个标识符和一个语句联系起来–标识符是过程名，语句是过程体。过程的分类–过程：没有返回值的过程–函数：有返回值的过程–也可以把函数、一个完整的程序看作过程过程引用：过程名出现在一个可执行语句中参数：–形参、实参WenshengLiBUPT@20086/71活动活动–一个过程的每次执行称为它的一次活动–如果一个过程在执行中，则称它的这次活动是活着的过程与活动–过程是一个静态概念，活动是一个动态概念–过程与活动之间可以是1:1、1:m的关系–递归过程，同一时刻可能有若干个活动是活着的–每个活动都有自己独立的存储空间/数据空间PPPP有3个活着的活动P有2个活着的活动P有1个活着的活动WenshengLiBUPT@20087/71活动的生存期程序执行时,过程之间的控制流–是连续的–过程的每一次执行都是从过程体的起点开始，最后控制返回到直接跟随本次调用点的位置。活动的生存期–过程体的执行中，第一步和最后一步之间的一系列步骤的执行时间–过程P的一次活动的生存期，包括执行过程P所调用的过程的时间，以及这些过程所调用的过程的时间–如果a和b是过程的活动，那么它们的生存期要么是不重叠，要么是嵌套的。递归过程：–如果一个过程，它的不同活动的生存期可以嵌套，则这个过程是递归的–直接递归、间接递归abababWenshengLiBUPT@20088/71一、程序运行空间的划分编译程序在编译源程序时，向操作系统申请一块内存区域，以便被编译程序在其中运行代码区/保存目标代码静态数据区控制栈堆编译时可以确定代码段的长度，可以放在一个静态确定的区域内编译时可确定大小的数据对象，放在静态确定的区域内，目标地址可以编入目标代码中用于管理过程的活动、保存断点的现场信息，用于返回时的恢复程序控制下进行的动态存储分配，分配在堆中，如Pascal中new函数???WenshengLiBUPT@20089/71二、控制栈与活动记录控制栈：用于保存控制信息的栈。–程序执行过程中使用控制栈来保存活动的生存踪迹及活动的运行环境。活动记录：一个连续的存储块–记录过程在一次执行中所需要的信息通常，活动记录分配在控制栈中（像Pascal、C）–当一个过程被调用时，被调用过程的一次新的活动被激活，在栈顶为该活动创建一个新的活动记录来保存其环境信息；–当活动结束，控制从被调用过程返回时，释放该活动记录，使调用过程的活动记录成为栈顶活动记录，即恢复调用过程的执行环境。WenshengLiBUPT@200810/71活动记录的内容返回值实参区域控制链访问链机器状态域局部数据区临时数据区存放中间计算结果在本次活动中，为过程中定义的局部变量分配的存储空间保存断点的现场信息，寄存器、PSW等指向直接外围过程的最近一次活动的活动记录的指针，用于对非局部名字的访问指向调用过程的活动记录的指针，用于本活动结束时的恢复调用过程提供给本活动的实参值本活动返回给调用过程的值根据确定每个域所需空间大小的时间早晚安排其位置。(1)早：中间晚：两头(2)用于通信：前面自己用的：后面WenshengLiBUPT@200811/71活动记录中内容的安排原则大小能够较早确定的区域放在活动记录的中间，大小较晚才能确定、并且变化较多的区域放在活动记录的两头。–控制链、访问链、机器状态域，是编译器设计的一部分，编译器构造时就可以确定它们的大小，所以把这些区域放在活动记录的中间。–参数域放在前面，便于调用过程进行参数传递，同时，被调用过程也可很方便地进行访问。–返回值域放在最前面，便于调用过程可以根据自己的栈指针访问该区域，取回返回值。–局部数据/临时数据安排在最后，其大小变化不会影响到活动记录中其他数据的存取。并且调用过程也无权访问被调用过程中的局部数据。WenshengLiBUPT@200812/71局部数据的安排常识：–程序运行时使用连续的存储空间–内存可编址的最小单位是字节–一个机器字由若干个字节组成–一个名字所需存储空间的大小由其类型决定–需多个字节表示的数据对象，存放在连续字节的存储块中，第一个字节的地址作为它的地址局部数据的安排–局部数据区是在编译过程中检查声明语句时安排的–长度可变的数据对象，放在该区域之外数据对象的存储安排受目标机器编址限制的影响WenshengLiBUPT@200813/71编址限制的影响整数加法指令可能要求整数的地址能够被4整除要求地址对齐如：x:integer;y:char;z:integer;为求分配上的全局统一，而多余出来的无用空间叫做填塞（padding）如果char占一个字节，integer占2个字节,x、y、z共需要5个字节。如果要求从双字节地址分配，则需要为这三个变量分配6个字节，WenshengLiBUPT@200814/71三、作用域及名字绑定声明是一个把信息与名字联系起来的语法结构–显式声明（如PASCAL中的声明：vari:integer）–隐含声明（如FORTRAN程序）在一个程序的不同部分可能有对同一个名字的相互独立的声明一个声明起作用的程序部分称为该声明的作用域语言的作用域规则决定了当这样的名字在程序正文中出现时应该使用哪一个声明Pascal中的名字遵循“最近嵌套原则”编译过程中，名字的作用域信息记录在符号表中WenshengLiBUPT@200815/71名字的绑定把名字对应到存储单元的过程名字与存储单元的对应关系：–1:1–1:m当environment把一个存储单元S与一个名字X联系起来时，称X受限于S。S的大小取决于X的类型一个活动中的名字与其存储单元之间一个递归过程中的名字与其存储单元之间名字X存储单元SS的内容Venvironmentstate地址为名字的左值名字的右值WenshengLiBUPT@200816/71与存储组织与管理有关的其他问题名字的存储空间如何组织、名字绑定的方法等主要取决于对以下问题的回答：–过程是否可递归？–当控制从过程的一次活动返回时，对局部名字的值如何处理？–过程是否可以引用非局部的名字？–过程调用时如何传递参数？–过程是否可以作为参数传递？–过程可否作为结果被返回？–存储空间能否在程序控制下进行动态分配？–存储空间是否必须显式地归还？WenshengLiBUPT@200817/717.2存储分配策略运行时刻存储空间的划分，除目标代码外，其余三种数据空间采用的存储分配策略是不同的。–静态存储分配：编译时对所有数据对象分配存储空间–栈式存储分配：运行时把存储器作为栈进行管理，数据对象分配在栈中–堆式存储分配：运行时把存储器组织成堆结构，对用户提出的存储空间的申请与归还进行存储分配与回收。一、静态存储分配二、栈式存储分配三、堆式存储分配WenshengLiBUPT@200818/71一、静态存储分配条件：源程序中出现的各种数据所需要的存储空间的大小在编译时可以确定存储分配：编译时,为他们分配固定的存储空间运行时：总是使用这些存储空间–过程每次被激活，同一名字都使用相同的存储空间–允许局部名字的值在活动结束后被保留下来–当控制再次进入时，局部名字的值即上次离开时的值数据对象：–每个过程的活动记录的位置及大小–记录中每一个名字所占用的存储空间的位置及大小–数据在运行时刻的地址可以填入到目标代码中WenshengLiBUPT@200819/71静态存储分配策略对源语言的限制数据对象的大小和它们在内存中的位置必须在编译时都能够确定不允许过程递归调用–因为使用静态存储分配，一个过程里声明的局部数据在该过程的所有活动中都结合到同一个地址。不能建立动态数据结构–因为没有在运行时进行存储分配的机制。WenshengLiBUPT@200820/71静态存储分配策略的实现编译器处理声明语句时，每遇到一个变量名就创建一个符号表条目，填入相应的属性，包括目标地址。每个变量所需空间的大小由其类型确定，并且在编译时刻是已知的。根据名字出现的先后顺序，连续分配空间nametypeaddress...lengthN10n1N2n1n2N3n1+n2n3.........代码区数据区N1N2程序的逻辑空间0LA...WenshengLiBUPT@200821/71PROGRAMCNSUMECHARACTER*50BUFINTEGERNEXTCHARACTERC,PRDUCEDATANEXT/1/,BUF//6C=PRDUCE()BUF(NEXT:NEXT)=CNEXT=NEXT+1IF(C.NE.)GOTO6WRITE(*,(A))BUFENDFortran程序举例CHARACTERFUNCTIONPRDUCE()CHARACTER*80BUFFERINTEGERNEXTSAVEBUFFER,NEXTDATANEXT/81/IF(NEXT.GT.80)THENREAD(*,(A))BUFFERNEXT=1ENDIFPRDUCE=BUFFER(NEXT:NEXT)NEXT=NEXT+1ENDWenshengLiBUPT@200822/71存储空间分配CNSUME的代码PRDUCE的代码静态数据区代码区CNSUME的活动记录PRDUCE的活动记录CHARACTER*50BUFINTEGERNEXTCHARACTERCCHARACTER*80BUFFERINTEGERNEXTWenshengLiBUPT@200823/71二、栈式存储分配存储空间被组织成栈存储管理–活动开始时，与活动相应的活动记录入栈，局部变量的存储空间分配在该活动记录中。同一过程中声明的名字在不同的活动中被结合到不同的存储空间。–活动结束时，活动记录出栈，分配给局部名字的存储空间被释放。名字的值将丢失，不可再用。...top...ntopq的活动开始qa...topq的活动结束WenshengLiBUPT@200824/71programsort(input,output);vara:array[0..10]ofinteger;x:integer;procedurereadarray;vari:integer;beginfori:=1to9doread(a[i])end;prcedureexchange(i,j:integer);beginx:=a[i];a[i]:=a[j];a[j]:=xend;procedurequicksort(m,n:integer);vark,v:integer;functionpartition(y,z:integer):integer;vari,j:integer;begin…a…;…v…;exchange(i,j);end;beginif(nm)thenbegini:=partition(m,n);quicksort(m,i-1);quicksort(i+1,n)endend{quicksort};begina[0]:=-99